facebook / facebook/zstd

Question about LZ77 decode dependencies and parallelization (learning)

未关闭
#4,630 2 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
C
星标
27.9k
派生
2.6k
平均合并
1 天 3 小时
30 天内合并 PR
8

描述

Hi,

I’m not very experienced with compression, so sorry if this is a naive question.

I’ve been experimenting with an LZ77-like approach and got a result that I don’t fully understand.

I managed to get:
- bit-perfect decoding
- ~10 GB/s decode on a ~1GB file
- while still using a global compression context

The way I structured it is roughly:

- compression is global (matches can reference earlier data across the whole input)
- but I split the output into blocks
- and precompute offsets so each block knows where its literals / offsets / lengths / commands are

So blocks are not independently compressed, but I try to make them independently decodable.

This seems to allow parallel decode, which is where the speed comes from.

But I feel like I’m probably misunderstanding something fundamental, because I don’t see this pattern used much.

My questions:

- Is there a fundamental reason why LZ77 decode is usually strictly sequential?
- Are there known designs that separate compression context from decode dependency like this?
- What are the main pitfalls of this approach in real implementations?

I’m not claiming this is new — I’m just trying to understand what I might be missing.

Happy to share code or more details if that helps.

Thanks

贡献指南

打开贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。