News for hackers. Stuff that matters.
Re:BLAS-level CPU Performance in 100 Lines of C by GistNoesis on Tuesday March 01, 2022 @04:58AM (#30512063)
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).

Re:BLAS-level CPU Performance in 100 Lines of C by tomn on Tuesday March 01, 2022 @08:49AM (#30514041)
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 , 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.

Re:BLAS-level CPU Performance in 100 Lines of C by MaxBarraclough on Tuesday March 01, 2022 @05:25AM (#30512301)
> 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.

Re:BLAS-level CPU Performance in 100 Lines of C by qayxc on Tuesday March 01, 2022 @06:03AM (#30512605)
> 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.

Re:BLAS-level CPU Performance in 100 Lines of C by gpderetta on Tuesday March 01, 2022 @06:11AM (#30512669)
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.

Re:BLAS-level CPU Performance in 100 Lines of C by qayxc on Tuesday March 01, 2022 @07:50AM (#30513468)
> 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.
Re:BLAS-level CPU Performance in 100 Lines of C by gpderetta on Tuesday March 01, 2022 @08:44AM (#30513974)
I believe the flags are in the compile.sh script in the repo:

   OMP_NUM_THREADS=8 g++ -Wall -std=c++11 -fopenmp -D_USE_OPENBLAS -O3 -L/usr/lib  -lopenblas   -I /usr/include/openblas -march=native -mavx2 -mfma -funroll-loops compare_blas.cpp  -lopenblas -o matmul
Of course it is possible that different flags were used to benchmark the naive version.

edit: and of course those f*ss suffixes show that the compiler is not actually vectorizing the loops, just using the avx encoding of scalar instructions (plus fma).

edit2: likely -ffast-math is also required for vectorization as it will change the sequence of operations, but after experimenting with it a bit it seems that in this case is still not sufficient.

Re:BLAS-level CPU Performance in 100 Lines of C by __dt__ on Tuesday March 01, 2022 @08:20AM (#30513762)
> 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.

> 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.

Re:BLAS-level CPU Performance in 100 Lines of C by MauranKilom on Tuesday March 01, 2022 @06:15AM (#30512697)
> 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.

Re:BLAS-level CPU Performance in 100 Lines of C by keithalewis on Tuesday March 01, 2022 @06:07AM (#30512645)
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.
Re:BLAS-level CPU Performance in 100 Lines of C by GistNoesis on Tuesday March 01, 2022 @09:22AM (#30514441)
Sorry, I should have proofread it. A french-anglicism for nested-loops ("boucles imbriquées") slipped through.
Re:BLAS-level CPU Performance in 100 Lines of C by jpf0 on Tuesday March 01, 2022 @09:13AM (#30514346)
Since you supposedly know something about this topic, please contribute it.
Re:BLAS-level CPU Performance in 100 Lines of C by keithalewis on Thursday March 03, 2022 @08:49AM (#30540932)
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.

Re:BLAS-level CPU Performance in 100 Lines of C by mamcx on Tuesday March 01, 2022 @07:19AM (#30513219)
This is, I think, the gist of array langs like APL. Vectors + tight inner loops are very close to be great.
Re:BLAS-level CPU Performance in 100 Lines of C by hugh-avherald on Tuesday March 01, 2022 @05:34AM (#30512364)
Literally no-one can write compilers smart enough.
Re:BLAS-level CPU Performance in 100 Lines of C by adgjlsfhk1 on Tuesday March 01, 2022 @10:51AM (#30515606)
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.