Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Outperforming LAPACK with C++ metaprogramming

wordsandbuttons.online

Post reply on HN
Print view View original

51–60 of 82 posts

Re: Outperforming LAPACK with C++ metaprogramming

#51

Post by thanatropism »

pletnes wrote: post #34
sevensor wrote: post #17

Earlier quoted context omitted.

Personally, my biggest reason to prefer LAPACK in general is that its authors have already put a great deal of effort into correctness and numerical stability, so I don't have to. Even basic LAPACK is pretty fast, let alone the optimized libraries. Hand-optimizing my own special case is an absolute last resort.

Yes, Cramer’s rule (referred to in the article) does not give numerically stable results AFAIK - which is yet another can of worms. Good catch.

I don't think I have heard Cramer's rule mentioned without the caveat "but don't use this for real problems".

Re: Outperforming LAPACK with C++ metaprogramming

#53

Post by pkaye »

dpwm wrote: post #7
barrkel wrote: post #4

Please check with array initialized from file or other dynamic source. With maximal inlining, there's a risk of constant propagation resulting in a lot of computation happening at compile time rather than run time.

As an anecdote of just how powerful this can be, I once wrote a prototype of a simulation (written in C) that used a lot of integer divisions and needed to be run many times with different parameters. As a quick and dirty hack that took about half hour to implement, I decided to just have the program as a template string and the parameters be substituted in by a python script that called GCC. To the amazement of a ve…

You should check out this presentation done by Matt Godbolt about compiler internals. He talks about what kind of optimizations are being done by GCC and Clang. Pretty amazing stuff. For example, the compiler will figure out you are trying to write a pop count in high level code and replace it with a single popcount instruction.

https://www.youtube.com/watch?v=bSkpMdDe4g4

Re: Outperforming LAPACK with C++ metaprogramming

#54

Post by flatline »

gpderetta wrote: post #27
flatline wrote: post #25

Earlier quoted context omitted.

I know that SFINAE exploited the preprocessor's template overload resolution rules. It was later standardized and expanded on. https://books.google.com/books?id=i7M1DwAAQBAJ&pg=PT564

there is no preprocessor template overloading, or overloading at all really. The preprocessor has nothing to do with templates.

Thank you, please excuse my pre-coffee ramblings and mentally strike "preprocessor" from my comment;)

Re: Outperforming LAPACK with C++ metaprogramming

#55

Post by electricslpnsld »

stephencanon wrote: post #36
costrouc wrote: post #20

For those wondering the lapack guys are working on a new version of lapack to run on heterogeneous architecture including gpus. See their work at http://www.icl.utk.edu/research I have worked with these guys and all I can say is good luck outperforming the highly optimized routines they have written. My bet is that the the guy writing this blog used a non optimized version of lapack.

There's no mystery here, author is only solving a 5x5 system. LAPACK will have barely finished checking function call parameters by the time a fully specialized and inlined solver is finished. Also, from a cursory inspection, author does no pivoting [edit: worse, it just uses Cramer's rule, which is insane], so their solver will be much less numerically robust (but this is admittedly less of a problem for the 5x5 cas…

A better comparison might be a C++ library like Eigen that is intended for use on these small systems, that should optimize out function calls in a similar way, and that uses intrinsics.

Re: Outperforming LAPACK with C++ metaprogramming

#56

Post by mpweiher »

pkaye wrote: post #53
dpwm wrote: post #7

Earlier quoted context omitted.

As an anecdote of just how powerful this can be, I once wrote a prototype of a simulation (written in C) that used a lot of integer divisions and needed to be run many times with different parameters. As a quick and dirty hack that took about half hour to implement, I decided to just have the program as a template string and the parameters be substituted in by a python script that called GCC. To the amazement of a ve…

You should check out this presentation done by Matt Godbolt about compiler internals. He talks about what kind of optimizations are being done by GCC and Clang. Pretty amazing stuff. For example, the compiler will figure out you are trying to write a pop count in high level code and replace it with a single popcount instruction. https://www.youtube.com/watch?v=bSkpMdDe4g4

Amazing, yes. Scary, also.

If you're going to figure this out, please output a warning and ask me to call the optimized intrinsic or something.

Re: Outperforming LAPACK with C++ metaprogramming

#57

Post by ska »

1024core wrote: post #32

Template metaprogramming just shifts the burden of computation to compile time. Sure, I could pre-compute the first 10000 factorials, put them in an array, compile and then print the answer in constant time. But it'll work for the first 10000 numbers only.

It's not nearly that simple. You can use template meta-programming to make expressions both easy to read and efficient, by avoiding creation of temporary objects, fusion, lifting, etc. etc.

In some domains (e.g. linear algebra) this can be very powerful because you don't have write non idiomatic expressions just to feed the compiler things it can understand.

Re: Outperforming LAPACK with C++ metaprogramming

#58

Post by stochastic_monk »

electricslpnsld wrote: post #55
stephencanon wrote: post #36

Earlier quoted context omitted.

There's no mystery here, author is only solving a 5x5 system. LAPACK will have barely finished checking function call parameters by the time a fully specialized and inlined solver is finished. Also, from a cursory inspection, author does no pivoting [edit: worse, it just uses Cramer's rule, which is insane], so their solver will be much less numerically robust (but this is admittedly less of a problem for the 5x5 cas…

A better comparison might be a C++ library like Eigen that is intended for use on these small systems, that should optimize out function calls in a similar way, and that uses intrinsics.

If your matrices are of arbitrary size, Blaze [0] would be my pick. It has the best performance on their benchmarks, Baptiste Wicht's benchmarks, and my own.

Though if the matrices are guaranteed to be small (like in this example), libxsmm [1] is specialized and highly optimized for this use case and beats its competitors above.

And yes, it's absolutely essential to make sure you didn't just move computations to compile-time.

[0]: https://bitbucket.org/blaze-lib/blaze

[1]: https://github.com/hfp/libxsmm

Re: Outperforming LAPACK with C++ metaprogramming

#59

Post by blt »

Others have already mentioned Cramer's rule, but even if this code were switched to Gaussian elimination it might not beat lapack on big problems. Lapack implementations do extra tricks to optimize cache usage on big matrices. Would be interesting to include eigen in the benchmark too.

Re: Outperforming LAPACK with C++ metaprogramming

#60

Post by xaedes »

bstamour wrote: post #44
nicwilson wrote: post #40

Earlier quoted context omitted.

> C++ also has static if Not even close. You can't conditionally insert a member.

Hopefully that will be fixed in a future C++ standard. There is an interesting static reflection proposal floating around that would allow for this, plus more.

The talk about the reflection proposal was amazing. Meta classes are also very cool. We can only hope it comes fast.

https://www.youtube.com/watch?v=4AfRAVcThyA

Post reply on HN