Hacker News Reader

Comment by edoo | Hacker News Reader

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.

View on HN

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.

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

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

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

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