how to convert code that uses cmp to python3

[Marko Rauhamaa]

Paul Rubin <no.email at nospam.invalid>:

> Marko Rauhamaa <marko at pacujo.net> writes:
>> On the surface, the garbage collection scheme looks dubious, but
>> maybe it works perfect in practice.
>
> It looked suspicious at first glance but I think it is ok. Basically
> on at most every timeout event (scheduling, expiration, or
> cancellation), it does an O(n) operation (scanning and re-heapifying
> the timeout list) with probability O(1/n) where n is the queue size,
> which itself changes (by 0, +1 or -1) when a timeout event happens.
> That is, its overhead is a constant factor unless I'm missing
> something. There are some efficiency gains possible but it seems par
> for the course for Python code.

I compared the performance of AVL trees, the older heapq technique as
well as the "GC scheme" in 2014 with a challenging but realistic
test scenario. AVL trees and the GC scheme had pretty much the same
throughput (and the older, simple heapq was slower).

With AVL trees, it's easier to be convinced about worst-case
performance. It is more difficult to see the potential pathological
cases with the GC scheme.


Marko