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

Performance improvement in `SimHashIterator`

Abierto
  • ¿Algo no está bien?
#78 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
38/100
Tipo de issue
Refactorización
Claridad
Bastante claro
Estado de actividad
Estancado
Stack tecnológico
rust
Área
performance

Línea de trabajo

Comienza localizando SimHashIterator, BitChunks y SIM_BUCKET_SIZE en el repositorio; después, lee cómo se forman actualmente los buckets. Investiga cómo BitChunks puede omitir rangos de ceros y cómo se manejaría un bucket que abarque varios chunks. Se considera terminado cuando se reduzca la mezcla de rangos vacíos sin cambiar los resultados de los buckets de SimHash.

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

Descripción

The current SimHashIterator works by finding the most significant active bit, and then calculating the number of SimHash buckets that will exist from that bit to the end of the filter. This means we are iterating (most_significant_bit / SIM_BUCKET_SIZE) + SIM_BUCKETS buckets.

The problem here is that in the higher order bits the sparsity is very high, meaning that there will potentially be many buckets where the values we're mixing into our SimHashes will just be zeros, and given any value XOR 0 is just that value this is wasted computation.

We could move to use the BitChunks iterators which batch up our chunks into a u64 and an index of that block of bits, skipping ranges full of zeros. This will introduce issues where if our SimHash bucket straddles multiple BitChunks, which can be solved by peeking the next chunk, making sure that the index is contiguous with our current chunk.

Right now SIM_BUCKET_SIZE is always 6 bits but if we allowed fully arbitrary SimHash bucket sizes this could get slightly gnarly because we'd need to be able to peek an arbitrary number of BitChunks ahead of the current position.

The following is a line chart plot of the proportion of empty bit_ranges mixed into the SimHashes using pseudorandomly generated geofilters with 0..100_000 items added to them.

Image

The ratio reduces very sharply after a couple of inserts but remains relatively high since newly added items have some chance of landing in a very significant bucket which introduces a load of zero gaps before the next one bit.

Lenguaje dominante
Rust
Estrellas
134
Forks
23
Merge medio
14 h 37 min
PR fusionados (30 d)
8

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 github/rust-gems

Todos los issues de github/rust-gems

Issues similares

Más issues de Rust

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.