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.
As mentioned, something like it already exists inside Linux. Maybe it could be pulled out and turned into an app library, if it's so much better than a heap queue. Info: https://duckduckgo.com/?q=timer+wheel+linux
I remember writing a heap queue in C++ myself because std::priority_queue had some kind of shortcoming whose specifics I don't remember. Maybe I can find that program and check what it wanted. It wasn't a performance issue, but rather, something I needed was missing from the stdlib API and I remember thinking that it was silly that they omitted it.
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.