Hacker News Reader

Comment by mgaunard | Hacker News Reader

[flagged]

To those who don't know about compiler optimisation, the replacement with a closed form is rather suprising I'd say, especially if someone with Matt Godbolt's experience of all people is saying it is surprising.

Also this series is targeted towards more of a beginner audience to compilers, thus its likely to be suprising to the audience, even if not to you.

Gauss supposedly did it when he was 7. The hardest part for the compiler is figuring out that you have a loop that computes that sum and does nothing else important.

Unfortunately I don’t have a hiring pipeline filled with Gausses

It's something we saw in highschool, I would expect anyone with a CS degree to recognize this optimization.

I barely know anything about compiler optimization, so I have no clue whether a compiler applying this optimization is surprising or something trivial.

Implementing this in a compiler is nontrivial.

Yes, that was clear to me from the article and the discussion. My point is that to someone who knows about Gauss' formula but doesn't know anything about compilers might not understand what the fuss is about.

https://www.npopov.com/2023/10/03/LLVM-Scalar-evolution.html

“basic and essential” are interesting ways to describe the field of compiler optimization research.

Are you suggesting that the discovery and implementation of SCEV in LLVM is basic and essential? Or that summing integers in a range is basic and essential?

I spoke in the context of coding those optimizations yourself.

Yeah. Pretty basic. Just 14k LOC

https://github.com/llvm/llvm-project/blob/release/21.x/llvm/...

I would've assumed it was hardcoded. Not a generic solution for any loop involving a recurring variable.

Im curious what exactly you ask here. I consider myself to be a decent engineer (for practical purposes) but without a CS degree, and I might likely have not passed that question.

I know compilers can do some crazy optimizations but wouldn't have guessed it'll transform something from O(n) to O(1). Having said that, I dont still feel this has too much relevance to my actual job for the most part. Such performance knowledge seems to be very abstracted away from actual programming by database systems, or managed offerings like spark and snowflake, that unless you intend to work on these systems this knowledge isn't that useful (being aware they happen can be though, for sure).

He thinks it makes him look clever, or more likely subtlety wants people to think "wow, this guy thinks something is obvious when Matt Godbolt found it surprising".

This kind of question is entirely useless in an interview. It's just a random bit of trivia that either a potential hire happen to have come across, or happens to remember from math class.

Trying to look smart by dissing Matt is not a good idea.

Have you considered that maybe Matt isn’t all that surprised by this optimization, but he is excited about how cool it is, and he wants readers of all backgrounds to also be excited about how cool it is, and is just feigning surprise so that he can share a sense of excitement with his audience?

It’s writing for effect.

Everybody who has seen any video of Matt knows that.

You can be surprised about things you know for years.

For example I am surprised every time I think about js coalescing even tougth I know it for decades.

The one that always gets me is what Truffle/JRuby was capable of, ten years ago:

https://x.com/chrisgseaton/status/619885182104043520

https://x.com/chrisgseaton/status/619888649866448896

I dunno he can honestly be quite a jerk sometimes

Bro...

AKA you get exactly the opposite…

I guess what's surprising here is that compilers are able to perform those optimizations systematically on arbitrary code, not the optimizations themselves, which should be obvious to a human.

Whether they get the question exactly right and can pinpoint the specific compiler passes or algebraic properties responsible for reductions like this is totally irrelevant and not what you’re actually looking for or asking about. It’s a very good jumping point for a conversation about optimization and testing whether they’re the type of developer who has ever looked at the assembly produced in their hotpath or not.

Anyone who dumbly suggests that loops in source code will always result in loops in assembly doesn’t have a clue. Anyone who throws their hands up and says, “I have no idea, but I wonder if there’s some loop invariant or algebraic trick that can be used to optimize this, let’s think about it out loud for a bit” has taken a compiler class and gets full marks. Anyone who says, “I dunno, let’s see what godbolt does and look through the llvm-opt pane” gets an explicit, “hire this one” in the feedback to the hiring manager.

