4 ms·

How so?

zamadatix 2y ago
Even when something isn't a galactic algorithm "how well it maps to being done efficiently in real hardware with hardware sized data sizes" is more and more often the important bit over "slightly better bounds at infinity". The former is probing the edge of mathematics while the latter is probing the edges of practical construction so they rarely seem to align much anymore at these depths.
- gauge_field 2y ago
  A contributing factor is how complex/smart the current hardware is. It can have cache line size, different forms of hardware/software prefetching, different ports for different ops, memory latency, simd extensions. These leave many opportunities for algorithms to be optimized over. There is also the issue of real life scenarios not matching with asymptotic ones (due to e.g., size of input), which when coupled with previous factors, leads to even more potential optimization schemes. Obligatory reference: https://agner.org/optimize/ https://agner.org/optimize/
- naasking 2y ago
  > Even when something isn't a galactic algorithm "how well it maps to being done efficiently in real hardware with hardware sized data sizes" is more and more often the important bit over "slightly better bounds at infinity" You're just repeating the same claim. Why is that more and more often then important bit? Why is it more important now? Why are these factors not captured in complexity analysis? For instance, some complexity analysis assumes random access memory of arbitrary size, but memory above a certain size is better modelled with logarithmic access time. But this too can be captured in complexity analysis, so it's not really evidence of any divergence. And then you have cache-oblivious data structures that scale uniformly across all cache sizes, which is a product of complexity analysis. So I'm asking for what exactly is being meant with a justification of why you think this matters now more than it did before.
  - fngjdflmdflg 2y ago
    >Why you think this matters now more than it did before. More of the low hanging fruit has been picked over time. The motivation most of the original algorithms for a lot of computer science problems were practical. Once all (or most) of the optimal solutions for practical purposes have been found you are necessarily (or almost necessarily) left with only theoretical solutions.
  - rictic 2y ago
    Can the reality of hardware be modeled with complexity analysis? Yes. Is it, in practice? I haven't seen it.
  - zamadatix 2y ago
    Ignoring the galactic algorithm bit, as it's in the quote but I think you get why it would cause a divide here, just because you could try to do something in a field does not mean that's what is actually being done in a field. This is what I mean by probing the edges of mathematics vs practical construction, using the same toolset to probe isn't enough to unite those two approaches alone. Look at this paper as an example. Does its worst case Big O analysis attempt to model memory hierarchies for constructable systems or does it further diverge from any hardware considerations in favor of asymptotic behaviors towards infinities for a generic construction?
    - jeffbee 2y ago
      This is a good summary, but getting down to exactly what I meant: there aren't any hash table authors or maintainers in the business who have been stopped from trying something because of Yao's conjecture. So this result is not going to unleash a wave of practical innovation.
  - im3w1l 2y ago
    I think because computers are more complicated than they used to be. They have more features that need to be accounted for than they used to. This in turned happened because cpu frequencies stopped increasing so we had to find other ways to make things go faster. Like simd, threads, speculative execution, caches.
