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

In-memory representation of slice run iterator is inefficient #24

Open
Stebalien opened this issue Jun 30, 2020 · 1 comment
Open

In-memory representation of slice run iterator is inefficient #24

Stebalien opened this issue Jun 30, 2020 · 1 comment
Labels
enhancement New feature or request

Comments

@Stebalien
Copy link
Member

The current in-memory representation of the run iterator is really inefficient. On a 64 bit system, it'll take 16 bytes per run due to alignment. This is an issue because we cache this iterator whenever we first try to read a bitfield.

We can cut this in half by:

  1. First combining (or failing) on adjacent runs with the same value.
  2. Encoding the runs as a slice of 64 bit integers where the value if 0 elements are even, and the value of odd elements are 1.

We can make this even smaller if we're willing to use a variable-length integer encoding (or simply avoid caching and get better at decoding in-place).

@acruikshank
Copy link

sorry, closed it accidentally.

@acruikshank acruikshank reopened this Sep 14, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants