4 ms·

> Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant. That's a theore

> Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant. That's a theoretical problem that might happen sometime in the future. Meanwhile the author's approach brings a 10x speedup in real-world deployments? Why the snark? Theoretical work is vital to understand some problems but practical applications is where the real problem expresses itself, and where real-world constraints manifest hemselves.

tempguy9999 7y ago
> Why the snark? Because author didn't discover anything stunningly novel, not even slightly, but bragged rather big. Read the comments, the full list, to see many others saying the same thing. His 'discovery' isn't.
- rumanator 7y ago
  > Because author didn't discover anything stunningly novel, not even slightly, but bragged rather big. I honestly don't understand your complaint. Did the author discovered a novel data structure? No. But did the author discovered that a data structure performs far better in the real world than theoretically optimal data structures that fail to take into account real-world constraints? Why, yes. > Read the comments, the full list, to see many others saying the same thing. His 'discovery' isn't. Sounds like the nay-sayers are entirely oblivious to real-world problems. That's one of the main complaints regarding the ivory tower mentality and how some very clever people fail to fulfill their potential by focusing on theoretical frameworks that have no relation with reality. Some algorithms may present the lowest theoretical time complexity within fictitious theoretical frameworks, where all memory regions are accessible in constant time and where all ops take the same time to perform, but that is far from what we have in reality. In reality cache misses penalize performance and cache locality is fundamental to reduce any performance penalty. It means nothing if a theoretical optimal algorithm that is only optimal under unrealistic assumptions is proven to be optimal in an unrealistic scenario if another algorithm is found to perform far better on the real-world.
  - tempguy9999 7y ago
    > But did the author discovered that a data structure performs far better in the real world than theoretically optimal data structures that fail to take into account real-world constraints? Why, yes. Which has been known about since forever. It's not a new discovery. (Edit: by 'since forever' that's the 70's and quite possibly earlier). It's not even remotely surprising because anyone who know anything about memory architectures will appreciate it. Please read the full comments in the original ACM article. Or at least a sample. Also read https://www.goodreads.com/book/show/12485556-what-every-programmer-should-know-about-memory https://www.goodreads.com/book/show/12485556-what-every-prog... (which can also be found online) which explains very clearly why this is predictable.
    - rumanator 7y ago
      > Please read the full comments in the original ACM article. Or at least a sample. I've read the comments and I'm a bit surprised you suggest it because a) there are far more supportive comments and praises than criticism, b) the complains in general are entirely oblivious to the content and are more outraged by the perceived tone than the actual finding regarding real-world performance. Take for instance the absurd and entirely oblivious jab asking how the proposed algorithm performs on a Turing machine (?!) to, from there, criticising the author for pointing a major flaw in CS education. As the author stated in the comments section: > The response to my article broadly falls in two camps, which can be paraphrased as: Physisists arguing that bridges and buildings is simply not their job vs. people who try to build bridges and buildings, asking "whos job is it then ?" >The obvious answer would be "The Software Engineers". >Maybe we ought to educate some of those...
      - ThrowawayR2 7y ago
        > ...for pointing a major flaw in CS education. L2 cache was available in consumer hardware as far back as the '486 in the early '90s; CS students were being taught about the effects of having a memory hierarchy as far back as then. PHK wasn't pointing out a flaw in CS education, he was merely demonstrating how out of touch he was.
ultrablack 7y ago
Its not a bad idea. I did it myself in 98, down to making data fit in the L3 cache. Memory optimisation isn’t really new.
- rumanator 7y ago
  The concept of cache misses and the importance of cache locality is nothing new. That's HPC 101. Demonstrating that in the real world a specific data structure performs far better than the theoretically optimal data structure is not. That's novel, unless you can find any prior work that presents the exact same findings. That's one of the main problems with ivory tower types: claiming that a novel poem is nothing new because all the words in it were already known and even published in a few dictionaries.
