use a heap instead of sorteddict?

[lilydjwg]

I see trio depends on sortedcontainers solely because it needs a priority queue for sorting deadlines and the similar, and the Python standard library has one (heapq) for that exact purpose.

Pros:

• one less dependency
• it's (at least) slightly faster (13.29s vs 12.97s running the tests; it varies but the fastest sortedcontainers one took the same time as the slowest heap one)

Cons:

• may introduce bugs
• I have only a rough implementation, need some work to send a pull request

What do you think?

[njsmith]

Hey, thanks for your interest! And those are really interesting measurements...

There is one complication: we don't quite use sortedcontainers just as a pure priority queue. We need three operations:

• insert an arbitrary item
• pop the minimum
• delete an arbitrary item (for when a deadline gets removed)

heapq provides fast versions of the first two operations, but not the third, so it's not just a trivial drop-in replacement. Basically I'm using sortedcollections because it was a quick and easy way to get reasonable behavior (and in particular worst-case behavior) for all of these :-). If there's something else that's faster and has reasonable worst-case behavior then that'd be great though.

There are tons of possible options. The simplest thing is to use a heapq and leave stale items in the heap, then drop them as they come out – but this makes me nervous because if you have a workload that frequently creates and then removes deadlines, then it you can end up wasting a lot of memory just holding onto stale deadlines. You can also go all the way to proper timer wheels – curio has one of these – but I'm not sure how fast they end up being once implemented in Python. Or double-linked skiplists. Or... here's an interesting summary of an article from 1987 going over lots of options :-).

How does your version work? Do you think there's a practical improvement that's worth doing?

[njsmith]

Oh, there's also a relatively simple option for heaps: let stale deadlines accumulate in the heap, but also keep track of how many of them there are, and if it exceeds some limit (e.g. 50% of all heap entries) then do a compacting pass. I think this keeps everything within amortized O(log(n)) worst-case.

[lilydjwg]

I use list.remove in my version, which will be slow when there are a lot of deadlines. Tornado and pyftpdlib clean up the heap like you said. That needs some bookkeeping.

SortedDict has a dict and a list. It uses bisecting to find the value to remove and remove it from the list. This will take more memory than a heap, but there is no cleanup that comes up and take up a bit time.

curio has a good idea, but it still needs some kind of periodic work. It will be interesting to see which one is faster.

Thanks for the explanation 👍

PS: you seems to have pasted a wrong link.

[njsmith]

PS: you seems to have pasted a wrong link.

Whoops! Too much cutting-and-pasting... I've edited the comment to put the right link in.