11 ms·

Exploring Clang/LLVM optimization on programming horror

362 points by maattdd 5y ago

CalChris 5y ago
These optimizations are on LLVM IR into LLVM IR. So basically every backend benefits. I don't think most backend engineers would even understand them. I don't.
- dragontamer 5y ago
  None of these steps are too hard to think about in SSA form (a specific transformation of code that LLVM does near the beginning of its analysis). So the key is to first understand SSA form. After that, a lot of optimization passes become obvious to think about. --------- SSA has two bits to understand: 1. Single static assignment -- variables can be assigned, but once assigned they can never change. (This part is easy). 2. Graph-based, and therefore requires the 'Phi' function to understand -- variables may take on two different values. EX: "r0" may come from Node#1, while "r0" comes from Node#2. r0 may have been renamed %1 in #1, and %2 in #2. "Phi" is a "fake function" that resolves the ambiguity and kinda makes SSA code "real" again. Hmm, maybe that's a bad explanation. But whatever, my point is that understanding "Phi" is the concept you want to focus on in SSA. Phi is the harder part, but its still not that hard to understand. Once you get it, the whole form "clicks" in your brain and you suddenly understand how optimizations can become possible.
  - jcranmer 5y ago
    Another explanation of SSA: SSA is static single assignment. Every variable has a single point of declaration. If you want to change the value of a variable (say, i = i + 1), you instead have to create a new variable. The advantage of this form is that tracking the definition of a variable is trivial; in LLVM IR, to use a variable, you literally pass in a pointer to the instruction that defined it. The inverse, finding all uses of a value, is done by building a use-list: whenever you create an instruction, it adds itself to the use-list of all the values it's using, which allows easy iteration of the users of a value. In short, SSA gives you a trivially correct-by-construction to understand the dataflow of a program (at least, that data which lives in registers; memory is more complicated). There's no separate analysis that has to be maintained throughout optimizations, and hence a possible source of programs (as there is for failure to maintain the dominator tree through CFG transformations, a historically bug-prone step in LLVM). Now, as you may notice, there are cases where it would seem hard to pin down a single definition of a variable: conditional assignment. SSA solves this by creating Phi values. Phi values can be better thought of as basic block arguments: when you enter a basic block, you must provide a value for each of the phi values in that basic block. The actual value of the phi is dependent on which edge you used to enter a basic block, or in other words, the control dependencies of the code. In short, phis are the intersection of control flow in the code with the dataflow--and they are the only things in that intersection.
  - mhh__ 5y ago
    LLVMs IR has linear basic blocks inside a function graph, there are IRs which are graph all the way down as well.
