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

LLVM Is Smarter Than Me

blog.sulami.xyz

Post reply on HN
Print view View original

11–18 of 18 posts

Re: LLVM Is Smarter Than Me

#11

Post by constantcrying »

valleyer wrote: post #2

A small correction: the sigma summation should go to n-1, not n. It's weird that LLVM computes n(n-1)/2 in such a convoluted way, namely: (n-1)(n-2)/2 + n - 1

It has to. Just imagine what happens when in the iterative algorithm

count = count + i

is just before overflowing. In that case the O(N) algorithm has no overflow, but if you look at the closed form solution. Surely

(count)*(count-1)

would overflow.

A compiler must never be allowed to swap a non-overflow with a overflow. Which is one big limit of these optimizations.

Re: LLVM Is Smarter Than Me

#13

Post by fooker »

echoangle wrote: post #3

Does someone know how the compiler comes up with the closed form solution? Is there a hardcoded list of common patterns and their solution in the compiler, or is this really generated from the code itself?

It's more like a hundred matched patterns, with more added once in a while.

Re: LLVM Is Smarter Than Me

#14

Post by valleyer »

constantcrying wrote: post #11
valleyer wrote: post #2

A small correction: the sigma summation should go to n-1, not n. It's weird that LLVM computes n(n-1)/2 in such a convoluted way, namely: (n-1)(n-2)/2 + n - 1

It has to. Just imagine what happens when in the iterative algorithm count = count + i is just before overflowing. In that case the O(N) algorithm has no overflow, but if you look at the closed form solution. Surely (count)*(count-1) would overflow. A compiler must never be allowed to swap a non-overflow with a overflow. Which is one big limit of these optimizations.

Sure, but in the scenario you describe, (count-1)*(count-2) also overflows, and that's why the generated code already to 64 bits for the multiply. (See my cousin comment to this one.)

Re: LLVM Is Smarter Than Me

#15

Post by pjmlp »

Actually that was the reason Compiler Explorer was created in first place, Matt Godbolt wanted an easy way to sort out all the usual discussions "I know better than the compiler" in regards to using C++ abstractions.

Re: LLVM Is Smarter Than Me

#17

Post by moomin »

lambdaxyzw wrote: post #8
moomin wrote: post #6

Earlier quoted context omitted.

Yeah, one suspects this is a dumb micro-optimisation to make benchmark figures look better with little practical application.

Doing micro optimizations is precisely the compiler's job - so I don't have to worry about it.

Yeah, but all micro optimisations come with costs, from compiler time to maintenance overhead. Someone's still got to ask if it's worth it. And in this case, I just can't see many regular programs containing code likely to trip this, but benchmarks? All the time.
Post reply on HN