Make Word.MergeAll sub-quadratic
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
- 42/100
- Issue-Typ
- Refactoring
- Klarheit
- Größtenteils klar
- Aktivitätsstatus
- Aktiv
- Tech-Stack
- csharp, machine-learning
- Bereich
- performance
Rechercherichtung
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.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Beschreibung
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).)
- Vorherrschende Sprache
- C#
- Sterne
- 9.4k
- Forks
- 2k
- Ø Merge
- 2 T. 18 Std.
- Gemergte PRs (30 T.)
- 64
Entwicklungsumgebung
- Kein Dockerfile und keine Docker-Compose-Datei
- Hat eine Pull-Request-Vorlage
- Beitragsleitfaden lesen
Erste Schritte
- Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
- Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
- Forken Sie das Repository und arbeiten Sie in einem Branch.
- Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.
Mehr aus dotnet/machinelearning
-
area-Native untriaged
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 76/100
dotnet/machinelearning#7837 ·
Maintainer antworten meist innerhalb von 1 Tag
-
area-TensorFlow untriaged
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 62/100
dotnet/machinelearning#7836 ·
Maintainer antworten meist innerhalb von 1 Tag
-
ToArrowRecordBatches accumulates arrays from previous batches, producing invalid record batchesOffenarea-DataFrame bug untriaged
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 62/100
dotnet/machinelearning#7799 ·
Maintainer antworten meist innerhalb von 1 Tag
-
LlamaTokenizer encodes some runs of repeated characters differently from SentencePieceEvtl. vergeben @Laurianti hat das vor 42 Tagen übernommen. Offenarea-Tokenizers untriaged
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 88/100
dotnet/machinelearning#7751 · 1 Kommentar ·
Maintainer antworten meist innerhalb von 1 Tag
-
BertTokenizer merges words separated only by `\n`, `\t` or `\r`Evtl. vergeben @Laurianti hat das vor 23 Tagen übernommen. Offenarea-Tokenizers green
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 85/100
dotnet/machinelearning#7724 · 3 Kommentare ·
Maintainer antworten meist innerhalb von 1 Tag
Alle Issues in dotnet/machinelearning
Ähnliche Issues
-
bug emitter:client:csharp
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 84/100
microsoft/typespec#12572 · 1 Kommentar · 1 Reaktion ·
Maintainer antworten meist innerhalb von 1 Tag
-
needs-area-label
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 78/100
Maintainer antworten meist innerhalb von 2 Tagen
-
AWS Lambda: KeyNotFoundException drops HTTP-triggered transactions when allowAllHeaders is disabledOffenbug
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 70/100
newrelic/newrelic-dotnet-agent#3949 · 1 Kommentar ·
Maintainer antworten meist innerhalb von 1 Tag
-
area-networking
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 78/100
dotnet/aspnetcore#70545 · 1 Kommentar ·
Maintainer antworten meist innerhalb von 1 Tag
-
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 87/100
Maintainer antworten meist innerhalb von 1 Tag