timer: cache the minimal value.

We spend a lot of time searching for the next timer to expire: by caching
the minimum, we can skip most of this work.  Even if timers are deleted,
the minimum will be a starting point for searching.

The expected-usage benchmark has to be increased by a factor of 100,
otherwise it's now too short.

Before:
	$ ./expected-usage
	1000000 in 12.701647935

After:
	$ ./expected-usage  1000000
	1000000 in 0.061095153

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/ccan/timer/benchmarks/expected-usage.c b/ccan/timer/benchmarks/expected-usage.c
index 9777856550ec2eb2bdec25bc63567bfcb6d77513..a5018271d581de7938c4d064b27bb381bcf1dbae 100644 (file)
--- a/ccan/timer/benchmarks/expected-usage.c
+++ b/ccan/timer/benchmarks/expected-usage.c
@@ -24,7 +24,7 @@ int main(int argc, char *argv[])
 
        opt_parse(&argc, argv, opt_log_stderr_exit);
 
-       num = argv[1] ? atoi(argv[1]) : (check ? 10000 : 1000000);
+       num = argv[1] ? atoi(argv[1]) : (check ? 100000 : 100000000);
 
        list_head_init(&expired);
        curr = start = time_now();

diff --git a/ccan/timer/test/run-add.c b/ccan/timer/test/run-add.c
index 79f029a9dd7b85d1685f1c5a77211184574c20a3..6c5007c77468bdc44b7291121eeb7ef4580f0a24 100644 (file)
--- a/ccan/timer/test/run-add.c
+++ b/ccan/timer/test/run-add.c
@@ -36,8 +36,7 @@ int main(void)
                for (timers.base = 0;
                     timers.base < (1ULL << MAX_ORD)+2;
                     timers.base = next(timers.base)) {
-                       t.time = timers.base + diff;
-                       timer_add_raw(&timers, &t);
+                       timer_add(&timers, &t, grains_to_time(timers.base + diff));
                        ok1(timers_check(&timers, NULL));
                        timer_del(&timers, &t);
                }

diff --git a/ccan/timer/timer.c b/ccan/timer/timer.c
index 9486e6b92872ac22a50f38fd14f5077b2fd220e3..59d1ff377cb6498e01ffbed8cad1ef4290466fdf 100644 (file)
--- a/ccan/timer/timer.c
+++ b/ccan/timer/timer.c
@@ -34,19 +34,24 @@ void timers_init(struct timers *timers, struct timespec start)
 
        list_head_init(&timers->far);
        timers->base = time_to_grains(start);
+       timers->first = -1ULL;
        for (i = 0; i < ARRAY_SIZE(timers->level); i++)
                timers->level[i] = NULL;
 }
 
-static void timer_add_raw(struct timers *timers, struct timer *t)
+static unsigned int level_of(const struct timers *timers, uint64_t time)
 {
-       struct list_head *l;
        uint64_t diff;
-       unsigned int level;
 
        /* Level depends how far away it is. */
-       diff = t->time - timers->base;
-       level = ilog64(diff / 2) / TIMER_LEVEL_BITS;
+       diff = time - timers->base;
+       return ilog64(diff / 2) / TIMER_LEVEL_BITS;
+}
+
+static void timer_add_raw(struct timers *timers, struct timer *t)
+{
+       struct list_head *l;
+       unsigned int level = level_of(timers, t->time);
 
        if (!timers->level[level])
                l = &timers->far;
@@ -65,6 +70,8 @@ void timer_add(struct timers *timers, struct timer *t, struct timespec when)
        /* Added in the past?  Treat it as imminent. */
        if (t->time < timers->base)
                t->time = timers->base;
+       if (t->time < timers->first)
+               timers->first = t->time;
 
        timer_add_raw(timers, t);
 }
@@ -159,17 +166,26 @@ static const struct timer *find_first(const struct list_head *list,
        return prev;
 }
 
-static struct timer *get_first(const struct timers *timers)
+static const struct timer *get_first(const struct timers *timers)
 {
-       unsigned int level = 0, i, off;
+       unsigned int level, i, off;
        bool need_next;
-       uint64_t base = timers->base;
+       uint64_t base;
        const struct timer *found = NULL;
        struct list_head *h;
 
+       if (timers->first < timers->base) {
+               base = timers->base;
+               level = 0;
+       } else {
+               /* May not be accurate, due to timer_del / expiry. */
+               level = level_of(timers, timers->first);
+               base = timers->first >> (TIMER_LEVEL_BITS * level);
+       }
+
 next:
        if (!timers->level[level])
-               return (struct timer *)find_first(&timers->far, NULL);
+               return find_first(&timers->far, NULL);
 
        need_next = false;
        off = base % PER_LEVEL;
@@ -206,17 +222,28 @@ next:
                        found = find_first(h, found);
                }
        }
