Make Word.MergeAll sub-quadratic
维护者通常 1 天内回复
还没有人认领这个 Issue。
评估
- 难度
- 3/5
- 预计耗时
- 1-2 天
- 新手友好度
- 42/100
- Issue 类型
- 重构
- 描述清晰度
- 基本清楚
- 活跃度
- 活跃
- 技术栈
- csharp, machine-learning
- 领域
- performance
调研方向
The slow path is Word.MergeAll in src/Microsoft.ML.Tokenizers/Model/Word.cs, where symbols are removed from a Vec<T>-style list with Remove() while a PriorityQueue<T> drives the merges. Read that method first and find which tests in the Microsoft.ML.Tokenizers test project cover BPE merging so you can confirm the output is unchanged. Done means the removal no longer shifts the list on every merge, the existing tokenizer tests still pass, and the change is benchmarked against the old version.
由索引模型根据 Issue 内容生成。
描述
The current implementation of Word.MergeAll uses Vec<T>.Remove() to remove symbols from the list:
Based on data I found, it seems it's common that around 75 % of symbols are removed here (though the data conflates multiple steps, so it could be not fully relevant). This makes the method quadratic, likely significantly affecting its performance.
We should consider improving that. (This won't make the method linear, since the use of PriorityQueue<T> leads to at least O(n log n).)
- 主要语言
- C#
- 星标
- 9.4k
- 派生
- 2k
- 平均合并
- 2 天 18 小时
- 30 天内合并 PR
- 64
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
dotnet/machinelearning 的其他 Issue
-
area-Native untriaged
难度 2/5 1-3 小时 新手友好度 76/100
dotnet/machinelearning#7837 ·
维护者通常 1 天内回复
-
area-TensorFlow untriaged
难度 2/5 1-3 小时 新手友好度 62/100
dotnet/machinelearning#7836 ·
维护者通常 1 天内回复
-
area-DataFrame bug untriaged
难度 2/5 1-3 小时 新手友好度 62/100
dotnet/machinelearning#7799 ·
维护者通常 1 天内回复
-
LlamaTokenizer encodes some runs of repeated characters differently from SentencePiece可能已有人在做 @Laurianti 于 42 天前认领。 未关闭area-Tokenizers untriaged
难度 2/5 1-3 小时 新手友好度 88/100
dotnet/machinelearning#7751 · 1 条评论 ·
维护者通常 1 天内回复
-
BertTokenizer merges words separated only by `\n`, `\t` or `\r`可能已有人在做 @Laurianti 于 23 天前认领。 未关闭area-Tokenizers green
难度 2/5 1-3 小时 新手友好度 85/100
dotnet/machinelearning#7724 · 3 条评论 ·
维护者通常 1 天内回复
查看 dotnet/machinelearning 的全部 Issue
相似的 Issue
-
bug emitter:client:csharp
难度 2/5 1-3 小时 新手友好度 84/100
microsoft/typespec#12572 · 1 条评论 · 1 个 reaction ·
维护者通常 1 天内回复
-
needs-area-label
难度 2/5 1-3 小时 新手友好度 78/100
维护者通常 2 天内回复
-
AWS Lambda: KeyNotFoundException drops HTTP-triggered transactions when allowAllHeaders is disabled未关闭bug
难度 2/5 1-3 小时 新手友好度 70/100
newrelic/newrelic-dotnet-agent#3949 · 1 条评论 ·
维护者通常 1 天内回复
-
area-networking
难度 2/5 1-3 小时 新手友好度 78/100
dotnet/aspnetcore#70545 · 1 条评论 ·
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 87/100
维护者通常 1 天内回复