6 ms·

This article appeared in the ACM a while ago[0] and it didn't go down entirely well (some of the snarky comments I remember seem to be missing there, but some r

This article appeared in the ACM a while ago[0] and it didn't go down entirely well (some of the snarky comments I remember seem to be missing there, but some remain [see Edit below]). He just laid out the data to match the memory architecture and... that's it, really. Important but hardly a new field of computer science. [0] https://queue.acm.org/detail.cfm?id=1814327Data https://queue.acm.org/detail.cfm?id=1814327Data Edit: Here's the full comments: https://queue.acm.org/fullcomments.cfm?id=1814327 https://queue.acm.org/fullcomments.cfm?id=1814327

joe_the_user 7y ago
From comment in link: "So you reinvented the T-tree, plus some Straw Man graphs and some comments on how you're smarter than the entire CS field. Congrats?" Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant. "Cache oblivious" are one seemingly better approach since they're optimal to some degree on a wide range of cache structures - but no theoretically as fast purely in-memory structures, if they are somehow in a single memory type. "Architecture aware" trees are yet another scheme, if the program can discover the architecture. Of course, a lot of algorithms are going to GPUs and how these structures relate to GPU processing is another thing I'd be curious about.
- rumanator 7y ago
  > 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.
  - 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.
- mcguire 7y ago
  Once upon a time, Jon Bentley wrote one of his Programming Pearls (IIRC) about two string reversal algorithms; both were Big-O identical, but one finished in seconds on a sufficiently large string and he killed the other after several minutes. The punchline was that the second was exactly pessimal with regard to paged VM. This wasn't a new realization, even in 2010. The neat thing is that Bentley's string could probably be reversed in cache today.
  - loeg 7y ago
    > The neat thing is that Bentley's string could probably be reversed in cache today. Yeah, those big Zen 2 Epyc CPUs have 256 Megabytes of L3 cache. Now. That's more than like, either of my first two computers had in RAM.
    - caf 7y ago
      Zen 2 EPYC CPUs have more than a third as much storage in their register file as my first computer had RAM.
      - tempguy9999 7y ago
        Are you including the shadow registers? I suspect EPYCs actually have quite a bit more. Edit. 8 byte registers * 168 total regs = 1344 bytes, so a) you were and b) guessing it was a VIC20?
        caf 7y ago
        I was working off a figure of 180 in the Zen 2 core for 1440. It was the TRS-80 Model III with 4K, though I did acquire a VIC-20 a little later too.
- gridlockd 7y ago
  > Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant. Choosing an algorithm based on the architecture it will run and the data sets it will operate on on is the right thing to do, period. That's engineering. If you have a different architecture, you choose a different algorithm. You don't go looking for some mutant yeti super-algorithm that somehow runs well on all of them. This is just a symptom of computer science's obsession with generalization, which is rather counter-productive. > Of course, a lot of algorithms are going to GPUs and how these structures relate to GPU processing is another thing I'd be curious about. GPUs are a good example for how you need to craft an algorithm to fit the architecture, not the other way around. The way you can program GPUs today is different from five and ten years ago.
qtplatypus 7y ago
I suspect that the paper would have gone down much better if it wasn't phrased in such a snarky way. If he had just presented his results as b-heap is faster under VM pressure it would have just been accepted.
commandlinefan 7y ago
Well, his irritating writing style aside, he’s pinpointing one instance of a much larger problem in software development: the pervasive belief that “just enough” understanding is the right amount of understanding. I can’t count how many times I’ve been shot down in design meetings when I even bring up efficiency with “optimization is the root of all evil”. In most organizations, nothing matters except time to market (including user experience, efficiency and even accuracy) because “how long did it take to program” is the easiest thing for lazy managers to measure. Until organizations stop hiring people with only a vague notion of what they’re doing to deliver software, software will continue to get slower, buggier, and more unpredictable.
- pkaye 7y ago
  > "premature optimization is the root of all evil" The full quote is: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." People forget that last bit.
  - commandlinefan 7y ago
    Oh, I know... but don't try telling them that.
  - karmakaze 7y ago
    But I do like the optimization of the quote. From now on I'll quote it as "We should forget about small efficiencies 97% of the time."

