Speed up LexicalDistance.measure used for "Did you mean" suggestions
维护者通常 1 天内回复
还没有人认领这个 Issue。
评估
- 难度
- 3/5
- 预计耗时
- 1-2 天
- 新手友好度
- 75/100
- Issue 类型
- 重构
- 描述清晰度
- 描述清楚
- 活跃度
- 活跃
- 技术栈
- python
调研方向
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.
由索引模型根据 Issue 内容生成。
描述
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.
- 主要语言
- Python
- 星标
- 534
- 派生
- 159
- 平均合并
- 1 天 18 小时
- 30 天内合并 PR
- 9
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 有 Pull Request 模板
- 没有贡献指南
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
graphql-python/graphql-core 的其他 Issue
-
collect_fields spends extra time on selections without directives可能已有人在做 关联的 PR 仍在进行中或已合并。 未关闭
难度 2/5 1-3 小时 新手友好度 78/100
graphql-python/graphql-core#315 ·
维护者通常 1 天内回复
-
is_printable_as_block_string checks each character in a Python loop可能已有人在做 关联的 PR 仍在进行中或已合并。 未关闭
难度 2/5 1-3 小时 新手友好度 83/100
graphql-python/graphql-core#312 ·
维护者通常 1 天内回复
-
natural_comparison_key: faster sort keys for names without digits可能已有人在做 关联的 PR 仍在进行中或已合并。 未关闭
难度 2/5 1-3 小时 新手友好度 76/100
graphql-python/graphql-core#310 ·
维护者通常 1 天内回复
-
Make is_awaitable faster for values that are not awaitable可能已有人在做 关联的 PR 仍在进行中或已合并。 未关闭
难度 2/5 1-3 小时 新手友好度 72/100
graphql-python/graphql-core#308 ·
维护者通常 1 天内回复
-
assert_name checks each character in a Python generator可能已有人在做 @swayamdudhela 于 2 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 76/100
graphql-python/graphql-core#304 · 4 条评论 ·
维护者通常 1 天内回复
查看 graphql-python/graphql-core 的全部 Issue
相似的 Issue
-
难度 2/5 1-3 小时 新手友好度 67/100
bigbio/sdrf-pipelines#372 · 1 条评论 ·
维护者通常 1 天内回复
-
难度 1/5 1 小时以内 新手友好度 84/100
521xueweihan/HelloGitHub#4297 ·
-
难度 2/5 1-3 小时 新手友好度 83/100
aws-samples/sample-per-model-bedrock#822 ·
维护者通常 1 天内回复
-
area:study-data p2-high ready-for-agent type:chore
难度 2/5 1-3 小时 新手友好度 78/100
fderuiter/deruiter.dev#3706 ·
维护者通常 1 天内回复
-
bug
难度 2/5 1-3 小时 新手友好度 74/100
awslabs/visual-asset-management-system#1234 ·
维护者通常 1 天内回复