Performance-Aware Loops

Loop Order Shape

Match the Array Layout

Fortran arrays are column-major, so loop order is part of performance-aware design even when no elapsed-time measurement is run.

Program

Play the program to choose a traversal shape and see the same grid summarized with different visit patterns.

order_mode
loop_order_shape.f90
Replay: real traced execution (multi-file project)
program loop_order_shape_demo
    implicit none
    integer :: grid(2, 3)
    integer :: order_mode
    integer :: row
    integer :: col
    integer :: visits
    integer :: total
    character(len=12) :: order_name

    grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])
    order_mode = 1
    visits = 0
    total = 0
    if (order_mode == 1) then
        order_name = 'column'
        do col = 1, 3
            do row = 1, 2
                visits = visits + 1
                total = total + grid(row, col)
            end do
        end do
    else if (order_mode == 2) then
        order_name = 'row'
        do row = 1, 2
            do col = 1, 3
                visits = visits + 1
                total = total + grid(row, col)
            end do
        end do
    else
        order_name = 'sample'
        do col = 1, 3
            row = 1 + mod(col + 1, 2)
            visits = visits + 1
            total = total + grid(row, col)
        end do
    end if
    print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total
end program loop_order_shape_demo

program loop_order_shape_demo
    implicit none
    integer :: grid(2, 3)
    integer :: order_mode
    integer :: row
    integer :: col
    integer :: visits
    integer :: total
    character(len=12) :: order_name

    grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])
    order_mode = 2
    visits = 0
    total = 0
    if (order_mode == 1) then
        order_name = 'column'
        do col = 1, 3
            do row = 1, 2
                visits = visits + 1
                total = total + grid(row, col)
            end do
        end do
    else if (order_mode == 2) then
        order_name = 'row'
        do row = 1, 2
            do col = 1, 3
                visits = visits + 1
                total = total + grid(row, col)
            end do
        end do
    else
        order_name = 'sample'
        do col = 1, 3
            row = 1 + mod(col + 1, 2)
            visits = visits + 1
            total = total + grid(row, col)
        end do
    end if
    print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total
end program loop_order_shape_demo

program loop_order_shape_demo
    implicit none
    integer :: grid(2, 3)
    integer :: order_mode
    integer :: row
    integer :: col
    integer :: visits
    integer :: total
    character(len=12) :: order_name

    grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])
    order_mode = 3
    visits = 0
    total = 0
    if (order_mode == 1) then
        order_name = 'column'
        do col = 1, 3
            do row = 1, 2
                visits = visits + 1
                total = total + grid(row, col)
            end do
        end do
    else if (order_mode == 2) then
        order_name = 'row'
        do row = 1, 2
            do col = 1, 3
                visits = visits + 1
                total = total + grid(row, col)
            end do
        end do
    else
        order_name = 'sample'
        do col = 1, 3
            row = 1 + mod(col + 1, 2)
            visits = visits + 1
            total = total + grid(row, col)
        end do
    end if
    print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total
