2 ms·
Say your code has two strings "split pea" and "pea soup". In the binary file, you can overlap the suffix of the first with the prefix of the second to form "spl
by ridiculous_fish 4y ago
Say your code has two strings "split pea" and "pea soup". In the binary file, you can overlap the suffix of the first with the prefix of the second to form "split pea soup": the "pea" is shared, and this reduces both memory usage and binary size.
"split pea soup" is called a superstring of "split pea" and "pea soup" because it contains them both. An optimal superstring packs strings as closely as possible, and its construction is a moderately well-studied problem. This is the best paper I found: https://www.sciencedirect.com/science/article/pii/0304397588901673 https://www.sciencedirect.com/science/article/pii/0304397588...
After implementation I found that "optimal superstrings" compress poorly because the string ranges are unpredictable, and I later did some work to make the string ranges compress better even if the superstring gets longer.
The Hermes superstring optimization was time unwisely spent but is pretty cool anyways, and I don't know of any other work in this area. Check it out: https://github.com/facebook/hermes/blob/main/lib/BCGen/HBC/ConsecutiveStringStorage.cpp https://github.com/facebook/hermes/blob/main/lib/BCGen/HBC/C...
- leni536 4y agoThis can't work for "split pea" and "pea soup" in C, due to the zero terminator at the end of "split pea". edit: However this could work with C++ sring_views. I can imagine a library implementing this like: constexpr auto store = superstring< "split pea", "pea soup", "split pea soup" >; where `get<i>(store)` gets you a corresponding string_view. edit2: doh, I just skimmed your github link. I presume you implement just this.