Memory Randomization

[adamsitnik]

The Problem

The problem that we are facing with our current setup are benchmarks that:

• have a flat distribution when run just once locally because the memory is allocated just once and BenchmarkDotNet uses the same input for all the iterations in a given run.
• have a multimodal distribution when considering historical data from multiple runs because the memory alignment changes over time and we don't control it. Example: today we are sorting an aligned array, tomorrow an unaligned one, and the reported time is different.

Goal

The goal of the study was to see how randomizing memory alignment could improve long-term benchmark stability. What might seem to be surprising is that we don't want to get a flat distribution when running locally, but get a full picture for all possible scenarios (aligned and not aligned).

The idea comes from stabilizer project, which was suggested as a possible solution by @AndyAyersMS a few years ago when we started discussing this problem.

Implementation

The "randomization" has been implemented as a new, optional feature in BenchmarkDotNet in the following way:

• allocate a random-size stack memory at the beginning of every iteration (idea comes from @AndyAyersMS, code) and keep it alive for the iteration period
• between every iteration:
  • call the [GlobalCleanup] method that should be disposing of all resources (code)
  • allocate a random-size small byte array (Gen 0 object) (idea comes from @jkotas, code)
  • allocate a random-size large byte array (LOH object) (idea comes from @AndyAyersMS, code)
  • call the [GlobalSetup] method that should be allocating all memory (while both arrays are kept alive) (code)

All the changes that have been required to introduce this feature in BenchmarkDotNet can be seen here

To make the existing benchmarks work with the new feature, the following changes were required:

• implement missing [GlobalCleanup] methods: #1586. So far [GlobalSetup] was called only once and since every benchmark was running in a dedicated process and OS was cleaning all resources after process exit, the lack of proper resources cleanup was not a problem.
• move fields initialization from constructors to [GlobalSetup] methods to make it possible to reallocate them: #1587
• split big setups into smaller, dedicated ones to allocate as little as possible to increase the chance for having randomized input (by allocating only what we need for the given benchmark right after the random-size arrays): #1587
• fix some bugs that occurred when [GlobalSetup] methods were invoked more than once: #1587

Methodology

The following methodology was used:

• run existing benchmarks with randomization disabled (default setting) using .NET 5 RTM.
• run existing benchmarks with randomization enabled using .NET 5 RTM and the same hardware and OS.
• use a modified version of ResultsComparer that would be searching for benchmarks that meet the following criteria:
  • the performance has changed (improved or regressed). I've used a threshold of 5% and a 1 ns noise filter.
  • the distribution for randomized results is multimodal (this is the expected randomization effect)
• re-run the benchmarks reported by ResultsComparer and filter out the benchmarks that are simply unstable

Observations

Managed memory buffers

The Randomization has a very strong effect on benchmarks that use continuous managed memory buffers like arrays or spans for input and perform some simple operations on them. Example:

https://github.com/dotnet/performance/blob/8aed638c9ee65c034fe0cca4ea2bdc3a68d2a6b5/src/benchmarks/micro/libraries/System.Memory/Span.cs#L74-L75

With Randomization disabled we are always getting a flat distribution:

-------------------- Histogram --------------------
[19.319 ns ; 19.739 ns) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
---------------------------------------------------

With Randomization enabled, the distribution becomes multimodal:

-------------------- Histogram --------------------
[17.531 ns ; 19.318 ns) | @@@@@@@@@
[19.318 ns ; 20.833 ns) | @@@@@@@@@@@@@@@@@@@@@@@@@@@
[20.833 ns ; 22.428 ns) | @
[22.428 ns ; 23.943 ns) |
[23.943 ns ; 25.662 ns) |
[25.662 ns ; 27.177 ns) | @@@
---------------------------------------------------

Which better represents what we can see in the historical data:

The reporting system is currently using the average of all iterations for a given run to represent it as a single point on the chart. If we switch to Median, we should be able to flatten the charts. We can't display every iteration result as a separate point because we run every benchmark multiple times per day (each run gives us 15-20 iteration results) and existing charting libraries can't handle this amount of data (showing few hundreds data points per day for a period of a year (current .NET release cycle)).

The more inputs are used, the bigger the difference. The best example is copying one array to another:

