Loop fission and fusion

Loop fission (or loop distribution) is a <a href="/facts/Compiler_optimization/JXnv4LUd">compiler optimization</a> in which a <a href="/facts/Loop_(computing)/2XTDfErC">loop</a> is broken into multiple loops over the same index range with each taking only a part of the original loop's body. The goal is to break down a large loop body into smaller ones to achieve better utilization of <a href="/facts/Locality_of_reference/fYFKDv5q">locality of reference</a>. This optimization is most efficient in <a href="/facts/Multi-core_processor/ABNb65hQ">multi-core processors</a> that can split a task into multiple tasks for each <a href="/facts/Computer_processor/Jxp1bqMV">processor</a>.
Conversely, loop fusion (or loop jamming) is a <a href="/facts/Compiler_optimization/JXnv4LUd">compiler optimization</a> and <a href="/facts/Loop_transformation/2eFKIg32">loop transformation</a> which replaces multiple <a href="/facts/Control_flow/2XTDfErC">loops</a> with a single one. Loop fusion does not always improve run-time speed. On some <a href="/facts/Computer_architectures/tHtwxgR2">architectures</a>, two loops may actually perform better than one loop because, for example, there is increased <a href="/facts/Data_locality/fYFKDv5q">data locality</a> within each loop. One of the main benefits of loop fusion is that it allows temporary allocations to be avoided, which can lead to huge performance gains in numerical computing languages such as <a href="/facts/Julia_(programming_language)/AoB0PJ9C">Julia</a> when doing elementwise operations on arrays (however, Julia's loop fusion is not technically a compiler optimization, but a syntactic guarantee of the language). 
Other benefits of loop fusion are that it avoids the overhead of the loop control structures, and also that it allows the loop body to be parallelized by the processor by taking advantage of <a href="/facts/Instruction-level_parallelism/2W8qvN8K">instruction-level parallelism</a>. This is possible when there are no data dependencies between the bodies of the two loops (this is in stark contrast to the other main benefit of loop fusion described above, which only presents itself when there are data dependencies that require an intermediate allocation to store the results). If loop fusion is able to remove redundant allocations, performance increases can be large. Otherwise, there is a more complex trade-off between data locality, instruction-level parallelism, and loop overhead (branching, incrementing, etc.) that may make loop fusion, loop fission, or neither, the preferable optimization.

Loop fission and fusion open-in-new

Loop fission and fusion