Skip to content

Small performance improvement of PathParser#4208

Merged
dipeshmsft merged 1 commit intodotnet:mainfrom
ThomasGoulet73:pathparser-performance
Aug 12, 2022
Merged

Small performance improvement of PathParser#4208
dipeshmsft merged 1 commit intodotnet:mainfrom
ThomasGoulet73:pathparser-performance

Conversation

@ThomasGoulet73
Copy link
Contributor

I replaced the IndexOf call on a private static string with a custom method that returns whether or not a char is a special char. I think this method is on a hot path because it is called on almost every char of the path passed to the method Parse and one of the usage of this method is in the constructor of Binding when you pass a path, which I think is a very common usage.

Check here to follow the usage in Binding ctor:
https://github.com/dotnet/wpf/blob/master/src/Microsoft.DotNet.Wpf/src/PresentationFramework/System/Windows/Data/Binding.cs#L230
https://github.com/dotnet/wpf/blob/master/src/Microsoft.DotNet.Wpf/src/PresentationFramework/System/Windows/PropertyPath.cs#L93
https://github.com/dotnet/wpf/blob/master/src/Microsoft.DotNet.Wpf/src/PresentationFramework/System/Windows/PropertyPath.cs#L369
https://github.com/dotnet/wpf/blob/master/src/Microsoft.DotNet.Wpf/src/PresentationFramework/MS/Internal/Data/PathParser.cs#L82

I used the following code to benchmark it:
https://gist.github.com/ThomasGoulet73/9220a9e448f86f0c181fe9771fe174d7

Here are the results:

Method ch Mean Error StdDev Median Ratio RatioSD Gen 0 Gen 1 Gen 2 Allocated
Old . 3.899 ns 0.0435 ns 0.0385 ns 3.900 ns 1.00 0.00 - - - -
New . 1.900 ns 0.0212 ns 0.0198 ns 1.893 ns 0.49 0.01 - - - -
Old / 4.155 ns 0.0183 ns 0.0171 ns 4.154 ns 1.00 0.00 - - - -
New / 1.715 ns 0.0768 ns 0.0718 ns 1.739 ns 0.41 0.02 - - - -
Old [ 3.979 ns 0.2053 ns 0.5653 ns 4.306 ns 1.00 0.00 - - - -
New [ 1.837 ns 0.1387 ns 0.4069 ns 1.569 ns 0.49 0.19 - - - -
Old ] 3.909 ns 0.2167 ns 0.6389 ns 4.288 ns 1.00 0.00 - - - -
New ] 1.178 ns 0.0518 ns 0.0509 ns 1.182 ns 0.29 0.05 - - - -
Old a 4.864 ns 0.1259 ns 0.1399 ns 4.803 ns 1.00 0.00 - - - -
New a 1.215 ns 0.0374 ns 0.0350 ns 1.225 ns 0.25 0.01 - - - -

The perf gain is small but since it's called on almost every char of the path, I think it is worth it.

Thank you!

@ThomasGoulet73 ThomasGoulet73 requested a review from a team as a code owner February 23, 2021 04:52
@ghost ghost added the PR metadata: Label to tag PRs, to facilitate with triage label Feb 23, 2021
@ghost ghost requested review from SamBent, fabiant3 and ryalanms February 23, 2021 04:52
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You can get even more performance if the bound-checks* are eleminated.
_n is the length of the path, so use this information for the JIT.

Suggested change
while (_index < _n && (level > 0 || !IsSpecialChar(_path[_index])))
string path = _path;
int index = _index;
while ((uint)index < (uint)path.Length && (level > 0 || !IsSpecialChar(path[index])))