https://github.com/dotnet/performance/blob/2bc578a6b60bf794d58669e94cc8bcd30cbbf5a8/src/benchmarks/micro/libraries/System.Collections/CopyTo.cs#L35-L36

Randomization disabled:

-------------------- Histogram --------------------
[87.431 ns ; 89.140 ns) | @@@@@@@@@@@@@
---------------------------------------------------

-------------------- Histogram --------------------
[ 79.009 ns ; 183.239 ns) | @@@@@@@@@@
[183.239 ns ; 287.047 ns) | @
[287.047 ns ; 391.277 ns) | @@@@@@@@
[391.277 ns ; 501.821 ns) | @
---------------------------------------------------

We have few modes here: none|all arrays aligned and source|desitnation only aligned.

Stack memory

Allocating random-size stack memory affects CPU bound benchmarks that don't use any managed memory as an input. An example:

https://github.com/dotnet/performance/blob/2bc578a6b60bf794d58669e94cc8bcd30cbbf5a8/src/benchmarks/micro/libraries/System.Numerics.Vectors/Perf_Matrix4x4.cs#L105-L106

Before this change, a single run with BenchmarkDotNet would be always producing a flat distribution:

-------------------- Histogram --------------------
[17.139 ns ; 17.937 ns) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
---------------------------------------------------

But with randomization enabled, the distribution is not flat anymore:

-------------------- Histogram --------------------
[17.313 ns ; 17.859 ns) | @@@@@@@@@@@@@@@@@@@@@@
[17.859 ns ; 18.315 ns) | @@@@@@@@@@
[18.315 ns ; 19.027 ns) | @@@
---------------------------------------------------

And is much closer to what we can see in the historical data:

The benchmark seems to be stable from a high-level perspective:

But has a 0.5-1 ns variance when we zoom-in:

Not a Silver Bullet

There are some unstable benchmarks like System.Collections.CreateAddAndClear.Stack where randomizing memory does not help. We still have a flat distribution, but the reported time slightly changes (most probably due to not having a perfectly warmed up memory or just being dependent on code alignment):

Before:

-------------------- Histogram --------------------
[1.846 us ; 1.960 us) | @@@@@@@@@@@@@@@
---------------------------------------------------

After:

-------------------- Histogram --------------------
[2.087 us ; 2.204 us) | @@@@@@@@@@@@@@@
---------------------------------------------------

BenchmarkDotNet

For a given distribution:

-------------------- Histogram --------------------
[ 79.009 ns ; 183.239 ns) | @@@@@@@@@@
[183.239 ns ; 287.047 ns) | @
[287.047 ns ; 391.277 ns) | @@@@@@@@
[391.277 ns ; 501.821 ns) | @
---------------------------------------------------

The 391.277 ns ; 501.821 ns bucket would be typically recognized by BenchmarkDotNet as an upper outlier and removed. So for benchmarks with randomization enabled, the outlier removal is disabled.

The performance repo is configured to run up to 20 iterations. To get a full picture, we need to run more iterations for benchmarks with randomization enabled.

Moreover, the default BenchmarkDotNet heuristic stops the benchmarking when the results are stable or it has executed 100 iterations. This is why this setting should not be enabled in BenchmarkDotNet by default.

Summary

Randomization is not a silver bullet that solves all our problems and it should not be enabled by default.

It can help a lot with unstable benchmarks that use continuous managed memory buffers like arrays or spans for input and perform some simple operations on them. Examples:

• System.Collections.CopyTo<*>.Array|Span|List
• System.Memory.Span<*>.IndexOfAnyThreeValues|SequenceEqual|StartsWith|EndsWith|LastIndexOfValue
• System.Collections.Contains<*>.Array|Span|List
• System.Memory.SequenceReader.TryReadTo
• System.IO.Tests.Perf_FileStream.ReadByte

So far CPU-bound benchmarks with a 0-1 ns variance between runs were not unstable enough to cause a problem to the auto-filing bot and I believe that we should not enable this feature for them until it becomes a problem.

Proposed order of actions

@DrewScoggins @AndyAyersMS @kunalspathak @tannergooding if you agree with my findings then these are the steps that need to be taken to enable the randomization: (I can do all of them except the last one)

