What’s wrong with using associativity by compilers?

by

Here is how I understand your two cases: In the first case, you have a loop that takes N steps; in the second case you manually merged two consecutive iterations of the first case into one, so you only need to do N/2 steps in the second case. Your second case runs faster and you are wondering why the dumb compiler couldn’t do it automatically.

There is nothing that would prevent the compiler from doing such an optimization. But please note that this re-write of the original loop leads to larger executable size: You have more instructions inside the for loop and the additional if after the loop.
If N=1 or N=3, the original loop is likely to be faster (less branching and better caching/prefetching/branch prediction). It made things faster in your case but it may make things slower in other cases. It is not a clear cut whether it is worth doing this optimization and it can be highly nontrivial to implement such an optimization in a compiler.

By the way, what you have done is very similar to loop vectorization but in your case, you did the parallel step manually and plugged-in the result. Eric Brumer’s Compiler Confidential talk will give you insight why rewriting loops in general is tricky and what drawbacks / disadvantages there are (larger executable size, potentially slower in some cases). So compiler writers are very well aware of this optimization possibility and are actively working on it but it is highly nontrivial in general and can also make things slower.

Please try something for me:

int a = 0;
for (int i=0; i<N; ++i) 
  a = ((a<<5) - a) + t[i];

assuming M1=31. In principle, the compiler should be smart enough to rewrite 31*a into (a<<5)-a but I am curious if it really does that.

More Related Contents:

  1. What is GCC and minGW, and how are they related to C++ ?
  2. Java Reflection Performance
  3. Swing animation running extremely slow
  4. Efficiently compute Intersection of two Sets in Java?
  5. What is more efficient, i++ or ++i? [duplicate]
  6. Java local vs instance variable access speed
  7. Java HashMap performance optimization / alternative
  8. Is the ternary operator faster than an “if” condition in Java [duplicate]
  9. Most efficient way of converting String to Integer in java
  10. fastest (low latency) method for Inter Process Communication between Java and C/C++
  11. Why defining class as final improves JVM performance?
  12. Fastest way to strip all non-printable characters from a Java String
  13. Java split String performances
  14. Is there a memory-efficient replacement of java.lang.String?
  15. Hashmap vs Array performance
  16. Java equivalent to C++ arrow [closed]
  17. java vs C++ in pre and post increment
  18. Declaring variables inside or outside of a loop
  19. Why does the order of the loops affect performance when iterating over a 2D array?
  20. Does use of final keyword in Java improve the performance?
  21. Why is creating a Thread said to be expensive?
  22. Java: what’s the big-O time of declaring an array of size n?
  23. What’s the best way to implement `next` and `previous` on an enum type?
  24. Performance difference between Java 8 lambdas and anonymous inner classes
  25. Know of any Java garbage collection log analysis tools? [closed]
  26. Does a c/c++ compiler optimize constant divisions by power-of-two value into shifts?
  27. What is the quantitative overhead of making a JNI call?
  28. ArrayList vs. Vectors in Java if thread safety isn’t a concern
  29. Algorithm – How to delete duplicate elements in a list efficiently?
  30. Convert static windows library to dll

Leave a Comment