4 ms·

There is something, I found quite liberating, was writing matrix operations in the naive way. Forget about performance for a moment, and just write those imbric

There is something, I found quite liberating, was writing matrix operations in the naive way. Forget about performance for a moment, and just write those imbricated loops. They can run everywhere from javascript in the web, to your raspberry pi, to your arduino where you want to have a linear classifier, windows, linux, embedded platform. No need for complex to compile library. When you realize that most deep learning library, "einsum is all you need", and that einsum is just loops and sum, it kind of screams you are doing it the wrong way when using numerical libraries ranging from BLAS to cuda. Loops can also be automatically differentiated. Loops can also be reordered. Loops can be tiled. There are some techniques (polyhedral loop optimization) to do it automatically. Loops can be parallelized and vectorized. Most of the optimization are always the same and due to the memory hierarchy. The problem space is well defined. Candidates solutions can be benchmarked automatically. Some architectures like to have their memory access in a Structures of Arrays, other in Array of Structures, or even Arrays of structures of Arrays. Benchmark depend of sizes in various dimensions. Are you really always going to write the optimizations manually, and do the complex code transforms by hand. This feels like one area ripped for disruption. The other day there was this thread about not writing your own computer language, but here one domain specific language can have a huge impact. Take the naive form and automatically generate the forward, backward, (nth order autodiff) optimized version given an instruction set whether for cpu, gpu or tpu, and for various memory usage profile. Optimizing code, even though it feels quite fun and rewarding to do manually is a job for compilers. Write naive algorithms but smart compilers. Extra kudos if you handle the mathematical function : For example if you want an exponential : write it as an infinite taylor sum. If you want matrix exponential write it as a taylor sum also ( and if your compiler automatically derive the Pade approximation for improved numerical stability you know you are on the right track).

MaxBarraclough 5y ago
> Optimizing code, even though it feels quite fun and rewarding to do manually is a job for compilers. > Write naive algorithms but smart compilers. I'm not sure where you're coming from here. The article's charts show that in this case, naive code gets you less than 2% the performance of an optimised implementation.
- qayxc 5y ago
  > The article's charts show that in this case, naive code gets you less than 2% the performance of an optimised implementation. That's not what the chart shows at all. The charts shows what non optimized code compiles to. Just run the code through any optimizing compiler released in the past decade and you'll find that do the vectorization for you. No need to use non-portable intrinsics. Even the block optimisation can be done in plain C. While optimised algorithms are better than naive algorithms, optimising machine code is indeed a compiler task. Some languages tend to do a better job of describing the algorithm than others, but that's a different can worms entirely.
  - gpderetta 5y ago
    I think that by non-optimized the chart refers to not hand-optimized. The code is likely still compiled via -O3. In theory the GCC is capable to do all these optimizations, even loop tiling, vectorization and autopar as it indeed has a polyhedral representation of loops. In practice it might be another story of course.
    - qayxc 5y ago
      > The code is likely still compiled via -O3. That doesn't matter. You have to specify the target platform as well. Just take the naive code and specify -O3 in godbolt.org for example. Assembly exerpt of the inner loop: L5: movss xmm0, DWORD PTR [rax] mulss xmm0, DWORD PTR [rdx] add rax, 4 add rdx, rdi addss xmm1, xmm0 movss DWORD PTR [rcx], xmm1 cmp rsi, rax jne .L5 No AVX in sight. Now specify -mavx2 -mfma and compare the inner loop: .L5: vmovss xmm2, DWORD PTR [rax] vfmadd231ss xmm0, xmm2, DWORD PTR [rdx] add rax, 4 add rdx, rdi vmovss DWORD PTR [rcx], xmm0 cmp rsi, rax jne .L5 Case in point: without providing the compiler flags used for compilation, charts are misleading at best and outright wrong at worst.
      - gpderetta 5y ago
