Loop Sentinel

Loop Sentinel

Loop sentinels are an optimization that removes the overhead of checking an array index or pointer scanning an array or pointer chain. The technique does this by adding a pretend extra element onto the end of the array, in a way that we can pretend to succeed. And since we're guaranteed to always succeed, we don't need to check for failure while scanning the loop.

This technique is not particularly useful for vectorization, but is quite powerful for long sequential scanning of arrays. It also has the downside of requiring at least one writeable array element, so it cannot run on read-only arrays.

Example: Check Vector Negatives: Here's the basic loop sentinel version that sets up a dummy success in v[n]:

   bool aussie_vector_has_negative_sentinel(float v[], int n)
   {
        v[n] = -99.0;  // Dummy negative (BUG!)
        int i = 0;
        for ( ; /*GONE!*/; i++) {
            if (v[i] < 0.0) break;  // Found negative
        }
        if (i == n) return false;  // Fake success
        return true;  // Found a negative (for real)
   }

However, this is actually buggy, since “v[n]” is potentially an array overflow. A better version can manipulate the last valid element “v[n-1]” instead of modifying “v[n]”. Then, we have to remember to fix it before we leave town. And we also have to remember to check the last vector element that we temporarily overwrote wasn't also a real success.

    bool aussie_vector_has_negative_sentinel2(float v[], int n)
    {
        float save = v[n - 1];  // Save it!
        v[n - 1] = -99.0;  // Dummy negative at end
        int i = 0;
        for ( ; /*GONE!*/; i++) {
            if (v[i] < 0.0) break;  // Found negative
        }
        v[n - 1] = save;  // Restore it!
        if (i == n - 1) {
            // At the dummy (fake success)
            if (save < 0.0) return true; // Must check
            return false;  
        }
        return true;  // Found a negative (for real)
    }

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++