anonlink
anonlink copied to clipboard
Improve priority queue use in C++ matching code
The use of the std::priority_queue in the C++ matching code (match_one_against_many_dice_k_top), is the main bottleneck when k is large. There a few deficiencies that may be negatively impacting performance. For example:
- Extensive use of
priority_queue::pop()in loops as though it were O(1) when it is in fact O(log n). - AoS memory layout of the queue elements (
struct Node) when SoA would probably be better. - Possibly unnecessary maintenance of the queue invariant when
kis small (aqsortat the end might do).
Some potentially useful resources:
- https://stackoverflow.com/a/10761286
- https://playfulprogramming.blogspot.com.au/2015/08/cache-optimizing-priority-queue.html
- https://github.com/rollbear/prio_queue
Aha! Link: https://csiro.aha.io/features/ANONLINK-70
Working on this in the fix-prio-queue branch; currently works but is slower for reasons that I don't currently understand.
Moving this to the icebox as my attempts to improve the implementation haven't yielded anything useful yet.