Improved propagation queue for top down propagation.
Instead of using a std::priority_queue this uses a custom data structure based on a linked list of pre-allocated nodes.
More testing needs to be done, but this seems to be faster than std::priority_queue for our use-case.
The speedup can probably be explained by a couple of things:
The priority queue seems to be quite small for our current benchmarks so the worst-case O(n) insert time seems negligible.
The priority of IDs is saved in the nodes so there is no need for calling a lambda/comparator.
Inserts at the end of the queue are instantaneous (note that we will never insert at the head of the queue, so maybe a reversed queue and double-linked list is better...).
There is definitely no heap allocation of list nodes during runtime, they are pre-allocated and re-used.
popping the head of the list is truely constant time (no bookkeeping needed) instead of log(n).
Improved propagation queue for top down propagation. Instead of using a std::priority_queue this uses a custom data structure based on a linked list of pre-allocated nodes.
More testing needs to be done, but this seems to be faster than std::priority_queue for our use-case.
The speedup can probably be explained by a couple of things: