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

You can't fool the optimizer

xania.org

Post reply on HN
Print view View original

181–190 of 193 posts

Re: You can't fool the optimizer

#181

Post by zbentley »

manbitesdog wrote: post #27
qsort wrote: post #5

Earlier quoted context omitted.

> I always code with the mindset “the compiler is smarter than me.” Like with people in general, it depends on what compiler/interpreter we're talking about, I'll freely grant that clang is smarter than me, but CPython for sure isn't. :) More generally, canonicalization goes very far, but no farther than language semantics allows. Not even the notorious "sufficiently smart compiler" with infinite time can figure out…

To add to this, the low-level constraints also make this assumption noisy, no matter how smart the compiler is. On the CPython case, if you do `dis.dis('DAY = 24 * 60 * 60)` you will see that constant folding nicely converts it to `LOAD_CONST 86400`. However, if you try `dis.dis('ATOMS_IN_THE_WORLD = 10*50')` you will get LOAD_CONST 10, LOAD_CONST 50, BINARY_OP **.

> However, if you try `dis.dis('ATOMS_IN_THE_WORLD = 10*50')` you will get LOAD_CONST 10, LOAD_CONST 50...

I do not get that, I get LOAD_CONST 500.

Tested on: Python 3.9.3 MacOS (Apple provided), 3.13.3 (uv provided) MacOS and Linux, and 3.14.0 (uv provided) MacOS and Linux.

Re: You can't fool the optimizer

#182

Post by amai »

> This process of converting different code patterns into a standard, canonical form is what lets the compiler treat them all identically.

Wouldn‘t it be nice if we could transform back from the canonical form into the most readable code? In the example that would convert all functions into x + y.

Re: You can't fool the optimizer

#183

Post by valleyer »

1718627440 wrote: post #170
SpaceManNabs wrote: post #133

Earlier quoted context omitted.

> No, the compiler may assume that the behavior of standard library functions is standards-conformant. Why? What happens if it isn't?

What happens when you change random functions in your C compiler? The C standard library and compiler are not independent, both make up a C implementation, which behaviour is described by the C standard.

Yes, though it's worth stating that it's a little more nuanced than that, since (for historical, path-dependent reasons) the compiler and libc are often independent projects (and libc often includes a bunch of other stuff beyond what the standard/compiler need).

This is the case, for example, on macOS, FreeBSD, and Linux.

Cute username, BTW.

Re: You can't fool the optimizer

#184

Post by lmm »

1718627440 wrote: post #180
lmm wrote: post #178

Earlier quoted context omitted.

No-one's getting out of bed for 1.2x.

Depends. If you have a real-time system, that might very well will be what you chase after. Also why not make your program a bit faster when it is no work, by starting it the right way upfront. I mean I wouldn't rewrite a program for this, but when I program some new part and I can avoid an indirection, why not do it? Less complexity, less (failure) state, better performance.

> If you have a real-time system, that might very well will be what you chase after.

If you have a real-time system you care about the difference between real-time and not. But any given 1.2x factor is extremely unlikely to be the difference-maker.

> When I program some new part and I can avoid an indirection, why not do it? Less complexity, less (failure) state, better performance.

Well if it makes the code simpler then you should do it for that reason. But thinking about this kind of low-level performance detail at all will usually do more harm than good.

Re: You can't fool the optimizer

#185

Post by 1718627440 »

valleyer wrote: post #183
1718627440 wrote: post #170

Earlier quoted context omitted.

What happens when you change random functions in your C compiler? The C standard library and compiler are not independent, both make up a C implementation, which behaviour is described by the C standard.

Yes, though it's worth stating that it's a little more nuanced than that, since (for historical, path-dependent reasons) the compiler and libc are often independent projects (and libc often includes a bunch of other stuff beyond what the standard/compiler need). This is the case, for example, on macOS, FreeBSD, and Linux. Cute username, BTW.

You are right, it depends, whether you write C (from the standard) or a specific dialect from your vendor (everybody does in practice). In the latter case, you need to know about the rules of the compiler. But to allow optimization, these are often similar, so that the compiler assumes these have the behaviour of the implementation, that the compiler is tailored against.

> Cute username, BTW.

Thanks, I was to lazy to think of a real name, so this is the timestamp, I created the account.

Re: You can't fool the optimizer

#186

Post by 1718627440 »

lmm wrote: post #184
1718627440 wrote: post #180

Earlier quoted context omitted.

Depends. If you have a real-time system, that might very well will be what you chase after. Also why not make your program a bit faster when it is no work, by starting it the right way upfront. I mean I wouldn't rewrite a program for this, but when I program some new part and I can avoid an indirection, why not do it? Less complexity, less (failure) state, better performance.

> If you have a real-time system, that might very well will be what you chase after. If you have a real-time system you care about the difference between real-time and not. But any given 1.2x factor is extremely unlikely to be the difference-maker. > When I program some new part and I can avoid an indirection, why not do it? Less complexity, less (failure) state, better performance. Well if it makes the code simpler…

In languages that don't hide much (e.g heap allocations in Java), less complexity corresponds to better performance (up to a point). Because better performance is fundamentally about letting the computer do less work. When pointer indirection is explicit, the programmer is nudged towards thinking whether they actually want it. Same with dynamic dispatch, polymorphism and every other runtime complexity.

Re: You can't fool the optimizer

#187

Post by teworks »

lmm wrote: post #184
1718627440 wrote: post #180

Earlier quoted context omitted.

Depends. If you have a real-time system, that might very well will be what you chase after. Also why not make your program a bit faster when it is no work, by starting it the right way upfront. I mean I wouldn't rewrite a program for this, but when I program some new part and I can avoid an indirection, why not do it? Less complexity, less (failure) state, better performance.

