4 ms·

Just to point out the obvious: the thing to take away from this article isn't that this is the right way to do matrix multiplication (ATLAS and BLAS are), but t

by moomin 13y ago

Just to point out the obvious: the thing to take away from this article isn't that this is the right way to do matrix multiplication (ATLAS and BLAS are), but that cache considerations can beat even complexity concerns. Bjarme Stroustroup is quite fond of demonstrating the superiority of vector even when complexity would suggest list was the right approach.

gngeal 13y ago
ATLAS and BLAS are What you probably meant was that ATLAS and BLAS are implementations of the right way, not the way itself. Because the alternative would be really, really sad.
- moomin 13y ago
  Actually, I meant that, for most of us, using ATLAS or BLAS is superior to any implementation of our own. I'll allow exceptions for people who have unusual requirements or a phenomenal amount of skill.
  - gngeal 13y ago
    I may be mistaken, but don't ATLAS, BLAS, LINPACK etc. only operate on single and double precision floats? What if the elements you're operating on are, say, rationals or polynomials? Somehow it seemed to me that linear algebra is a somewhat more abstract concept than what Fortran numerical libraries usually tend to implement. Also, the drawback of anything written in this way is that it doesn't compose well. The individual operations may well have been optimized into oblivion, but their composition may not necessarily be what you'd like it to be. One can also say goodbye to higher-order functions. But I'm not exactly a Fortran person when it comes to code style, so I may be prejudiced against overly loopy code. (BTW, am I the only one who thinks that the Sourceforge (http://sourceforge.net/projects/math-atlas/ http://sourceforge.net/projects/math-atlas/) comments are machine-generated? I mean, comments like "An essential Windows program." or "The best program that I've ever used." are hardly what I'd expect for a numerical library.)
    - moomin 13y ago
      True. I guess I was putting rationals et al under "unusual requirements". Happy to accept they're not as unusual as I think. Composability is a huge issue: I think the whole reason SciPy exists is to provide an interoperability standard for this sort of work. That said, I think your average scientist can more intuitively see ways of composing _using_ matrices than the rest of us. (Checks the Sourceforge reviews. ROTFL. What's the purpose of this spam?)
betterunix 13y ago
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.

by moomin 13y ago

gngeal 13y ago

ATLAS and BLAS are What you probably meant was that ATLAS and BLAS are implementations of the right way, not the way itself. Because the alternative would be really, really sad.

moomin 13y ago
Actually, I meant that, for most of us, using ATLAS or BLAS is superior to any implementation of our own. I'll allow exceptions for people who have unusual requirements or a phenomenal amount of skill.
- gngeal 13y ago
  I may be mistaken, but don't ATLAS, BLAS, LINPACK etc. only operate on single and double precision floats? What if the elements you're operating on are, say, rationals or polynomials? Somehow it seemed to me that linear algebra is a somewhat more abstract concept than what Fortran numerical libraries usually tend to implement. Also, the drawback of anything written in this way is that it doesn't compose well. The individual operations may well have been optimized into oblivion, but their composition may not necessarily be what you'd like it to be. One can also say goodbye to higher-order functions. But I'm not exactly a Fortran person when it comes to code style, so I may be prejudiced against overly loopy code. (BTW, am I the only one who thinks that the Sourceforge (http://sourceforge.net/projects/math-atlas/ http://sourceforge.net/projects/math-atlas/) comments are machine-generated? I mean, comments like "An essential Windows program." or "The best program that I've ever used." are hardly what I'd expect for a numerical library.)
  - moomin 13y ago
    True. I guess I was putting rationals et al under "unusual requirements". Happy to accept they're not as unusual as I think. Composability is a huge issue: I think the whole reason SciPy exists is to provide an interoperability standard for this sort of work. That said, I think your average scientist can more intuitively see ways of composing _using_ matrices than the rest of us. (Checks the Sourceforge reviews. ROTFL. What's the purpose of this spam?)

betterunix 13y ago

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.