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

Review hash functions

Aperta
  • Qualcosa non va?
#859 1 commento 1 reazione 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 2 giorni

Nessuno ha ancora preso questa issue.

Valutazione

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

Direzione di ricerca

Start by reading test case #456 and locating the hash functions and hash-table code it exercises; the issue does not name specific files. Compare collision rates for the approaches discussed, including the current functions, and establish what improvement is expected before proposing a change.

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

Descrizione

enhancement

I've observed that the test case from #456 (which has about 15,000 variables, IIRC) shows pretty bad collision rates, even after switching from k&r hash to perl hash.

I suspect two things are in play:

  1. We use 32 bits hash functions. Per the Birthday Paradox, that means a 50% chance of collision after ~25,000 elements, and growing rapidly1. A 64 bits hash function reaches that point only after 1.6 billion elements.

  2. We use multiplicative hashes and those tend to have poor entropy in their low bits. Perl hash tries to mitigate that with a final shuffle but I have a hunch that a 64 bits big prime multiplicative hash performs better.

Counterpoint contra (2): we could get better distribution out of our 32 bits multiplicative hash functions with h >> (32-N), where N is a power of two, but only if we used power-of-two hash tables. But we don't because those are more memory hungry.

1 ninja edit: which we then bucket - truncating the result, basically - compounding the effect

Lingua principale
C
Stelle
3.9k
Fork
389
Merge medio
2g 17h
PR unite (30g)
21

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

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 quickjs-ng/quickjs

Tutte le issue di quickjs-ng/quickjs

Issue simili

Altre issue su C

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.