> If you have a real-time system, that might very well will be what you chase after. If you have a real-time system you care about the difference between real-time and not. But any given 1.2x factor is extremely unlikely to be the difference-maker. > When I program some new part and I can avoid an indirection, why not do it? Less complexity, less (failure) state, better performance. Well if it makes the code simpler…

I know games are constantly brought up as an example, but it's for good reason. Your frametime being 16.6ms instead of 20ms is the difference between a shipped feature and a cut one in a console title. And all the data and instruction cache thrashing caused by pointer chasing can (and does) absolutely make that difference.

Re: You can't fool the optimizer

#188

Post by senfiaj »

1718627440 wrote: post #174
senfiaj wrote: post #77

Earlier quoted context omitted.

So you claim that the compiler "knows about this but doesn't optimize because of some safety measures"? As far as I remember, compilers don't optimize math expressions / brackets, probably because the order of operations might affect the precision of ints/floats, also because of complexity. But my example is trivial (x % 2 == 0 && x % 3 == 0 is exactly the same as x % 6 == 0 for all C/C++ int), yet the compiler produ…

> the order of operations might affect the precision of ints/floats That's only the problem of floats, with ints this issue doesn't exist. Why do you write (x % 2 == 0 && x % 3 == 0) instead of (x % 2 == 0 & x % 3 == 0), when the latter is what you think you mean? Are you sure, that dividing by 6 is actually faster, than dividing by 2 and 3? A division operation is quite costly compared to other arithmetic and 2 and…

> That's only the problem of floats, with ints this issue doesn't exist.

With ints the results can be dramatically different (often even worse than floats) even though in pure mathematics the order doesn't matter:

  1 * 2 * 3 * 4 / 8 --> 3
  3 * 4 / 8 * 1 * 2 --> 2
This is a trivial example, but it shows why it's extremely hard for compilers to optimize expressions and why they usually leave this task to humans.

But x % 2 == 0 && x % 3 == 0 isn't such case, swapping operands of && has no side effects, nor swapping operands of each ==.

> Are you sure, that dividing by 6 is actually faster

Compilers usually transform divisions into multiplications when the denominator is a constant.

I wrote another example in other comment but I'll write again.

I also tried this

  bool is_divisible_by_15(int x) {
      return x % 3 == 0 && x % 5 == 0;
  }

  bool is_divisible_by_15_optimal(int x) {
      return x % 15 == 0;
  }
is_divisible_by_15 still has a branch, while is_divisible_by_15_optimal does not

  is_divisible_by_15(int):
        imul    eax, edi, -1431655765
        add     eax, 715827882
        cmp     eax, 1431655764
        jbe     .LBB0_2
        xor     eax, eax
        ret
  .LBB0_2:
        imul    eax, edi, -858993459
        add     eax, 429496729
        cmp     eax, 858993459
        setb    al
        ret

  is_divisible_by_15_optimal(int):
        imul    eax, edi, -286331153
        add     eax, 143165576
        cmp     eax, 286331153
        setb    al
        ret
My point is that the compiler still doesn't notice that 2 functions are equivalent. Even when choosing 3 and 5 (to eliminate the questionable bit check trick for 2) the 1st function appears less optimal (more code + branch).

Re: You can't fool the optimizer

#189

Post by manbitesdog »

zbentley wrote: post #181
manbitesdog wrote: post #27

Earlier quoted context omitted.

To add to this, the low-level constraints also make this assumption noisy, no matter how smart the compiler is. On the CPython case, if you do `dis.dis('DAY = 24 * 60 * 60)` you will see that constant folding nicely converts it to `LOAD_CONST 86400`. However, if you try `dis.dis('ATOMS_IN_THE_WORLD = 10*50')` you will get LOAD_CONST 10, LOAD_CONST 50, BINARY_OP **.

> However, if you try `dis.dis('ATOMS_IN_THE_WORLD = 10*50')` you will get LOAD_CONST 10, LOAD_CONST 50... I do not get that, I get LOAD_CONST 500. Tested on: Python 3.9.3 MacOS (Apple provided), 3.13.3 (uv provided) MacOS and Linux, and 3.14.0 (uv provided) MacOS and Linux.

Sorry, I meant 10**50; HN formatting removed one asterisk

Re: You can't fool the optimizer

#190

Post by 1718627440 »

senfiaj wrote: post #188
1718627440 wrote: post #174

Earlier quoted context omitted.

> the order of operations might affect the precision of ints/floats That's only the problem of floats, with ints this issue doesn't exist. Why do you write (x % 2 == 0 && x % 3 == 0) instead of (x % 2 == 0 & x % 3 == 0), when the latter is what you think you mean? Are you sure, that dividing by 6 is actually faster, than dividing by 2 and 3? A division operation is quite costly compared to other arithmetic and 2 and…

> That's only the problem of floats, with ints this issue doesn't exist. With ints the results can be dramatically different (often even worse than floats) even though in pure mathematics the order doesn't matter: 1 * 2 * 3 * 4 / 8 --> 3 3 * 4 / 8 * 1 * 2 --> 2 This is a trivial example, but it shows why it's extremely hard for compilers to optimize expressions and why they usually leave this task to humans. But x %…

> in pure mathematics the order doesn't matter

I don't perceive that as an ordering issue. "Pure mathematics" has multiple division definitions, what we see here is the definition you use in class 1: integer division. The issue here is not associativity, it is that the inverse of an integer division is NOT integer multiplication, the inverse of division is the sum of multiplication and the modulo. Integer division is a information destroying operation.

> I wrote another example in other comment but I'll write again. [...]

Yes, this is because optimizing compilers are not optimizers in the mathematical sense, but heuristics and sets of folk wisdoms. This doesn't make them any less impressive.

Post reply on HN