Feature/performance: This PR introduces a high number of performance improvements. by r-Larch · Pull Request #33 · dmitry-brazhenko/SharpToken

r-Larch · 2024-03-23T19:54:22Z

This PR delivers a suite of performance enhancements, primarily spurred by the discussion in issue #2.
These optimizations were urgently needed by me.

I changed a lot in this repository. I hope this changes are welcome and get merged.
Please tell me if something does not comply with your guidelines or code styles.

Key Highlights:

Significant performance upgrades have been implemented for .NET 8.0 due to its superior support for high-performance coding practices.
While .NET 6.0 and .NET Standard have also received optimizations, they do not support certain APIs necessary for achieving the same level of performance enhancement as .NET 8.0.

For detailed performance metrics, refer to the Performance Benchmarks.

Additionally, this PR introduces a high-performance, low-allocation TokenCount method. This method is essential for my use case and, I believe, beneficial for others. It primarily facilitates the counting of tokens prior to dispatching a prompt to a LLM, ensuring that the prompt does not surpass the context window size limit. This functionality is also advantageous for segmenting text into manageable chunks for RAG.

EDIT

With my latest commits, I was able to improve speed. With these changes, SharpToken effectively becomes the fastest library for .NET with the lowest allocations.

Performance Overview:

Code: CompareBenchmark.cs

After Optimization:

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3296/23H2/2023Update/SunValley3)
AMD Ryzen 9 3900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK 8.0.200
  [Host]               : .NET 8.0.2 (8.0.224.6711), X64 RyuJIT AVX2
  .NET 6.0             : .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2
  .NET 8.0             : .NET 8.0.2 (8.0.224.6711), X64 RyuJIT AVX2
  .NET Framework 4.7.1 : .NET Framework 4.8.1 (4.8.9181.0), X64 RyuJIT VectorSize=256

Method	Runtime	Mean	Error	StdDev	Gen0	Gen1	Allocated
SharpToken	.NET 8.0	100.4 ms	1.95 ms	1.91 ms	2000.0000	-	22.13 MB
SharpToken	.NET 6.0	169.9 ms	2.42 ms	2.15 ms	24333.3333	1000.0000	196.3 MB
SharpToken	.NET Framework	455.3 ms	8.34 ms	6.97 ms	34000.0000	1000.0000	204.39 MB

TiktokenSharp	.NET 8.0	211.4 ms	1.83 ms	1.53 ms	42000.0000	1000.0000	338.98 MB
TiktokenSharp	.NET 6.0	258.6 ms	5.09 ms	6.25 ms	39000.0000	1000.0000	313.26 MB
TiktokenSharp	.NET Framework	638.3 ms	12.47 ms	16.21 ms	63000.0000	1000.0000	378.31 MB

TokenizerLib	.NET 8.0	124.4 ms	1.81 ms	1.60 ms	27250.0000	1000.0000	217.82 MB
TokenizerLib	.NET 6.0	165.5 ms	1.38 ms	1.16 ms	27000.0000	1000.0000	217.82 MB
TokenizerLib	.NET Framework	499.7 ms	9.81 ms	14.07 ms	40000.0000	1000.0000	243.79 MB

Before Optimization:

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3296/23H2/2023Update/SunValley3)
AMD Ryzen 9 3900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK 8.0.200
  [Host]               : .NET 8.0.2 (8.0.224.6711), X64 RyuJIT AVX2
  .NET 6.0             : .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2
  .NET 8.0             : .NET 8.0.2 (8.0.224.6711), X64 RyuJIT AVX2
  .NET Framework 4.7.1 : .NET Framework 4.8.1 (4.8.9181.0), X64 RyuJIT VectorSize=256

Method	Runtime	Mean	Error	StdDev	Gen0	Gen1	Allocated
SharpToken	.NET 8.0	214.1 ms	4.26 ms	3.99 ms	33000.0000	1000.0000	264.44 MB
SharpToken	.NET 6.0	267.9 ms	2.61 ms	2.31 ms	33000.0000	1000.0000	264.82 MB
SharpToken	.NET Framework	640.2 ms	9.03 ms	7.54 ms	54000.0000	2000.0000	326.51 MB