- nol3cachein1998 7y ago
  I'm calling BS because there was no L3 cache in 1998, Pentium pro only had l2
  - saltcured 7y ago
    All the world was not x86. The DEC Alpha definitely had 3-level cache systems by the mid 90s, and I would not be surprised if other RISC systems did as well.

tempguy9999 7y ago

> Why the snark? Because author didn't discover anything stunningly novel, not even slightly, but bragged rather big. Read the comments, the full list, to see many others saying the same thing. His 'discovery' isn't.

rumanator 7y ago
> Because author didn't discover anything stunningly novel, not even slightly, but bragged rather big. I honestly don't understand your complaint. Did the author discovered a novel data structure? No. But did the author discovered that a data structure performs far better in the real world than theoretically optimal data structures that fail to take into account real-world constraints? Why, yes. > Read the comments, the full list, to see many others saying the same thing. His 'discovery' isn't. Sounds like the nay-sayers are entirely oblivious to real-world problems. That's one of the main complaints regarding the ivory tower mentality and how some very clever people fail to fulfill their potential by focusing on theoretical frameworks that have no relation with reality. Some algorithms may present the lowest theoretical time complexity within fictitious theoretical frameworks, where all memory regions are accessible in constant time and where all ops take the same time to perform, but that is far from what we have in reality. In reality cache misses penalize performance and cache locality is fundamental to reduce any performance penalty. It means nothing if a theoretical optimal algorithm that is only optimal under unrealistic assumptions is proven to be optimal in an unrealistic scenario if another algorithm is found to perform far better on the real-world.
- tempguy9999 7y ago
  > But did the author discovered that a data structure performs far better in the real world than theoretically optimal data structures that fail to take into account real-world constraints? Why, yes. Which has been known about since forever. It's not a new discovery. (Edit: by 'since forever' that's the 70's and quite possibly earlier). It's not even remotely surprising because anyone who know anything about memory architectures will appreciate it. Please read the full comments in the original ACM article. Or at least a sample. Also read https://www.goodreads.com/book/show/12485556-what-every-programmer-should-know-about-memory https://www.goodreads.com/book/show/12485556-what-every-prog... (which can also be found online) which explains very clearly why this is predictable.
  - rumanator 7y ago
    > Please read the full comments in the original ACM article. Or at least a sample. I've read the comments and I'm a bit surprised you suggest it because a) there are far more supportive comments and praises than criticism, b) the complains in general are entirely oblivious to the content and are more outraged by the perceived tone than the actual finding regarding real-world performance. Take for instance the absurd and entirely oblivious jab asking how the proposed algorithm performs on a Turing machine (?!) to, from there, criticising the author for pointing a major flaw in CS education. As the author stated in the comments section: > The response to my article broadly falls in two camps, which can be paraphrased as: Physisists arguing that bridges and buildings is simply not their job vs. people who try to build bridges and buildings, asking "whos job is it then ?" >The obvious answer would be "The Software Engineers". >Maybe we ought to educate some of those...
    - ThrowawayR2 7y ago
      > ...for pointing a major flaw in CS education. L2 cache was available in consumer hardware as far back as the '486 in the early '90s; CS students were being taught about the effects of having a memory hierarchy as far back as then. PHK wasn't pointing out a flaw in CS education, he was merely demonstrating how out of touch he was.

ultrablack 7y ago

Its not a bad idea. I did it myself in 98, down to making data fit in the L3 cache. Memory optimisation isn’t really new.

rumanator 7y ago
The concept of cache misses and the importance of cache locality is nothing new. That's HPC 101. Demonstrating that in the real world a specific data structure performs far better than the theoretically optimal data structure is not. That's novel, unless you can find any prior work that presents the exact same findings. That's one of the main problems with ivory tower types: claiming that a novel poem is nothing new because all the words in it were already known and even published in a few dictionaries.
nol3cachein1998 7y ago
I'm calling BS because there was no L3 cache in 1998, Pentium pro only had l2
- saltcured 7y ago
  All the world was not x86. The DEC Alpha definitely had 3-level cache systems by the mid 90s, and I would not be surprised if other RISC systems did as well.