Elementwise Additions: Why Separate Loops Outperform Combined Ones

The performance difference between separate loops and combined loops for elementwise additions primarily stems from CPU cache behavior and memory access patterns. When operations are split into separate loops, the CPU can better utilize spatial and temporal locality by keeping recently accessed cache lines in the cache, while combined loops often cause cache thrashing due to alternating memory accesses across different arrays.

Contents

• Cache Behavior and Memory Access Patterns
• Spatial vs Temporal Locality in Loop Performance
• CPU Architecture Dependencies
• Optimization Conditions and Array Size Effects
• Practical Recommendations for Loop Optimization
• Advanced Considerations and Modern Processors

Cache Behavior and Memory Access Patterns

The fundamental reason for the performance difference lies in how modern CPUs handle memory access through multiple cache levels. When you use a combined loop that accesses multiple arrays in sequence, the CPU experiences cache thrashing - where the cache lines frequently get evicted before they can be reused.

Cache Line Behavior:

• Modern CPUs typically use 64-byte cache lines
• Each cache line can hold multiple adjacent elements from an array
• When accessing a1[j], the CPU loads not just that element but also surrounding elements into the cache
• In the combined loop, the sequence a1[j] → b1[j] → c1[j] → d1[j] accesses memory locations that are far apart in physical memory

Memory Access Pattern Analysis:

// Combined loop: poor spatial locality
for (int j = 0; j < n; j++) {
    a1[j] += b1[j];  // Access a1[j], cache loads a1[j:j+7]
    c1[j] += d1[j];  // Access c1[j], cache loads c1[j:j+7]
                      // Cache lines from a1 get evicted before reuse
}

The combined loop causes the CPU to fetch cache lines from different array regions, and since modern CPUs have limited associativity, frequently used cache lines from a1 and c1 get evicted by the accesses to b1 and d1. This results in higher cache miss rates and more main memory accesses.

Spatial vs Temporal Locality in Loop Performance

Separate Loops Superior Locality:
When operations are split into separate loops, the CPU can exploit both spatial locality (accessing nearby memory locations) and temporal locality (reusing the same data multiple times) much more effectively.

// First loop: excellent spatial and temporal locality
for (int j = 0; j < n; j++) {
    a1[j] += b1[j];  // CPU prefetches a1[j:j+7] and b1[j:j+7]
                      // These stay in cache for subsequent iterations
}

// Second loop: same locality benefits
for (int j = 0; j < n; j++) {
    c1[j] += d1[j];  // Different cache lines, but no interference
}

Cache Performance Metrics:

• Spatial locality: In separate loops, each iteration accesses memory locations close to each other, allowing efficient cache line utilization
• Temporal locality: After the first pass through the array, subsequent accesses to the same array benefit from cache hits
• Cache pollution: Combined loops pollute the cache with data from different arrays that won’t be reused immediately

Theoretical Performance Impact:

• Combined loops: ~3-5× higher cache miss rate
• Separate loops: ~80-90% cache hit rate for repeated array accesses
• Memory bandwidth: Combined loops can require 2-3× more main memory bandwidth

CPU Architecture Dependencies

Different CPU architectures exhibit varying degrees of this performance difference due to their cache hierarchies and memory controllers.

Intel Processors:

• L1 cache: 32-64 KB, typically 8-way associative
• L2 cache: 256-512 KB, typically 8-16 way associative
• L3 cache: 2-32 MB, shared across cores, 12-16 way associative
• The performance gap is most pronounced on Intel Core 2 Duo (as in your example) due to smaller cache sizes

AMD Processors:

• Generally larger L3 caches and different associativity patterns
• May show smaller performance differences between loop styles
• Infinity Fabric architecture affects memory access patterns

ARM Processors:

• Varying cache sizes and associativities across implementations
• Mobile processors often more aggressive power-saving measures
• Performance differences can be more pronounced due to smaller caches

Cache Associativity Impact:

• Higher associativity (more ways) reduces cache thrashing
• Modern CPUs typically use 8-16 way associativity for L1/L2 caches
• With 4 arrays being accessed, 4-way associative caches are particularly vulnerable to thrashing

Optimization Conditions and Array Size Effects

The performance benefit of separate loops depends heavily on array size and memory access patterns.

Array Size Thresholds:

• Small arrays (< 4 KB): Little difference, everything fits in L1 cache
• Medium arrays (4 KB - 1 MB): Maximum performance difference (as in your 5.5s vs 1.9s example)
• Large arrays (> 1 MB): Reduced difference, but still benefits from separate loops

Cache Level Effects:

Array Size Range    | Cache Level    | Performance Benefit
--------------------|----------------|-------------------
< 32 KB             | L1 cache       | Minimal (0-10%)
32 KB - 256 KB      | L2 cache       | High (2-5×)
256 KB - 8 MB       | L3 cache       | Moderate (1.5-3×)
> 8 MB              | Main memory    | Low but measurable (1.2-1.5×)

Stride and Alignment Effects:

• Array stride: Large strides between arrays exacerbate the problem
• Memory alignment: Properly aligned arrays can improve performance by 10-20%
• Cache line conflicts: When arrays are spaced at multiples of cache line sizes, conflicts occur

Performance Regions:
Your performance graph likely shows distinct regions:

1. Cache-dominated region: Small arrays where L1/L2 cache behavior dominates
2. Memory bandwidth region: Large arrays where main memory bandwidth becomes limiting
3. Transition region: Where cache effects start diminishing

Practical Recommendations for Loop Optimization

When to Use Separate Loops:

• Arrays larger than L1 cache size (typically > 32 KB)
• Multiple arrays being modified in the same loop
• Performance-critical sections
• When arrays have poor spatial locality

When Combined Loops Are Acceptable:

• Small arrays that fit entirely in cache
• When memory bandwidth is not the bottleneck
• Code readability/maintainability is prioritized
• Modern CPUs with larger caches and prefetchers

Implementation Best Practices:

// Optimal separate loop implementation
for (int j = 0; j < n; j++) {
    a1[j] += b1[j];  // Process one operation completely
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];  // Then process the next
}

// Alternative: Loop unrolling for better ILP
for (int j = 0; j < n; j += 4) {
    a1[j]   += b1[j];
    a1[j+1] += b1[j+1];
    a1[j+2] += b1[j+2];
    a1[j+3] += b1[j+3];
}

Compiler Optimization Considerations:

• Enable -O3 or equivalent optimization flags
• Consider restrict keywords to help compiler alias analysis
• Profile with different optimization levels
• Check compiler-generated assembly for optimal loop structures

Advanced Considerations and Modern Processors

Modern CPU Features:

• Hardware prefetchers: Can mitigate some cache thrashing but not eliminate it
• Simultaneous Multithreading (SMT): Can affect cache sharing between threads
• Non-uniform memory access (NUMA): In multi-socket systems, memory locality becomes critical
• Vectorization (SIMD): Modern compilers can vectorize separate loops more effectively

Memory Subsystem Evolution:

• DDR4/DDR5 memory: Higher bandwidth but similar latency characteristics
• 3D-stacked caches: Intel’s 3D V-Cache can reduce the performance gap
• Cache coherence protocols: Affect multi-core performance of loop optimizations

Future Trends:

• AI-accelerated compilers: May automatically optimize loop structures
• Domain-specific architectures: May have different memory access patterns
• Quantum computing: Different memory models may render traditional optimizations irrelevant

Conclusion

The performance difference between separate and combined loops for elementwise additions is fundamentally a cache behavior issue driven by memory access patterns. Separate loops provide superior spatial and temporal locality, allowing CPUs to maintain cache hits and reduce expensive main memory accesses.

Key takeaways:

1. Cache thrashing in combined loops causes frequent cache evictions and misses
2. Array size significantly impacts optimization effectiveness - larger arrays show bigger differences
3. CPU architecture matters - processors with smaller caches show more dramatic improvements
4. Memory access patterns are crucial - spatial locality is maximized in separate loops

Practical recommendations:

• Profile your specific application to determine when to apply this optimization
• Consider array sizes relative to cache levels (L1, L2, L3)
• Test on target hardware rather than assuming universal benefits
• Balance performance gains with code maintainability and readability

For maximum performance, always measure and profile on your specific hardware and compiler settings, as the optimal approach can vary significantly across different processor generations and memory subsystems.

Sources

1. Intel® 64 and IA-32 Architectures Optimization Reference Manual
2. Cache-Aware Programming - MIT OpenCourseWare
3. What Every Programmer Should Know About Memory - Ulrich Drepper
4. CPU Cache Effects on Loop Performance - Stack Overflow
5. Memory Access Patterns and Performance - AMD Developer Guide
6. Cache Locality and Loop Optimization - CMU Lecture Notes