jamwt/diesel — pull request #70 by dowski (2013-06-07 16:27:33+00:00)
Title: Timer Families for Better Performance

More on my quest to make timers more efficient. This change makes timers around 20% more efficient than the currently released code.

Here are a few observations about timers.

There are really two classes of timers in diesel: timers that will fire (`diesel.sleep(n)`) and timers that are unlikely to fire because they are timeouts (`diesel.first(waits=[expected_thing], sleep=n)`). I think that most practical timer use is of the latter form; timeouts that are unlikely to fire.

Another common feature of timers in an application is that there are many timers with common intervals. 30 seconds, 5 seconds, etc. For lack of a better term, I'm calling these timer families. A useful property of timers in the same family is that timers added later are automatically in the right sorted order.

The changes in this PR exploit those two observations and store timers in common-interval families. No sorting is required within families. The data structure for timers in a family is moved back to a deque for O(1) operations at either end (`append`/`popleft`). In benchmarking with an updated script, the `remove` cost is negligible.

Here are the benchmarking results with the new script. Closer to 30 seconds and lower numbers (CPU %) in the list are better:

```
# old single-deque
$ python examples/timer_bench.py 2500
done in 133.86 secs
[97, 91, 98, 95, 98, 99, 98, 99, 98, 99, 98, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]

# updated single-list (current release)
$ python examples/timer_bench.py 2500
done in 30.44 secs
[90, 73, 80, 83, 90, 91, 92, 93, 86, 87, 90, 92, 93, 93, 94, 91, 93, 93, 93, 93, 93, 94, 94, 95, 93, 93, 93, 91]

# heap (in this PR, but superseded)
$ python examples/timer_bench.py 2500
done in 31.09 secs
[92, 68, 72, 76, 78, 82, 83, 86, 86, 80, 80, 81, 82, 83, 84, 84, 86, 86, 82, 83, 83, 83, 85, 85, 85, 85, 83, 82]

# new deque families
$ python examples/timer_bench.py 2500
done in 30.69 secs
[99, 65, 68, 69, 70, 71, 72, 72, 73, 73, 74, 74, 74, 74, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 76, 76, 76, 76, 76, 76]
```