5 ms·
Are your memory-bound benchmarking timings normally distributed?
- josephcsible 4y ago> It is not possible, in a normal distribution, to be multiple times the standard deviation away from the mean. Is "possible" supposed to be "probable" there?
- b1c1jones 4y agoI've found timings in general were lognormal a long time ago. I had to routinely apply transformations to get meaningful ANOVA and DOE results.
- hackandthink 4y agoThe obvious transformation is the log. Are there other?
- b1c1jones 4y agoYes, box-cox can be used, even if the lognormal itself isn't a perfect match for the actual distribution, with the correct choice of lambda.
- ericpauley 4y agoGreat article! Statistical fallacies are rampant in performance eval, even in academic settings. When designing statistical tests for performance, the keyword you want to use here is non-parametric. I.e., a U-test is a non-parametric analog to the t-test. It just looks at the rank statistics of results instead of their value, thus eliminating dependence on the underling distribution. Another issue that pops up is sample independence. Statistical tests are often predicated on each sample being independent and identically distributed (i.i.d.), but in reality this is often not the case. For instance, running all the tests of one group and then all the tests of the other could heat the CPU and cause reduced performance in the second trial.
- zX41ZdbW 4y agoWe use non-parametric statistics for performance testing in ClickHouse[1], picked from the article "A Randomized Design Used in the Comparison of Standard and Modified Fertilizer Mixtures for Tomato Plants". [1] https://clickhouse.com/blog/testing-the-performance-of-click-house https://clickhouse.com/blog/testing-the-performance-of-click...
- kurthr 4y agoMany would do well to look at simple DOE when building experimental design. At least look at the data distributions before taking means and stdev. NIST has some nice simple descriptions and example experimental designs: https://www.itl.nist.gov/div898/handbook/pmd/pmd.htm
- kelseyfrog 4y agoI mean it's physically impossible for the generating process of positive timings to be normally distributed. The normal distribution has support x ∈ ℝ.
- sliken 4y agoI've been writing micro memory benchmarks and have been rather surprised how hard something as simple as quantifying latency and bandwidth under multicore loads can be. The memory hierarchy is getting ever more complex. Cacheline sizes, prefetch, 3 levels of cache, TLB effects, page alignments, cache associativity, etc. Also have to be careful that the compiler doesn't optimize away parts of your code. It's quite tricky to get a nice clean array size vs latency graph, doubly so when multiple cores are involved. Some of my assumptions about latency were wrong. One thing I didn't realize is it takes about half the latency to main memory to get miss through L1, L2, and L3. Also that you need to have around 2x the memory references pending to keep the memory system busy. It makes sense in retrospect, you want 16 pending memory references to keep 8 memory channels busy, otherwise a memory channel will return a cache line, and there won't be any L3 cache misses pending for that channel. Generally I like to keep a small histogram of cycle counters to make sure I'm seeing the distribution I expect, seeing an unusual distribution is key for tracking down something you didn't account for.
- hinkley 4y agoI want a viewport onto a parallel universe where we embraced NUMA more thoroughly, and instead of making processors with ever growing layers of transparent caching, we just put 16MB of working memory on each chip. Partitionable for concurrent workloads. Maybe it could never have been then, but maybe it can be now, or soon. For instance a borrow checker might be a very good way to help decide how and when to move working memory between processors and main memory. But what do you do with all of the existing C code? I think for backward compatibility you'd need to implement virtual memory at the working memory layer. It wouldn't be the fastest code, but it would work.
- sliken 4y agoWell the tools are there, and the hardware is there as well. Early AMD epycs had multiple chiplets, each with it's own memory controller. However that means that even on a single socket different chiplets would see different memory latencies and some apps/benchmarks people cared about handled it poorly. The newest AMD Epycs have a unified memory controller per socket, so all chiplets see the same memory latency. But now Intel entered the chiplet game, and now has one memory controller per chiplet again. There's plenty of support for NUMA support in the kernel and various language runtimes. Apps and OSs can pin processes to cores, allocate local ram, and migrate non-local ram to local or migrate processes to cores that are memory local. Generally the automatic stuff works reasonably, but numactl and various NUMA related calls let you override those decisions as needed.
- darksaints 4y agoYou might want to check out the gamma distribution. It is also zero-bounded just like the log normal distribution, but it was originally created to model waiting times within queue theory, which is actually an excellent parallel to the idea of measuring compute latency.
- pclmulqdq 4y agoGamma and delta distributions have been very helpful to me in performance work, as well as non-parametric statistical tests. However, when you try to tell a lot of other engineers about them, they don't really understand why a t-test and a standard deviation doesn't work.
- deleted 4y ago[deleted]
- bick_nyers 4y agoI too am an engineer that doesn't understand why/when you would use a gamma distribution. Could you point me in the right direction?
- darksaints 4y agoThere's a pretty good section on the natural occurrences and applications of the distribution in the wikipedia article. https://en.wikipedia.org/wiki/Gamma_distribution#Occurrence_and_applications https://en.wikipedia.org/wiki/Gamma_distribution#Occurrence_...
- nextaccountic 4y ago> Consider a sequence of events, with the waiting time for each event being an exponential distribution with rate β Why is the exponential distribution of waiting times a reasonable assumption in this case?
- 4y ago
- a_cardboard_box 4y agoWhat's extra fun is you can run into a distribution that doesn't have a mean. A concrete example of this: Exponential backoff where each attempt has a 1/2 probability of succeeding independently of other attempts, and you double the time between each attempt. If you try to benchmark this process, you'll find that no matter how big your sample size is you'll never get consistent results.
- legulere 4y agoThat’s only true though if you don’t have a time-out at some point.
- brucethemoose2 4y agoOne thing I discovered benching Oracle instances is that cloud performance is extremely non deterministic. Sometimes you get variance each run. Sometimes you get consistent results, but then you bench it later and the results are consistent, but totally different. Then I would run the same bench on my laptop and (with turbo disabled) ands its pretty much always consistent. I can only guess why... turbo on the host cpu? Other transient tenants competing for the same cache? Something to do with VMs? Also I am not sure if AWS has this issue.
- userbinator 4y agoYou're sharing the same hardware, with who knows how many others.
- brucethemoose2 4y agoYeah. Hence I'm saying an AWS c6i is maybe the wrong platform for benchmarks... Bare metal ia OK if you must test NUMA and such, but you are still at the mercy of turbo behavior, where you can completely control that in a local machine.
- hedora 4y agoI feel obligated to point out that, by the central limit theorem, it doesn’t matter if the timings are normally distributed. The measurements only need to be independently and identically distributed with finite variance for the estimate of the mean to be normally distributed. https://en.m.wikipedia.org/wiki/Central_limit_theorem https://en.m.wikipedia.org/wiki/Central_limit_theorem
- juunpp 4y agoI think he's saying that since the distribution follows a log-normal, the mean is harder to pin down than if it were a normal due to the higher variance. From the CLT, the variance of the mean statistic is var(X)/sqrt(N) -- the var(X) is higher and he'd expect from an assumed normal of X. The other point he makes is that the mean is not very representative in this wide log-normal scenario, and optimizing for the difference between min and mean is more relevant. My 2 cents. Also to nitpick on the article: "It is not possible, in a normal distribution, to be multiple times the standard deviation away from the mean." I guess he meant probable :)
- pygy_ 4y agoOne can also work in log space to do the stats, and report the geometric mean in linear space…
- juunpp 4y agoI think we're nitpicking too much here, but the main takeaway seems to be to not assume normals and to actually measure things. Seems pretty straightforward advice, but if you've worked anywhere, you'll know how often people content themselves with reporting averages.
- deleted 4y ago[deleted]
- _0w8t 4y agoBy definition timing benchmarks cannot be Gaussian since the time cannot be negative. For anything that has such bound on one side log-normal is a safer default choice and the usage of the normal distribution must be justified.
- zokier 4y agoCaches and other hidden state complicate matters significantly.
- graycat 4y agoFrom the OP: > The typical assumption is that we get a normal distribution, and so we should therefore report the average time. That "assumption" is asking a lot and is not justified. Actually, the main source of normal distributions is from the central limit theorem where get the distribution from adding lots of random variables. > ... therefore report the average time There are good reasons to consider averages for any distribution, "normal" or not. Of course, as in a classic paper by Halmos and Savage, there is the topic of sufficient statistics that for the normal distribution is a bit amazing. Gee, maybe the OP (original post) was thinking about sufficient statistics. But for the normal distribution, the sufficient statistics are the pair of sample average and sample standard deviation. > If you have normal distributions, you can mathematically increase the accuracy of the measure by taking more samples. This is justified by the law of large numbers, both the strong and weak versions, where need not assume a normal distribution. Texts where the law of large numbers is proven in great detail and generality are by authors Loeve, Chung, Neveu, and Breiman, among others. > It is not possible, in a normal distribution, to be multiple times the standard deviation away from the mean. Sorry, with the normal distribution, there is positive probability of samples positive or negative with finite absolute value as large as please.
- EvelynFrank 4y ago[dead]
- hackandthink 4y agoUsually I don't do any statistical tests when benchmarking and optimizing. ("If your result depends on statistics then you need a better experiment.” Oft quoted remark attributed to Rutherford.) s/experiment/optimization/ I'm happy with min, max and average. max is actually often the most important. On the other hand the point of view in this paper is interesting: "Violating the normality assumption may be the lesser of two evils" (1) If you really feel the urge to do statistical tests then do it. (I do not work in medicine or anything dangerous at all) https://link.springer.com/article/10.3758/s13428-021-01587-5 https://link.springer.com/article/10.3758/s13428-021-01587-5 (1)
- dan-robertson 4y agoThe only extra statistic in the article not on your list is standard deviation. I don’t know whom this comment is aimed at.
- hackandthink 4y agoThe comment is a bit abrupt. The article questions the normal distribution assumption for benchmark timings. It says that this assumption would be important for the "standard error of the mean": "Your error should go down as the square root of the number of measures." Standard distribution is not even necessary for this: https://en.wikipedia.org/wiki/Standard_error https://en.wikipedia.org/wiki/Standard_error However, normal distributions actually behave benignly and are a prerequisite for some statistical tests. This is where my first comment gets in, that for my benchmarking statistical tests are not necessary at all ... --- The author writes that he only measures minimum and average, but the maximum values are of course also important and worth to measure. The author's key point is that without a normal distribution, the maximum values can be highly scattered. I agree and basically it is always nice to know the distribution of the random variable.