Paul Rubin <no.email@nospam.invalid>: > Marko Rauhamaa <ma...@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 -- https://mail.python.org/mailman/listinfo/python-list