hugh-avherald 5y ago
Literally no-one can write compilers smart enough.
- adgjlsfhk1 5y ago
  Julia+LoopVectorization is already smart enough for this (it can't yet deal with more complicated transforms like lu or ffts, but it already gives you near optimal matmul code from a triple loop.
keithalewis 5y ago
Does HN use a GPT-3 detector? This smells like the slightly imbricated (sic) prose it generates. It seems to make sense unless you actually know something this topic.
- jpf0 5y ago
  Since you supposedly know something about this topic, please contribute it.
  - keithalewis 5y ago
    Okay. Learn how to install and link a BLAS version appropriate for your machine architecture. Do not assume the particular compiler you are currently using has a magical optimizer. This will future-proof your code and make it more portable, not to mention instill confidence that your code is correct. Of course if you are just playing around with a toy project, this is probably not worth the effort.
- GistNoesis 5y ago
  Sorry, I should have proofread it. A french-anglicism for nested-loops ("boucles imbriquées") slipped through.
MauranKilom 5y ago
> and if your compiler automatically derive the Pade approximation for improved numerical stability you know you are on the right track I don't know what you're smoking, but I want some of it.
mamcx 5y ago
This is, I think, the gist of array langs like APL. Vectors + tight inner loops are very close to be great.
__dt__ 5y ago
> Forget about performance for a moment, and just write those imbricated loops. Right, if we forget about performance a three-nested-loop GEMM is certainly better than any other implementation. But that's completely meaningless and you could find such examples for almost any task. This is almost as saying writing hash functions is easy as long as you forget about collisions and avalanche effects. > When you realize that most deep learning library, "einsum is all you need", and that einsum is just loops and sum, it kind of screams you are doing it the wrong way when using numerical libraries ranging from BLAS to cuda. That is just not true: It is correct that deep learning tasks mainly reduce to convolutions and GEMM. Convolutions can be mapped to contraction kernels which again can be mapped to GEMM. However, Numpy's einsum is a great example how you shouldn't do it as it's notoriously slow. Also, the main task in general tensor contraction functions is to find an optimal contraction ordering rather than executing GEMM (you can have exponential savings if you choose a good contraction sequence). You can read more about this in e.g. https://arxiv.org/abs/2002.01935 https://arxiv.org/abs/2002.01935. > Loops can also be automatically differentiated. Loops can also be reordered. Loops can be tiled. There are some techniques (polyhedral loop optimization) to do it automatically. Loops can be parallelized and vectorized. This is true in theory and while modern compilers get better and better there is still no compiler framework that could, given an arbitrary linear algebra task outperform a manually optimized BLAS or LAPACK library. Also, you are mentioning just a very few low-level optimization techniques that can be applied while modern compiler research currently focuses on different aspects as implemented in XLA for example. > Optimizing code, even though it feels quite fun and rewarding to do manually is a job for compilers. > Write naive algorithms but smart compilers. Still, don't write bad code and use compilers as an excuse.
tomn 5y ago
The response to this comment is a bit sad. Yes, "we just needs a sufficiently advanced compiler" is a meme, but 1) not everyone knows that and 2) that's not what this comment is asking for: > but here one domain specific language can have a huge impact There's a big difference between a sufficiently advanced compiler for general C code, and a compiler for a domain-specific array processing language, for example. Have a look at halide: https://halide-lang.org https://halide-lang.org , where you specify the computation to perform and a schedule (loop order, blocking, vectorisation) separately. There's even an automatic scheduler that can find a good schedule given some example array sizes and parameters. The fftw paper is worth a read, too -- this shows that for a restricted domain it's possible to automatically find code that works as well as or better than hand-tuned algorithms. Generalising this is of course very hard. For deep learning I think a lot of this is already done, see XLA for example.

MaxBarraclough 5y ago

> Optimizing code, even though it feels quite fun and rewarding to do manually is a job for compilers. > Write naive algorithms but smart compilers. I'm not sure where you're coming from here. The article's charts show that in this case, naive code gets you less than 2% the performance of an optimised implementation.

qayxc 5y ago
> The article's charts show that in this case, naive code gets you less than 2% the performance of an optimised implementation. That's not what the chart shows at all. The charts shows what non optimized code compiles to. Just run the code through any optimizing compiler released in the past decade and you'll find that do the vectorization for you. No need to use non-portable intrinsics. Even the block optimisation can be done in plain C. While optimised algorithms are better than naive algorithms, optimising machine code is indeed a compiler task. Some languages tend to do a better job of describing the algorithm than others, but that's a different can worms entirely.
- gpderetta 5y ago
  I think that by non-optimized the chart refers to not hand-optimized. The code is likely still compiled via -O3. In theory the GCC is capable to do all these optimizations, even loop tiling, vectorization and autopar as it indeed has a polyhedral representation of loops. In practice it might be another story of course.
  - qayxc 5y ago
    > The code is likely still compiled via -O3. That doesn't matter. You have to specify the target platform as well. Just take the naive code and specify -O3 in godbolt.org for example. Assembly exerpt of the inner loop: L5: movss xmm0, DWORD PTR [rax] mulss xmm0, DWORD PTR [rdx] add rax, 4 add rdx, rdi addss xmm1, xmm0 movss DWORD PTR [rcx], xmm1 cmp rsi, rax jne .L5 No AVX in sight. Now specify -mavx2 -mfma and compare the inner loop: .L5: vmovss xmm2, DWORD PTR [rax] vfmadd231ss xmm0, xmm2, DWORD PTR [rdx] add rax, 4 add rdx, rdi vmovss DWORD PTR [rcx], xmm0 cmp rsi, rax jne .L5 Case in point: without providing the compiler flags used for compilation, charts are misleading at best and outright wrong at worst.
    - gpderetta 5y ago

