I spent a solid few days chasing this exact damn rabbit.

I thought I could beat the PQ implementation in .NET with something like this but I never even got close.

I think my use case breaks the assumptions in this paper due to the volatility of the distribution over time.

Edit: For reference, this is the approach taken by .NET - https://en.m.wikipedia.org/wiki/D-ary_heap

I tested two C++ implementations of Calendar Queues again the standard library priority_queue. The first implementation uses a deque as a backing container and then fills the calendar with linked lists. The second implementation just uses vectors in the calendar with no backing container.

The calendar queues have an interesting failure mode. If you are randomly inserting elements with a priority that is less than "now", and then pop some number of elements, and doing this repeatedly, then the front of the calendar empties out. As a result, the random insertions create a single value in the front of the calendar, then there are many many days that are empty after that. So subsequent pops will always have to search a lot of days in the calendar. So, these calendar queues are only fast if you keep track of "now" and only insert events after "now".

https://gist.github.com/nbingham1/611d37fce31334a1520213ce5d...

seed 1725545662 priority_queue 0.644354 calendar_queue 0.215860 calendar_queue_vector 0.405788

seed 1725545667 priority_queue 0.572672 calendar_queue 0.196812 calendar_queue_vector 0.392303

seed 1725545672 priority_queue 0.622041 calendar_queue 0.241419 calendar_queue_vector 0.413713

seed 1725545676 priority_queue 0.590372 calendar_queue 0.204428 calendar_queue_vector 0.386992

It would be nice to note in the title that this is a pdf. The algorithm is something like the timer wheels in the Linux kernel. Related to radix sorting more or less. Basically there are a bunch of buckets containing sorted lists of events. I didn't read too carefully since most people use a heap for this, which is O(log n) but likely has better constants.

I've had very similar experience as other commenters have stated W.R.T. calendar queues vs just good-old-fashioned std::priority_queue.

Then, one day, my team hired this ancient soviet engineer who looked like he could have been Lenin's drinking buddy. He was not impressed that I was using std::priority_queue, and he sat down and wrote a calendar queue.

I'll be damned if that thing wasn't 7 to 9 times faster. I thought I was an engineer, but next to this guy, I was just a monkey poking at the typewriter.

It is possible to make a calendar queue which will absolutely mop the floor with any other queue, but the algorithms given in these papers is just a starting point. Going from the published algorithm to an actual performant, production-ready product is always the hardest part.

I independently invented something similar around 1993 inside the scheduler of a threading implementation. I wanted to have a priority scheme whereby the ratios of priority values determined the amount of CPU quanta given to the thread. E.g. a priority 5 thread would twice the CPU time compared to a priority 10.

I called the algorithm "appointment calendar". Threads were scheduled in a calendar, with the lower priority threads (higher value) getting appointments farther in the future. The scheduler just marched through the calendar in order, taking the appointments.

I believe the Re-Pair algorithm used for doing linear time byte-pair encoding makes use of a similar idea: https://en.m.wikipedia.org/wiki/Re-Pair

There, instead of dates, the “priority index” reflects the frequencies of pairs seen in the input string. This leads to guaranteed O(1) runtime amortized over the input string, since the largest frequency count is bounded by the size of the input and can only decrease as merges happen.

I think I reinvented and started implementing something like this, but then just ended up using std::priority_queue (the C++ standard library priority queue) which is pretty fast.

Everything can be O(1) if you put bounds on every operation.

If this is really O(1), then that makes sorting O(N).

Year in title is wrong: the paper is from 1988, not 1998.