patternModerate
What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?
Viewed 0 times
intoloopoptimizationtwoprogramdataoverthearecombined
Problem
On an imperative programming language, let us consider the following program:
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:
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?
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.
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.