actioninja / refpack-rs / 15969602071

91%

master: 92%

Build Type

push

github

Committed by web-flow

Commit Message

Improve compression ratio (#12)

* Update benchmarks

- add all zeros benchmark
- remove redundant benchmark
- add compressed size print

* Improve compression ratio

* fix clippy lints and format

* make number of hash chaining levels a constant

* add CompressionOptions parameter to compress functions

* add random booleans benchmark

This is a surprisingly useful benchmark, as a theoretically optimal compression algorithm will compress to a ratio of 8:1, and compression speeds tend to follow real-world usage better than the other benchmarks.

* make benchmark sizes cover a broader range

* change "fast" algorithm to use hash chaining

* add back original algorithm as "fastest"

* make optimal algorithm use a circular buffer

With this the memory usage for large data sizes is a fraction of what it used to be, but the current implementation needs to be re-optimized for this layout

* fix control bench

* formatting

* ignore optimal_matches_reference test

* remove short_skip_position

In theory it is a small algorithmic improvement, but the extra space needed for alignment and hash table pretty much completely nullify the benefit.
Removing this also simplifies the algorithm somewhat.

* change HashMap to PrefixTable

* merge duplicate search loop

* drop cost_state early

This reduces peak memory usage slightly.

* format

* refactor: rename HASH_CHAIN_MODULO to HASH_CHAIN_BUFFER_SIZE

* refactor: format

* refactor: add MPL headers to files that are missing the header

* refactor: replace commented code with a comment explaining why the code is not present

* doc: add documentation to CompressionOptions

* refactor: do not expose PrefixSearcher in the library interface

* refactor: only compile HashchainPrefixSearcher in test builds

* doc: document PrefixSearcher search function

* doc: add doc comment to encode_slice_hc

* fix: change debug_assert to assert to make sure all tests pass in release

* doc: fully comment encode_slice_hc

* doc: fully... (continued)

Run Details

834 of 919 new or added lines in 12 files covered. (90.75%)

4 existing lines in 2 files now uncovered.

1529 of 1661 relevant lines covered (92.05%)

370838.14 hits per line