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

Consider storing count per node #20

Open
marcelocantos opened this issue Jan 10, 2020 · 0 comments
Open

Consider storing count per node #20

marcelocantos opened this issue Jan 10, 2020 · 0 comments
Labels
P2 Low priority

Comments

@marcelocantos
Copy link
Collaborator

marcelocantos commented Jan 10, 2020

An efficient per-node element-count, which currently doesn't exist, would speed up some operations dramatically. One simple possibility is to get each node to hold its count of elements up to whatever number fits into currently unused space (see below), and then recurse to its children when the count exceeds that. This means more bookkeeping for every algorithm, so some profiling will be in order before deciding that any of this is a good idea. There may be other uses of count, such as determining concurrency thresholds based on quantity rather than depth, which should be factored into the decision.

The number of free bits in a node is platform_bits - n_ways. This determines the largest expressible count:

32-bit 64-bit
8-way 224 - 1 256 - 1
16-way 216 - 1 248 - 1

Except for 16-way fanout on a 32-bit platform, those numbers are all beyond practical concern and will not require saturation handling for the foreseeable future. Once distributed nodes are implemented, 8-way on 32-bit (IoT clusters?) will become a concern.

Another complication is that the most efficient way to store this is to overlay it with the mask (n-bits for n-way fanout), but the mask needs to go at the unused high-order end of the count, which is different across big-endian and little-endian platforms.

@marcelocantos marcelocantos changed the title Consider store count per node Consider storing count per node Jan 10, 2020
@ChloePlanet ChloePlanet added the P2 Low priority label Apr 8, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
P2 Low priority
Projects
None yet
Development

No branches or pull requests

2 participants