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

Interleave dictionaries and bits #1

Open
tixxit opened this issue Oct 6, 2015 · 0 comments
Open

Interleave dictionaries and bits #1

tixxit opened this issue Oct 6, 2015 · 0 comments

Comments

@tixxit
Copy link
Contributor

tixxit commented Oct 6, 2015

It seems to me that it may be nice to chunk the structure into simpler blocks, made up of (Offset, Chunk Offset Dictionary, Bits), encoding those into the array, and then repeating. This has the benefit of being better for cache locality from Offset -> Chunk Offset Dictionary. It would also help with locality when digging into the actual bits, but I suspect it wouldn't be as big of a gain.

For reference, we currently encode the entire level 1 dictionary, then the entire level2 dictionary, and then all the bits.

Also, we have some space in the level 2 dictionary, since we are aligning on Int boundaries (2 bits per 96 bits). We could use this to encode some extra information to let us switch between implementations. For example, if that chunk has < X bits (2^16, 2^8, etc), we could save some space in the storage.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant