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

31–40 of 82 posts

Re: Outperforming LAPACK with C++ metaprogramming

#31

Post by jordigh »

tzahola wrote: post #26
jordigh wrote: post #16

D's Mir does the same sort of thing, and metaprogramming in D is much nicer, because it was designed from the ground up instead of the bug elevated to feature that metaprogramming is in C++. http://docs.mir.dlang.io/latest/index.html http://blog.mir.dlang.io/glas/benchmark/openblas/2016/09/23/...

>and metaprogramming in D is much nicer, because it was designed from the ground up instead of the bug elevated to feature that metaprogramming is in C++ Yet neither of them are as elegant as LISP macros.

Very true! I wish D's metaprogramming was slightly more structured instead of relying on raw string concatenation. However, it's not so bad, and it's miles ahead of C++ metaprogramming in terms of ease of use. It's nice that it's so much more deliberately conceived. There's static if, static for, compile-time function evaluation, template and string mixins, and more!

I think D's metaprogramming is very close to lisp, possibly as close as possible without having sexps.

Re: Outperforming LAPACK with C++ metaprogramming

#33

Post by beojan »

jordigh wrote: post #31
tzahola wrote: post #26

Earlier quoted context omitted.

>and metaprogramming in D is much nicer, because it was designed from the ground up instead of the bug elevated to feature that metaprogramming is in C++ Yet neither of them are as elegant as LISP macros.

Very true! I wish D's metaprogramming was slightly more structured instead of relying on raw string concatenation. However, it's not so bad, and it's miles ahead of C++ metaprogramming in terms of ease of use. It's nice that it's so much more deliberately conceived. There's static if, static for, compile-time function evaluation, template and string mixins, and more! I think D's metaprogramming is very close to lisp,…

> relying on raw string concatenation

> it's not so bad

You can always use the C preprocessor in C++ if raw string manipulation is enough.

Seriously, though, constexpr means C++ also has static if, compile time loops, function eval, etc.

Re: Outperforming LAPACK with C++ metaprogramming

#34

Post by pletnes »

sevensor wrote: post #17
pletnes wrote: post #10

Earlier quoted context omitted.

Also, it seems the author solved a triangular system. LAPACK has special routines for that. Were they used? LAPACK is typically optimized for larger systems, not 5 unknowns. Also, 5 is not a great number for vectorized operations - it might even be beneficial to zero/one pad the matrix. Optimized LAPACK is often 5-10x faster than «basic LAPACK». BLAS/LAPACK was originally written in the 70s/80s and sometimes unroll l…

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.

Re: Outperforming LAPACK with C++ metaprogramming

#35

Post by ChrisRackauckas »

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…

That's pretty much what you get with Julia, except it will also do interprocedural optimization (i.e. inline constants and functions across calls) on v0.7. All without playing with templates. I'll gladly pay a 1 second JiT lag for a few days off my computation. At the same time, I don't have screw around with templates.

Re: Outperforming LAPACK with C++ metaprogramming

#36

Post by stephencanon »

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

The performance is completely expected--in fact, I would expect an optimized 5x5 solver to be faster than this.

Re: Outperforming LAPACK with C++ metaprogramming

#37

Post by ChrisRackauckas »

tzahola wrote: post #26
jordigh wrote: post #16

D's Mir does the same sort of thing, and metaprogramming in D is much nicer, because it was designed from the ground up instead of the bug elevated to feature that metaprogramming is in C++. http://docs.mir.dlang.io/latest/index.html http://blog.mir.dlang.io/glas/benchmark/openblas/2016/09/23/...

>and metaprogramming in D is much nicer, because it was designed from the ground up instead of the bug elevated to feature that metaprogramming is in C++ Yet neither of them are as elegant as LISP macros.

Compilation with LISP-like macros for fast generic programming? Julia?

Re: Outperforming LAPACK with C++ metaprogramming

#38

Post by jordigh »

beojan wrote: post #33
jordigh wrote: post #31

Earlier quoted context omitted.

Very true! I wish D's metaprogramming was slightly more structured instead of relying on raw string concatenation. However, it's not so bad, and it's miles ahead of C++ metaprogramming in terms of ease of use. It's nice that it's so much more deliberately conceived. There's static if, static for, compile-time function evaluation, template and string mixins, and more! I think D's metaprogramming is very close to lisp,…

> relying on raw string concatenation > it's not so bad You can always use the C preprocessor in C++ if raw string manipulation is enough. Seriously, though, constexpr means C++ also has static if, compile time loops, function eval, etc.

Raw string manipulation in D's mixins is much more limited than in CPP, and it's also not the only tool available for metaprogramming.

https://dlang.org/mixin.html

> constexpr means C++ also has static if, compile time loops, function eval, etc.

It's still not quite the same. I'm sorry to not bring examples, but if you look for them yourself, I think you'll find that D's metaprogramming looks nicer than C++'s constexpr.

Re: Outperforming LAPACK with C++ metaprogramming

#39

Post by ChrisRackauckas »

vog wrote: post #2

I wonder if the similar tricks work in other languages with similarily optimizing compilers, but "nicer" metaprogramming, such as Common LISP, Rust and perhaps OCaml? (with camlp4) Even more interesting would be whether this leads to the same huge performance gains in those languages as well.

It does lead to performance gains. This kind of stuff is done all the time in Julia's numerical codes. Flexible macros definitely make this easier, and multiple dispatch + automatic function specialization on types + inlining + interprocedural optimizations makes a lot of what's discussed here automatic. If it's not automatic, then libraries like StaticArrays.jl make functions that use small arrays do these kinds of tricks automatically (it overloads and unrolls operations specifically to match the size of the array which is compile time information). I am sure other languages can do this too, but having it semi-automatic is pretty cool if what you do all day is write numerical codes.

Re: Outperforming LAPACK with C++ metaprogramming

#40

Post by nicwilson »

beojan wrote: post #33
jordigh wrote: post #31

Earlier quoted context omitted.

Very true! I wish D's metaprogramming was slightly more structured instead of relying on raw string concatenation. However, it's not so bad, and it's miles ahead of C++ metaprogramming in terms of ease of use. It's nice that it's so much more deliberately conceived. There's static if, static for, compile-time function evaluation, template and string mixins, and more! I think D's metaprogramming is very close to lisp,…

> relying on raw string concatenation > it's not so bad You can always use the C preprocessor in C++ if raw string manipulation is enough. Seriously, though, constexpr means C++ also has static if, compile time loops, function eval, etc.

> C++ also has static if

Not even close. You can't conditionally insert a member.

Post reply on HN