KillingSpark / KillingSpark/zstd-rs

Further optimizations

Open
#25 0 comments 4 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
449
Forks
66
PR merge metrics
No merged PRs in 30d

Description

I need a place to put down some ideas for further optimizing this crate:

## Decoder

1. [ ] We only need to call reserve once for each block of sequences. We can calculate how many bytes will be added to the decode buffer by a list of sequences. This might save some re-allocations.
2. [ ] The way the zstd_streaming binary works is not optimal. It should just use the drain_to_writer() functions instead of reading into an intermediary buffer. That's why we have these functions.
3. [x] Read https://fgiesen.wordpress.com/2018/02/19/reading-bits-in-far-too-many-ways-part-1/ and https://fgiesen.wordpress.com/2018/02/20/reading-bits-in-far-too-many-ways-part-2/ again carefully and optimize the bitreaders further
4. [ ] The ReversedBitreader performance can be enhanced quite a bit by being less useful in the generic case. Just returning wrong values for requests of >56 bits eliminates the need for error handling on calls to the get_bits_(triple) started in #58
5. [X] The `RingBuffer::extend_from_within` does a lot of small memcpy calls. These can be sped up a lot by not caring about precise copying of values behind the range we want to copy. Copying a/multiple u128 (where possible) speeds this up by a lot.

## Encoder

The main thing taking time in the encoder is the match finding algorithm

1. [ ] Different matcher algorithms
2. [ ] Faster hashing for the hashtable based matcher algorithm

Contributor guide

No contributing guide indexed for this repository

Research direction

This issue is a backlog of decoder and encoder optimization ideas rather than one defined task. Start by reading the unchecked item you choose, such as the zstd_streaming binary and drain_to_writer() functions, or the ReversedBitreader and matcher algorithms. Confirm the relevant benchmark or behavior, then define completion criteria for that single optimization.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.