5 ms·

The article showed nothing of the kind. All that it shows is that cache considerations matter, not that they necessarily beat algorithmic improvements. Really

The article showed nothing of the kind. All that it shows is that cache considerations matter, not that they necessarily beat algorithmic improvements. Really, nobody has ever claimed that constant factor improvements are irrelevant. They certainly do matter: twice as fast is twice as fast no matter what problem size you are talking about. The point of asymptotic analysis is how the running time of an algorithm will change as the input size changes. At scale, even a very bad implementation of Strassen's algorithm will be faster than a highly tuned implementation of the textbook algorithm. The constant factors matter in determining how large the input must be for one algorithm to outperform another. "Bjarme Stroustroup is quite fond of demonstrating the superiority of vector even when complexity would suggest list was the right approach." [citation needed] Most of the time people who claim that vectors are outperforming lists on tasks where lists are "asymptotically better" they are actually hiding some asymptotic cost. Linked lists have poor asymptotic performance for most interesting tasks, just like vectors.

mpyne 13y ago
> Bjarne Stroustroup is quite fond of demonstrating the superiority of vector even when complexity would suggest list was the right approach. [citation needed] You might want to read his Fourth Edition of The C++ Programming Language, where he basically recommends std::vector<> as the default container unless you're dealing with large amounts of data that you add into the vector without using .push_back(). In essence, std::vector<> first, switch to std::list<> if profiling shows a speedup. > Most of the time people who claim that vectors are outperforming lists on tasks where lists are "asymptotically better" they are actually hiding some asymptotic cost. Linked lists have poor asymptotic performance for most interesting tasks, just like vectors. On the contrary, perhaps the most interesting task we ever do with a list is iterate over it and vectors kick ass there. There's also hardly any indirection or special 'short list' optimization hacks required, such as used in Qt's QList to make its performance reasonable.
- betterunix 13y ago
  "On the contrary, perhaps the most interesting task we ever do with a list is iterate over it and vectors kick ass there." You need to populate a sequence before you can iterate over it, and that is where the poor asymptotic performance becomes a problem. An example that came up on HN a few weeks ago is this: insert a bunch of elements into a sequence, while maintaining some order (i.e. the sequence must be in order after each insertion). Sure, vectors outperform linked lists on this task -- but both are crushed by a priority queue (even if it is just a pairing heap built from linked lists), and even a balanced binary tree will do better at reasonable scales.
  - mpyne 13y ago
    Sure, but I think the issue is that 'reasonable scales' are growing larger and larger due to the improvement in constant factors associated with use of vectors. Especially if you already know the size you need to allocate it can be quicker to dump the data into the vector and then sort it than to branch hither-and-yon while maintaining an ordering invariant during push_back(). Of course there's probably some kind of cache-aware binary heap that gives the best of both worlds (algorithmic complexity and constant factor improvements), but vector<> already works now without needing fancy things like Judy arrays. The real answer (as ever) is probably to profile to be sure.