hugh-avherald 5y ago

Literally no-one can write compilers smart enough.

adgjlsfhk1 5y ago
Julia+LoopVectorization is already smart enough for this (it can't yet deal with more complicated transforms like lu or ffts, but it already gives you near optimal matmul code from a triple loop.

keithalewis 5y ago

Does HN use a GPT-3 detector? This smells like the slightly imbricated (sic) prose it generates. It seems to make sense unless you actually know something this topic.

jpf0 5y ago
Since you supposedly know something about this topic, please contribute it.
- keithalewis 5y ago
  Okay. Learn how to install and link a BLAS version appropriate for your machine architecture. Do not assume the particular compiler you are currently using has a magical optimizer. This will future-proof your code and make it more portable, not to mention instill confidence that your code is correct. Of course if you are just playing around with a toy project, this is probably not worth the effort.
GistNoesis 5y ago
Sorry, I should have proofread it. A french-anglicism for nested-loops ("boucles imbriquées") slipped through.

MauranKilom 5y ago

> and if your compiler automatically derive the Pade approximation for improved numerical stability you know you are on the right track I don't know what you're smoking, but I want some of it.

mamcx 5y ago

This is, I think, the gist of array langs like APL. Vectors + tight inner loops are very close to be great.

__dt__ 5y ago

> Forget about performance for a moment, and just write those imbricated loops. Right, if we forget about performance a three-nested-loop GEMM is certainly better than any other implementation. But that's completely meaningless and you could find such examples for almost any task. This is almost as saying writing hash functions is easy as long as you forget about collisions and avalanche effects. > When you realize that most deep learning library, "einsum is all you need", and that einsum is just loops and sum, it kind of screams you are doing it the wrong way when using numerical libraries ranging from BLAS to cuda. That is just not true: It is correct that deep learning tasks mainly reduce to convolutions and GEMM. Convolutions can be mapped to contraction kernels which again can be mapped to GEMM. However, Numpy's einsum is a great example how you shouldn't do it as it's notoriously slow. Also, the main task in general tensor contraction functions is to find an optimal contraction ordering rather than executing GEMM (you can have exponential savings if you choose a good contraction sequence). You can read more about this in e.g. https://arxiv.org/abs/2002.01935 https://arxiv.org/abs/2002.01935. > Loops can also be automatically differentiated. Loops can also be reordered. Loops can be tiled. There are some techniques (polyhedral loop optimization) to do it automatically. Loops can be parallelized and vectorized. This is true in theory and while modern compilers get better and better there is still no compiler framework that could, given an arbitrary linear algebra task outperform a manually optimized BLAS or LAPACK library. Also, you are mentioning just a very few low-level optimization techniques that can be applied while modern compiler research currently focuses on different aspects as implemented in XLA for example. > Optimizing code, even though it feels quite fun and rewarding to do manually is a job for compilers. > Write naive algorithms but smart compilers. Still, don't write bad code and use compilers as an excuse.

tomn 5y ago

The response to this comment is a bit sad. Yes, "we just needs a sufficiently advanced compiler" is a meme, but 1) not everyone knows that and 2) that's not what this comment is asking for: > but here one domain specific language can have a huge impact There's a big difference between a sufficiently advanced compiler for general C code, and a compiler for a domain-specific array processing language, for example. Have a look at halide: https://halide-lang.org https://halide-lang.org , where you specify the computation to perform and a schedule (loop order, blocking, vectorisation) separately. There's even an automatic scheduler that can find a good schedule given some example array sizes and parameters. The fftw paper is worth a read, too -- this shows that for a restricted domain it's possible to automatically find code that works as well as or better than hand-tuned algorithms. Generalising this is of course very hard. For deep learning I think a lot of this is already done, see XLA for example.