Performance Optimization of Compression: Low hanging fruits

[torfmaster]

Although asymptotically BWT is the most expensive operation during compression, only 40% is spent during BWT. There are some hot spots which are potentially easy to fix:

• [x] ribzip2::lib::block::zle::zle_transform spends 15% in HashSet and HashMap operations. Both can be replaced by operations which finish in constant time. Also vector operations might be improved up by pre-allocating sufficient memory.
• [x] ribzip2::lib::block::block_data::generate_block_data spends 15% of the time on the final encoding step, most of the time during inefficient (linear) access to the coding table.
• [ ] run ribzip2::lib::block::huffman::package_merge::package_merge only if code length exceeds 20 bits - saves 1,5% of runtime

[torfmaster]

Having implemented the first two goals, the impact of the third now is 2.65%.

[torfmaster]

Updated difficulty: the last point is significantly easier.

[NiklasEi]

I do not understand the last point. Looking at the usage of ribzip2::lib::block::huffman::package_merge::package_merge, it only gets called with length = 17

https://github.com/torfmaster/ribzip2/blob/71d3373c981cfa6a52c978aadcb23e1f0a943f2a/lib/src/block/huffman/huffman_internal.rs#L92

[torfmaster]

@NiklasEi the re-computation of the huffman tables is only necessary if the maximum length actually exceeds 17 bits. So otherwise this step can be skipped.