Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Question about LZ77 decode dependencies and parallelization (learning)

Aperta
  • Qualcosa non va?
#4,630 2 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Da chiarire
Stato di attività
Tranquilla
Stack tecnologico
c
Ambito
performance

Direzione di ricerca

L’issue non indica file sorgente, test o punti di ingresso. Inizia esaminando il contesto globale LZ77 descritto, gli offset dei blocchi e le questioni relative alla decodifica parallela; il lavoro sarebbe completato con una spiegazione documentata del modello delle dipendenze e delle insidie, supportata dal codice promesso o da dettagli aggiuntivi.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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

Lingua principale
C
Stelle
28.1k
Fork
2.7k
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di facebook/zstd

Tutte le issue di facebook/zstd

Issue simili

Altre issue su C

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.