KEMBAR78
Improve IndexOfAnyValues throughput for needles with 0 by MihaZupan · Pull Request #84184 · dotnet/runtime · GitHub
Skip to content

Improve IndexOfAnyValues throughput for needles with 0 #84184

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
May 9, 2023
Merged

Improve IndexOfAnyValues throughput for needles with 0 #84184

merged 1 commit into from
May 9, 2023

Conversation

@MihaZupan
Copy link
Member

Increases IndexOfAny throughput by 25-40% for values that contain a 0.

Instead of doing "is ascii" detection at the end as a secondary step to rule out false positives, we can effectively merge it into the "pack sources" step in a cheaper way.

Method Toolchain Length Mean Error Ratio Code Size
IndexOfAnyWithZero main 10000 414.4 ns 1.17 ns 1.38 682 B
IndexOfAnyWithZero pr 10000 301.2 ns 1.15 ns 1.00 556 B

Codegen difference: https://www.diffchecker.com/DVRMVOkA

The main loop with AVX2
image

This should help with Regex after #83992, and with ASP.NET's header validation.

@MihaZupan MihaZupan added this to the 8.0.0 milestone Mar 31, 2023
@MihaZupan MihaZupan requested a review from stephentoub March 31, 2023 20:13
@MihaZupan MihaZupan self-assigned this Mar 31, 2023
@ghost
Copy link

ghost commented Mar 31, 2023

Tagging subscribers to this area: @dotnet/area-system-memory
See info in area-owners.md if you want to be subscribed.

Issue Details

Increases IndexOfAny throughput by 25-40% for values that contain a 0.

Instead of doing "is ascii" detection at the end as a secondary step to rule out false positives, we can effectively merge it into the "pack sources" step in a cheaper way.

Method Toolchain Length Mean Error Ratio Code Size
IndexOfAnyWithZero main 10000 414.4 ns 1.17 ns 1.38 682 B
IndexOfAnyWithZero pr 10000 301.2 ns 1.15 ns 1.00 556 B

Codegen difference: https://www.diffchecker.com/DVRMVOkA

The main loop with AVX2
image

This should help with Regex after #83992, and with ASP.NET's header validation.

Author: MihaZupan
Assignees: MihaZupan
Labels:

area-System.Memory
Milestone: 8.0.0

@stephentoub
Copy link
Member

Contributes to #84139

@build-analysis build-analysis bot mentioned this pull request Mar 31, 2023
Closed
@stephentoub stephentoub requested a review from EgorBo April 3, 2023 01:51
@MihaZupan MihaZupan force-pushed the indexofanyvalues-cheaper-0 branch from d32a923 to 682e307 Compare May 3, 2023 23:35
@MihaZupan
Copy link
Member Author

Bump

Can this one be merged?

@MihaZupan MihaZupan merged commit 1b56e96 into dotnet:main May 9, 2023
@sebastienros
Copy link
Member

@MihaZupan mind doing a quick benchmark on fortunes to check for this one #86113

crank command before the change:

crank --config https://raw.githubusercontent.com/aspnet/Benchmarks/main/scenarios/database.benchmarks.yml --scenario fortunes --profile aspnet-citrine-win --application.framework net8.0 --application.aspNetCoreVersion 8.0.0-preview.5.23259.4 --application.runtimeVersion 8.0.0-preview.5.23259.2 --application.sdkVersion 8.0.100-preview.5.23259.3

@MihaZupan
Copy link
Member Author

I can check, but I'd be quite surprised if this regressed anything (especially fortunes)

@MihaZupan
Copy link
Member Author

Tried the following commits:

  1. 1b56e96 (PR Improve IndexOfAnyValues throughput for needles with 0 #84184)
  2. e241509 (commit just before nr. 3)
  3. 58a1365 (PR Unroll StringBuilder.Append for const string #85894)
load 1 2 3
Requests/sec 304,458 302,716 -0.57% 281,044 -7.69%
Requests 4,585,264 4,570,922 -0.31% 4,243,602 -7.45%
Bad responses 0 0 0

@MihaZupan MihaZupan mentioned this pull request May 11, 2023
Closed
@EgorBo EgorBo mentioned this pull request May 16, 2023
Closed
@ghost ghost locked as resolved and limited conversation to collaborators Jun 11, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

@EgorBo EgorBo EgorBo approved these changes

@stephentoub stephentoub Awaiting requested review from stephentoub

Assignees

@MihaZupan MihaZupan

Labels

area-System.Memory

Projects

None yet

Milestone

8.0.0

Development

Successfully merging this pull request may close these issues.

4 participants

@MihaZupan @stephentoub @sebastienros @EgorBo