4 ms·

Way better detailed explanation: https://stackoverflow.com/questions/72580828/what-is-a-succinct-rank-data-structure-how-does-it-work https://stackoverflow.com/

Way better detailed explanation: https://stackoverflow.com/questions/72580828/what-is-a-succinct-rank-data-structure-how-does-it-work https://stackoverflow.com/questions/72580828/what-is-a-succi...

zero_shift 2y ago
That IS excellent - thank you
topspin 2y ago
Yes, that's great. This part: "Intuitively, a succinct data structure is one whose space usage equals the space needed to write out the data, plus something that grows more slowly than that. If you're familiar with little-o notation, a succinct data structure is one whose space usage is X + o(X), where X is the number of bits needed to write out the data itself." Brings to mind COBS encoding, which does this for streams bytes containing arbitrary length "packets" or similar.
adgjlsfhk1 2y ago
This is great! I love both how far you can push this and get meaningful improvements, and how it's totally overkill for anything we'll ever be able to implement on a physical computer. The hardware focused approach is to use popcnt for a base size of 512 (since cache architecture will make you fetch that much memory if you touch the original array anyway). We then can store 1 UInt16 prefix sum per 512 bits (n/32 bits overall), and if we have more than 2^16 bits in total, we can store UInt64 prefixes every 2^16 bits (n/1024 bits overall). Theoretically, this approach uses O(nlogn) bits as opposed to o(n) for the theoretical approach, but in practice, for <2^64 bools, the actual storage ens up being n/32+n/1024 which is pretty hard to beat. The theoretical approach gets it's wins from making extremely clever use of the difference between O(loglog(n)) and O(1), but unfortunately for the foreseeable future, logn < 64 and loglog(n) < 6, so all the subtlety gets swallowed up into the base case of a single popcnt instruction.
atiedebee 2y ago
This is great. A very understandable explanation, thanks for sharing!
akoboldfrying 2y ago
templatetypedef answers are the best answers. I know going in that (1) there are going to be surprising insights, and (2) I'm going to understand them fully.

Way better detailed explanation: https://stackoverflow.com/questions/72580828/what-is-a-succinct-rank-data-structure-how-does-it-work https://stackoverflow.com/questions/72580828/what-is-a-succi...

zero_shift 2y ago

That IS excellent - thank you

topspin 2y ago

Yes, that's great. This part: "Intuitively, a succinct data structure is one whose space usage equals the space needed to write out the data, plus something that grows more slowly than that. If you're familiar with little-o notation, a succinct data structure is one whose space usage is X + o(X), where X is the number of bits needed to write out the data itself." Brings to mind COBS encoding, which does this for streams bytes containing arbitrary length "packets" or similar.

adgjlsfhk1 2y ago

This is great! I love both how far you can push this and get meaningful improvements, and how it's totally overkill for anything we'll ever be able to implement on a physical computer. The hardware focused approach is to use popcnt for a base size of 512 (since cache architecture will make you fetch that much memory if you touch the original array anyway). We then can store 1 UInt16 prefix sum per 512 bits (n/32 bits overall), and if we have more than 2^16 bits in total, we can store UInt64 prefixes every 2^16 bits (n/1024 bits overall). Theoretically, this approach uses O(nlogn) bits as opposed to o(n) for the theoretical approach, but in practice, for <2^64 bools, the actual storage ens up being n/32+n/1024 which is pretty hard to beat. The theoretical approach gets it's wins from making extremely clever use of the difference between O(loglog(n)) and O(1), but unfortunately for the foreseeable future, logn < 64 and loglog(n) < 6, so all the subtlety gets swallowed up into the base case of a single popcnt instruction.

atiedebee 2y ago

This is great. A very understandable explanation, thanks for sharing!

akoboldfrying 2y ago

templatetypedef answers are the best answers. I know going in that (1) there are going to be surprising insights, and (2) I'm going to understand them fully.