12 ms·

This is really overstating how hard it is to compete with matrix multiply libraries. The main reason those libraries are so big and have had so much work invest

This is really overstating how hard it is to compete with matrix multiply libraries. The main reason those libraries are so big and have had so much work invested in them is their generality: they're reasonably fast for almost any kind of inputs. If you have a specific problem with constraints you can exploit (e.g. known fixed dimensions, sparsity patterns, data layouts, type conversions, etc.), it's not hard at all to beat MKL, etc... if you are using a language like C++. If you are using python, you have no chance. It isn't even necessarily that different from a few nested loops. Clang is pretty damn good at autovectorizing, you just have to be a little careful about how you write the code.

lifthrasiir 3y ago
You need to have enough experience to be able to be a little careful though. This is generally true for most languages, loop unrolling works even better in Python for example, but many Python programmers aren't even aware of this possibility.
p-e-w 3y ago
> If you are using python, you have no chance. Of course you do. Every special-case multiplication algorithm you might need already has an optimized implementation that you can just `pip install`, and move on with what you're actually working on. The whole scientific computing world runs on Python. Straightforward numerics code using NumPy tends to murder C/C++ code in regard to performance, unless that code is written by people who make a living hand-optimizing computational routines.
- SideQuark 3y ago
  > The whole scientific computing world runs on Python If you ignore the majority of scientific code running on supercomputers doing most of science in C++ and Fortran. Even in areas where python is used, the majority of the compute runs on C/C++/Fortran, with a little python as glue. If you think numpy (written in c/c++) murders c/c++ code, you should learn about HPC, where really high performance happens. They don't use numpy.
geysersam 3y ago
If you need a really fast compiled inner loop then you can often implement it in Python using Numba. Using that you can easily implement something like sparse matrix multiplication in Python.
bjourne 3y ago
> This is really overstating how hard it is to compete with matrix multiply libraries. I'll file this under "talk is cheap". :) I tried it last year and got within 50% of BLAS. Getting above that is tons of work. Which you have to repeat for every processor model, NUMA, and every combination of matrix type (long thin, short wide, etc).
- dsharlet 3y ago
  This gets to 90% of BLAS: https://github.com/dsharlet/array/blob/38f8ce332fc4e26af08325ad0654c8516a445e8c/examples/linear_algebra/matrix.cpp#L271 https://github.com/dsharlet/array/blob/38f8ce332fc4e26af0832... The less involved versions still get ~70%. But this is also quite general. I’m claiming you can beat BLAS if you have some unique knowledge of the problem that you can exploit. For example, some kinds of sparsity can be implemented within the above example code yet still far outperform the more general sparsity supported by MKL and similar.
  - bjourne 3y ago
    I don't believe you. OpenBLAS is multithreaded but the code you posted is single-threaded. The inner kernel isn't very well optimized either. So, no way.
    - dsharlet 3y ago
      I should have mentioned somewhere, I disabled threading for OpenBLAS, so it is comparing one thread to one thread. Parallelism would be easy to add, but I tend to want the thread parallelism outside code like this anyways. As for the inner loop not being well optimized... the disassembly looks like the same basic thing as OpenBLAS. There's disassembly in the comments of that file to show what code it generates, I'd love to know what you think is lacking! The only difference between the one I linked and this is prefetching and outer loop ordering: https://github.com/dsharlet/array/blob/master/examples/linear_algebra/matrix.cpp#L133 https://github.com/dsharlet/array/blob/master/examples/linea...
      - 3y ago

lifthrasiir 3y ago

You need to have enough experience to be able to be a little careful though. This is generally true for most languages, loop unrolling works even better in Python for example, but many Python programmers aren't even aware of this possibility.

p-e-w 3y ago

> If you are using python, you have no chance. Of course you do. Every special-case multiplication algorithm you might need already has an optimized implementation that you can just `pip install`, and move on with what you're actually working on. The whole scientific computing world runs on Python. Straightforward numerics code using NumPy tends to murder C/C++ code in regard to performance, unless that code is written by people who make a living hand-optimizing computational routines.

SideQuark 3y ago
> The whole scientific computing world runs on Python If you ignore the majority of scientific code running on supercomputers doing most of science in C++ and Fortran. Even in areas where python is used, the majority of the compute runs on C/C++/Fortran, with a little python as glue. If you think numpy (written in c/c++) murders c/c++ code, you should learn about HPC, where really high performance happens. They don't use numpy.

geysersam 3y ago

If you need a really fast compiled inner loop then you can often implement it in Python using Numba. Using that you can easily implement something like sparse matrix multiplication in Python.

bjourne 3y ago

> This is really overstating how hard it is to compete with matrix multiply libraries. I'll file this under "talk is cheap". :) I tried it last year and got within 50% of BLAS. Getting above that is tons of work. Which you have to repeat for every processor model, NUMA, and every combination of matrix type (long thin, short wide, etc).

dsharlet 3y ago
This gets to 90% of BLAS: https://github.com/dsharlet/array/blob/38f8ce332fc4e26af08325ad0654c8516a445e8c/examples/linear_algebra/matrix.cpp#L271 https://github.com/dsharlet/array/blob/38f8ce332fc4e26af0832... The less involved versions still get ~70%. But this is also quite general. I’m claiming you can beat BLAS if you have some unique knowledge of the problem that you can exploit. For example, some kinds of sparsity can be implemented within the above example code yet still far outperform the more general sparsity supported by MKL and similar.
- bjourne 3y ago
  I don't believe you. OpenBLAS is multithreaded but the code you posted is single-threaded. The inner kernel isn't very well optimized either. So, no way.
  - dsharlet 3y ago
    I should have mentioned somewhere, I disabled threading for OpenBLAS, so it is comparing one thread to one thread. Parallelism would be easy to add, but I tend to want the thread parallelism outside code like this anyways. As for the inner loop not being well optimized... the disassembly looks like the same basic thing as OpenBLAS. There's disassembly in the comments of that file to show what code it generates, I'd love to know what you think is lacking! The only difference between the one I linked and this is prefetching and outer loop ordering: https://github.com/dsharlet/array/blob/master/examples/linear_algebra/matrix.cpp#L133 https://github.com/dsharlet/array/blob/master/examples/linea...
    - 3y ago