Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

Question about LZ77 decode dependencies and parallelization (learning)

Đang mở
  • Có gì không ổn?
#4,630 2 bình luận 0 reaction 0 người được giao Xem trên GitHub

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
25/100
Loại issue
Tính năng
Độ rõ ràng
Cần làm rõ
Mức độ hoạt động
Ít trao đổi
Công nghệ
c
Lĩnh vực
performance

Hướng nghiên cứu

Issue không nêu tệp mã nguồn, bài kiểm thử hoặc các điểm vào nào. Hãy bắt đầu bằng việc xem xét ngữ cảnh LZ77 toàn cục đã mô tả, các offset của block và những câu hỏi về giải mã song song; công việc được xem là hoàn tất khi có phần giải thích được ghi thành tài liệu về mô hình phụ thuộc và các cạm bẫy, được hỗ trợ bởi đoạn code đã hứa hoặc các chi tiết bổ sung.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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

Ngôn ngữ chính
C
Star
28.1k
Fork
2.7k
Không có pull request nào được merge trong 30 ngày

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của facebook/zstd

Tất cả issue của facebook/zstd

Issue tương tự

Thêm issue về C

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.