Gallery of Processor Cache Effects | Hacker News Reader

Gallery of Processor Cache Effects

igoro.com

150 pointsKirinDave36 comments

When I worked at LSI Logic, we had a dual core processor that didn't have any cache consistency at all between cores. You actually had to pad all memory allocations to a cache line so that the two cores didn't interfere with each other.

Unfortunately, we also let our customers develop their own code. One of our best customers (Motorola) starting having problems with one of their projects. Small changes in their code would cause all kinds of bizarre crashes.

I was asked to help out and after reviewing their code, I realized that nobody had told them about the cache coherency issue. After making a few changes (just moving .bss and .data variables into cache line protected malloc's), all the problems disappeared.

The funny part was when their engineering manager found out. He calls me on the phone and starts to chew me out. He was furious, so I put him on speaker and called my managers into the lab. We stood around and just let him rant for a few minutes until he ran out of steam. A legendary episode that we chuckled about many times thereafter.

The PortalPlayer 5020 in my iPod mini was designed similarly. Two ARM7TDMIs with non coherent caches. I tried to hack up iPodLinux to support both cores in a general way, but never really got it working well. The official iPod software used one for the OS and dedicated the other to codecs IIRC.

Same situation on the LSI Logic (actually, it came from C-Cube Microsystems) processor. One SPARC core running VxWorks and applications and the other SPARC core running bare metal and MPEG-2 codecs.

The first version of the chip was introduced at CES 2001. Pretty early for a multi-core CPU. Only 150 MHz clock rate though.

>"You actually had to pad all memory allocations to a cache line so that the two cores didn't interfere with each other."

Can you elaborate? Specifically ow did you "pad all memory allocations to a cache line" and how exactly did that prevent interference?

>"After making a few changes (just moving .bss and .data variables into cache line protected malloc's), all the problems disappeared."

What is a "cache line protected malloc" exactly?

Just an aligned malloc. The cache line size was eight 64-bit words, so aligning on 64 byte boundaries did the trick.

The failure mechanism is when one processor writes a memory variable, the entire cache line is written. If the variable is within 64 bytes of a variable on the other processor (and in the same cache line), the variable on the other processor gets (possibly) overwritten.

I forget exactly how the aligned malloc was coded. This was 18 years ago and gcc 2.7.2 on SPARC. For the application programmers, we just had an overloaded new operator that was aligned.

I'm envisioning how this played out...

First LSI engineer: "He seems pretty upset."

Second LSI engineer: "Yeah."

First LSI engineer: "Think we should do anything?"

Second LSI engineer: "Meh, he'll get over it."

First LSI engineer: "Still, maybe we should throw him a bone."

Second LSI engineer: "<sigh> Fine. I'll add an overloaded new operator after I finish my beer."

... something like that? :)

We had figured out the issue years before that episode. We did write him a nice application note / errata describing the issue.

They were just declaring static/global variables that they didn't know were forbidden.

2014: https://news.ycombinator.com/item?id=8778990

2010: https://news.ycombinator.com/item?id=1094797

