Speed up LexicalDistance.measure used for "Did you mean" suggestions

Abierto
  • ¿Algo no está bien?
#314 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
3/5
Tiempo estimado
1-2 días
Aptitud para principiantes
75/100
Tipo de issue
Refactorización
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
python
Área
backend-api-design, performance

Línea de trabajo

Start by locating LexicalDistance.measure() and its callers in suggestion_list(); the issue names tests/benchmarks/test_validate_invalid_gql.py as a performance benchmark. Read the current distance calculation and run that benchmark to establish a baseline. Implement the proposed prefix/suffix trimming, threshold early return, and row-buffer changes, then compare benchmark results and check that suggestion behavior remains correct.

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

Descripción

Problem

suggestion_list() calls LexicalDistance.measure() once for each option. When a query has a typo, validation uses this to build "Did you mean ...?" hints. On large schemas, this distance code takes most of the validation time.

The method does extra work for each option:

  • It builds the full distance table even when a shared prefix or suffix needs no edits.
  • It builds the table even when the option has more missing characters than the threshold allows.
  • It calls min() with three values in every cell, even when the two characters are equal.
  • It converts the option to a list of code points on every call.

Numbers

Python 3.12 on Linux. The Before column is the current main, and the After column is the proposed change.

Situation Before After Change
tests/benchmarks/test_validate_invalid_gql.py (median) 22.49 ms 11.42 ms 49% faster
suggestion_list, 12-char typo, 2000 random names 27.04 ms 2.69 ms 90% faster
suggestion_list, 4-char typo, 2000 random names 2.28 ms 0.61 ms 73% faster
suggestion_list, 30-char input, 2000 random names 0.70 ms 0.30 ms 58% faster
Exact or case-only matches, 2000 options 0.170 ms 0.179 ms about the same (early return, code unchanged)

Proposed fix

Skip the common prefix and suffix, and return early when too many characters are missing. In the table, copy the diagonal cell for equal characters, and rotate the row buffers.

Environment

graphql-core main (1d505c1), CPython 3.12, Linux x86_64.

Lenguaje dominante
Python
Estrellas
534
Forks
159
Merge medio
1 d 18 h
PR fusionados (30 d)
9

Preparar el entorno

  • Sin Dockerfile ni archivo de Docker Compose
  • Tiene una plantilla de pull request
  • Sin guía de contribución

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 graphql-python/graphql-core

Todos los issues de graphql-python/graphql-core

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.