Constant Time Lookup NibbleMap #108939
Merged
Constant Time Lookup NibbleMap #108939
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
lambdageek
reviewed
Oct 16, 2024
max-charlamb
force-pushed
the
nibble-optimize
branch
2 times, most recently
from
e105570
to
d59ea81
Compare
This was referenced Oct 18, 2024
|
/azp run |
|
You have several pipelines (over 10) configured to build pull requests in this repository. Specify which pipelines you would like to run by using /azp run [pipelines] command. You can specify multiple pipelines using a comma separated list. |
|
/azp run runtime-coreclr outerloop |
|
Azure Pipelines successfully started running 1 pipeline(s). |
|
/azp run runtime-coreclr outerloop |
|
Azure Pipelines successfully started running 1 pipeline(s). |
3 tasks
max-charlamb
force-pushed
the
nibble-optimize
branch
2 times, most recently
from
836f71f
to
25c987e
Compare
lambdageek
reviewed
Oct 30, 2024
|
@max-charlamb when this is ready to go, please also add a task to #108553 to update the |
max-charlamb
changed the title
|
No pipelines are associated with this pull request. |
added 7 commits
November 5, 2024 10:30
added 14 commits
November 5, 2024 10:30
max-charlamb
force-pushed
the
nibble-optimize
branch
from
867afe4
to
f975925
Compare
davidwrighton
approved these changes
Nov 7, 2024
Thanks David. I skimmed through and it looked fine to me. On the DAC side we might find that doing many small reads has higher perf costs than we'd like, but I don't think its worth optimizing right now just based on my speculation. The current DAC probably has similar overhead and we have room to optimize in the future if testing broader scenarios identifies this part of the code as a hot spot. |
|
Looks like this change broke AltJits, I am seeing cc @dotnet/jit-contrib if you observe the same |
|
Yes, i can confirm that I have seen this failure using altjit: |
|
Opened #109970 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
What is it?
The existing nibblemap data structure has O(n) reads and O(1) writes.
Implements an alternative nibblemap data structure that has O(1) reads and O(n) writes.
Fixes #93550
See other PR which adds cDAC support for the new algorithm: #109654
Changes
NibbleMapSetandFindMethodCodeNibbleMapDeletebecause the codeSize argument is not required for deletion.size_t codeSizeargument toNibbleMapSetand passes proper code size in all invocations.MethodSectionIteratorto new nibblemap implementation.OutOfProcessFindHeaderto new nibblemap implementation."nibblemapmacros.h"incodepitchingmanager.cpp. This does not appear to be used and is removed for clarity and to keep nibblemap changes isolated.Benchmarking
Tests
In order to compare the performance of the previous (Linear) algorithm with the new algorithm (Constant), all of the dotnet/performance benchmarks relating to Exceptions were run.
In addition, an optimal scenario for the Constant algorithm was created (but not checked in). The new algorithm should see the most improvement when it is reading from the end of an extremely long function. The previous algorithm would have needed to iterate to the beginning of the function body, with a single DWORD read accounting for 256 bytes of the function. Usually this is a small number but can grow given method length is unbounded.
To show off the difference, I created a benchmark
StackTracewith an artificially long function which recursively calls itself (requiring multiple nibblemap reads to unwind the stack). This was done by using ~6000 successiveif (b) { Console.WriteLine("Hello World"); }statements. In the test runbis always false but still generates extra instructions.When this is compiled down to win-x64 assembly the function is
152990bytes long. Therefore, doing aFindMethodCode(nibble map read) near the end of the function should result in almost 600 successive DWORD reads in the Linear algorithm compared to 2 in the Constant algorithm.Results
The microbenchmark runs seem to have inconclusive results. While we would expect the Constant algorithm to be faster in extremely long functions (StackTrace test) this is only true some of the time. This could be due the the microbenchmark format allowing the processors branch predictor to correctly guess the number of iterations to read in the linear algorithm effectively skipping a large cost in real world scenarios. This effect varies across stack depth and seems inconsistent run to run.
Overall, this change seems to be within ~5% (better or worse) performance from the previous linear algorithm, but reduces the theoretical worst-case performance.
Benchmarking details
Verification
OutOfProcessFindHeader