From a40fc5a89e5336f405b84387d387c9f5a74e95fa Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Fri, 5 Apr 2013 16:43:48 +1030 Subject: [PATCH] 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 --- ccan/timer/benchmarks/expected-usage.c | 2 +- ccan/timer/test/run-add.c | 3 +- ccan/timer/timer.c | 85 ++++++++++++++++++-------- ccan/timer/timer.h | 3 +- 4 files changed, 64 insertions(+), 29 deletions(-) diff --git a/ccan/timer/benchmarks/expected-usage.c b/ccan/timer/benchmarks/expected-usage.c index 97778565..a5018271 100644 --- 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 79f029a9..6c5007c7 100644 --- 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 9486e6b9..59d1ff37 100644 --- 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 7b5d1994..3bf28d0f 100644 --- 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]; }; -- 2.39.2