Graph coloring is NP-hard so it would be very difficult to replace it with an O(1) algorithm.
If you mean graph coloring restricted to planar graphs, yes it can always be done with at most 4 colors. But it could still be less, so the answer is not always the same.
(I know it was probably not a very serious comment but I just wanted to infodump about graph theory.)
Those are just basic and essential optimizations, nothing too surprising here.
The sum of integers is actually a question I ask developers in interviews (works well from juniors to seniors), with the extra problem of what happens if we were to use floating-point instead of integers.
Since GCC is lacking such an essential optimization, you should consider have one of your junior interviewee contribute this basic optimization mainline.
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.
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.
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.
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 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” gets an explicit, “hire this one” in the feedback to the hiring manager.
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.
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.
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".
I'm actually surprised that gcc doesn't do this! If there's one thing compilers do well is pattern match on code patterns and replace with more efficient ones; just try pasting things from Hacker's Delight and watch it always canonicalise it to the equivalent, fastest machine code.
This particular case isn't really due to pattern matching -- it's a result of a generic optimization that evaluates the exit value of an add recurrence using binomial coefficients (even if the recurrence is non-affine). This means it will work even if the contents of the loop get more exotic (e.g. if you perform the sum over x * x * x * x * x instead of x).
https://github.com/llvm/llvm-project/blob/release/21.x/llvm/...
If you mean graph coloring restricted to planar graphs, yes it can always be done with at most 4 colors. But it could still be less, so the answer is not always the same.
(I know it was probably not a very serious comment but I just wanted to infodump about graph theory.)
The sum of integers is actually a question I ask developers in interviews (works well from juniors to seniors), with the extra problem of what happens if we were to use floating-point instead of integers.
Maybe you have much more experience than Mr Godbolt in compiliers.
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.
For you are essentials.
You and the juniors you hire must have a deeper knoledge than him.
I spend a lot of time looking at generated assembly and there are some more impressive ones.
It would be great if you shared it with the world like Matt does instead of being smug about it.
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).
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.
Anyone who dumbly suggests that loops in source code will 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” gets an explicit, “hire this one” in the feedback to the hiring manager.
This kind of optimization, complete loop removal and computing the final value for simple math loops, is at least 10 years old.