-
-       return (struct timer *)found;
+       return found;
 }
 
-bool timer_earliest(const struct timers *timers, struct timespec *first)
+static bool update_first(struct timers *timers)
 {
-       struct timer *found = get_first(timers);
+       const struct timer *found = get_first(timers);
+
+       if (!found) {
+               timers->first = -1ULL;
+               return false;
+       }
+
+       timers->first = found->time;
+       return true;
+}
 
-       if (!found)
+bool timer_earliest(struct timers *timers, struct timespec *first)
+{
+       if (!update_first(timers))
                return false;
-       *first = grains_to_time(found->time);
+
+       *first = grains_to_time(timers->first);
        return true;
 }
 
@@ -274,7 +301,6 @@ void timers_expire(struct timers *timers,
 {
        uint64_t now = time_to_grains(expire);
        unsigned int off;
-       const struct timer *first;
 
        assert(now >= timers->base);
 
@@ -286,24 +312,23 @@ void timers_expire(struct timers *timers,
                add_level(timers, 0);
        }
 
-       while ((first = get_first(timers)) != NULL) {
-               assert(first->time >= timers->base);
-               if (first->time > now) {
+       do {
+               if (timers->first > now) {
                        timer_fast_forward(timers, now);
                        break;
                }
 
-               timer_fast_forward(timers, first->time);
+               timer_fast_forward(timers, timers->first);
                off = timers->base % PER_LEVEL;
 
                list_append_list(list, &timers->level[0]->list[off]);
                if (timers->base == now)
                        break;
-       }
+       } while (update_first(timers));
 }
 
 static bool timer_list_check(const struct list_head *l,
-                            uint64_t min, uint64_t max,
+                            uint64_t min, uint64_t max, uint64_t first,
                             const char *abortstr)
 {
        const struct timer *t;
@@ -321,6 +346,15 @@ static bool timer_list_check(const struct list_head *l,
                        }
                        return false;
                }
+               if (t->time < first) {
+                       if (abortstr) {
+                               fprintf(stderr,
+                                       "%s: timer %p %llu < minimum %llu\n",
+                                       abortstr, t, t->time, first);
+                               abort();
+                       }
+                       return false;
+               }
        }
        return true;
 }
@@ -341,7 +375,7 @@ struct timers *timers_check(const struct timers *timers, const char *abortstr)
 
                h = &timers->level[l]->list[(i+off) % PER_LEVEL];
                if (!timer_list_check(h, timers->base + i, timers->base + i,
-                                     abortstr))
+                                     timers->first, abortstr))
                        return NULL;
        }
 
@@ -359,7 +393,7 @@ struct timers *timers_check(const struct timers *timers, const char *abortstr)
 
                        h = &timers->level[l]->list[(i+off) % PER_LEVEL];
                        if (!timer_list_check(h, base, base + per_bucket - 1,
-                                             abortstr))
+                                             timers->first, abortstr))
                                return NULL;
                        base += per_bucket;
                }
@@ -368,7 +402,8 @@ struct timers *timers_check(const struct timers *timers, const char *abortstr)
 past_levels:
        base = (timers->base & ~((1ULL << (TIMER_LEVEL_BITS * l)) - 1))
                + (1ULL << (TIMER_LEVEL_BITS * l)) - 1;
-       if (!timer_list_check(&timers->far, base, -1ULL, abortstr))
+       if (!timer_list_check(&timers->far, base, -1ULL, timers->first,
+                             abortstr))
                return NULL;
 
        return (struct timers *)timers;

diff --git a/ccan/timer/timer.h b/ccan/timer/timer.h
index 7b5d199470c49e829aa19c0363eaa715c6324fee..3bf28d0fbda2cdd8f4e3396bc19928d2b1ac7960 100644 (file)
--- a/ccan/timer/timer.h
+++ b/ccan/timer/timer.h
@@ -61,7 +61,7 @@ void timer_del(struct timers *timers, struct timer *timer);
  * timers.  Otherwise, it sets @first to the expiry time of the first
  * timer (rounded to TIMER_GRANULARITY nanoseconds), and returns true.
  */
-bool timer_earliest(const struct timers *timers, struct timespec *first);
+bool timer_earliest(struct timers *timers, struct timespec *first);
 
 /**
  * timer_expire - update timers structure and remove expired timers.
@@ -123,6 +123,7 @@ struct timers {
        /* Far in the future. */
        struct list_head far;
        uint64_t base;
+       uint64_t first;
 
        struct timer_level *level[(64 + TIMER_LEVEL_BITS-1) / TIMER_LEVEL_BITS];
 };