3 ms·

> Please show us some of these promised optimizations. I don't think they actually exist. I already gave two examples: "removing redundant elements from struct

> Please show us some of these promised optimizations. I don't think they actually exist. I already gave two examples: "removing redundant elements from struct definitions all the way down to bitshift optimizations like i * 28 == i<<4 + i<<3 + i<<2". Neither of those optimizations are used by mainstream compilers, although it is possible that LLVM might include some optimizations like the latter due to work from the Souper project. > Most of the larger code / algorithm tweaks require subtle changes to the behaviour. The compiler can't choose to do that by itself, as it could break the program. Programmers need to make these choices for themselves. If it introduces a bug, then it is not an optimization, and it has no business being included in an optimizer (at least without explicit flags like -ffast-math). > Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize compile time if they wish. There are plenty of people who would give anything for faster code, no matter what the compile time is. My whole point is that -O3 is still weak sauce. There are tons of compiler optimizations that are excluded from both GCC and LLVM because of fears of compilation time impacts. Take a look at the specific techniques section of this wiki article: https://en.wikipedia.org/wiki/Optimizing_compiler https://en.wikipedia.org/wiki/Optimizing_compiler I can guarantee you that the mainstream C compilers cover maybe half of those, and for lesser known languages far less than half.

roel_v 11y ago
"removing redundant elements from struct definitions" When is an element in a struct definition 'redundant'? Let's say I write a struct to a network socket, and my receiver (on the other side of the socket) expects a certain memory layout. But one of the fields isn't used in my code (but maybe it is by another program that uses the same header, like two programs that share a library with common data types). How would that work? I just don't understand what you're saying.
- Retra 11y ago
  I don't know what OP meant, but I could see some potential advantage to removeing fields from structs at interfaces. Say you have a loop that goes over a million structs, but only accesses one field. Drop the extras, do the loop, then add them back. Though it would probably take more time to rearrange things than it would to just do the original loop. The point is, you might be able to look at where the struct is used and change its structure when it moves in memory. If a function is a 'consumer' of structs, and doesn't need all the fields, there is no need to copy all the fields.
  - roel_v 11y ago
    "Say you have a loop that goes over a million structs, but only accesses one field. Drop the extras, do the loop, then add them back." Why? Why would you copy at all? Are you saying that with small structs you'll be able to fit more of your data into caches? I haven't timed it (anyone have 20 minutes to spare?) but then you have to make full copy, very expensive not to mention having major implications on memory usage. If my compiler would do that under the hood, even when set to 'optimize for speed', I'd be pretty annoyed. The only way to know if such a thing is faster, is by looking at each use specifically - at which point we're not talking about a compiler anymore. Well ok we'd be talking about "runtime pgo", and approaching JIT territory. Furthermore, such an 'optimization' would also have to, e.g., detect offsetof() and make sure that that works correctly, and account for packing and people relying on that, and unions, etc etc. I'm not going to spend much time here further on examining and deconstructing this whole concept, especially as I still fail to comprehend the goal.
fanf2 11y ago
Those kinds of bitshift optimizations have been basic for 25 years or more. Read Hacker's Delight by Henry Warren for hundreds of pages of this kind of standard compiler technique.
joosters 11y ago
> i * 28 == i<<4 + i<<3 + i<<2 gcc will do these kind of optimizations, when they make sense. But for 28, most processors will actually be faster doing the multiply. Multiply instructions only take a few clock cycles. A sequence of adds and shifts can also be slower because they are a sequence of dependent instructions - you need the result of the first one to calculate the next. (You can do some of the adds in parallel, but you still need to total them up) Here's some old data for an ancient ARM9 processor - http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0091a/BEIEDGJJ.html http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.... - it takes 2-5 cycles for a MUL (3 for a MUL of 28), compared with 1 for an ADD, 2 for an ADD with shift. So your 'optimization' would take 6 cycles on an ARM 9, while the MUL takes 3. It's really easy to double check this. Compile this dumb code with 'gcc -s -O3 test.c' #include <stdio.h> int main(int argc, char *argv[]) { int i = argc; printf("%d\n", i*28); return 0; } Try changing the 28 to different values and run a diff against each version (e.g. try 8, 9 and 10). On x86, gcc will use a variety of techniques based upon the multiplier.
- lorenzhs 11y ago
  it's even easier to play around with these things using https://gcc.godbolt.org https://gcc.godbolt.org

roel_v 11y ago

"removing redundant elements from struct definitions" When is an element in a struct definition 'redundant'? Let's say I write a struct to a network socket, and my receiver (on the other side of the socket) expects a certain memory layout. But one of the fields isn't used in my code (but maybe it is by another program that uses the same header, like two programs that share a library with common data types). How would that work? I just don't understand what you're saying.

Retra 11y ago
I don't know what OP meant, but I could see some potential advantage to removeing fields from structs at interfaces. Say you have a loop that goes over a million structs, but only accesses one field. Drop the extras, do the loop, then add them back. Though it would probably take more time to rearrange things than it would to just do the original loop. The point is, you might be able to look at where the struct is used and change its structure when it moves in memory. If a function is a 'consumer' of structs, and doesn't need all the fields, there is no need to copy all the fields.
- roel_v 11y ago
  "Say you have a loop that goes over a million structs, but only accesses one field. Drop the extras, do the loop, then add them back." Why? Why would you copy at all? Are you saying that with small structs you'll be able to fit more of your data into caches? I haven't timed it (anyone have 20 minutes to spare?) but then you have to make full copy, very expensive not to mention having major implications on memory usage. If my compiler would do that under the hood, even when set to 'optimize for speed', I'd be pretty annoyed. The only way to know if such a thing is faster, is by looking at each use specifically - at which point we're not talking about a compiler anymore. Well ok we'd be talking about "runtime pgo", and approaching JIT territory. Furthermore, such an 'optimization' would also have to, e.g., detect offsetof() and make sure that that works correctly, and account for packing and people relying on that, and unions, etc etc. I'm not going to spend much time here further on examining and deconstructing this whole concept, especially as I still fail to comprehend the goal.

fanf2 11y ago

Those kinds of bitshift optimizations have been basic for 25 years or more. Read Hacker's Delight by Henry Warren for hundreds of pages of this kind of standard compiler technique.

joosters 11y ago

> i * 28 == i<<4 + i<<3 + i<<2 gcc will do these kind of optimizations, when they make sense. But for 28, most processors will actually be faster doing the multiply. Multiply instructions only take a few clock cycles. A sequence of adds and shifts can also be slower because they are a sequence of dependent instructions - you need the result of the first one to calculate the next. (You can do some of the adds in parallel, but you still need to total them up) Here's some old data for an ancient ARM9 processor - http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0091a/BEIEDGJJ.html http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.... - it takes 2-5 cycles for a MUL (3 for a MUL of 28), compared with 1 for an ADD, 2 for an ADD with shift. So your 'optimization' would take 6 cycles on an ARM 9, while the MUL takes 3. It's really easy to double check this. Compile this dumb code with 'gcc -s -O3 test.c' #include <stdio.h> int main(int argc, char *argv[]) { int i = argc; printf("%d\n", i*28); return 0; } Try changing the 28 to different values and run a diff against each version (e.g. try 8, 9 and 10). On x86, gcc will use a variety of techniques based upon the multiplier.

lorenzhs 11y ago
it's even easier to play around with these things using https://gcc.godbolt.org https://gcc.godbolt.org