- Peaker 13y ago
  I think the issue here is that std::list is an extremely bad implementation of a linked list. One of the nice advantages of linked lists as opposed to vectors, is that you can avoid allocations, and std::list doesn't facilitate this advantage unless your data is only inside a single list. Another advantage of proper lists, is that it is very cheap to do things like remove an item from multiple lists it is in. std::list requires maintaining extra list iterators in the item for this, which is both difficult and wasteful. If std::list is the benchmark for lists, vectors indeed beat them handily for virtually any task. But compare Linux's intrusive linked list (Linux's list.h) with vectors for the many many tasks that fit these lists' use cases, and vectors are going to lose on all fronts, including cache misses.
moomin 13y ago
Just to be clear, I said cache cOnsiderations can beat complexity, not that it will always beat complexity at the kind of scale that busts the cache. The interesting point is that you're not necessarily comparing like with like. For the right sized matrix, one is bound by compute speed and one by memory access.
- betterunix 13y ago
  "For the right sized matrix, one is bound by compute speed and one by memory access." I am not sure that is a distinction worth making. Memory access and computation go hand-in-hand: programs do not access memory without performing some computation, and computations cannot be performed without accessing some kind of memory (even if it is just a register). At scale an asymptotically faster algorithm will perform fewer computations and fewer memory accesses (for all levels of memory) than an asymptotically slower algorithm.
  - stephencanon 13y ago
    The crucial point is that two algorithms with the same asymptotic complexity may have radically different performance characteristics; if algorithm A asymptotically "always” hits L1, and algorithm B asymptotically “never” hits L1, then A may very well be bound purely by compute resources and B may be entirely bound by memory hierarchy throughput, despite the fact that they perform the same number of computations and memory accesses. Yes, this effect will always eventually be overtaken by wins in asymptotic complexity, but (as is often the case when matrix multiplication is involved) the constants may be such that reaching the crossover requires such comically large inputs as to render such considerations essentially negligible.
    - betterunix 13y ago
      "The crucial point is that two algorithms with the same asymptotic complexity may have radically different performance characteristics" OK, but this was not a thread about the difference in constant factors, and I freely admit that constant factors matter. As I said elsewhere, twice as fast is twice as fast, there is no denying that. Strassen's algorithm does not have the same asymptotic performance as the textbook algorithm. Strassen's algorithm is faster at scale. "Yes, this effect will always eventually be overtaken by wins in asymptotic complexity, but (as is often the case when matrix multiplication is involved) the constants may be such that reaching the crossover requires such comically large inputs as to render such considerations essentially negligible." It sounds like you are confusing the best known matrix multiplication algorithm, William's algorithm, with Strassen's algorithm. Strassen's algorithm is used in practice, and depending on what sort of architecture you are on the crossover point is N being in the hundreds or the thousands (for an NxN matrix). These are not comically large, these are sizes that are seen in practice in various settings.

mpyne 13y ago

> Bjarne Stroustroup is quite fond of demonstrating the superiority of vector even when complexity would suggest list was the right approach. [citation needed] You might want to read his Fourth Edition of The C++ Programming Language, where he basically recommends std::vector<> as the default container unless you're dealing with large amounts of data that you add into the vector without using .push_back(). In essence, std::vector<> first, switch to std::list<> if profiling shows a speedup. > Most of the time people who claim that vectors are outperforming lists on tasks where lists are "asymptotically better" they are actually hiding some asymptotic cost. Linked lists have poor asymptotic performance for most interesting tasks, just like vectors. On the contrary, perhaps the most interesting task we ever do with a list is iterate over it and vectors kick ass there. There's also hardly any indirection or special 'short list' optimization hacks required, such as used in Qt's QList to make its performance reasonable.

betterunix 13y ago
"On the contrary, perhaps the most interesting task we ever do with a list is iterate over it and vectors kick ass there." You need to populate a sequence before you can iterate over it, and that is where the poor asymptotic performance becomes a problem. An example that came up on HN a few weeks ago is this: insert a bunch of elements into a sequence, while maintaining some order (i.e. the sequence must be in order after each insertion). Sure, vectors outperform linked lists on this task -- but both are crushed by a priority queue (even if it is just a pairing heap built from linked lists), and even a balanced binary tree will do better at reasonable scales.
- mpyne 13y ago
  Sure, but I think the issue is that 'reasonable scales' are growing larger and larger due to the improvement in constant factors associated with use of vectors. Especially if you already know the size you need to allocate it can be quicker to dump the data into the vector and then sort it than to branch hither-and-yon while maintaining an ordering invariant during push_back(). Of course there's probably some kind of cache-aware binary heap that gives the best of both worlds (algorithmic complexity and constant factor improvements), but vector<> already works now without needing fancy things like Judy arrays. The real answer (as ever) is probably to profile to be sure.
Peaker 13y ago
I think the issue here is that std::list is an extremely bad implementation of a linked list. One of the nice advantages of linked lists as opposed to vectors, is that you can avoid allocations, and std::list doesn't facilitate this advantage unless your data is only inside a single list. Another advantage of proper lists, is that it is very cheap to do things like remove an item from multiple lists it is in. std::list requires maintaining extra list iterators in the item for this, which is both difficult and wasteful. If std::list is the benchmark for lists, vectors indeed beat them handily for virtually any task. But compare Linux's intrusive linked list (Linux's list.h) with vectors for the many many tasks that fit these lists' use cases, and vectors are going to lose on all fronts, including cache misses.

moomin 13y ago

Just to be clear, I said cache cOnsiderations can beat complexity, not that it will always beat complexity at the kind of scale that busts the cache. The interesting point is that you're not necessarily comparing like with like. For the right sized matrix, one is bound by compute speed and one by memory access.

betterunix 13y ago
"For the right sized matrix, one is bound by compute speed and one by memory access." I am not sure that is a distinction worth making. Memory access and computation go hand-in-hand: programs do not access memory without performing some computation, and computations cannot be performed without accessing some kind of memory (even if it is just a register). At scale an asymptotically faster algorithm will perform fewer computations and fewer memory accesses (for all levels of memory) than an asymptotically slower algorithm.
- stephencanon 13y ago
  The crucial point is that two algorithms with the same asymptotic complexity may have radically different performance characteristics; if algorithm A asymptotically "always” hits L1, and algorithm B asymptotically “never” hits L1, then A may very well be bound purely by compute resources and B may be entirely bound by memory hierarchy throughput, despite the fact that they perform the same number of computations and memory accesses. Yes, this effect will always eventually be overtaken by wins in asymptotic complexity, but (as is often the case when matrix multiplication is involved) the constants may be such that reaching the crossover requires such comically large inputs as to render such considerations essentially negligible.
  - betterunix 13y ago
    "The crucial point is that two algorithms with the same asymptotic complexity may have radically different performance characteristics" OK, but this was not a thread about the difference in constant factors, and I freely admit that constant factors matter. As I said elsewhere, twice as fast is twice as fast, there is no denying that. Strassen's algorithm does not have the same asymptotic performance as the textbook algorithm. Strassen's algorithm is faster at scale. "Yes, this effect will always eventually be overtaken by wins in asymptotic complexity, but (as is often the case when matrix multiplication is involved) the constants may be such that reaching the crossover requires such comically large inputs as to render such considerations essentially negligible." It sounds like you are confusing the best known matrix multiplication algorithm, William's algorithm, with Strassen's algorithm. Strassen's algorithm is used in practice, and depending on what sort of architecture you are on the crossover point is N being in the hundreds or the thousands (for an NxN matrix). These are not comically large, these are sizes that are seen in practice in various settings.