(Those are for people who like to look at old discussions. Reposts are ok after about a year on HN: https://news.ycombinator.com/newsfaq.html.)

Nicely written post that summarizes the major pain points wrt cache hierarchies.

The canonical reference for diving deeper is "What Every Programmer Should Know About Memory" [1].

[1] https://people.freebsd.org/~lstewart/articles/cpumemory.pdf

I was sort of surprised in example 4 that the compiler couldn't optimize {a[0]++; a[0]++;} to {a[0]+=2;}, given that the allocation was right there in the same function as the usage.

EDIT: Should have kept reading, other people apparently had this same comment and it was addressed. This was for C# rather than C++ so no wonder my intuition was off.

It was addressed that it didn't optimize it this way, but no one has clarified why it didn't. I'm curious!

A Just-in-time compiler has to find a balance between compilation time (which slows down your program or makes it slower to start) and optimization quality. So a lot of optimizations that are OK in C++ where you have lots of time because of AOT compilation are not feasible for a JIT.

Things could be different by now, though, with RyuJIT and tiered compilation. That article is quite old (although processors still work the same, just with larger caches).

Constant propagation is pretty cheap though and is a common JIT compiler technique.

Constant propagation yes. But knowing that that memory location wasn't volatile, say, is a lot harder and I don't blame a JIT for not being sure.

C# very easily knows if a variable like that is volatile.

Mike Acton's CppCon 2014 talk on this subject is still the best I've seen:

https://www.youtube.com/watch?v=rX0ItVEVjHc

A collection of Acton's videos and documents on Data-Oriented Design (plus other authors on the same topic): https://github.com/dbartolini/data-oriented-design

This is a really interesting explanation of why some code might have a longer or shorter runtime than you'd expect. And, as a bonus, it's not titled "What every programmer should know about ..."

https://hn.algolia.com/?query=what%20every%20programmer%20sh...

For those of us wishing to play along at home, what's the easy way to get a disassembly of a single function with C# (Mono or DotNetCore)? The last one would be fun to figure out.

This was from 9 years ago. Did anybody find an explanation of the last example?

I always found it slightly frightening when an app depends on cache characteristics for max performance. It has to be rather isolated on a machine to be able to expect it to be used.

I've always found it annoying that the cache offers drastic speedups for doing things 'wrong' in the sense an algorithm is faster in cache than the 'correct' way until it scales out of the cache.

It's only 'wrong' in the sense that physics limits the speed of DRAM memory access. If you consider engineering to be the art of designing systems within constraints then you definitely should be paying attention to cache coherency and linear access patterns.

Feel free to ignore 50x performance/battery gains at your own peril.

By 'wrong' I mean you have algorithm A which is logically less work than algorithm B, but algorithm B runs much faster if you are in cache, but the moment your workload doesn't fit in the cache B is running much slower than A. If you don't hit that line great otherwise you have issues.

> logically less work

Is it? If you're excluding memory access then I would argue it's not a proper representation of the work performed. You can have an algorithm that's mathematically ideal but from an engineering perspective is the wrong choice.

Also your workload doesn't always define if you fit in/out of cache. Linear access algorithms will scale on any architecture/cache size as the pre-fetcher will step in and bridge your DRAM/network access time. It's essentially like an infinite cache.

Realtime Collision Detection[1] (which is basically datastructures for 3D space) does a fantastic job of picking algorithms that are both correct and cache friendly. Data Oriented Design, SoA/AoS and the like are all techniques that I think any Software Engineer worth their salt should be familiar with.

[1] http://realtimecollisiondetection.net/books/rtcd/

There is a whole school of programming by now around not closing ones eyes to the actual hardware engineering - of course fought against by the church of moores law, who hoped to finally abstract away all those details into virtual machines. And they wouldt have got away with it too, if it were not for those plateauing speed gains.

https://en.wikipedia.org/wiki/Data-oriented_design

Seems like you might be trying to say that these optimizations are fragile, in the sense that small changes environment or workload can invalidate them. Which seems like a fair criticism, although maybe not reason to ignore them.

That can happen, but doesn't necessarily have to:

https://en.wikipedia.org/wiki/Cache-oblivious_algorithm

You can have both. Your software can have a switch to use A if the dataset is larger than N, otherwise use B. N can be determined by a heuristic, by system parameters if available or hardcoded.

The catch being that now your bugs will be "fun" to pin down.

I don't think it'll be that much more complicated, if it's well documented and you write tests for it, it's fine.

Well, you can have all the fancy algorithms you want but currently software performance is dominated by memory access patterns. Often the best solution is an algorithm with suboptimal complexity but superior memory access patterns. See for example sorting algorithm performance. Nobody operating at scale can afford to ignore cache effects.

Regarding your first comment, see https://danluu.com/intel-cat/

Thanks, that is interesting. They are able to pin the processes to certain cores to keep it in certain cache blocks to avoid exactly what I worry about.

They avoid my second concern by having lots of cache memory even though they technically need a small fraction of it to maintain performance. There is a trade off, so probably still lots of room for improvement if they can get finer cache control.

My fear in those scenarios is you have profiled your workload, your cluster is at 75%+ utilization, and something non standard hits and triggers a workload profile that removes any cache performance benefits, sinking your hole cluster.

That would imply that accommodations for using the cache are data dependant which would be orthogonal to building in mechanics for a specifically sized cache.

Also this is about CPU caches so it doesn't have anything to do with cluster utilization. A cluster will see the CPU as being ultilized at 100% regardless of how many cache misses there are.

If you have a cluster at 75% utilization because the workload is fully in cache and something happens that does not allow the workload to be processed in cache and your processing speed slows by half then your cluster would immediately require twice the resources to meet the workflow demand. An attacker for example could figure out a rarely used access pattern that trashes the caches and causes a severe backup.

Once again, that would imply that someone is both hardcoding a cache size and yet somehow making their use of the cache data dependant. I'm not sure what specifically you are trying to say here. It sounds like you have some sort of fear of edge cases in general, regardless of anything that has to do with caches.

I think that if you consider the cost of accessing a random piece of data from a pool of size n to have an asymptotic cost of sqrt(n) then you can have a pretty good analysis, mathematically, while still being congruent to the world we live in.

Reply on news.ycombinator.com