facebook / facebook/zstd

[edge case] Zstd performs badly on 200-symbol uniform data

Open
#3,162 2 comments 4 reactions 1 assignee Claimed by @yoniko View on GitHub
enhancement release-blocking
Dominant language
C
Stars
27.9k
Forks
2.6k
Avg merge
1d 3h
Merged PRs (30d)
8

Description

Data generated by this script:

```python3
import random
rd = random.Random()
rd.seed(0)
HIGH_ENTROPY = bytes(rd.randint(0, 200) for _ in range(10_000_000)) * 10
with open("med.bin", "wb") as f:
f.write(HIGH_ENTROPY)
```

gzip -1: 100000000 -> 96526120
zstd -1: 100000000 -> 100002299

If I remove these heusistics:

https://github.com/facebook/zstd/blob/b7b7edb3a3017ac8e16d7eb2dbede45168560c58/lib/compress/huf_compress.c#L1297
https://github.com/facebook/zstd/blob/b7b7edb3a3017ac8e16d7eb2dbede45168560c58/lib/compress/huf_compress.c#L1303

We get:

zstd -1: 100000000 -> 96449637

Zstd should do a better job with determining compressibility so we don't lose out on this case.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.