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

71–80 of 82 posts

Re: Outperforming LAPACK with C++ metaprogramming

#71

Post by sannee »

AnimalMuppet wrote: post #64
bachmeier wrote: post #63

Earlier quoted context omitted.

I've read your comment several times and can't follow it. I think you're saying that even if the author continued to use Cramer's rule, he would lose to LAPACK on big problems.

No. If he continued to use Cramer's rule, he would definitely lose to LAPACK on big problems, purely because of using Cramer's rule . But even if he didn't continue to use Cramer's rule (if he switched to Gaussian elimination), he still might lose to LAPACK, because LAPACK is pretty well optimized. At least, that's how I interpreted the comment...

> he would definitely lose to LAPACK on big problems, purely because of using Cramer's rule.

More importantly though, the code would probably take ages (as in, "age of the universe" ages) to compile, as Cramer's rule is O(n!) (using a naive implementation, I think one could get to O(n^4) if determinant was computed using LU factorization, but what's the point of Cramer's rule then...).

Re: Outperforming LAPACK with C++ metaprogramming

#72

Post by bigcheesegs »

mpweiher wrote: post #56
pkaye wrote: post #53

Earlier quoted context omitted.

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.

Why? The intrinsics aren't portable, the other code is.

Re: Outperforming LAPACK with C++ metaprogramming

#73

Post by dpwm »

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

That talk really revealed some brilliant optimizations that Clang does. In addition to what you mentioned, the bit where Clang recognises the summation loop, removes the loop and replaces it with a closed-form solution feels intuitively more like the operations that only some cutting edge research-language compiler should be able to do. To see this for C and C++ is very impressive.

Re: Outperforming LAPACK with C++ metaprogramming

#74

Post by pkaye »

mpweiher wrote: post #56
pkaye wrote: post #53

Earlier quoted context omitted.

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.

What is your concern?

Re: Outperforming LAPACK with C++ metaprogramming

#75

Post by dpwm »

bigcheesegs wrote: post #72
mpweiher wrote: post #56

Earlier quoted context omitted.

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.

Why? The intrinsics aren't portable, the other code is.

Even with intrinsics that do have a degree of portability, I prefer the more explicit form of the bit counting just for readability. Nobody has to learn what popcnt means.

These optimizations really mean that as software writers we can declare our intent and have the compiler do safe optimizations.

It seems like these optimizations of Clang are also quite insensitive to the many different ways of writing the same thing that C++ has earned notoriety for.

Re: Outperforming LAPACK with C++ metaprogramming

#76

Post by sedachv »

bachmeier wrote: post #69
sedachv wrote: post #68

Earlier quoted context omitted.

> You have the Common Lisp approach, where you work in a complicated sublanguage like this example from PCL: I don't think you actually understand anything about the example code you posted. There is no special "complicated sublanguage" - the backquote[1] is an extension of the quote shorthand notation[2] for list literals. It is for building data structures and has nothing to do with "sublanguages" or macros. There…

> I don't think you actually understand anything about the example code you posted. This doesn't add anything to the conversation. If you want to discuss my post, I'm happy to discuss. You're clearly upset that I didn't praise Common Lisp, but things like that don't lead to useful discussion. > There is no special "complicated sublanguage" - the backquote[1] is an extension of the quote shorthand notation[2] for list…

> You're clearly upset that I didn't praise Common Lisp, but things like that don't lead to useful discussion. > How is that is relevant to my comment?

No, I am upset that you are posting misinformed comments about Common Lisp macros vs D templating while representing yourself as being knowledgeable about the subject. You clearly do not understand how the former works.

> I've never seen anyone write macros using only s-expressions. True, you don't need to learn any special syntax to do it, but that's not how anyone writes macros.

Please stop pretending that you have enough experience with Common Lisp to say things like "I've never seen anyone do X." Writing macros that call functions that return code is a basic technique - Graham's On Lisp is full of examples. Saying that quoting as a way of specifying list literals is a "complicated sublanguage" is on the level of "C++ templates have too many pointy brackets" of criticism.

Re: Outperforming LAPACK with C++ metaprogramming

#77

Post by uadjet »

ChrisRackauckas wrote: post #39
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…

Julia's flexibility in the numerical space is why it's my daily driver language for prototyping and implementation nowadays. Truly a fantastic language.

Re: Outperforming LAPACK with C++ metaprogramming

#79

Post by lispm »

bachmeier wrote: post #62
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.

I'm not sure how you're measuring elegance, but writing Lisp macros and getting them to work correctly has never been something I'd call elegant. You have the Common Lisp approach, where you work in a complicated sublanguage like this example from PCL: (defmacro when (condition &rest body) `(if ,condition (progn ,@body))) and then you think hard about where the leaks are. Or else you take the Scheme approach of hygie…

> complicated sublanguage

I kind of fail to see how it is especially complicated. The macro uses a general mechanism to create lists. This mechanism isn't tied to macros and does not do anything special in macros.

It's also not really a sublanguage.

> then you think hard about where the leaks are

There are no leaks in the example.

Re: Outperforming LAPACK with C++ metaprogramming

#80

Post by mpweiher »

dpwm wrote: post #75
bigcheesegs wrote: post #72

Earlier quoted context omitted.

Why? The intrinsics aren't portable, the other code is.

Even with intrinsics that do have a degree of portability, I prefer the more explicit form of the bit counting just for readability. Nobody has to learn what popcnt means. These optimizations really mean that as software writers we can declare our intent and have the compiler do safe optimizations. It seems like these optimizations of Clang are also quite insensitive to the many different ways of writing the same thi…

> I prefer the more explicit form

Huh? It's not explicit, the purpose is implicit. You are writing down an algorithm that implements a popcount algorithm. The compiler than has to infer the fact that you actually wanted popcount (maybe you just wanted to waste a bit of time in a timing loop?) and then substitute something based on that inference.

I am all for it being explicit, i.e. some library function that has a name that somewhere mentions "popcount" or some such. Then have the compiler generate whatever code it needs for that function.

Post reply on HN