end program loop_order_shape_demo

  1. grid ← [[1, 3, 5], [2, 4, 6]]

    11grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])12order_mode = 1
    values this step[[1, 3, 5], [2, 4, 6]]grid

  2. order_mode ← 1

    11grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])12order_mode = 113visits = 0
    values this step1order_mode

  3. visits ← 0

    12order_mode = 113visits = 014total = 0
    values this step0visits

  4. total ← 0

    13visits = 014total = 015if (order_mode == 1) then
    values this step0total

  5. order_name ← column

    15if (order_mode == 1) then16    order_name = 'column'17    do col = 1, 3
    values this stepcolumnorder_name

  6. visits ← 1

    18do row = 1, 219    visits = visits + 120    total = total + grid(row, col)
    values this step0 → 1visits1col1row

  7. total ← 1

    19    visits = visits + 120    total = total + grid(row, col)21end do
    values this step0 → 1total1grid(row,col)

  8. visits ← 2

    18do row = 1, 219    visits = visits + 120    total = total + grid(row, col)
    values this step1 → 2visits1col2row

  9. total ← 3

    19    visits = visits + 120    total = total + grid(row, col)21end do
    values this step1 → 3total2grid(row,col)

  10. visits ← 6

    18do row = 1, 219    visits = visits + 120    total = total + grid(row, col)
    values this step2 → 6visits2..3col1..2row

  11. total ← 21

    19    visits = visits + 120    total = total + grid(row, col)21end do
    values this step3 → 21total3,4,5,6remaining values

  12. print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total

    38    end if39    print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total40end program loop_order_shape_demo
    outputcolumn 6 21
    values this stepcolumnorder_name6visits21total

  1. grid ← [[1, 3, 5], [2, 4, 6]]

    11grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])12order_mode = 2
    values this step[[1, 3, 5], [2, 4, 6]]grid

  2. order_mode ← 2

    11grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])12order_mode = 213visits = 0
    values this step2order_mode

  3. visits ← 0

    12order_mode = 213visits = 014total = 0
    values this step0visits

  4. total ← 0

    13visits = 014total = 015if (order_mode == 1) then
    values this step0total

  5. order_name ← row

    23else if (order_mode == 2) then24    order_name = 'row'25    do row = 1, 2
    values this steproworder_name

  6. visits ← 1

    26do col = 1, 327    visits = visits + 128    total = total + grid(row, col)
    values this step0 → 1visits1row1col

  7. total ← 1

    27    visits = visits + 128    total = total + grid(row, col)29end do
    values this step0 → 1total1grid(row,col)

  8. visits ← 2

    26do col = 1, 327    visits = visits + 128    total = total + grid(row, col)
    values this step1 → 2visits1row2col

  9. total ← 4

    27    visits = visits + 128    total = total + grid(row, col)29end do
    values this step1 → 4total3grid(row,col)

  10. visits ← 6

    26do col = 1, 327    visits = visits + 128    total = total + grid(row, col)
    values this step2 → 6visitsremainingrow/col

  11. total ← 21

    27    visits = visits + 128    total = total + grid(row, col)29end do
    values this step4 → 21total5,2,4,6remaining values

  12. print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total

    38    end if39    print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total40end program loop_order_shape_demo
    outputrow 6 21
    values this steproworder_name6visits21total

  1. grid ← [[1, 3, 5], [2, 4, 6]]

    11grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])12order_mode = 3
    values this step[[1, 3, 5], [2, 4, 6]]grid

  2. order_mode ← 3

    11grid = reshape([1, 2, 3, 4, 5, 6], [2, 3])12order_mode = 313visits = 0
    values this step3order_mode

  3. visits ← 0

    12order_mode = 313visits = 014total = 0
    values this step0visits

  4. total ← 0

    13visits = 014total = 015if (order_mode == 1) then
    values this step0total

  5. order_name ← sample

    31else32    order_name = 'sample'33    do col = 1, 3
    values this stepsampleorder_name

  6. row ← 1

    33do col = 1, 334    row = 1 + mod(col + 1, 2)35    visits = visits + 1
    values this step1row1col

  7. visits ← 1

    34row = 1 + mod(col + 1, 2)35visits = visits + 136total = total + grid(row, col)
    values this step0 → 1visits

  8. total ← 1

    35    visits = visits + 136    total = total + grid(row, col)37end do
    values this step0 → 1total1grid(row,col)

  9. row ← 2

    33do col = 1, 334    row = 1 + mod(col + 1, 2)35    visits = visits + 1
    values this step2row2col

  10. visits ← 2

    34row = 1 + mod(col + 1, 2)35visits = visits + 136total = total + grid(row, col)
    values this step1 → 2visits

  11. total ← 5

    35    visits = visits + 136    total = total + grid(row, col)37end do
    values this step1 → 5total4grid(row,col)

  12. row ← 1

    33do col = 1, 334    row = 1 + mod(col + 1, 2)35    visits = visits + 1
    values this step1row3col

  13. visits ← 3

    34row = 1 + mod(col + 1, 2)35visits = visits + 136total = total + grid(row, col)
    values this step2 → 3visits

  14. total ← 10

    35    visits = visits + 136    total = total + grid(row, col)37end do
    values this step5 → 10total5grid(row,col)

  15. print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total

    38    end if39    print '(A, 1X, I0, 1X, I0)', trim(order_name), visits, total40end program loop_order_shape_demo
    outputsample 3 10
    values this stepsampleorder_name3visits10total
column-major Fortran stores the leftmost subscript contiguously.
loop order Changing traversal order changes the access pattern, not the mathematical total.
shape summary A small visit count and total can explain the loop shape without timing.