TiktokenSharp	.NET 8.0	218.2 ms	4.25 ms	6.49 ms	42000.0000	1000.0000	338.98 MB
TiktokenSharp	.NET 6.0	250.1 ms	1.64 ms	1.28 ms	39000.0000	1000.0000	313.26 MB
TiktokenSharp	.NET Framework	654.2 ms	11.57 ms	9.66 ms	63000.0000	1000.0000	378.31 MB

TokenizerLib	.NET 8.0	130.3 ms	2.29 ms	2.03 ms	27200.0000	1000.0000	217.82 MB
TokenizerLib	.NET 6.0	166.3 ms	0.74 ms	0.58 ms	27000.0000	1000.0000	217.82 MB
TokenizerLib	.NET Framework	489.4 ms	6.41 ms	5.68 ms	40000.0000	1000.0000	243.79 MB

Older benchmarks

Before Optimization:

### feat(performance): add benchmark project

- version: 1.2.17 -- (baseline)

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3155/23H2/2023Update/SunValley3)
AMD Ryzen 9 3900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK 8.0.200
  [Host]               : .NET 8.0.2 (8.0.224.6711), X64 RyuJIT AVX2
  .NET 6.0             : .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2
  .NET 8.0             : .NET 8.0.2 (8.0.224.6711), X64 RyuJIT AVX2
  .NET Framework 4.7.1 : .NET Framework 4.8.1 (4.8.9181.0), X64 RyuJIT VectorSize=256

| Method | Job                  | Runtime              | Mean     | Error     | StdDev    | Ratio | RatioSD | Gen0     | Gen1    | Allocated | Alloc Ratio |
|------- |--------------------- |--------------------- |---------:|----------:|----------:|------:|--------:|---------:|--------:|----------:|------------:|
| Encode | .NET 6.0             | .NET 6.0             | 1.732 ms | 0.0309 ms | 0.0274 ms |  0.49 |    0.01 | 191.4063 | 15.6250 |   1.53 MB |        0.62 |
| Encode | .NET 8.0             | .NET 8.0             | 1.387 ms | 0.0277 ms | 0.0406 ms |  0.39 |    0.02 | 191.4063 | 15.6250 |   1.53 MB |        0.62 |
| Encode | .NET Framework 4.7.1 | .NET Framework 4.7.1 | 3.595 ms | 0.0704 ms | 0.1287 ms |  1.00 |    0.00 | 406.2500 | 39.0625 |   2.46 MB |        1.00 |

After Optimization:

### feat(benchmark): add benchmark for large file token count

- version: 1.2.17 + improvements

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3155/23H2/2023Update/SunValley3)
AMD Ryzen 9 3900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK 8.0.200
  [Host]               : .NET 8.0.2 (8.0.224.6711), X64 RyuJIT AVX2
  .NET 6.0             : .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2
  .NET 8.0             : .NET 8.0.2 (8.0.224.6711), X64 RyuJIT AVX2
  .NET Framework 4.7.1 : .NET Framework 4.8.1 (4.8.9181.0), X64 RyuJIT VectorSize=256