- woodruffw 5y ago
  > I don't think most backend engineers would even understand them. I don't. Most engineers are intimidated by compilers, but they really shouldn't be! LLVM's source code is very approachable and well-isolated by concern, and most of the fundamental concepts in an optimizing compiler are understandable with a beginner's understanding of data structures, assembly, and resource allocation. One slightly funny thing, though: LLVM's optimizations are on IR, so every frontend can theoretically benefit from them. However, many assume patterns originating from the C/C++ frontend or heavy canonicalization, so you need to be a little careful as a language frontend developer to take full advantage of all optimizations!
  - mhh__ 5y ago
    LLVM is approachable but some things are no better than GCC, I find. In particular I have noticed there seems to be very little high level documentation for the instruction scheduler. I find GCC machine def files actually slightly easier to read than LLVM's
  - jagger27 5y ago
    > so you need to be a little careful as a language frontend developer to take full advantage of all optimizations! So does this mean that it’s possible to express exotic patterns in LLVM-IR that aren’t typically produced when compiling C or C++? Are Rust’s optimizer passes significantly different than clang's? I would guess borrow checking has a special pass that wouldn’t be applicable to C. This topic is really fascinating to me!
    - jamincan 5y ago
      Notably, the Rust borrow checker has exposed a tonne of bugs in the LLVM noalias optimizations. I believe the latest versions of rustc now have noalias enabled since the LLVM 12 release, but it's been a long cycle of enabling it, discovering a bug, and disabling it to this point.
    - sillycross 5y ago
      My experience is that LLVM can generally optimize the IR produced from clang frontend a bit better than the IR produced by myself. The advantage is small, but still exists. I think the major reason is that TBAA optimization is only possible if you manually emit those metadata (clang does, but I didn't, due to time limitation and fear of aliasing-related bugs). But that LLVM is designed to work best on the pattern emitted by Clang is definitely another reason. In fact, even the official documentation recommends users to emit IR in a way that looks similar to what is emitted by Clang, so you have a better chance to keep the LLVM optimizer happy.
- srcreigh 5y ago
  EDIT - nvm, the CS241 UWaterloo course doesn't cover SSA. In case anybody's interested in learning the basics, here's some course notes to a compilers class which I love! http://anthony-zhang.me/University-Notes/CS241/CS241.html http://anthony-zhang.me/University-Notes/CS241/CS241.html
  - CalChris 5y ago
    Your notes, while honestly very good, don't cover data flow analysis or Single Static Assignment (SSA) which is what LLVM IR [1] uses and which are the tools that the article's optimizations are based on. Hell, LLVM backend engineers rarely even look at IR. We mostly look at Generic Machine IR [2]. [1] https://llvm.org/docs/LangRef.html https://llvm.org/docs/LangRef.html [2] https://llvm.org/docs/GlobalISel/GMIR.html https://llvm.org/docs/GlobalISel/GMIR.html
    - srcreigh 5y ago
      Ah, my bad. When you said "backend" I thought you mean "HTTP backend" hence my over-simplification. You're right -- SSA isn't covered in that course. Cheers.
  - dleslie 5y ago
    Interesting, in my day SFU kept this til 3rd year, as CMPT379 IIRC, and only as an option for Theoretical or Systems paths. Looks like it's still 379; not sure about the optional component. http://anoopsarkar.github.io/compilers-class/ http://anoopsarkar.github.io/compilers-class/
  - macintux 5y ago
    Decades ago I participated in some group programming contest for universities (in person, not online). We did terribly, but mainly I remember being in awe of how quickly Waterloo was solving the challenges.
woodruffw 5y ago
Great writeup! This is a nice overview of how LLVM's optimization passes compose to produce nicely optimized assembly. One nitpicky observation: mem2reg doesn't "move values from memory [...] to registers (directly inside the CPU)." It's an SSA expansion pass, taking the minimal SSA form produced by the C/C++ frontend to turning it into a more aggressive SSA form by eliminating as many `alloca`s as possible. SSA is characterized by the presence of infinitely many "fresh" abstract registers, none of which correspond to actual CPU registers -- LLVM is responsible at a later stage for performing efficient lowering and allocation of registers/stack slots for the SSA registers.
- dragontamer 5y ago
  https://llvm.org/docs/Passes.html#passes-mem2reg https://llvm.org/docs/Passes.html#passes-mem2reg > -mem2reg: Promote Memory to Register > This file promotes memory references to be register references. It promotes alloca instructions which only have loads and stores as uses. An alloca is transformed by using dominator frontiers to place phi nodes, then traversing the function in depth-first order to rewrite loads and stores as appropriate. This is just the standard SSA construction algorithm to construct “pruned” SSA form. ----------- https://llvm.org/docs/LangRef.html#alloca-instruction https://llvm.org/docs/LangRef.html#alloca-instruction > The ‘alloca’ instruction allocates memory on the stack frame of the currently executing function, to be automatically released when this function returns to its caller. If the address space is not explicitly specified, the object is allocated in the alloca address space from the datalayout string. -------- Based on my reading and understanding of alloca and mem2reg above, I have to disagree with your assessment. It seems like alloca roughly corresponds to a "push" in your typical x86 assembly language, or maybe a "add esp, #ofBytes". By removing alloca instructions, the mem2reg step is turning stack-memory into registers.
  - woodruffw 5y ago
    > By removing alloca instructions, the mem2reg step is turning stack-memory into registers. This is true, but it's also misleading: the transformation of stack slots into machine registers is a beneficial side effect of mem2reg. Reducing stack use is an important optimization, but producing an optimal SSA form is even more important, since key passes like folding, DCE and SRoA rely heavily on the SSA form. The "reg" in "mem2reg" refers explicitly to the latter (SSA registers), as the text you've excerpted directly says. You can also prove this to yourself by contriving an IR function that contains more SSA registers than machine registers: you'll see that, in addition to any ABI constraints, LLVM will be forced to spill any excess SSA registers back onto the stack. Edit: but also yes, to confirm: `alloca` corresponds more or less directly to `add ESP, <adjust>` within the x86 stack model. But it doesn't have to! LLVM's semantics are target independent even when the IR isn't.
eatonphil 5y ago
The core simplification is due to LLVM's induction-detection step. Even after doing induction-based proofs in school, until reading this I had the sense that induction is kinda magical and kinda not real. I still cannot fathom how you can encode induction detection into an algorithm, any pointers welcome (keeping it simple, please, and ideally with working code). The only case that makes sense to me is if you did numeric computation against some fixed number of cases and if that worked out then you assume it's right. I guess this is what proof assistants do (among other things). Maybe I should look into how to write a basic proof assistant.
- benmmurphy 5y ago
  the induction step is pretty cool. it will remove the loop calculating the sum of an arithmetic progression and replace it with just multiplies/shifts/subtracts and adds.
- contravariant 5y ago
  Well in this case it seems reasonable that they simply added a rule for the specific line: even = !even and the line numberCompare++ resulting in even = (indvar & 1) numberCompare = indvar You can then solve from the exit condition that number == numberCompare, which gives you the indvar which can then be substituted into 'even'. I'm not saying it isn't magical, and certainly requires some symbolic solving, but it's doable. Of course the real goal is to eventually get it to optimize while (number != 1) { if (number & 1) number = number * 3 + 1 number >>= 1; }
  - missblit 5y ago
    > Of course the real goal is to eventually get it to optimize `while (number != 1) { ... }` Valid C++ programs are guaranteed to be able to make forward progress [1]. So if `number` is a normal stack allocated integer (and not volatile, etc), then the infinite looping case is undefined behavior here. So it would be a valid optimization to transform this to `number = 1;`. (And indeed: https://godbolt.org/z/eodhfWe6h https://godbolt.org/z/eodhfWe6h ) [1] https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/language/memory_model
thrasumachos 5y ago
Nice that it even provides the right answer for negative numbers as undefined behavior but only when optimizations are enabled!
- titzer 5y ago
  Nice catch. One of many instances where C/C++ compilers rely on integer wraparound being UB.
martincmartin 5y ago
you get a linear time O(n) isEven function In complexity theory, the size of a problem is the number of bits to represent the input, so if the input integer is i, then the size is n = log_2(i) so the algorithm is actually exponential in the number of bits it takes to represent the input.
- trias 5y ago
  is complexity theory constrained to binary representations? Why should it?
  - Ar-Curunir 5y ago
    Every base except unary is a constant-factor away from binary, and so is irrelevant asymptotically. We don't use unary because it's artificially slow.
    - creata 5y ago
      See also: https://medium.com/@veedrac/why-unary-is-the-best-number-system-cc1e0edfb928 https://medium.com/@veedrac/why-unary-is-the-best-number-sys...
      - Ar-Curunir 5y ago
        That post is a joke, right?
        deleted 5y ago
        [deleted]
- dragontamer 5y ago
  In a strict sense, you're right. But in practice, you're not. Case in point: matrix multiplication is commonly quoted as O(n^3) (naive), when in fact, the amount of data used is O(n^2), and therefore should be quoted as O(size^2) (quadratic) with respect to data-size. (EDIT: was bad at math for a second). But no, people mean "n-by-n matrix" has "O(n^3) naive" implementation. In practice, the "n" is just whatever is most convenient for a problem. In many cases, n is proportional to the input size. But in other cases (such as the famous matrix multiplication examples), n is the sqrt(input-size).
ufo 5y ago
I'm very curious how it optimizes that recursive version at the end, because it is not tail recursive. Does anyone know? Perhaps it becomes tail recursive after one round of inlining?
- pertymcpert 5y ago
  It seems the TailRecursionElimination.cpp pass is responsible for that. It has some smarts to know that the xor instruction between the call and return can be turned into an "accumulator", although what exactly that means I'm unsure.
  - ufo 5y ago
    Thanks for investigating that! An accumulator is when we add an extra parameter to hold the "loop variable", like this: bool doit(int n, bool acc) { if (n == 0) return acc; else return doit(n-1, !acc); } bool isEven(int n) { return doit(n, true); } The function is now tail-recursive and behaves similarly to this loop: bool acc = true; while (n != 0) { acc = !acc; n = n - 1; } return acc; According to the comment on the top of the file, apparently llvm can create this accumulator variable if the operation is associative and commutative. That's because after introducing the accumulator, the evaluation order is outside->inside instead of inside->outside.
  - b3morales 5y ago
    Further reading about the relationship between recursion, iteration, and accumulators: https://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html https://blog.moertel.com/posts/2013-05-11-recursive-to-itera... This transformation is one you can apply in your own source as well. An example from that link, the recursive def factorial(n): if n < 2: return 1 return n * factorial(n - 1) can be rewritten iteratively: def factorial1d(n, acc=1): while n > 1: (n, acc) = (n - 1, acc * n) return acc
PostThisTooFast 5y ago
Nice hysterical, non-informative headline.
jagrsw 5y ago
O(n) isEven function compared to the obvious constant time O(1) modulo algorithm In the holy name of nitpickiness: the modulo operation is not always O(1), as div/mod CPU instructions have complex internal implementations and require varying number of cycles depending on what the input args are. However, for x%2 it'll be probably O(1), both on the cpu level, and b/c it'll get optimized to something like x&1 by most compilers (at least for unsigned values)
- 8192kjshad09- 5y ago
  I will nitpick your nitpick. In a language with arbitrary size integers you're right. This is a C++ int, therefore 32/64 bits (in all sane cases, ik the spec doesn't specify), so the maximum number of cycles is upper bounded. Therefore modulo on C++ ints is is O(1).
  - jagrsw 5y ago
    But having an upper bound doesn't make it O(1) automatically, no? It'd be like saying that Erastotenes' sieve is O(1) b/c for 64bit integers we know what upper exec time limit is? IMO id'd be rather creative use of current conventions around comp. complexity, but my knowledge of those topics is bad.
    - laszlokorte 5y ago
      big O() notation is simply not precise enough (and not meant to be) to be used in such nitpicky discussions. Everything is O(1) for a large anough constant, for example O(live time of the universe). There are other notations like small o(), Omega(), omega() or theta() to capture the asymtotic runtime behavior more or less precisely.
- athrowaway3z 5y ago
  It states "constant time O(1) modulo _algorithm_" for implementing an isEven function.

362 points by maattdd 5y ago

These optimizations are on LLVM IR into LLVM IR. So basically every backend benefits. I don't think most backend engineers would even understand them. I don't.

dragontamer 5y ago
None of these steps are too hard to think about in SSA form (a specific transformation of code that LLVM does near the beginning of its analysis). So the key is to first understand SSA form. After that, a lot of optimization passes become obvious to think about. --------- SSA has two bits to understand: 1. Single static assignment -- variables can be assigned, but once assigned they can never change. (This part is easy). 2. Graph-based, and therefore requires the 'Phi' function to understand -- variables may take on two different values. EX: "r0" may come from Node#1, while "r0" comes from Node#2. r0 may have been renamed %1 in #1, and %2 in #2. "Phi" is a "fake function" that resolves the ambiguity and kinda makes SSA code "real" again. Hmm, maybe that's a bad explanation. But whatever, my point is that understanding "Phi" is the concept you want to focus on in SSA. Phi is the harder part, but its still not that hard to understand. Once you get it, the whole form "clicks" in your brain and you suddenly understand how optimizations can become possible.
- jcranmer 5y ago
  Another explanation of SSA: SSA is static single assignment. Every variable has a single point of declaration. If you want to change the value of a variable (say, i = i + 1), you instead have to create a new variable. The advantage of this form is that tracking the definition of a variable is trivial; in LLVM IR, to use a variable, you literally pass in a pointer to the instruction that defined it. The inverse, finding all uses of a value, is done by building a use-list: whenever you create an instruction, it adds itself to the use-list of all the values it's using, which allows easy iteration of the users of a value. In short, SSA gives you a trivially correct-by-construction to understand the dataflow of a program (at least, that data which lives in registers; memory is more complicated). There's no separate analysis that has to be maintained throughout optimizations, and hence a possible source of programs (as there is for failure to maintain the dominator tree through CFG transformations, a historically bug-prone step in LLVM). Now, as you may notice, there are cases where it would seem hard to pin down a single definition of a variable: conditional assignment. SSA solves this by creating Phi values. Phi values can be better thought of as basic block arguments: when you enter a basic block, you must provide a value for each of the phi values in that basic block. The actual value of the phi is dependent on which edge you used to enter a basic block, or in other words, the control dependencies of the code. In short, phis are the intersection of control flow in the code with the dataflow--and they are the only things in that intersection.
- mhh__ 5y ago
  LLVMs IR has linear basic blocks inside a function graph, there are IRs which are graph all the way down as well.
woodruffw 5y ago
> I don't think most backend engineers would even understand them. I don't. Most engineers are intimidated by compilers, but they really shouldn't be! LLVM's source code is very approachable and well-isolated by concern, and most of the fundamental concepts in an optimizing compiler are understandable with a beginner's understanding of data structures, assembly, and resource allocation. One slightly funny thing, though: LLVM's optimizations are on IR, so every frontend can theoretically benefit from them. However, many assume patterns originating from the C/C++ frontend or heavy canonicalization, so you need to be a little careful as a language frontend developer to take full advantage of all optimizations!
- mhh__ 5y ago
  LLVM is approachable but some things are no better than GCC, I find. In particular I have noticed there seems to be very little high level documentation for the instruction scheduler. I find GCC machine def files actually slightly easier to read than LLVM's
- jagger27 5y ago
  > so you need to be a little careful as a language frontend developer to take full advantage of all optimizations! So does this mean that it’s possible to express exotic patterns in LLVM-IR that aren’t typically produced when compiling C or C++? Are Rust’s optimizer passes significantly different than clang's? I would guess borrow checking has a special pass that wouldn’t be applicable to C. This topic is really fascinating to me!
  - jamincan 5y ago
    Notably, the Rust borrow checker has exposed a tonne of bugs in the LLVM noalias optimizations. I believe the latest versions of rustc now have noalias enabled since the LLVM 12 release, but it's been a long cycle of enabling it, discovering a bug, and disabling it to this point.
  - sillycross 5y ago
    My experience is that LLVM can generally optimize the IR produced from clang frontend a bit better than the IR produced by myself. The advantage is small, but still exists. I think the major reason is that TBAA optimization is only possible if you manually emit those metadata (clang does, but I didn't, due to time limitation and fear of aliasing-related bugs). But that LLVM is designed to work best on the pattern emitted by Clang is definitely another reason. In fact, even the official documentation recommends users to emit IR in a way that looks similar to what is emitted by Clang, so you have a better chance to keep the LLVM optimizer happy.
srcreigh 5y ago
EDIT - nvm, the CS241 UWaterloo course doesn't cover SSA. In case anybody's interested in learning the basics, here's some course notes to a compilers class which I love! http://anthony-zhang.me/University-Notes/CS241/CS241.html http://anthony-zhang.me/University-Notes/CS241/CS241.html
- CalChris 5y ago
  Your notes, while honestly very good, don't cover data flow analysis or Single Static Assignment (SSA) which is what LLVM IR [1] uses and which are the tools that the article's optimizations are based on. Hell, LLVM backend engineers rarely even look at IR. We mostly look at Generic Machine IR [2]. [1] https://llvm.org/docs/LangRef.html https://llvm.org/docs/LangRef.html [2] https://llvm.org/docs/GlobalISel/GMIR.html https://llvm.org/docs/GlobalISel/GMIR.html
  - srcreigh 5y ago
    Ah, my bad. When you said "backend" I thought you mean "HTTP backend" hence my over-simplification. You're right -- SSA isn't covered in that course. Cheers.
- dleslie 5y ago
  Interesting, in my day SFU kept this til 3rd year, as CMPT379 IIRC, and only as an option for Theoretical or Systems paths. Looks like it's still 379; not sure about the optional component. http://anoopsarkar.github.io/compilers-class/ http://anoopsarkar.github.io/compilers-class/
- macintux 5y ago
  Decades ago I participated in some group programming contest for universities (in person, not online). We did terribly, but mainly I remember being in awe of how quickly Waterloo was solving the challenges.

woodruffw 5y ago

Great writeup! This is a nice overview of how LLVM's optimization passes compose to produce nicely optimized assembly. One nitpicky observation: mem2reg doesn't "move values from memory [...] to registers (directly inside the CPU)." It's an SSA expansion pass, taking the minimal SSA form produced by the C/C++ frontend to turning it into a more aggressive SSA form by eliminating as many `alloca`s as possible. SSA is characterized by the presence of infinitely many "fresh" abstract registers, none of which correspond to actual CPU registers -- LLVM is responsible at a later stage for performing efficient lowering and allocation of registers/stack slots for the SSA registers.

dragontamer 5y ago
https://llvm.org/docs/Passes.html#passes-mem2reg https://llvm.org/docs/Passes.html#passes-mem2reg > -mem2reg: Promote Memory to Register > This file promotes memory references to be register references. It promotes alloca instructions which only have loads and stores as uses. An alloca is transformed by using dominator frontiers to place phi nodes, then traversing the function in depth-first order to rewrite loads and stores as appropriate. This is just the standard SSA construction algorithm to construct “pruned” SSA form. ----------- https://llvm.org/docs/LangRef.html#alloca-instruction https://llvm.org/docs/LangRef.html#alloca-instruction > The ‘alloca’ instruction allocates memory on the stack frame of the currently executing function, to be automatically released when this function returns to its caller. If the address space is not explicitly specified, the object is allocated in the alloca address space from the datalayout string. -------- Based on my reading and understanding of alloca and mem2reg above, I have to disagree with your assessment. It seems like alloca roughly corresponds to a "push" in your typical x86 assembly language, or maybe a "add esp, #ofBytes". By removing alloca instructions, the mem2reg step is turning stack-memory into registers.
- woodruffw 5y ago
  > By removing alloca instructions, the mem2reg step is turning stack-memory into registers. This is true, but it's also misleading: the transformation of stack slots into machine registers is a beneficial side effect of mem2reg. Reducing stack use is an important optimization, but producing an optimal SSA form is even more important, since key passes like folding, DCE and SRoA rely heavily on the SSA form. The "reg" in "mem2reg" refers explicitly to the latter (SSA registers), as the text you've excerpted directly says. You can also prove this to yourself by contriving an IR function that contains more SSA registers than machine registers: you'll see that, in addition to any ABI constraints, LLVM will be forced to spill any excess SSA registers back onto the stack. Edit: but also yes, to confirm: `alloca` corresponds more or less directly to `add ESP, <adjust>` within the x86 stack model. But it doesn't have to! LLVM's semantics are target independent even when the IR isn't.

eatonphil 5y ago

The core simplification is due to LLVM's induction-detection step. Even after doing induction-based proofs in school, until reading this I had the sense that induction is kinda magical and kinda not real. I still cannot fathom how you can encode induction detection into an algorithm, any pointers welcome (keeping it simple, please, and ideally with working code). The only case that makes sense to me is if you did numeric computation against some fixed number of cases and if that worked out then you assume it's right. I guess this is what proof assistants do (among other things). Maybe I should look into how to write a basic proof assistant.

benmmurphy 5y ago
the induction step is pretty cool. it will remove the loop calculating the sum of an arithmetic progression and replace it with just multiplies/shifts/subtracts and adds.
contravariant 5y ago
Well in this case it seems reasonable that they simply added a rule for the specific line: even = !even and the line numberCompare++ resulting in even = (indvar & 1) numberCompare = indvar You can then solve from the exit condition that number == numberCompare, which gives you the indvar which can then be substituted into 'even'. I'm not saying it isn't magical, and certainly requires some symbolic solving, but it's doable. Of course the real goal is to eventually get it to optimize while (number != 1) { if (number & 1) number = number * 3 + 1 number >>= 1; }
- missblit 5y ago
  > Of course the real goal is to eventually get it to optimize `while (number != 1) { ... }` Valid C++ programs are guaranteed to be able to make forward progress [1]. So if `number` is a normal stack allocated integer (and not volatile, etc), then the infinite looping case is undefined behavior here. So it would be a valid optimization to transform this to `number = 1;`. (And indeed: https://godbolt.org/z/eodhfWe6h https://godbolt.org/z/eodhfWe6h ) [1] https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/language/memory_model

thrasumachos 5y ago

Nice that it even provides the right answer for negative numbers as undefined behavior but only when optimizations are enabled!

titzer 5y ago
Nice catch. One of many instances where C/C++ compilers rely on integer wraparound being UB.

martincmartin 5y ago

you get a linear time O(n) isEven function In complexity theory, the size of a problem is the number of bits to represent the input, so if the input integer is i, then the size is n = log_2(i) so the algorithm is actually exponential in the number of bits it takes to represent the input.

trias 5y ago
is complexity theory constrained to binary representations? Why should it?
- Ar-Curunir 5y ago
  Every base except unary is a constant-factor away from binary, and so is irrelevant asymptotically. We don't use unary because it's artificially slow.
  - creata 5y ago
    See also: https://medium.com/@veedrac/why-unary-is-the-best-number-system-cc1e0edfb928 https://medium.com/@veedrac/why-unary-is-the-best-number-sys...
    - Ar-Curunir 5y ago
      That post is a joke, right?
      - deleted 5y ago
        [deleted]
dragontamer 5y ago
In a strict sense, you're right. But in practice, you're not. Case in point: matrix multiplication is commonly quoted as O(n^3) (naive), when in fact, the amount of data used is O(n^2), and therefore should be quoted as O(size^2) (quadratic) with respect to data-size. (EDIT: was bad at math for a second). But no, people mean "n-by-n matrix" has "O(n^3) naive" implementation. In practice, the "n" is just whatever is most convenient for a problem. In many cases, n is proportional to the input size. But in other cases (such as the famous matrix multiplication examples), n is the sqrt(input-size).

ufo 5y ago

I'm very curious how it optimizes that recursive version at the end, because it is not tail recursive. Does anyone know? Perhaps it becomes tail recursive after one round of inlining?

pertymcpert 5y ago
It seems the TailRecursionElimination.cpp pass is responsible for that. It has some smarts to know that the xor instruction between the call and return can be turned into an "accumulator", although what exactly that means I'm unsure.
- ufo 5y ago
  Thanks for investigating that! An accumulator is when we add an extra parameter to hold the "loop variable", like this: bool doit(int n, bool acc) { if (n == 0) return acc; else return doit(n-1, !acc); } bool isEven(int n) { return doit(n, true); } The function is now tail-recursive and behaves similarly to this loop: bool acc = true; while (n != 0) { acc = !acc; n = n - 1; } return acc; According to the comment on the top of the file, apparently llvm can create this accumulator variable if the operation is associative and commutative. That's because after introducing the accumulator, the evaluation order is outside->inside instead of inside->outside.
- b3morales 5y ago
  Further reading about the relationship between recursion, iteration, and accumulators: https://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html https://blog.moertel.com/posts/2013-05-11-recursive-to-itera... This transformation is one you can apply in your own source as well. An example from that link, the recursive def factorial(n): if n < 2: return 1 return n * factorial(n - 1) can be rewritten iteratively: def factorial1d(n, acc=1): while n > 1: (n, acc) = (n - 1, acc * n) return acc

PostThisTooFast 5y ago

Nice hysterical, non-informative headline.

jagrsw 5y ago

O(n) isEven function compared to the obvious constant time O(1) modulo algorithm In the holy name of nitpickiness: the modulo operation is not always O(1), as div/mod CPU instructions have complex internal implementations and require varying number of cycles depending on what the input args are. However, for x%2 it'll be probably O(1), both on the cpu level, and b/c it'll get optimized to something like x&1 by most compilers (at least for unsigned values)

8192kjshad09- 5y ago
I will nitpick your nitpick. In a language with arbitrary size integers you're right. This is a C++ int, therefore 32/64 bits (in all sane cases, ik the spec doesn't specify), so the maximum number of cycles is upper bounded. Therefore modulo on C++ ints is is O(1).
- jagrsw 5y ago
  But having an upper bound doesn't make it O(1) automatically, no? It'd be like saying that Erastotenes' sieve is O(1) b/c for 64bit integers we know what upper exec time limit is? IMO id'd be rather creative use of current conventions around comp. complexity, but my knowledge of those topics is bad.
  - laszlokorte 5y ago
    big O() notation is simply not precise enough (and not meant to be) to be used in such nitpicky discussions. Everything is O(1) for a large anough constant, for example O(live time of the universe). There are other notations like small o(), Omega(), omega() or theta() to capture the asymtotic runtime behavior more or less precisely.
athrowaway3z 5y ago
It states "constant time O(1) modulo _algorithm_" for implementing an isEven function.