You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
marcelocantos
changed the title
Consider store count per node
Consider storing count per node
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: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.
The text was updated successfully, but these errors were encountered: