Show timing variations from poor data access patterns

demo_cache_locality.py

#!/usr/bin/env python3
from numba import njit


@njit
def f(arr):
    s = 0
    i = 0
    while i < len(arr):
        s += arr[i]
        i += 1
    return s


@njit
def f2(arr, jump=1357):
    n = len(arr)
    count = 0
    idx = 0
    s = 0
    while count < n:
        s += arr[idx]
        count += 1
        idx += jump
        # Modulo is slow, so use if instead
        if idx >= n:
            idx -= n
    return s


@njit
def f3(arr, jump=1357):
    count = 0
    idx = 0
    s = 0
    n = len(arr)
    while count < n:
        s += arr[idx]
        count += 1
        idx = (idx + jump) % n
    return s


if __name__ == "__main__":
    import timeit
    from rich import table, print
    import numpy as np
    import argparse

    parser = argparse.ArgumentParser()
    parser.add_argument("--seq", action="store_true")
    parser.add_argument("--rand", action="store_true")
    parser.add_argument("--rand-mod", action="store_true")
    parser.add_argument("--jump", type=int, default=1357)
    args = parser.parse_args()

    # Build a Rich table
    table = table.Table(title="Cache locality")
    table.add_column("Access pattern")
    table.add_column("Average time (s)")

    a = np.random.randn(1_000_000)
    print("Sums should match:")
    print(f"{f(a):.3f} {f2(a, jump=args.jump):.3f} {f3(a, jump=args.jump):.3f}")

    if args.seq:
        t = timeit.Timer("f(a)", globals=globals())
        results_seq = t.repeat(repeat=10, number=100)
        table.add_row("Sequential", f"{np.mean(results_seq):.3f}")

    if args.rand:
        t = timeit.Timer("f2(a, jump=args.jump)", globals=globals())
        results_rand = t.repeat(repeat=10, number=100)
        table.add_row("Random", f"{np.mean(results_rand):.3f}")

    if args.rand_mod:
        t = timeit.Timer("f3(a, jump=args.jump)", globals=globals())
        results_rand = t.repeat(repeat=10, number=100)
        table.add_row("Random (modulo)", f"{np.mean(results_rand):.3f}")

    print(table)

results.txt

$ python ../demo_cache_locality.py --seq --rand --rand-mod
Sums should match: -23.885 -23.885 -23.885
            Cache locality            
┏━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━┓
┃ Access pattern  ┃ Average time (s) ┃
┡━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━┩
│ Sequential      │ 0.052            │
│ Random          │ 0.245            │
│ Random (modulo) │ 0.643            │
└─────────────────┴──────────────────┘


$ lscpu 
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-1240P
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  12
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            4224.00
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss
                          ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonsto
                         p_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16
                          xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowpr
                         efetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsba
                         se tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsave
                         c xgetbv1 xsaves split_lock_detect avx_vnni dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp hwp
                         _pkg_req hfi umip pku ospke waitpkg gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_clear serialize arch
                         _lbr ibt flush_l1d arch_capabilities
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   448 KiB (12 instances)
  L1i:                   640 KiB (12 instances)
  L2:                    9 MiB (6 instances)
  L3:                    12 MiB (1 instance)

test_jump_sizes.sh

for j in 1 3 5 11 37 137 1357; do
  perf stat -x "\t" --append -o perf_rand_jumps.tsv -e instructions,cache-misses,branch-misses \
  python ../demo_cache_locality.py --rand --jump $j
 done