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:

• 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.
• 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

ribzip2/lib/src/block/huffman/huffman_internal.rs

Line 92 in 71d3373

let code_lengths = compute_lis(&weights, 17);

[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.