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

Offen
  • Stimmt etwas nicht?
#314 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
3/5
Geschätzter Aufwand
1-2 Tage
Anfängerfreundlichkeit
75/100
Issue-Typ
Refactoring
Klarheit
Klar beschrieben
Aktivitätsstatus
Aktiv
Tech-Stack
python
Bereich
backend-api-design, performance

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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.

Vorherrschende Sprache
Python
Sterne
534
Forks
159
Ø Merge
1 T. 18 Std.
Gemergte PRs (30 T.)
9

Entwicklungsumgebung

  • Kein Dockerfile und keine Docker-Compose-Datei
  • Hat eine Pull-Request-Vorlage
  • Kein Beitragsleitfaden

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus graphql-python/graphql-core

Alle Issues in graphql-python/graphql-core

Ähnliche Issues

Weitere Issues zu Python

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.