5 ms·

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 t

by edoo 8y ago

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.

shereadsthenews 8y ago
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/ https://danluu.com/intel-cat/
- edoo 8y ago
  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.
  - BubRoss 8y ago
    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.
    - edoo 8y ago
      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.
      - BubRoss 8y ago
        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.
vvanders 8y ago
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.
- edoo 8y ago
  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.
  - mrec 8y ago
    That can happen, but doesn't necessarily have to: https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
  - vvanders 8y ago
    > 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/ http://realtimecollisiondetection.net/books/rtcd/
    - LifeLiverTransp 8y ago
      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 https://en.wikipedia.org/wiki/Data-oriented_design
Symmetry 8y ago
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.

by edoo 8y ago

shereadsthenews 8y ago

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/ https://danluu.com/intel-cat/

edoo 8y ago
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.
- BubRoss 8y ago
  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.
  - edoo 8y ago
    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.
    - BubRoss 8y ago
      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.

vvanders 8y ago

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.

edoo 8y ago
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.
- mrec 8y ago
  That can happen, but doesn't necessarily have to: https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
- vvanders 8y ago
  > 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/ http://realtimecollisiondetection.net/books/rtcd/
  - LifeLiverTransp 8y ago
    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 https://en.wikipedia.org/wiki/Data-oriented_design

Symmetry 8y ago

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.