From: Jens Axboe <jens.axboe@oracle.com>
Date: Tue, 27 Mar 2007 08:36:12 +0000 (+0200)
Subject: Avoid using the rbtree if we don't have to
X-Git-Tag: fio-1.15~27
X-Git-Url: https://git.kernel.dk/?p=fio.git;a=commitdiff_plain;h=8de8f047bd025f12d23cfc3fc1793434c6d8ff94;hp=bb5d7d0b5bde867690590aaa61d77307d773107f;ds=sidebyside

Avoid using the rbtree if we don't have to

Basically reinstate the old logic of not sorting when it's
not a win for reading the data back.

Signed-off-by: Jens Axboe <jens.axboe@oracle.com>
---

diff --git a/fio.c b/fio.c
index 6a3a87b0..bed1e287 100644
--- a/fio.c
+++ b/fio.c
@@ -736,6 +736,7 @@ static void *thread_main(void *data)
 	INIT_LIST_HEAD(&td->io_u_busylist);
 	INIT_LIST_HEAD(&td->io_u_requeues);
 	INIT_LIST_HEAD(&td->io_log_list);
+	INIT_LIST_HEAD(&td->io_hist_list);
 	td->io_hist_tree = RB_ROOT;
 
 	if (init_io_u(td))
diff --git a/fio.h b/fio.h
index 4d7e6ea7..ec08e423 100644
--- a/fio.h
+++ b/fio.h
@@ -515,9 +515,15 @@ struct thread_data {
 	unsigned int ddir_nr;
 
 	/*
-	 * IO historic logs
+	 * IO history logs for verification. We use a tree for sorting,
+	 * if we are overwriting. Otherwise just use a fifo.
 	 */
 	struct rb_root io_hist_tree;
+	struct list_head io_hist_list;
+
+	/*
+	 * For IO replaying
+	 */
 	struct list_head io_log_list;
 
 	/*
diff --git a/log.c b/log.c
index 0614b277..6c7c4d6b 100644
--- a/log.c
+++ b/log.c
@@ -43,16 +43,33 @@ void prune_io_piece_log(struct thread_data *td)
  */
 void log_io_piece(struct thread_data *td, struct io_u *io_u)
 {
-	struct rb_node **p = &td->io_hist_tree.rb_node;
-	struct rb_node *parent = NULL;
+	struct rb_node **p, *parent;
 	struct io_piece *ipo, *__ipo;
 
 	ipo = malloc(sizeof(struct io_piece));
-	RB_CLEAR_NODE(&ipo->rb_node);
 	ipo->file = io_u->file;
 	ipo->offset = io_u->offset;
 	ipo->len = io_u->buflen;
 
+	/*
+	 * We don't need to sort the entries, if:
+	 *
+	 *	Sequential writes, or
+	 *	Random writes that lay out the file as it goes along
+	 *
+	 * For both these cases, just reading back data in the order we
+	 * wrote it out is the fastest.
+	 */
+	if (!td_random(td) || !td->o.overwrite) {
+		INIT_LIST_HEAD(&ipo->list);
+		list_add_tail(&ipo->list, &td->io_hist_list);
+		return;
+	}
+
+	RB_CLEAR_NODE(&ipo->rb_node);
+	p = &td->io_hist_tree.rb_node;
+	parent = NULL;
+
 	/*
 	 * Sort the entry into the verification list
 	 */
diff --git a/verify.c b/verify.c
index 99b21e8f..47335107 100644
--- a/verify.c
+++ b/verify.c
@@ -150,8 +150,7 @@ void populate_verify_io_u(struct thread_data *td, struct io_u *io_u)
 
 int get_next_verify(struct thread_data *td, struct io_u *io_u)
 {
-	struct io_piece *ipo;
-	struct rb_node *n;
+	struct io_piece *ipo = NULL;
 
 	/*
 	 * this io_u is from a requeue, we already filled the offsets
@@ -159,12 +158,17 @@ int get_next_verify(struct thread_data *td, struct io_u *io_u)
 	if (io_u->file)
 		return 0;
 
-	n = rb_first(&td->io_hist_tree);
-	if (n) {
-		ipo = rb_entry(n, struct io_piece, rb_node);
+	if (!RB_EMPTY_ROOT(&td->io_hist_tree)) {
+		struct rb_node *n = rb_first(&td->io_hist_tree);
 
+		ipo = rb_entry(n, struct io_piece, rb_node);
 		rb_erase(n, &td->io_hist_tree);
+	} else if (!list_empty(&td->io_hist_list)) {
+		ipo = list_entry(td->io_hist_list.next, struct io_piece, list);
+		list_del(&ipo->list);
+	}
 
+	if (ipo) {
 		io_u->offset = ipo->offset;
 		io_u->buflen = ipo->len;
 		io_u->file = ipo->file;