Removes the bound-checks.
The same could be done at other places -- and get rid of the (unnecessary) _n field (makes the parser 4-bytes smaller, not much but a little bit and it harms perf as the JIT can't remove bound-checks).

* the JIT needs to emit these bound-checks in order to prove the access to the array is within bound. Only if the JIT is sure the access won't be outside, these can be removed.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I already tried removing the bound-checks but I didn't see any perf gain. Though I didn't use the uint cast. I will try to benchmark it again with the cast and I can open another PR with your suggestions if you'd like.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The uint-cast is essential for the JIT, as any negative value (which is allowed by int) will be > int.MaxValue and so for sure outside the bounds. Then when the JIT sees that index is non-negative and < length it's OK to elide the bound-check.

Though the JIT could be improved in that area (and it is).

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

One cmp can be saved by

Suggested change
return ch == '.' || ch == '/' || ch == '[' || ch == ']';
// ASCII for . = 46 and for / = 47, so use this to save a comparison
return (uint)(ch - 46) <= 2 || ch == '[' || ch == ']';

The char between [ and ] is \, so if the backslash could be treated as (implicit) special char, then another cmp could be saved.

Copy link
Member

@gfoidl gfoidl Feb 23, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

With the benchmark above I get these numbers:

| Method | ch |     Mean |     Error |    StdDev |   Median | Ratio | RatioSD |
|------- |--- |---------:|----------:|----------:|---------:|------:|--------:|
|    New |  . | 1.708 ns | 0.0429 ns | 0.0380 ns | 1.709 ns |  1.00 |    0.00 |
|   New1 |  . | 2.255 ns | 0.0442 ns | 0.0392 ns | 2.247 ns |  1.32 |    0.04 |
|        |    |          |           |           |          |       |         |
|    New |  / | 1.683 ns | 0.0661 ns | 0.0707 ns | 1.670 ns |  1.00 |    0.00 |
|   New1 |  / | 1.690 ns | 0.0459 ns | 0.0430 ns | 1.687 ns |  1.00 |    0.06 |
|        |    |          |           |           |          |       |         |
|    New |  [ | 2.334 ns | 0.0830 ns | 0.0693 ns | 2.326 ns |  1.00 |    0.00 |
|   New1 |  [ | 2.259 ns | 0.0364 ns | 0.0323 ns | 2.257 ns |  0.97 |    0.03 |
|        |    |          |           |           |          |       |         |
|    New |  ] | 2.001 ns | 0.0623 ns | 0.0583 ns | 2.011 ns |  1.00 |    0.00 |
|   New1 |  ] | 1.760 ns | 0.0729 ns | 0.1473 ns | 1.691 ns |  0.89 |    0.12 |
|        |    |          |           |           |          |       |         |
|    New |  a | 1.912 ns | 0.0278 ns | 0.0217 ns | 1.911 ns |  1.00 |    0.00 |
|   New1 |  a | 1.430 ns | 0.0565 ns | 0.0528 ns | 1.437 ns |  0.75 |    0.03 |

Only the case . is slower, as in New this is the first char to be tested against. All other cases show some improvements.
To have a clear view if the regression for . is acceptable or not, one should benchmark with real pathes to make it more realistic. Also with these kind of benchmarks the cpu's branch predictor is trained well, so it will know which branch to take, which isn't very realistic either. So micro-benchmarks are fine, but not necessary reflect the usage of the method / type.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Here is a benchmark with only a call to PathParser.Parse:

Method str Mean Error StdDev Ratio RatioSD Gen 0 Gen 1 Gen 2 Allocated
Old Model 149.2 ns 1.93 ns 1.71 ns 1.00 0.00 0.0165 - - 104 B
New Model 129.8 ns 0.50 ns 0.47 ns 0.87 0.01 0.0165 - - 104 B
Old Model.Model 240.6 ns 1.22 ns 1.14 ns 1.00 0.00 0.0391 - - 248 B
New Model.Model 200.4 ns 0.60 ns 0.53 ns 0.83 0.00 0.0393 - - 248 B
Old Model.Model.Model 338.3 ns 5.32 ns 5.91 ns 1.00 0.00 0.0572 - - 360 B
New Model.Model.Model 279.5 ns 0.85 ns 0.80 ns 0.83 0.02 0.0572 - - 360 B
Old Model(...)Model [23] 422.6 ns 1.32 ns 1.11 ns 1.00 0.00 0.0749 - - 472 B
New Model(...)Model [23] 337.4 ns 1.84 ns 1.63 ns 0.80 0.00 0.0749 - - 472 B

I tried using values that represents real-word scenario. If you have other values that you'd like me to try, I can run another benchmark.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Here is the results with your suggestion:

Method str Mean Error StdDev Ratio RatioSD Gen 0 Gen 1 Gen 2 Allocated
Old Model 153.1 ns 3.04 ns 2.84 ns 1.00 0.00 0.0165 - - 104 B
New Model 135.1 ns 1.54 ns 1.36 ns 0.88 0.02 0.0165 - - 104 B
Old Model.Model 244.9 ns 3.42 ns 3.04 ns 1.00 0.00 0.0391 - - 248 B
New Model.Model 212.2 ns 2.22 ns 1.97 ns 0.87 0.01 0.0393 - - 248 B
Old Model.Model.Model 335.1 ns 0.91 ns 0.76 ns 1.00 0.00 0.0572 - - 360 B
New Model.Model.Model 289.5 ns 1.00 ns 0.84 ns 0.86 0.00 0.0572 - - 360 B
Old Model(...)Model [23] 424.1 ns 4.17 ns 3.69 ns 1.00 0.00 0.0749 - - 472 B
New Model(...)Model [23] 361.8 ns 0.70 ns 0.58 ns 0.85 0.01 0.0749 - - 472 B

It seems a bit worse on my machine.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for doing the benchmarks. So I think it's best to keep your code as the numbers don't show a clear winner, but your code is more intuitive and readable.

We should just make sure that the most common special-char comes first -- I don't know which one is the most common.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't know either which one is the most common but I suspect the most common is the ".". I've never seen a usage of "/". I don't think a path includes many "[" and "]" since it's for an indexer and I don't think it is common to have multiple indexer on the same path.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We have a rather large WPF app with about 70 projects, none of which use / and I found 29 instances of .. This doesn't include any of the XAML brought in thru Telerik controls.

@ThomasGoulet73
Copy link
Contributor Author

Thank you @gfoidl for your feedback!

Base automatically changed from master to main March 17, 2021 17:38
@ThomasGoulet73 ThomasGoulet73 force-pushed the pathparser-performance branch from 6214b3a to 26a15cd Compare August 17, 2021 18:00
@pchaurasia14 pchaurasia14 added the Community Contribution A label for all community Contributions label Jul 20, 2022
@ghost ghost assigned ThomasGoulet73 Jul 20, 2022
@dipeshmsft
Copy link
Member

We have taken this PR for the current Community Test Pass. Thanks for the contribution.

@dipeshmsft dipeshmsft merged commit 65c4dbe into dotnet:main Aug 12, 2022
@ThomasGoulet73 ThomasGoulet73 deleted the pathparser-performance branch August 12, 2022 14:29
@ghost ghost locked as resolved and limited conversation to collaborators Sep 11, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

Community Contribution A label for all community Contributions PR metadata: Label to tag PRs, to facilitate with triage

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants