Live data from Hacker News

Are your memory-bound benchmarking timings normally distributed?

lemire.me

31–40 of 50 posts

Re: Are your memory-bound benchmarking timings normally distributed?

#31
post #8
post #5

I'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 tri…

I 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 work…

> we just put 16MB of working memory on each chip.

Just? The chips we've got have between 32kb and 64kb -- maybe 128kb in some really big chips, and it's been that way for forty years! Everything else has to swap or cache through messaging layers (L2, L3) with real latency because we can't "just" put a bunch of memory on a chip.

I mean, I like thinking about star-trek computers too, but "just" isn't the word I would use for something like this... What would you possibly do with so much memory in a circuit?

> 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.

People rewrote almost everything in Java. And are doing it again with Rust. Programmers want to program, and if they can't come up with anything else to do, they'll just rewrite what someone else did. I don't think you should valuate existing C code the way its owners do, but by how their competition will valuate it; If someone can use FutureLang to outperform their business-competition who uses C, this problem will solve itself.

Re: Are your memory-bound benchmarking timings normally distributed?

#32

What'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.

That’s only true though if you don’t have a time-out at some point.

Re: Are your memory-bound benchmarking timings normally distributed?

#34
post #33

By 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.

Caches and other hidden state complicate matters significantly.

Re: Are your memory-bound benchmarking timings normally distributed?

#35
From 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.

Re: Are your memory-bound benchmarking timings normally distributed?

#36
post #8
post #5

I'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 tri…

I 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 work…

Reminds me of Movidius Myriad [0] or NEC IMAPCAR [1]. Other comments also mention Cell.

Programmung those is so different that you need to dressing specifically for the chip and unless there is no great consolidation, they stay niche.

[0] https://www.tomshardware.com/news/movidiud-myriad2-vpu-visio...

[1] https://www.nec.com/en/global/techrep/journal/g06/n05/pdf/t0...

Re: Are your memory-bound benchmarking timings normally distributed?

#38

You 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.

Gamma 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.

I too am an engineer that doesn't understand why/when you would use a gamma distribution. Could you point me in the right direction?

Re: Are your memory-bound benchmarking timings normally distributed?

#39

Earlier quoted context omitted.

Gamma 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.

I too am an engineer that doesn't understand why/when you would use a gamma distribution. Could you point me in the right direction?

There'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_...

Re: Are your memory-bound benchmarking timings normally distributed?

#40
post #18

Earlier quoted context omitted.

Hum... The hardware isn't actually there. It has the capabilities the GP wants, but it doesn't export them in a way you could tune into that NUMA machine.

You can run any process on any core and allocate local memory to that core. What is missing? Sure you can't hide metadata in the unused bits of a pointer, but that didn't seem particularly critical for making good use of a NUMA machine.

> What is missing?

Fast memory, addressable by the core.

The one that is there, but can only used by accessing the slow memory.

Post reply on HN