tevent: optimize adding new timer events

As new timestamps typically get higher:-)
it's better to traverse the existing list from
the tail.

This is not completely optimal, but it should be better
than before.

A second optimization could be done for zero timestamps,
we would just remember the last_zero_timer,
but that would change the internal ABI.
Normally thatshould not be a poblem, but the Samba's
source3/lib/events.c abuses tevent_internal.h
from the current source tree, even if an external tevent.h
is used. The other problem is that it makes use of
tevent_common_add_timer() without using
tevent_common_loop_timer_delay().

Signed-off-by: Stefan Metzmacher <metze@samba.org>
Reviewed-by: Jeremy Allison <jra@samba.org>

1 files changed, 24 insertions, 8 deletions

diff --git a/lib/tevent/tevent_timed.c b/lib/tevent/tevent_timed.c
index d3ec8f5913e..fd954f42d83 100644
--- a/lib/tevent/tevent_timed.c
+++ b/lib/tevent/tevent_timed.c
@@ -160,7 +160,7 @@ struct tevent_timer *tevent_common_add_timer(struct tevent_context *ev, TALLOC_C
 					     const char *handler_name,
 					     const char *location)
 {
-	struct tevent_timer *te, *last_te, *cur_te;
+	struct tevent_timer *te, *prev_te, *cur_te;
 
 	te = talloc(mem_ctx?mem_ctx:ev, struct tevent_timer);
 	if (te == NULL) return NULL;
@@ -174,17 +174,33 @@ struct tevent_timer *tevent_common_add_timer(struct tevent_context *ev, TALLOC_C
 	te->additional_data	= NULL;
 
 	/* keep the list ordered */
-	last_te = NULL;
-	for (cur_te = ev->timer_events; cur_te; cur_te = cur_te->next) {
-		/* if the new event comes before the current one break */
-		if (tevent_timeval_compare(&te->next_event, &cur_te->next_event) < 0) {
-			break;
+	prev_te = NULL;
+	/*
+	 * we traverse the list from the tail
+	 * because it's much more likely that
+	 * timers are added at the end of the list
+	 */
+	for (cur_te = DLIST_TAIL(ev->timer_events);
+	     cur_te != NULL;
+	     cur_te = DLIST_PREV(cur_te))
+	{
+		int ret;
+
+		/*
+		 * if the new event comes before the current
+		 * we continue searching
+		 */
+		ret = tevent_timeval_compare(&te->next_event,
+					     &cur_te->next_event);
+		if (ret < 0) {
+			continue;
 		}
 
-		last_te = cur_te;
+		break;
 	}
+	prev_te = cur_te;
 
-	DLIST_ADD_AFTER(ev->timer_events, te, last_te);
+	DLIST_ADD_AFTER(ev->timer_events, te, prev_te);
 
 	talloc_set_destructor(te, tevent_common_timed_destructor);