nijave 2y ago
A couple things immediately come to mind 1) complexity analysis ignores coefficients which can make a huge difference, especially since computers usually have bounds 2) real life may influence the likelihood of best/worst case. I think data tends to be somewhat sorted in practice so algorithms with best case on sorted data perform better
- jonstewart 2y ago
  Complexity analysis typically assumes an ideal Von Neumann machine. Systems programming embraces the discontinuities in registers, L1, L2, L3, ILP, branch prediction, and so on. (Maybe there's a good pun to be had that complexity analysis stays as far away from computer complexity as possible.) The simple model is essential, as it's the only way to create a body of proofs that will last. What's increasingly hard, though, is that there are oodles of papers, of the sort demonstrating that one algorithm or data structure is better than another, yada yada, and there's usually some benchmarking in each, and that kind of empirical demonstration is now far less than useful unless the paper's authors are good systems programmers and have given up on improvements.
  - iforgot22 2y ago
    Exactly, seems like the Von Neumann machine assumption is outdated, especially with modern supercomputers. Memory access itself isn't O(1), it's more like O(N^(1/3)) because space is a serious consideration, and that's your distance from a focal point to all other points within a 3D volume.
    - xxs 2y ago
      Yet, memory access can be limited by latency and bandwidth. Predictable access patterns (e.g. linear scan) tend to enjoy prefetech reduces the latency of accessing random parts.

How so?

Even when something isn't a galactic algorithm "how well it maps to being done efficiently in real hardware with hardware sized data sizes" is more and more often the important bit over "slightly better bounds at infinity". The former is probing the edge of mathematics while the latter is probing the edges of practical construction so they rarely seem to align much anymore at these depths.

gauge_field 2y ago
A contributing factor is how complex/smart the current hardware is. It can have cache line size, different forms of hardware/software prefetching, different ports for different ops, memory latency, simd extensions. These leave many opportunities for algorithms to be optimized over. There is also the issue of real life scenarios not matching with asymptotic ones (due to e.g., size of input), which when coupled with previous factors, leads to even more potential optimization schemes. Obligatory reference: https://agner.org/optimize/ https://agner.org/optimize/
naasking 2y ago
> Even when something isn't a galactic algorithm "how well it maps to being done efficiently in real hardware with hardware sized data sizes" is more and more often the important bit over "slightly better bounds at infinity" You're just repeating the same claim. Why is that more and more often then important bit? Why is it more important now? Why are these factors not captured in complexity analysis? For instance, some complexity analysis assumes random access memory of arbitrary size, but memory above a certain size is better modelled with logarithmic access time. But this too can be captured in complexity analysis, so it's not really evidence of any divergence. And then you have cache-oblivious data structures that scale uniformly across all cache sizes, which is a product of complexity analysis. So I'm asking for what exactly is being meant with a justification of why you think this matters now more than it did before.
- fngjdflmdflg 2y ago
  >Why you think this matters now more than it did before. More of the low hanging fruit has been picked over time. The motivation most of the original algorithms for a lot of computer science problems were practical. Once all (or most) of the optimal solutions for practical purposes have been found you are necessarily (or almost necessarily) left with only theoretical solutions.
- rictic 2y ago
  Can the reality of hardware be modeled with complexity analysis? Yes. Is it, in practice? I haven't seen it.
- zamadatix 2y ago
  Ignoring the galactic algorithm bit, as it's in the quote but I think you get why it would cause a divide here, just because you could try to do something in a field does not mean that's what is actually being done in a field. This is what I mean by probing the edges of mathematics vs practical construction, using the same toolset to probe isn't enough to unite those two approaches alone. Look at this paper as an example. Does its worst case Big O analysis attempt to model memory hierarchies for constructable systems or does it further diverge from any hardware considerations in favor of asymptotic behaviors towards infinities for a generic construction?
  - jeffbee 2y ago
    This is a good summary, but getting down to exactly what I meant: there aren't any hash table authors or maintainers in the business who have been stopped from trying something because of Yao's conjecture. So this result is not going to unleash a wave of practical innovation.
- im3w1l 2y ago
  I think because computers are more complicated than they used to be. They have more features that need to be accounted for than they used to. This in turned happened because cpu frequencies stopped increasing so we had to find other ways to make things go faster. Like simd, threads, speculative execution, caches.

nijave 2y ago

A couple things immediately come to mind 1) complexity analysis ignores coefficients which can make a huge difference, especially since computers usually have bounds 2) real life may influence the likelihood of best/worst case. I think data tends to be somewhat sorted in practice so algorithms with best case on sorted data perform better

jonstewart 2y ago
Complexity analysis typically assumes an ideal Von Neumann machine. Systems programming embraces the discontinuities in registers, L1, L2, L3, ILP, branch prediction, and so on. (Maybe there's a good pun to be had that complexity analysis stays as far away from computer complexity as possible.) The simple model is essential, as it's the only way to create a body of proofs that will last. What's increasingly hard, though, is that there are oodles of papers, of the sort demonstrating that one algorithm or data structure is better than another, yada yada, and there's usually some benchmarking in each, and that kind of empirical demonstration is now far less than useful unless the paper's authors are good systems programmers and have given up on improvements.
- iforgot22 2y ago
  Exactly, seems like the Von Neumann machine assumption is outdated, especially with modern supercomputers. Memory access itself isn't O(1), it's more like O(N^(1/3)) because space is a serious consideration, and that's your distance from a focal point to all other points within a 3D volume.
  - xxs 2y ago
    Yet, memory access can be limited by latency and bandwidth. Predictable access patterns (e.g. linear scan) tend to enjoy prefetech reduces the latency of accessing random parts.