| Method                 | Job                  | Runtime              | Mean        | Error     | StdDev    | Ratio | RatioSD | Gen0      | Gen1     | Gen2     | Allocated | Alloc Ratio |
|----------------------- |--------------------- |--------------------- |------------:|----------:|----------:|------:|--------:|----------:|---------:|---------:|----------:|------------:|
| Encode                 | .NET 6.0             | .NET 6.0             |    973.9 us |  19.27 us |  31.66 us |  0.77 |    0.03 |   62.5000 |   0.9766 |        - |  524034 B |        0.82 |
| Encode                 | .NET 8.0             | .NET 8.0             |    552.3 us |  10.73 us |  11.48 us |  0.44 |    0.01 |    2.9297 |        - |        - |   27841 B |        0.04 |
| Encode                 | .NET Framework 4.7.1 | .NET Framework 4.7.1 |  1,252.7 us |  24.12 us |  23.69 us |  1.00 |    0.00 |  101.5625 |   1.9531 |        - |  640074 B |        1.00 |
|                        |                      |                      |             |           |           |       |         |           |          |          |           |             |
| CountTokens            | .NET 6.0             | .NET 6.0             |    801.2 us |  16.00 us |  19.65 us |  0.65 |    0.02 |   58.5938 |   0.9766 |        - |  496386 B |       0.806 |
| CountTokens            | .NET 8.0             | .NET 8.0             |    557.3 us |  10.89 us |  10.69 us |  0.45 |    0.02 |         - |        - |        - |    4161 B |       0.007 |
| CountTokens            | .NET Framework 4.7.1 | .NET Framework 4.7.1 |  1,235.5 us |  24.52 us |  31.01 us |  1.00 |    0.00 |   97.6563 |   1.9531 |        - |  615801 B |       1.000 |
|                        |                      |                      |             |           |           |       |         |           |          |          |           |             |
| CountTokens_LargeInput | .NET 6.0             | .NET 6.0             | 13,955.6 us | 258.91 us | 242.19 us |  0.64 |    0.01 |  781.2500 | 328.1250 | 125.0000 | 6122849 B |       0.806 |
| CountTokens_LargeInput | .NET 8.0             | .NET 8.0             |  5,781.9 us | 115.07 us | 127.91 us |  0.27 |    0.01 |         - |        - |        - |      75 B |       0.000 |
| CountTokens_LargeInput | .NET Framework 4.7.1 | .NET Framework 4.7.1 | 21,674.7 us | 374.37 us | 350.18 us |  1.00 |    0.00 | 1312.5000 | 500.0000 | 156.2500 | 7596775 B |       1.000 |

… free solution

…tation in net8.0

…ly once

…ro allocations

…to support broader use

…method

…st.RemoveAt

dmitry-brazhenko · 2024-03-25T07:40:01Z

Hello @r-Larch

Thanks A LOT for this PR.

I will review it and merge it within 1-2 days.

dmitry-brazhenko · 2024-03-25T15:31:19Z

I will edit it a little bit and resolve all conflicts and merge after that.

Trying to understand some of the changes

r-Larch

I've added some comments and explanations to code decisions.

SharpToken/Lib/Internals/BytePairEncodingCore/FastPartitionList.cs

SharpToken/Lib/Internals/ModelParamsGenerator.cs

r-Larch · 2024-03-26T07:39:42Z

SharpToken/Lib/Internals/Extensions.cs

+            if (searchValues is string[] { Length: 0 })
+            {
+                return new FoundMatch { Success = false };
+            }


This if is a fast path to not have searchValues.GetEnumerator() heap allocation in case allowSpecials is empty (not provided)

This is the default case so this fast path will be taken most of the time.

I could have added a small comment..

This if could be added to net6.0 and netstandard too.

SharpToken/Lib/Internals/EmbeddedResourceReader.cs

SharpToken/Lib/Internals/BytePairIndex/BytePairIndex.net-old.cs

SharpToken/Lib/Internals/BytePairEncodingCore/BytePairEncodingCore.net8.cs

SharpToken/Lib/Encoding.cs

SharpToken.Tests/SharpToken.Tests.cs

SharpToken.Benchmark/README.md

dmitry-brazhenko · 2024-03-26T11:12:28Z

I am merging this change here: #36
Looks good to me :)

thanks a lot for contribution!

If you observe any issues, please let me know or open a new PR

r-Larch added 30 commits March 22, 2024 20:20

feat(performance): add benchmark project

02aa357

feat(performance): reduce public API surface

aa4cf54

feat(performance): reduce allocations

