← Back to the chapter · Previous detail · Next detail →

Technical detail · Software Optimization Techniques

Vectorization and tail handling

18.15 Vectorization and Tail Handling

The tail is visible when the same ten-element calibration loop is laid out lane by lane. Figure 7 compares ten scalar iterations with two complete four-lane vectors and the remaining two elements.

Ten scalar array elements become two four-lane vector operations plus a two-element cleanup tail.
Ten elements fill two four-lane vectors and leave a two-element tail. Masked lanes or scalar cleanup handle the remainder without accessing beyond the array.

In Figure 7, V0 · [0 1 2 3] and V1 · [4 5 6 7] account for eight valid elements. The TAIL [8 9] then branches to masked lanes or scalar cleanup, so the speedup boundary includes setup and remainder work and never reads beyond x[9] merely to fill a vector.

Suppose a scalar loop adds two arrays:

for (size_t i = 0; i < N; ++i)
    c[i] = a[i] + b[i];

A SIMD (single instruction, multiple data) instruction with WW lanes performs WW element additions per vector iteration. Split the trip count into

q=⌊NW⌋,r=N mod W.q=\left\lfloor\frac{N}{W}\right\rfloor,\qquad r=N\bmod W.

The vector loop executes qq times over qWqW elements; a tail path handles the remaining rr elements. For N=18N=18 and W=4W=4, there are four vector iterations covering 16 elements and two scalar tail iterations. Omitting the tail silently leaves c[16] and c[17] wrong.

size_t i = 0;
for (; i + W <= N; i += W)
    vector_add(&c[i], &a[i], &b[i]);
for (; i < N; ++i)
    c[i] = a[i] + b[i];

Some instruction sets provide masked loads and stores, allowing one final vector operation with only the first rr lanes enabled. That removes a scalar loop but does not remove the boundary obligation: the mask must prevent out-of-range memory access and preserve inactive lanes.

Ideal arithmetic speedup approaches WW, but real time is

Tvec=qTvector+rTscalar+Tsetup+Tremainder,T_{vec}=qT_{vector}+rT_{scalar}+T_{setup}+T_{remainder},

so short arrays, tails, alignment repair, alias checks, and memory bandwidth reduce the gain. Validate lengths 00, 11, W−1W-1, WW, W+1W+1, and a large non-multiple; test aligned and unaligned buffers; and compare every element with the scalar reference. Vectorization is complete only when the remainder path is as deliberate as the fast path.

← Back to the chapter · Previous detail · Next detail →