5 ms·

> 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

> 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.
    - tempguy9999 7y ago
      I'm going to reply because you read the comments as I requested and I appreciate that. I don't have much time so this will be brief. Here's an extract from the comments which actually says it well: <<< The claim "an algorithm that has been on the books as "optimal" for 46 years, which has been analyzed in excruciating detail by geniuses like Knuth and taught in all computer science courses in the world, can be optimized to run 10 times faster" is half wrong and half obvious. [which is what people here too have been saying] Is half wrong because you cannot talk about optimizing an algorithm in terms of "time", you can optimize its asymptotic computational complexity number of steps, which you did not. Is half obvious because the fact that heaps do not match well with virtual memory, with caches and with multiple execution pipelines in modern CPUs is something known since decades. [repeating what people have said here too, that once you have caches, memory accesses become very inconsistent. The time difference between a L1 cache hit and a main mem access can be 50 times, or even more. So much more than a single order of magnitude speed difference. If it hits disk via VM, OMG IT HURTS IT HURTS... That's why an 'inferior' algorithm that uses memory in a nice way can beat a technically superior algo that doesn't] Who decided to use a pure heap in that code was not a very good programmer, you proved to be a better one [I agree here], you did not change a little bit in the history of algorithms, a good CS class may help you about the fact that you think and claim you did, there is a long way before being able to even name Knuth. >>> Analysing algorithms can't AFAIK take into account much about caches. It's just too difficult. So analysis is valuable but limited (though with very important real-world value), and you need also to account for the fact that cache/VM effects are huge. The author didn't discover anything we - or you - aren't aware of, and he presented it badly. HTH

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.
  - tempguy9999 7y ago
    I'm going to reply because you read the comments as I requested and I appreciate that. I don't have much time so this will be brief. Here's an extract from the comments which actually says it well: <<< The claim "an algorithm that has been on the books as "optimal" for 46 years, which has been analyzed in excruciating detail by geniuses like Knuth and taught in all computer science courses in the world, can be optimized to run 10 times faster" is half wrong and half obvious. [which is what people here too have been saying] Is half wrong because you cannot talk about optimizing an algorithm in terms of "time", you can optimize its asymptotic computational complexity number of steps, which you did not. Is half obvious because the fact that heaps do not match well with virtual memory, with caches and with multiple execution pipelines in modern CPUs is something known since decades. [repeating what people have said here too, that once you have caches, memory accesses become very inconsistent. The time difference between a L1 cache hit and a main mem access can be 50 times, or even more. So much more than a single order of magnitude speed difference. If it hits disk via VM, OMG IT HURTS IT HURTS... That's why an 'inferior' algorithm that uses memory in a nice way can beat a technically superior algo that doesn't] Who decided to use a pure heap in that code was not a very good programmer, you proved to be a better one [I agree here], you did not change a little bit in the history of algorithms, a good CS class may help you about the fact that you think and claim you did, there is a long way before being able to even name Knuth. >>> Analysing algorithms can't AFAIK take into account much about caches. It's just too difficult. So analysis is valuable but limited (though with very important real-world value), and you need also to account for the fact that cache/VM effects are huge. The author didn't discover anything we - or you - aren't aware of, and he presented it badly. HTH