e9fdce3

feat(performance): use compiled regex for better performance

3d8565c

feat(performance): run benchmark

659f450

chore: move reorganize files

076843f

feat(performance): replace SpecialTokenPatternRegex with faster alloc…

7a5c48f

… free solution

feat(performance): reduce string allocations

87a19d6

feat(performance): run benchmark

f2f739f

feat(performance): add BytePairIndex class to support faster implemen…

a76a9cf

…tation in net8.0

feat(performance): cache model parameters to do params preparation on…

c27a616

…ly once

feat(performance): run benchmark

098524b

feat(performance): improve allowedSpecialTokens handling + bug fix

32b95a8

feat(performance): add support for ReadOnlySpan<char> in net8.0

d29f88a

feat(performance): run benchmark

390a693

feat(performance): use compile time generated regex in net8.0

b396e64

feat: run tests for netstandard2.0 over net471

3a40044

feat(performance): run benchmark

cdcc0b3

feat: remove unused lastTokenLength + refactoring

71a2661

feat(performance): implement fast MultiBytePairEncoder with almost ze…

9ae4222

…ro allocations

feat(performance): run benchmark

1856bc8

feat(performance): reduce allocations

3ab2251

feat(performance): backport some optimizations to net6.0 and netstandard

2bd47c3

feat(performance): run benchmark

181cf52

chore: cosmetics

8215e50

feat(refactor): extract Encoding.Encode() logic into priv EncodeCore …

2146f79

…to support broader use

feat(token-count): implement low allocation token count public method

4f8df6e

feat(performance): run benchmark

0c8cc8d

feat(benchmark): don't make allocations in benchmark methods

a4a0203

feat(performance): reduce minor allocations

ec640b1

r-Larch added 12 commits March 23, 2024 17:44

feat(benchmark): add benchmark for large file token count

f30608b

feat(performance): run benchmark

2b97c3d

fix: add test for allowedSpecialTokens and fix code

2962218

chore: fix naming

3a1523e

feat(benchmark): add another benchmark to show in README.md

07586b0

feat(readme): add benchmark to README.md and add docs for TokenCount …

1713302

…method

feat(performance): use multibyte cpu instructions for FastPartitionLi…

e0b6410

…st.RemoveAt

feat(performance): re-add fast path - got lost in refactoring

4c33ca2

feat(benchmark): add comparison to other tokenizer

7ab1b9d

feat(performance): improve ByteArrayEqualityComparer

964c571

feat(performance): small improvement

584ee05

chore: update benchmarks in README.md

0917f5a

r-Larch commented Mar 26, 2024

View reviewed changes

dmitry-brazhenko mentioned this pull request Mar 26, 2024

Pr 33 (Feature/performance: This PR introduces a high number of performance improvements) #36

Merged

dmitry-brazhenko closed this Mar 26, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Feature/performance: This PR introduces a high number of performance improvements.#33

Feature/performance: This PR introduces a high number of performance improvements.#33
r-Larch wants to merge 42 commits intodmitry-brazhenko:mainfrom
r-Larch:feature/performance

r-Larch commented Mar 23, 2024 •

edited

Loading

Uh oh!

dmitry-brazhenko commented Mar 25, 2024 •

edited

Loading

Uh oh!

dmitry-brazhenko commented Mar 25, 2024

Uh oh!

r-Larch left a comment

Uh oh!

Uh oh!

Uh oh!

r-Larch Mar 26, 2024

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

dmitry-brazhenko commented Mar 26, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

r-Larch commented Mar 23, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

EDIT

Uh oh!

dmitry-brazhenko commented Mar 25, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dmitry-brazhenko commented Mar 25, 2024

Uh oh!

r-Larch left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

r-Larch Mar 26, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

dmitry-brazhenko commented Mar 26, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

r-Larch commented Mar 23, 2024 •

edited

Loading

dmitry-brazhenko commented Mar 25, 2024 •

edited

Loading