HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
intoloopoptimizationtwoprogramdataoverthearecombined

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#134413, answer score: 18

Revisions (0)

No revisions yet.