Tracker: binary heaps

[anshumanmohan]

#1999 motivates the need for a general PIFO. It also discusses a made-up strategy for implementing such a PIFO. It leaves on the table, however, another straightforward solution: binary heaps.

This is a tracker for the things we need.

• A module that accepts values and pushes them into a min-heap ordered by value. Done via Queues: binary heap #2074
• Tweak the above to accept a value and a rank, and push a (value, rank) tuple ordered by rank. Done via Queues: extend binary heap #2145
• Modify the above to obey the queue interface. It won't be possible to obey the interface exactly, since the binary heap will need ranks as well as values, but maybe get it close. Done via Queues: extend binary heap #2145
• Add peek and pop functionality. Done via Queues: extend binary heap #2145
• Test! Done via Queues: randomized testing for binary heaps #2174
• Document! Done via Docs, Queues: binary heap #2182
• Write logic for a scheduling transaction that interacts with the above, granting ranks to values. The scheduling transaction + binary heap combination will be able to obey the queue interface exactly.
  • A basic first goal for this would be a scheduling transaction that achieves fairness among the incoming classes of traffic; if we can do this then the scheduling transaction + binary heap would become a drop-in replacement for our super limited PIFO that can only do fairness.
    Done via Queues: randomized testing for binary heaps #2174
  • More generally, there is lots of room to run here. Other scheduling transactions can achieve other goals, and our super limited PIFO will not be able to match this behavior. Sorta the point of a truly general PIFO. See this glossary for inspiration. It would be super if we had a little zoo of policies like this!
    Done via Queues: randomized testing for binary heaps #2174
• Implement PIFO trees using binary-heap PIFOs #2187

[ethanuppal]

Does this issue have a PR or a branch?

[anshumanmohan]

PR for the first task coming soon. My intention is to leave the other tasks for my BURE undergrads.

[anshumanmohan]

@ethanuppal see #2074 if you're curious!