Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

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

Abierto
  • ¿Algo no está bien?
#817 7 comentarios 1 reacción 0 asignados Ver en GitHub

Los mantenedores suelen responder en 2 días

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
35/100
Tipo de issue
Nueva funcionalidad
Claridad
Necesita aclaración
Estado de actividad
Tranquilo
Stack tecnológico
cpp
Área
hpc, performance

Línea de trabajo

Comienza revisando la comparación y la publicación del blog citadas sobre GPURobinHoodHashing y, después, inspecciona cómo cuco::static_map expone actualmente cuco::linear_probing y cuco::double_hashing. El issue necesita orientación de los maintainers sobre si Robin Hood hashing encaja como otra estrategia y qué estructura debería seguir un PR; se consideraría terminado cuando haya un alcance de implementación acordado.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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

Lenguaje dominante
Cuda
Estrellas
671
Forks
122
Merge medio
4 d 19 h
PR fusionados (30 d)
10

Preparar el entorno

Abrir en Codespaces

Inicia el contenedor de desarrollo del proyecto en tu navegador, con tu propia cuenta de GitHub.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de NVIDIA/cuCollections

Todos los issues de NVIDIA/cuCollections

Issues similares

Más issues de HPC

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.