Sparse Data Patterns

Nonzero Sum

Compact Stored Values

Sparse data often stores only nonzero entries and summarizes those compact values.

Program

Play the program to include a different number of stored nonzero values.

active_count
nonzero_sum.f90
Replay: real traced execution (multi-file project)
program nonzero_sum_demo
    implicit none
    integer :: indices(4)
    integer :: values(4)
    integer :: active_count
    integer :: i
    integer :: total

    indices = [2, 5, 9, 12]
    values = [4, 7, 3, 6]
    active_count = 3
    total = 0
    do i = 1, active_count
        total = total + values(i)
    end do
    print '(I0, 1X, I0)', active_count, total
end program nonzero_sum_demo

program nonzero_sum_demo
    implicit none
    integer :: indices(4)
    integer :: values(4)
    integer :: active_count
    integer :: i
    integer :: total

    indices = [2, 5, 9, 12]
    values = [4, 7, 3, 6]
    active_count = 2
    total = 0
    do i = 1, active_count
        total = total + values(i)
    end do
    print '(I0, 1X, I0)', active_count, total
end program nonzero_sum_demo

program nonzero_sum_demo
    implicit none
    integer :: indices(4)
    integer :: values(4)
    integer :: active_count
    integer :: i
    integer :: total

    indices = [2, 5, 9, 12]
    values = [4, 7, 3, 6]
    active_count = 4
    total = 0
    do i = 1, active_count
        total = total + values(i)
    end do
    print '(I0, 1X, I0)', active_count, total
end program nonzero_sum_demo

  1. indices ← [2, 5, 9, 12]

    9indices = [2, 5, 9, 12]10values = [4, 7, 3, 6]
    values this step[2, 5, 9, 12]indices

  2. values ← [4, 7, 3, 6]

    9indices = [2, 5, 9, 12]10values = [4, 7, 3, 6]11active_count = 3
    values this step[4, 7, 3, 6]values

  3. active_count ← 3

    10values = [4, 7, 3, 6]11active_count = 312total = 0
    values this step3active_count

  4. total ← 0

    11active_count = 312total = 013do i = 1, active_count
    values this step0total

  5. i ← 1

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step1i

  6. total ← 4

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step0 → 4total4values(1)

  7. i ← 2

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step2i

  8. total ← 11

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step4 → 11total7values(2)

  9. i ← 3

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step3i

  10. total ← 14

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step11 → 14total3values(3)

  11. print '(I0, 1X, I0)', active_count, total

    15    end do16    print '(I0, 1X, I0)', active_count, total17end program nonzero_sum_demo
    output3 14
    values this step3active_count14total

  1. indices ← [2, 5, 9, 12]

    9indices = [2, 5, 9, 12]10values = [4, 7, 3, 6]
    values this step[2, 5, 9, 12]indices

  2. values ← [4, 7, 3, 6]

    9indices = [2, 5, 9, 12]10values = [4, 7, 3, 6]11active_count = 2
    values this step[4, 7, 3, 6]values

  3. active_count ← 2

    10values = [4, 7, 3, 6]11active_count = 212total = 0
    values this step2active_count

  4. total ← 0

    11active_count = 212total = 013do i = 1, active_count
    values this step0total

  5. i ← 1

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step1i

  6. total ← 4

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step0 → 4total4values(1)

  7. i ← 2

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step2i

  8. total ← 11

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step4 → 11total7values(2)

  9. print '(I0, 1X, I0)', active_count, total

    15    end do16    print '(I0, 1X, I0)', active_count, total17end program nonzero_sum_demo
    output2 11
    values this step2active_count11total

  1. indices ← [2, 5, 9, 12]

    9indices = [2, 5, 9, 12]10values = [4, 7, 3, 6]
    values this step[2, 5, 9, 12]indices

  2. values ← [4, 7, 3, 6]

    9indices = [2, 5, 9, 12]10values = [4, 7, 3, 6]11active_count = 4
    values this step[4, 7, 3, 6]values

  3. active_count ← 4

    10values = [4, 7, 3, 6]11active_count = 412total = 0
    values this step4active_count

  4. total ← 0

    11active_count = 412total = 013do i = 1, active_count
    values this step0total

  5. i ← 1

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step1i

  6. total ← 4

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step0 → 4total4values(1)

  7. i ← 2

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step2i

  8. total ← 11

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step4 → 11total7values(2)

  9. i ← 3

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step3i

  10. total ← 14

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step11 → 14total3values(3)

  11. i ← 4

    12total = 013do i = 1, active_count14    total = total + values(i)
    values this step4i

  12. total ← 20

    13do i = 1, active_count14    total = total + values(i)15end do
    values this step14 → 20total6values(4)

  13. print '(I0, 1X, I0)', active_count, total

    15    end do16    print '(I0, 1X, I0)', active_count, total17end program nonzero_sum_demo
    output4 20
    values this step4active_count20total
sparse storage `indices` records where the stored values belong in the full shape.
active entries `active_count` chooses how many compact entries are present.
compact sum The summary loops over stored values, not over every possible position.