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

Ouverte
  • Quelque chose ne va pas ?
#314 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 1 jour

Personne n'a encore pris cette issue.

Évaluation

Difficulté
3/5
Temps estimé
1-2 jours
Accessibilité débutants
75/100
Type d'issue
Refactorisation
Clarté
Clairement spécifiée
Activité
Active
Stack technique
python
Domaine
backend-api-design, performance

Piste de recherche

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.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

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.

Langage dominant
Python
Étoiles
534
Forks
159
Merge moyen
1 j 18 h
PR mergées (30 j)
9

Préparer son environnement

  • Aucun Dockerfile ni fichier Docker Compose
  • Propose un modèle de pull request
  • Aucun guide de contribution

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de graphql-python/graphql-core

Toutes les issues de graphql-python/graphql-core

Issues similaires

Plus d'issues Python

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.