Are your memory-bound benchmarking timings usually distributed? – Daniel Lemire’s weblog
When optimizing software program, we routinely measure the time that takes a given operate or activity. The everyday assumption is that we get a standard distribution, and so we should always due to this fact report the common time.
I consider that this hidden assumption (normality) is often violated in software program benchmarks. I just lately gave a chat on exact and correct benchmarking (video, slides) at a “Benchmarking within the Information Middle” workshop the place I made this level intimately.
Why ought to it matter? In case you have regular distributions, you may mathematically improve the accuracy of the measure by taking extra samples. Your error ought to go down because the sq. root of the variety of measures.
When you ever tried to extend the variety of samples within the hope of getting a extra correct consequence, you might have been severely dissatisfied. And that’s as a result of the timings typically extra intently ressemble a log regular distribution:
A log regular distribution is asymmetrical, you’ve imply that’s comparatively shut the minimal, and an extended tail… as you are taking increasingly more samples, chances are you’ll discover increasingly more giant values.
You’ll be able to typically present that you simply do not need a standard distribution since you discover 4-sigma, 5-sigma and even 13-sigma occasions: you measure values which are far above the common in comparison with your estimated normal deviation. It isn’t attainable, in a standard distribution, to be a number of instances the usual deviation away from the imply. Nonetheless, it occurs way more simply with a log regular.
In fact, actual information is messy. I’m not claiming that your timings exactly comply with a log regular distribution. It’s merely a mannequin. However, it means that reporting the common and the usual error is insufficient. I prefer to measure the minimal and the common. You’ll be able to then use the space between the common and the minimal as an easy-to-measure error metric: if the common is much from the minimal, then your real-world efficiency might differ drastically from the minimal.
The minimal is simpler to measure precisely than the common. I routinely obtain a precision of 1% or higher in observe. That’s, if I rerun the identical benchmark one other day on the identical machine, I may be virtually sure that the consequence received’t range by way more than 1%. The common is barely tougher to nail down. You’ll be able to confirm that it’s so with a mannequin: if you happen to generate log-normally distributed samples, you can find it simpler to find out the minimal than the common with excessive accuracy.
For my discuss, I used a compute-bound routine: the efficiency of my operate was not sure by the pace of the RAM, by the community or by the disk. I took information that was in CPU cache and I generated extra information in CPU cache. For all these issues, I discover that timings typically ressemble a log regular.
What about different varieties of duties? What about memory-bound duties?
I took a memory benchmark that I like to use. It consists of a big array spanning tons of of megabytes, and the software program should leap from location to location in it, being incapable of predicting the subsequent leap earlier than finishing the learn. It’s typically known as a “pointer chasing” routine. I can interleave the pointer-chasing routines in order that I’ve a number of masses in flight at every time: I name this the variety of lanes. The extra lanes I’ve, the extra “bandwidth restricted” I grow to be, the less the lanes, the extra “reminiscence latency” I grow to be. I’m by no means compute sure in these assessments, which means that the variety of directions retired per cycle is at all times low.
For every fastened variety of lanes, I run the benchmark 30 instances on an Amazon Intel c6i node working Ubuntu 22. The time elapsed range between over 3 seconds per run (for one lane) to about 1/6 s (for 30 lanes). I then estimate the usual deviation, I compute the imply, the utmost and the minimal. I then compute the underside sigma because the hole (in variety of normal deviations) between the minimal and the common, after which the hole between the common and the utmost. If the distribution is regular, I ought to have roughly the identical variety of sigmas on both facet (min and max) and I shouldn’t exceed 3 sigmas. I discover that one facet (the utmost), simply exceed 3 sigmas, so it isn’t a standard distribution. It is usually clearly not symmetrical.
But my measures are comparatively exact. The relative distance between the minimal and the imply, I get a tiny margin, typically below 1%.
It’s fascinating that the extra lanes I’ve, the extra correct the outcomes: intuitively, this isn’t solely stunning because it breaks down the information dependency and one unhealthy step has much less influence on the entire processing.
Thus, for a variety of performance-related timings, you shouldn’t assume that you’ve got a standard distribution with out checking first! Computing the space between the utmost and the imply divided by the usual deviation is a helpful indicator. I personally discover {that a} log regular distribution is a greater mannequin for my timings.