joe_the_user 7y ago

From comment in link: "So you reinvented the T-tree, plus some Straw Man graphs and some comments on how you're smarter than the entire CS field. Congrats?" Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant. "Cache oblivious" are one seemingly better approach since they're optimal to some degree on a wide range of cache structures - but no theoretically as fast purely in-memory structures, if they are somehow in a single memory type. "Architecture aware" trees are yet another scheme, if the program can discover the architecture. Of course, a lot of algorithms are going to GPUs and how these structures relate to GPU processing is another thing I'd be curious about.

rumanator 7y ago
> 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.
- 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.
mcguire 7y ago
Once upon a time, Jon Bentley wrote one of his Programming Pearls (IIRC) about two string reversal algorithms; both were Big-O identical, but one finished in seconds on a sufficiently large string and he killed the other after several minutes. The punchline was that the second was exactly pessimal with regard to paged VM. This wasn't a new realization, even in 2010. The neat thing is that Bentley's string could probably be reversed in cache today.
- loeg 7y ago
  > The neat thing is that Bentley's string could probably be reversed in cache today. Yeah, those big Zen 2 Epyc CPUs have 256 Megabytes of L3 cache. Now. That's more than like, either of my first two computers had in RAM.
  - caf 7y ago
    Zen 2 EPYC CPUs have more than a third as much storage in their register file as my first computer had RAM.
    - tempguy9999 7y ago
      Are you including the shadow registers? I suspect EPYCs actually have quite a bit more. Edit. 8 byte registers * 168 total regs = 1344 bytes, so a) you were and b) guessing it was a VIC20?
      - caf 7y ago
        I was working off a figure of 180 in the Zen 2 core for 1440. It was the TRS-80 Model III with 4K, though I did acquire a VIC-20 a little later too.
gridlockd 7y ago
> Yeah, an incidentally-optimal-with-a-certain-architecture algorithm is great as long as you can count on the architecture remaining constant. Choosing an algorithm based on the architecture it will run and the data sets it will operate on on is the right thing to do, period. That's engineering. If you have a different architecture, you choose a different algorithm. You don't go looking for some mutant yeti super-algorithm that somehow runs well on all of them. This is just a symptom of computer science's obsession with generalization, which is rather counter-productive. > Of course, a lot of algorithms are going to GPUs and how these structures relate to GPU processing is another thing I'd be curious about. GPUs are a good example for how you need to craft an algorithm to fit the architecture, not the other way around. The way you can program GPUs today is different from five and ten years ago.

qtplatypus 7y ago

I suspect that the paper would have gone down much better if it wasn't phrased in such a snarky way. If he had just presented his results as b-heap is faster under VM pressure it would have just been accepted.

commandlinefan 7y ago

Well, his irritating writing style aside, he’s pinpointing one instance of a much larger problem in software development: the pervasive belief that “just enough” understanding is the right amount of understanding. I can’t count how many times I’ve been shot down in design meetings when I even bring up efficiency with “optimization is the root of all evil”. In most organizations, nothing matters except time to market (including user experience, efficiency and even accuracy) because “how long did it take to program” is the easiest thing for lazy managers to measure. Until organizations stop hiring people with only a vague notion of what they’re doing to deliver software, software will continue to get slower, buggier, and more unpredictable.

pkaye 7y ago
> "premature optimization is the root of all evil" The full quote is: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." People forget that last bit.
- commandlinefan 7y ago
  Oh, I know... but don't try telling them that.
- karmakaze 7y ago
  But I do like the optimization of the quote. From now on I'll quote it as "We should forget about small efficiencies 97% of the time."