anonlink icon indicating copy to clipboard operation
anonlink copied to clipboard

Improve priority queue use in C++ matching code

Open unzvfu opened this issue 8 years ago • 2 comments

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:

  1. Extensive use of priority_queue::pop() in loops as though it were O(1) when it is in fact O(log n).
  2. AoS memory layout of the queue elements (struct Node) when SoA would probably be better.
  3. Possibly unnecessary maintenance of the queue invariant when k is small (a qsort at 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

unzvfu avatar Feb 16 '18 00:02 unzvfu

Working on this in the fix-prio-queue branch; currently works but is slower for reasons that I don't currently understand.

unzvfu avatar Apr 10 '18 06:04 unzvfu

Moving this to the icebox as my attempts to improve the implementation haven't yielded anything useful yet.

unzvfu avatar Apr 16 '18 05:04 unzvfu