• [x] merge the PRs that adds missing [GlobalCleanups] #1586
• [x] review and merge the PRs that simplifies existing [GlobalSetup] and moves initialization logic from constructors and field initializers to the setups: #1587
• [x] review and merge the PR that adds Randomization as a feature to BenchmarkDotNet: https://github.com/dotnet/BenchmarkDotNet/pull/1587
• [x] refresh, review and merge the PR that allows for applying BDN attributes per method (not just per class): https://github.com/dotnet/BenchmarkDotNet/pull/1097
• [ ] enable Randomization for Array and Span based benchmarks (only for those where it helps), update BDN version
• [ ] change the Reporting System to use Medians instead of Averages

cc @andreyakinshin @billwert @Lxiamail @jeffhandley @danmosemsft

[jkotas]

change the Reporting System to use Medians instead of Averages

I do not follow the reasoning behind this. Does this carry a risk of missing regressions for the situations in the upper half of the spectrum?

[adamsitnik]

Does this carry a risk of missing regressions for the situations in the upper half of the spectrum?

Using Medians would only help to flatten the charts (visualization).

When it comes to missing regressions, then it depends on how the auto-filing bot is implemented. If it takes only medians under consideration, then as you said it might miss regressions for less common cases. The same is true for averages.

In a perfect world, the bot should take all the values under consideration. In the past @DrewScoggins mentioned that it would take too much time to fetch all the numbers from the database.

@DrewScoggins do you believe that we could optimize the DB queries and use full data? How it would affect the time it takes to detect regressions? Like from 5 minutes to half an hour or more like from an hour to ten hours? Maybe we could run it just once per week?

[kunalspathak]

This is great study and we should definitely go ahead with memory randomization. During my several investigations, (the most recent in https://github.com/dotnet/runtime/issues/44457#issuecomment-727063983) I have seen that the disassembly remains unchanged but the performance fluctuates and could happen because of memory alignment.

If others agree to the memory randomization, can you list down all the benchmarks (exact benchmark names) that improved, regressed or stabilized because of this change? That list will act as a guide for us whenever we see any improvements/regressions in benchmarks to see if they are impacted by memory alignment. I am not sure how you ran the benchmarks, but I would try it on the perf lab hardware (all available OS/arch) and use ResultComparer on that result to see how memory alignment impacts benchmarks on various configuration. It will be good to document that too so we can refer it in future. Lastly, this might reset the baseline of several benchmarks and our automated bug filing mechanism (@DrewScoggins ) should take that in account instead of flagging them.

[DrewScoggins]

In a perfect world, the bot should take all the values under consideration. In the past @DrewScoggins mentioned that it would take too much time to fetch all the numbers from the database.

@DrewScoggins do you believe that we could optimize the DB queries and use full data? How it would affect the time it takes to detect regressions? Like from 5 minutes to half an hour or more like from an hour to ten hours? Maybe we could run it just once per week?

The analysis engine really has two parts, doing a comparison between two builds to decide if we have a regression, and building a trend line for particular tests.

On the trend generation side I am not sure on exactly how much time downloading the full results would add to the analysis. I do know that we will have to pull down about 8x as much data as we do for using the summarized data row. Overall, I think the better approach would be to add median as something that we calculate when we insert the summarized data row. We could then use the median when appropriate and use average everywhere else when building our trend graphs.

We could however, switch over to using the full test data for the comparison between the two builds. This is actually five builds as we also look at the three builds before the comparison point to provide extra confidence, but that does not materially change much. Doing this would not only allow for average or median analysis, but also more advanced tests like Mann-Whitney. We would also not have to worry about the performance, as these five builds represent only about 1/8th of the total data that we pull down.

My recommendation is that we start adding median and a part of the summarized results data row, and make sure we have some way to mark a test as needing to use median instead of average as the comparison metric. This will have the smallest impact while getting us where we need to go.

[AndyAyersMS]

We expect memory randomization to produce broader/ more complex distributions on the tests where it matters, so summarizing those distributions by one number and then inferencing based on does seem problematic. At a minimum we could also look at standard deviation or IQR or some other non-parametric measure of breadth -- that would be two numbers per run instead of N.

[AndyAyersMS]

Just to echo what @jkotas said above...

As a thought experiment, imagine we have a method that behaves differently depending on alignment (say it has a top-level alignment dependent branch that chooses approach A or approach B). Say A is chosen with higher likelihood, and is faster than B. Will we be able to spot regressions in B?