It’s less about what they know and more about if they can find out.

So in other words, it isn't "basic and essential optimizations" that you would expect even a junior engineer to know (as your comment implies), but a mechanism to trigger a conversation to see how they think about problems. In fact, it sounds like something you wouldn't expect them to know.

I didn’t write the GP comment. I wouldn’t call this basic and essential, but I would say that compilers have been doing similar loop simplifications for quite some time. I’d expect any mid to senior developer with C/C++ on their resume to at least consider the possibility that the compiler can entirely optimize away a loop.

> In fact, it sounds like something you wouldn't expect them to know.

I’d go a step further, I don’t think anyone, no matter how experienced they are, can confidently claim that optimized assembly will or won’t be produced for a given loop. That’s why the best answer above is, “I dunno”. If performance really matters, you have to investigate and confirm that you’re getting good code. You can have an intuition for what you think might happen, and that’s a useful skill to have on its own, but it’s totally useless if you don’t also know how to confirm your suspicions.

My question is in the context of doing those optimizations yourself, understanding what can be done to make the code more efficient and how to code it up, not the compiler engineering to make that happen.

Yikes, gross. That’s like an option of last resort IMO. I’d rather maintain the clean loop-based code unless I had evidence that the compiler was doing the wrong thing and it was in my critical path.

The compiler is only able to perform certain optimizations that have no observable behaviour.

For example it can only parallelize code which is inherently parallelizable to begin with, and unless you design your algorithm with that in mind, it's unlikely to be.

My belief is that it's better to be explicit, be it with low-level or high-level abstractions.

My interview aims to assess whether the candidate understands that the dependency of each iteration on the previous one prevents effective utilization of a superscalar processor, knows the ways to overcome that, and whether the compiler is able to optimize that automatically, and if so when it absolutely cannot and why.

I generally focus more on sum of arbitrary data, but I used to also ask about a formulaic sum (linear to constant time) as an example of something a compiler is unlikely to do.

My thinking is that I expect good engineers to be able to do those optimizations themselves rather than rely on compilers.

Since GCC is lacking such an essential optimization, you should consider have one of your junior interviewee contribute this basic optimization mainline.

For Matt, the creator of compiler explorer, those are surprises.

For you are essentials.

You and the juniors you hire must have a deeper knoledge than him.

You don't have to be an expert in compiler design to make godbolt in fairness, although he does know a lot.

I spend a lot of time looking at generated assembly and there are some more impressive ones.

As i said you must have a deeper knoledge than him.

It would be great if you shared it with the world like Matt does instead of being smug about it.

What type of positions are you interviewing for? Software development is a big tent and I don't think this would be pertinent in a web dev interview, for example.

To provide the solution to the second part of the question, there is no closed-form solution. Since floating point math is not associative, there’s no O(1) optimization that can be applied that preserves the exact output of the O(n) loop.

Technically there is a closed form solution as long as the answer is less than 2^24 for a float32 or 2^53 for a float64, since below those all integers can be represented fully by a floating point number, and integer addition even with floating point numbers is identical if the result is below those caps. I doubt a compiler would catch that one, but it technically could do the optimisation and have the exact same bit answer. If result was intialised to a non-integer number this would not be true however of course.

A very good point! I didn’t think of that.

This is why you have options like -ffast-math, to allow more aggressive but not 100% identical outcome optimizations.

You can split the problem into chunks, where each chunk has the same exponents all the way through. It doesn't get you O(1), but it gets you O(log(n)).

I’m pretty sure making an algorithm that converts loops to close forms (I’m sure it detects much more than just a summation) is a little bit complicated.

Maybe you have much more experience than Mr Godbolt in compiliers.

Nothing is surprising once you know the answer. It takes some mental gymnastics to put yourself in someone else's shoes before they discovered it and thus making it less "basic".

Everyone knows the Gauss Summation formula for sum of n integers i.e. n*(n+1)/2 but it is just nice to see it in GCC vs. Clang.

https://xkcd.com/1053/

Reply on news.ycombinator.com