Loop fission and fusion

In computer science, loop fission (or loop distribution) is a compiler optimization in which a loop is broken into multiple loops over the same index range with each taking only a part of the original loop's body.[1][2] The goal is to break down a large loop body into smaller ones to achieve better utilization of locality of reference. This optimization is most efficient in multi-core processors that can split a task into multiple tasks for each processor.

Conversely, loop fusion (or loop jamming) is a compiler optimization and loop transformation which replaces multiple loops with a single one.[3][2] It is possible when two loops iterate over the same range and do not reference each other's data. Loop fusion does not always improve run-time speed. On some architectures, two loops may actually perform better than one loop because, for example, there is increased data locality within each loop.

Fusion

Example in C

 
  int i, a[100], b[100];
  for (i = 0; i < 100; i++)
    a[i] = 1;                     
  for (i = 0; i < 100; i++)
    b[i] = 2;

is equivalent to:

  int i, a[100], b[100];
  for (i = 0; i < 100; i++)
  {
    a[i] = 1; 
    b[i] = 2;
  }
gollark: Ah.
gollark: What? The only information I can find on rwasa is some random politician.
gollark: (also I may eventually want to use ARM)
gollark: On the one hand I do somewhat want to run osmarksforum™ with this for funlolz, but on the other hand handwritten ASM is probably not secure.
gollark: > Well, the answer is a good cause for flame war, but I will risk. ;) At first, I find assembly language much more readable than HLL languages and especially C-like languages with their weird syntax. > At second, all my tests show, that in real-life applications assembly language always gives at least 200% performance boost. The problem is not the quality of the compilers. It is because the humans write programs in assembly language very different than programs in HLL. Notice, that you can write HLL program as fast as an assembly language program, but you will end with very, very unreadable and hard for support code. In the same time, the assembly version will be pretty readable and easy for support. > The performance is especially important for server applications, because the program runs on hired hardware and you are paying for every second CPU time and every byte RAM. AsmBB for example can run on very cheap shared web hosting and still to serve hundreds of users simultaneously.

See also

References
  1. Y.N. Srikant; Priti Shankar (3 October 2018). The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition. CRC Press. ISBN 978-1-4200-4383-9.
  2. Kennedy, Ken & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
  3. Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2. loop fusion.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.