C++ priority_queue of tuple is slow

Question

I need to process a dynamic sorted list of events in C++. Each event is composed of 3 variables: the time (used to sort the list) and 2 others. I process data events by events, take the first one in the sorted list (with the lower time variable), process it, and then remove it from the list. During the processing of events I also have to add others to that list which can be added at any position.

I tried to use a prioriy_queue composed by tuple (std::priority_queue<tuple<double, int, int>, std::vector<tuple<double, int, int>>, greater<tuple<double, int, int>>>), the double's value is the time variable use to sort the list and integers are others variables useful for the processing. This works, it keeps a list sorted by time, I can easily add new events and remove the first one and I just need to access the first one (with the lower time value).

But this takes a lot of time. Most of the time spent by my program is used to add and remove items to my list. Is there other alternatives than priority queue? Using tuple<double, int, int> is probably not the best way and should impact by a lot, is there other alternatives?

Answer 1

The std::priority_queue is for all intents a heap, lg2 N push and pop. Note for a million items that would be 20KM, K small constant, M memory accesses. Memory usage 8MB, for a single core, so time to upgrade to a CPU that gives L3 access to at least that much memory.

This can be improved to lg lg N (the Thorup equivalence) with some effort, but there might be easier options.

If there are a lot of time collisions then tuple is not the right structure.

Something like

struct item {
  double time;
  int first, second;

  operator>(const item & other) const {
    return time > other.time;
  }
};

using pQueue = std::priority_queue<item, std::vector<item>, std::greater<item>>;

This should use the operator> else use a lampda as comparator.

If you insert new items as a group you could consider using a Leonardo Heap for extra fun in programming.

Another possibility is using std::partial_sort on the 128 first elements, leaving the rest unsorted, check against the highest value in the sorted array when you insert a new to see if it needs to be include in the top scores or just emplace_back in the others. When the top scores are empty make a new std::partial_sort. Using std::deque instead of std::vector might be better in this case, due to the better pop_front of O(1). Some extra bookkeeping must be done.