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

Aperta
  • Qualcosa non va?
#314 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
75/100
Tipo di issue
Refactoring
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
python
Ambito
backend-api-design, performance

Direzione di ricerca

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.

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

Descrizione

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.

Lingua principale
Python
Stelle
534
Fork
159
Merge medio
1g 18h
PR unite (30g)
9

Preparare l'ambiente

  • Nessun Dockerfile né file Docker Compose
  • Ha un modello di pull request
  • Nessuna guida per i contributori

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

Tutte le issue di graphql-python/graphql-core

Issue simili

Altre issue su Python

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.