Scheduler speedup improvement

[GoogleCodeExporter]

See r904 and its description.
With this change CallLater.cancel() is 2x faster at the expense on some little 
extra memory usage.

Original issue reported on code.google.com by g.rodola on 19 Nov 2011 at 4:40

[GoogleCodeExporter]

See also r912 for a small speedup when calling the scheduler.

Original comment by g.rodola on 22 Nov 2011 at 9:34

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Just one clarification: my first estimate (2x speedup) was wrong and doesn't 
tell what really happened here.
What we were doing before was a O(n) operation as opposed to O(log(n)) (now), 
therefore the improvement is much more incisive.
A simple benchmark which cancel()s 10.000 scheduled functions gives an idea:

before:
4.414453 secs

now:
0.019779 secs

Original comment by g.rodola on 23 Nov 2011 at 1:04

Attachments:

• bench.py

[GoogleCodeExporter]

Original comment by g.rodola on 23 Nov 2011 at 1:05

• Changed title: CallLater.cancel() method speedup improvement

[GoogleCodeExporter]

See also r914.

Original comment by g.rodola on 25 Nov 2011 at 8:54

[GoogleCodeExporter]

See also r916 for a global 2x speedup + 1/3 of memory consumption.

Original comment by g.rodola on 26 Nov 2011 at 4:00

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Ok I consider this one fixed.
The improvements involved pretty much all the aspects of the scheduler which is 
now about about from 0.5x to 8x faster and consumes 1/3 of memory.
cancel(), as said, is the one which benefited mostly (orders of magnitude).
This is particularly useful as close() is called every time a client is 
disconnected, hence something happening quite often.

Attached is a benchmark script which shows some numbers before and after 
applying patches.
Changesets involved were r904, r912, r914 and r916.

BEFORE APPLYING PATCHES (r903)

test_create (consumed memory)  : 174M
test_cancel                    : time=8.27629 : calls=1 : stdev=0.00000
test_create                    : time=0.79243 : calls=1 : stdev=0.00000
test_reset                     : time=1.60637 : calls=1 : stdev=0.00000
test_run                       : time=5.31241 : calls=1 : stdev=0.00000

AFTER APPLYING PATCHES (r916)

test_create (consumed memory)  : 57M
test_cancel                    : time=0.01735 : calls=1 : stdev=0.00000
test_create                    : time=0.42343 : calls=1 : stdev=0.00000
test_reset                     : time=0.92890 : calls=1 : stdev=0.00000
test_run                       : time=0.66907 : calls=1 : stdev=0.00000

OVERALL SPEEDUP

schedule   : +0.5x
reschedule : +1.7x
cancel     : +477x  (with 1 milion scheduled functions)
run:       : +8x

Original comment by g.rodola on 26 Nov 2011 at 6:58

[GoogleCodeExporter]

Original comment by g.rodola on 3 Jan 2012 at 11:40

• Added labels: Milestone-0.7.0

[GoogleCodeExporter]

0.7.0 is out. Closing this out as definitively fixed.

Original comment by g.rodola on 25 Jan 2012 at 7:24

• Changed state: Fixed