3 ms·

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

by 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
breischl 8y ago
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.
zaarn 8y ago
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.
- yjftsjthsd-h 8y ago
  The catch being that now your bugs will be "fun" to pin down.
  - zaarn 8y ago
    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.

by edoo 8y ago

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

breischl 8y ago

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.

zaarn 8y ago

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.

yjftsjthsd-h 8y ago
The catch being that now your bugs will be "fun" to pin down.
- zaarn 8y ago
  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.