timer: cache the minimal value.
authorRusty Russell <rusty@rustcorp.com.au>
Fri, 5 Apr 2013 06:13:48 +0000 (16:43 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Fri, 5 Apr 2013 06:21:08 +0000 (16:51 +1030)
commita40fc5a89e5336f405b84387d387c9f5a74e95fa
tree493bf06c79eecefa4e98ec29a7cf0a862c767bf1
parent606cca7b0ed5236d1df1c4436ca79db6e3fd5321
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>
ccan/timer/benchmarks/expected-usage.c
ccan/timer/test/run-add.c
ccan/timer/timer.c
ccan/timer/timer.h