4 ms·

That lacks a "theoretically", then? If an algorithm is optimal but still out-performed by something that is not, then the definition of "optimal" is not so help

• flohofwoe 4y ago
  A specific software implementation for a specific algorithm may be the optimal solution for one specific type of hardware, but not for others. Or: it doesn't make much sense to think about software performance without taking into account the specific hardware it needs to run on. Not sure if this is at all surprising for the more academical 'computer science types', but for low level coders it's been very obvious since pretty much forver.
  • Joker_vD 4y ago
    And then you quickly reach the conclusion that the only way to assess whether one of the implementation choices will be faster/less memory consuming/etc. in production is to implement both, deploy to production and observe the performance on the actual workloads. And the findings don't generalize, so you can't actually learn from them and build a predictive theory. And this conclusion doesn't sit well with quite a number of developers, myself included, because I personally would like to be able to do the "right" choice without the brute force of "try everything and see what works better".
• stabbles 4y ago
  In theory of cache oblivious algorithms this is modeled; for optimality the complexity should also be independent of block / cache size
  • Joker_vD 4y ago
    Yeah, and then somebody took care to actually implement and benchmark those cache-oblivious algorithms against the classic algorithms with hard-coded chunk sizes and somehow the cache-oblivious ones decisively lost in every single case [0]. [0] Kamen Yotov, Tom Roeder, Keshav Pingali, John Gunnels, and Fred Gustavson "An experimental comparison of cache-oblivious and cache-conscious programs" (2007). https://doi.org/10.1145/1248377.1248394 https://doi.org/10.1145/1248377.1248394
    • deleted 4y ago
      [deleted]