3 ms·

Please show us some of these promised optimizations. I don't think they actually exist. Most of the larger code / algorithm tweaks require subtle changes to the

Please show us some of these promised optimizations. I don't think they actually exist. 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. 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. Please prove me wrong and explain a few of these supposed too-slow optimizations.

johncolanduoni 11y ago
Not the OP, but one I think about a lot is converting functional, monadic code that uses first class functions/closures to equivalent imperative variants. For example, manipulating collections with functions like map, flatMap, filter, etc. has become common, even in popular imperative languages like C# and Java. These calls are can be chained together to create non-strict sequences (IEnumerable, Stream, etc.) which are made strict at a later time. Each call creates a new sequence, and many take closures. Both of these require memory allocation and indirect dispatch. However, in many cases it extremely straightforward to convert these into loops. For example, the following C# code: list.Select(f).Where(p).SelectMany(g).ToList() Could be turned into: var outList = new List<T>(); foreach(var x in list) { var y = f(x); if(!p(y)) continue; foreach(var z in g(y)) { outList.Add(z) } } This works, even if we known nothing about f, p, and g (e.g. they can be impure functions). This optimization is especially effective if these functions are lambdas. It is also always going to be faster and safe; the only difference is that we removed a series of extra allocations and indirect function calls. This example is admittedly simple, but many functional patterns and behaviors can be rewritten into longer imperative variants that avoid extra allocations. You are right that you can have subtle changes in behavior with similar high level optimizations. For example, most functional languages make calls like these actually create a new collection at each call. If any of these functions can throw and exception or cause an effect, then we cannot perform the above rewriting because if will call the functions out of order. But if a compiler can take the time to analyze functions for external purity, these can be optimized as well.
- kibwen 11y ago
  Your example doesn't necessarily bolster this thread's original point, because compiler backends are already sophisticated enough to apply this sort of transformation regularly (e.g. you'll see this sort of code generated in Rust, where closures are stack-allocated, iterators are lazy and single-pass, and the resulting loops can even be vectorized).
  - johncolanduoni 11y ago
    You're absolutely right, I chose a simple example because it's one I expect most people have seen in one language or another. A better one would be rewriting a combinator based parser (e.g. one written in Parsec) into an imperative one.
    - lunchTime42 11y ago
      Dont you cave in blindly believing into the infoscience gods of old having done good. Demand profile logs, demand numbers, demand evidence. Compilers do the most utterly unexpected nonsense, forget the most trivial optimisations. Take your code to https://gcc.godbolt.org/ https://gcc.godbolt.org/ and read what your "Compiler-knows-best" does with your code. yes, it doesent matter often in the end, cause even bad code must wait for worser memory, but still..
      - joosters 11y ago
        Could you give an example of 'forgetting the most trivial optimizations' please? It would be a bug in a compiler and many people would be interested in fixing it.
saosebastiao 11y ago
> 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.

johncolanduoni 11y ago

Not the OP, but one I think about a lot is converting functional, monadic code that uses first class functions/closures to equivalent imperative variants. For example, manipulating collections with functions like map, flatMap, filter, etc. has become common, even in popular imperative languages like C# and Java. These calls are can be chained together to create non-strict sequences (IEnumerable, Stream, etc.) which are made strict at a later time. Each call creates a new sequence, and many take closures. Both of these require memory allocation and indirect dispatch. However, in many cases it extremely straightforward to convert these into loops. For example, the following C# code: list.Select(f).Where(p).SelectMany(g).ToList() Could be turned into: var outList = new List<T>(); foreach(var x in list) { var y = f(x); if(!p(y)) continue; foreach(var z in g(y)) { outList.Add(z) } } This works, even if we known nothing about f, p, and g (e.g. they can be impure functions). This optimization is especially effective if these functions are lambdas. It is also always going to be faster and safe; the only difference is that we removed a series of extra allocations and indirect function calls. This example is admittedly simple, but many functional patterns and behaviors can be rewritten into longer imperative variants that avoid extra allocations. You are right that you can have subtle changes in behavior with similar high level optimizations. For example, most functional languages make calls like these actually create a new collection at each call. If any of these functions can throw and exception or cause an effect, then we cannot perform the above rewriting because if will call the functions out of order. But if a compiler can take the time to analyze functions for external purity, these can be optimized as well.

kibwen 11y ago
Your example doesn't necessarily bolster this thread's original point, because compiler backends are already sophisticated enough to apply this sort of transformation regularly (e.g. you'll see this sort of code generated in Rust, where closures are stack-allocated, iterators are lazy and single-pass, and the resulting loops can even be vectorized).
- johncolanduoni 11y ago
  You're absolutely right, I chose a simple example because it's one I expect most people have seen in one language or another. A better one would be rewriting a combinator based parser (e.g. one written in Parsec) into an imperative one.
  - lunchTime42 11y ago
    Dont you cave in blindly believing into the infoscience gods of old having done good. Demand profile logs, demand numbers, demand evidence. Compilers do the most utterly unexpected nonsense, forget the most trivial optimisations. Take your code to https://gcc.godbolt.org/ https://gcc.godbolt.org/ and read what your "Compiler-knows-best" does with your code. yes, it doesent matter often in the end, cause even bad code must wait for worser memory, but still..
    - joosters 11y ago
      Could you give an example of 'forgetting the most trivial optimizations' please? It would be a bug in a compiler and many people would be interested in fixing it.

saosebastiao 11y ago

> 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.