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

[ENHANCEMENT]: Robin Hood Hashing performance improvement - would a PR be welcome?

Aperta
  • Qualcosa non va?
#817 7 commenti 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
35/100
Tipo di issue
Funzionalità
Chiarezza
Da chiarire
Stato di attività
Tranquilla
Stack tecnologico
cpp
Ambito
hpc, performance

Direzione di ricerca

Inizia esaminando il confronto e il post sul blog citati su GPURobinHoodHashing, quindi analizza come cuco::static_map espone attualmente cuco::linear_probing e cuco::double_hashing. L'issue richiede indicazioni dei maintainer per stabilire se l'hashing Robin Hood sia adatto come ulteriore strategia e quale struttura dovrebbe seguire un PR; sarà completata quando sarà definito un ambito di implementazione condiviso.

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

Descrizione

topic: performance type: feature request
Is your feature request related to a problem? Please describe.

See below.

Describe the solution you'd like

I recently decided, mostly for fun, to challenge myself to re-implement a concurrent hashing table based on Robin Hood hashing that I designed and built in 2016 as part of a project on GPU-accelerated Latent Dirichlet Allocation, but never actually got to work.

This time, I did get it to work - and according to my benchmarks, the resulting table has higher get throughput than cuCollections' static_map with either linear probing or double hashing, by quite a bit at sufficiently high load factors.

Performance

Repo for this comparison: https://github.com/aterenin/GPURobinHoodHashing. I've also got a blog post around some of the ideas and why I found this exercise interesting: https://avt.im/blog/sculpting-fragile-glass/.

I don't know what Nvidia's policy on external contributions to this library is, but if there is interest, I'd love to contribute the core algorithmic ideas to cuCollections so that other people can use them. I'd image this would look like a third option like cuco::double_hashing or cuco::linear_probing but which would implement the Robin Hood strategy. It'd probably improve performance in static_map and possibly other data structures depending on how advanced your templating logic is.

Would a PR on this be welcome? If yes, I'll put one together - I'd appreciate pointers on the cleanest way to add this structure-wise in case you have any: I value high-quality code and will work to do everything the right way. If not, no worries, feel free to just close the issue. Please let me know either way.

Describe alternatives you've considered

No response

Additional context

No response

Lingua principale
Cuda
Stelle
671
Fork
122
Merge medio
4g 19h
PR unite (30g)
10

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

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 NVIDIA/cuCollections

Tutte le issue di NVIDIA/cuCollections

Issue simili

Altre issue su HPC

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.