10
$\begingroup$

On an imperative programming language, let us consider the following program:

for i in 0..N { // N is the length of the arrays A, B, C.
  A[i] = A[i] + B[i];
}
for i in 0..N {
  A[i] = A[i] + C[i];
}

This program just sums three arrays $A + B + C$ component-wisely and store it to $A$.

We can easily transform this program into the following equivalent one:

for i in 0..N {
  let tmp = A[i] + B[i];
  A[i] = tmp + C[i];
}

I think the latter code is more efficient than the former because we can decrease the number of memory accesses.

Now I have a question.

What is the name of this type of program transform or program optimization? Can we also call this deforestation?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I'm not clear on why tmp is needed. $\endgroup$
    – Acccumulation
    Jan 17, 2021 at 7:10
  • $\begingroup$ Note that for floating point numbers, those two programs are no longer equivalent. As such kinds of loops over floating point arrays are common in scientific computing, it's important to understand the implications. Just in case you're wondering, why a compiler might refuse to apply this and other similar optimizations to some of your loops. $\endgroup$
    – ComicSansMS
    Jan 17, 2021 at 8:56
  • $\begingroup$ @ComicSansMS Interesting! Do you mean that, in general (for floating point numbers), there maybe exist an index $i$ such that $A[i] \text{(of the former)} \neq A[i] \text{(of the latter)}$? Would you explain how such a situation happens? $\endgroup$
    – yuezato
    Jan 17, 2021 at 16:23
  • 1
    $\begingroup$ @yuezato Apologies, I misread your example and thought there was a change in associativity of the operations (which would trigger the difficulties for floats), but that is not the case. I withdraw my earlier comment, sorry for the confusion. The example presented here would only be problematic if the compiler were to perform the float addition with a different precision (such as using a fused-3-way-add in the second loop, or keeping the results in an extended precision register), but that will not happen unless you take explicit measures to allow this kind of optimization. $\endgroup$
    – ComicSansMS
    Jan 17, 2021 at 16:48
  • 1
    $\begingroup$ @ComicSansMS Thank you for your kindly comment! I've understood. In a similar code, when a compiler translates $A[i] \gets A[i] + B[i]; A[i] \gets A[i] \times C[i]$ to $A[i] \gets \text{FMA}(A[i], B[i], C[i])$, where FMA is a Fused Multiply-Add, then the results maybe are different due to floating-point precision errors. Also, if $A[i] \gets A[i] + B[i]; A[i] \gets A[i] + C[i]$ is translated to $A[i] \gets A[i] + (B[i] + C[i])$, then they maybe are different due to the lack of associativity. $\endgroup$
    – yuezato
    Jan 18, 2021 at 5:29

1 Answer 1

Reset to default
18
$\begingroup$

It's called "loop fusion".

It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in your example may also put more pressure on the CPU's cache prefetch system. So do test it before declaring it more efficient.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Thank you! By googling with the term "loop fusion", I can find a nice paper csc.lsu.edu/lcpc05/papers/lcpc05-paper-05.pdf . It treats performance degradation caused by cache-conflicts that are introduced by loop fusion. $\endgroup$
    – yuezato
    Jan 16, 2021 at 13:02
  • 5
    $\begingroup$ Generally speaking, loop fusion can also increase register pressure and prevent vectorization (neither of those effects would likely apply to the example above though!). It's certainly a useful optimization, but not a be-all and end-all, just like most other optimizations. $\endgroup$
    – undercat
    Jan 16, 2021 at 14:18
  • 4
    $\begingroup$ Also worth noting that the reverse of this is considered a type of refactoring called split loop in the Martin Fowler refactoring book: refactoring.com/catalog/splitLoop.html. $\endgroup$
    – mowwwalker
    Jan 17, 2021 at 16:23
  • 1
    $\begingroup$ I always thought this was called “Loop Jamming”. I remember reading a book on Bliss compiler optimizations from the early 80’s where they used this terminology. $\endgroup$
    – RBarryYoung
    Jan 17, 2021 at 17:49
  • $\begingroup$ @mowwalker That might be a good name for it as a refactoring. As a compiler optimisation, it's "loop fission". $\endgroup$
    – Pseudonym ♦
    Jan 17, 2021 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.