Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve priority queue use in C++ matching code #60

Open
unzvfu opened this issue Feb 16, 2018 · 2 comments
Open

Improve priority queue use in C++ matching code #60

unzvfu opened this issue Feb 16, 2018 · 2 comments
Assignees

Comments

@unzvfu
Copy link

unzvfu commented Feb 16, 2018

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:

Aha! Link: https://csiro.aha.io/features/ANONLINK-70

@unzvfu unzvfu self-assigned this Feb 16, 2018
@unzvfu unzvfu added this to the Sprint 2018-04-09 milestone Apr 10, 2018
@unzvfu
Copy link
Author

unzvfu commented Apr 10, 2018

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

@unzvfu
Copy link
Author

unzvfu commented Apr 16, 2018

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

@unzvfu unzvfu removed this from the Sprint 2018-04-09 milestone Apr 16, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant