]> git.ipfire.org Git - thirdparty/zstd.git/commit
[libzstd] Optimize ZSTD_insertBt1() for repetitive data
authorNick Terrell <terrelln@fb.com>
Thu, 6 Jun 2019 03:20:55 +0000 (20:20 -0700)
committerNick Terrell <nickrterrell@gmail.com>
Thu, 6 Jun 2019 03:34:00 +0000 (20:34 -0700)
commitcdb9481e388139a3ca534c46f58959971f4755d4
treee7f8639ef83d5d2b45fb73b1061f4d2752fb6f3f
parentc0eb6c9c81e2dd31571267b37c12cdaa92b7ffd7
[libzstd] Optimize ZSTD_insertBt1() for repetitive data

We would only skip at most 192 bytes at a time before this diff.
This was added to optimize long matches and skip the middle of the
match. However, it doesn't handle the case of repetitive data.

This patch keeps the optimization, but also handles repetitive data
by taking the max of the two return values.

```
> for n in $(seq 9); do echo strategy=$n; dd status=none if=/dev/zero bs=1024k count=1000 | command time -f %U ./zstd --zstd=strategy=$n >/dev/null; done
strategy=1
0.27
strategy=2
0.23
strategy=3
0.27
strategy=4
0.43
strategy=5
0.56
strategy=6
0.43
strategy=7
0.34
strategy=8
0.34
strategy=9
0.35
```

At level 19 with multithreading the compressed size of `silesia.tar` regresses 300 bytes, and `enwik8` regresses 100 bytes.
In single threaded mode `enwik8` is also within 100 bytes, and I didn't test `silesia.tar`.

Fixes Issue #1634.
lib/compress/zstd_opt.c