4 ms·

> It demonstrates that Python needs libraries like NumPy. People use matrix multiplication libraries (often written in Assembly) from every language if they re

by p-e-w 3y ago

> It demonstrates that Python needs libraries like NumPy. People use matrix multiplication libraries (often written in Assembly) from every language if they really care about performance. That's because such libraries incorporate 100 PhD theses' worth of tricks that no individual can hope to reinvent in the course of solving another problem. There is absolutely nothing special about Python in this context. > It also means that adding performance to an existing Python program requires dropping into a different language As stated above, this applies to all languages. BLAS routines used for serious numerical work are hand-vectorized Assembly fine-tuned for each processor architecture, written by a few hyper-experts who do nothing else. Nobody who needs performant matrix multiplication from C thinks "hey, let me just write two nested loops".

dsharlet 3y ago
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
mratsim 3y ago
> People use matrix multiplication libraries (often written in Assembly) from every language if they really care about performance. That's because such libraries incorporate 100 PhD theses' worth of tricks that no individual can hope to reinvent in the course of solving another problem. There is absolutely nothing special about Python in this context. You don't have to use Assembly. Case in point, this is as fast as OpenBLAS: https://github.com/mratsim/weave/tree/master/benchmarks/matmul_gemm_blas/gemm_pure_nim https://github.com/mratsim/weave/tree/master/benchmarks/matm...
- bjourne 3y ago
  That's a bold claim. Do you have any benchmarks to back it up? Even if it was as fast as OpenBLAS on your machine when you benchmarked it that doesn't mean it will be as fast on others' machines.
  - mratsim 3y ago
    The code is open-source I have benches on i5-5257U (dual core from old MBP15), i9-9980XE (Skylake-X 18 cores), Dual Xeon Gold 6132, AMD 7840U. See: https://github.com/mratsim/laser/blob/master/benchmarks%2Fgemm%2Fgemm_bench_float32.nim#L407 https://github.com/mratsim/laser/blob/master/benchmarks%2Fge... And using my own threadpool instead of OpenMP - https://github.com/mratsim/weave/issues/68#issuecomment-569238069 https://github.com/mratsim/weave/issues/68#issuecomment-5692... - https://github.com/mratsim/weave/pull/94 https://github.com/mratsim/weave/pull/94
    - bjourne 3y ago
      Can you explain how to build your project and how to run the benchmarks? Cause I just spent a few hours disproving another poster's claim of getting OpenBLAS-like performance and I won't want to waste more time (https://news.ycombinator.com/item?id=38867009 https://news.ycombinator.com/item?id=38867009). While I don't know Nim very well, I dare claim that you don't get anywhere near OpenBLAS performance.
      - 3y ago
morepedantic 3y ago
Anything fast in Python needs to be written in another language, and if your day job isn't multiplying matrices, then you're probably SoL. Assume the author knows about BLAS, and that the point is to benchmark the language not the FFI. Most people don't actually spend their time bashing vectors together.

by p-e-w 3y ago

dsharlet 3y ago

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

mratsim 3y ago

> People use matrix multiplication libraries (often written in Assembly) from every language if they really care about performance. That's because such libraries incorporate 100 PhD theses' worth of tricks that no individual can hope to reinvent in the course of solving another problem. There is absolutely nothing special about Python in this context. You don't have to use Assembly. Case in point, this is as fast as OpenBLAS: https://github.com/mratsim/weave/tree/master/benchmarks/matmul_gemm_blas/gemm_pure_nim https://github.com/mratsim/weave/tree/master/benchmarks/matm...

bjourne 3y ago
That's a bold claim. Do you have any benchmarks to back it up? Even if it was as fast as OpenBLAS on your machine when you benchmarked it that doesn't mean it will be as fast on others' machines.
- mratsim 3y ago
  The code is open-source I have benches on i5-5257U (dual core from old MBP15), i9-9980XE (Skylake-X 18 cores), Dual Xeon Gold 6132, AMD 7840U. See: https://github.com/mratsim/laser/blob/master/benchmarks%2Fgemm%2Fgemm_bench_float32.nim#L407 https://github.com/mratsim/laser/blob/master/benchmarks%2Fge... And using my own threadpool instead of OpenMP - https://github.com/mratsim/weave/issues/68#issuecomment-569238069 https://github.com/mratsim/weave/issues/68#issuecomment-5692... - https://github.com/mratsim/weave/pull/94 https://github.com/mratsim/weave/pull/94
  - bjourne 3y ago
    Can you explain how to build your project and how to run the benchmarks? Cause I just spent a few hours disproving another poster's claim of getting OpenBLAS-like performance and I won't want to waste more time (https://news.ycombinator.com/item?id=38867009 https://news.ycombinator.com/item?id=38867009). While I don't know Nim very well, I dare claim that you don't get anywhere near OpenBLAS performance.
    - 3y ago

morepedantic 3y ago

Anything fast in Python needs to be written in another language, and if your day job isn't multiplying matrices, then you're probably SoL. Assume the author knows about BLAS, and that the point is to benchmark the language not the FFI. Most people don't actually spend their time bashing vectors together.