prio_queue

This is the implementation of a cache friendly priority queue as a B-heap.

The workings and some performance observarions are available in a post on the blog playfulprogramming.

Usage differs slightly from std::priority_queue

The (simplified) signature is:

// in namespace rollbear
template <size_t miniheap_size, typename Prio, typename Value, class Compare = std::less<Prio>>
class prio_queue
{
public:
  prio_queue(Compare const& comp = Compare());
  
  using value type = Prio;
  using payload_type = Value;
  
  void                           push(Prio p, Value v);
  std::pair<Prio const&, Value&> top() const noexcept;
  void                           pop();
  void                           reschedule_top(Prio);
  bool                           empty() const noexcept;
  std::size_t                    size() const noexcept();
};

The reason for separate priority field and value data is that it offers much better performance than to have a priority queue over a struct/pair/tuple holding both and compare priority on it.

It is legal to set Value as void, in which case push() will accept only one parameter, and top() will return Prio const&, but generally performance will suffer when doing so.

miniheap_size is what you can tweak for optimum performance. How large to set it depends on the size of the Prio data type and the size of the cache lines. See the above mentioned blog post for guidance.

The real signatures for push() uses perfect forwarding.

reschedule_top() is synonymous to auto v = q.top(); q.pop(); q.push(v);, but is usually faster.

There is an additional allocator parameter.

If the Prio and Value types have noexcept move constructors and assignment, the strong exception guarantee holds, otherwise the weak exception guarantee.

Self test

The included self test program relies on two external frame works.

• Catch!
  • a header only unit test frame work
• trompeloeil
  • a header only mocking frame work

Performance benchmark

The included performance benchmark relies on one external frame work.

• tachymeter
  • a header only C++14 micro benchmark frame work