4 ms·
Succinct (space-saving) data structures often need "rank" and "select" operations. Rank(n) is the number of 1 bits up to position n. Select(n) is the reverse: a
by thomasmg 5y ago
Succinct (space-saving) data structures often need "rank" and "select" operations. Rank(n) is the number of 1 bits up to position n. Select(n) is the reverse: at which position is the n-th 1 bit.
For "rank", the "popcount" instruction can be used. Interestingly, for "select", the "PDEP" instruction can be used: you can put the data array in the PDEP mask, and 1 << n in the value; basically flip the operands. I found this quite fascinating. For details, there is a short paper on this: "A Fast x86 Implementation of Select".
I wonder if those succinct data structures are in any way related to what NSA is doing. I think not, but who knows.
- Bayart 5y agoThe paper, if anyone wants to save some clicks : https://arxiv.org/abs/1706.00990 https://arxiv.org/abs/1706.00990
- yvdriess 5y agoI've seen it used for large-scale genomics. Saving a few bits if you're dealing with billions of a thing is very useful. They're also vital for being able to pack as much of a datastructure (e.g. a graph) on a single node. Some graph algorithms, e.g. random walks, are latency bound and scale really badly in a distributed system.