Scheduler speedup improvement

[giampaolo]

From g.rodola on November 19, 2011 17:40:24

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

Original issue: http://code.google.com/p/pyftpdlib/issues/detail?id=189

[giampaolo]

From g.rodola on November 22, 2011 13:34:57

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

[giampaolo]

From g.rodola on November 22, 2011 17:04:06

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

Attachment: bench.py

[giampaolo]

From g.rodola on November 22, 2011 17:05:30

Summary: CallLater.cancel() method speedup improvement

[giampaolo]

From g.rodola on November 25, 2011 12:54:22

See also r914 .

[giampaolo]

From g.rodola on November 26, 2011 08:00:07

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

[giampaolo]

From g.rodola on November 26, 2011 10:58:08

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

[giampaolo]

From g.rodola on January 03, 2012 03:40:14

Labels: Milestone-0.7.0

[giampaolo]

From g.rodola on January 25, 2012 11:24:20

0.7.0 is out. Closing this out as definitively fixed.

Status: Fixed