Size optimize branch and leaf formats

Michael Howellrequested to merge
improved-alphabitmap into main

Branch optimize

This re-does the inline_neighbors_flag and no_leaves_flag, renaming the first one to no_branches_flag and using this truth table:

no_leaves_flag no_branches_flag -> representation
0 0 normal
0 1 normal, without branches
1 0 normal, without leaves
1 1 inline neighbors repr

Since nodes with neither branches nor leaves are so rare (they should only show up when disambig_level > 0), the setup here should make better use of both bits.

Leaf optimize

  • Add a representation for multiple runs (up to 16 of them, with up to 16 elements in each).
  • Check the correct size for two and one-byte offsets, so it's used more often.
  • Allow up to 47 elements in a single run for the one-run special representation.

Before 

54M    examples/search.index
14M    build/aarch64-apple-darwin/doc/search.index
51M    build/aarch64-apple-darwin/compiler-doc/search.index

After 

53M    examples/search.index
14M    build/aarch64-apple-darwin/doc/search.index
50M    build/aarch64-apple-darwin/compiler-doc/search.index

Merge request reports