Thanks for this video(s)! I'm a little confused about step (c.iii). From what I understand, you're saying that the section of bits remaining "to be scanned" is so small, that it could be done using popcount (if an efficient operation is available in the given programming language), or by creating a third lookup table. What would the third lookup table look like? Combos of bits mapped to rank values? In Jacobson's thesis he says the remaining bits (after using the two-level directory pattern) can be scanned directly from the bitmap and added to the other cumulative rank values, but I'm confused why this would be considered O(1).
It is a list of precomputed rank results. The index of the list is the decimal number corresponding to the binary coding of the subchunks. In other words, when querying the ranks for a sub-chunk, you can use the decimal number corresponding to the binary coding of the subchunk to get the rank results. The decimal number is less than a word size, so it is obtained automatically O(1) from the binary form. Hope this helps.
Awesome, clear video, thank you for existing
Thanks for this video(s)! I'm a little confused about step (c.iii). From what I understand, you're saying that the section of bits remaining "to be scanned" is so small, that it could be done using popcount (if an efficient operation is available in the given programming language), or by creating a third lookup table. What would the third lookup table look like? Combos of bits mapped to rank values? In Jacobson's thesis he says the remaining bits (after using the two-level directory pattern) can be scanned directly from the bitmap and added to the other cumulative rank values, but I'm confused why this would be considered O(1).
It is a list of precomputed rank results. The index of the list is the decimal number corresponding to the binary coding of the subchunks. In other words, when querying the ranks for a sub-chunk, you can use the decimal number corresponding to the binary coding of the subchunk to get the rank results. The decimal number is less than a word size, so it is obtained automatically O(1) from the binary form. Hope this helps.