Newbie article, again, but this time I’m learning SIMD

The story

Given a list of intervals [start, end), how can we detect the input intervals overlap or have some gap between them, or we say, the input intervals are continous or not?

This is an interview question that I’ve been used in interview for our new team member for at least 2 years now. This just test candidate’s knowledge of basic algorithm and understand of problem complexity.

For a while, I didn’t look at the problem anymore, as I assume the solution for this is kinda optimized. On last friday, I read some example that using SIMD to batch calcuations and this week I had a thought: Isn’t this a place to apply SIMD as well? So I jump into the experimental train.

The code before

The idea of checking continous interval is simple: we check if end of previous interval match with start of the current interval, and we must sort those intervals first.

    /// ...
    std::sort(intervals.begin(), intervals.end());
    bool is_valid = true;
    for (unsigned i = 1; i < intervals.size(); ++i) {
        if (intervals[i].start != intervals[i - 1].end) {
            is_valid = false;
            break;
        }
    }
    /// ...

The code after

The idea this time is simple: if the end of previous interval matches start of current interval, they return 0 if we subtract them. And we need to order start and end of all intervals in such a way that we can apply SIMD on them.

    /// ... we still need to sort the intervals before enter this block
    
    /// [1] Create a temporary XMM register to store calculation of prev loop
    __m128i prev = _mm_set_epi32(intervals[0].start, 0, 0, 0);
    
    /// [2] Here's a mask that can be used to reorder content of a YMM register
    __m256i mask = _mm256_setr_epi32(0, 2, 4, 6, 1, 3, 5, 7);
    
    for (; i < num_main; i += chunk_size) {
        Interval const *loc = intervals.data() + i;
        /// [3] Load a chunk of intervals: [s0, e0, s1, e1, s2, e2, s3, e3]
        __m256i data     = _mm256_loadu_si256(reinterpret_cast<__m256i const*>(loc));
        
        /// [4] Re-order it, we got: [s0, s1, s2, s3, e0, e1, e2, e3]
        __m256i permuted = _mm256_permutevar8x32_epi32(data, mask);
        
        /// [5] Extract the start and end into 2 new XMM registers
        __m128i starts   = _mm256_extracti128_si256(permuted, 0);
        __m128i ends     = _mm256_extracti128_si256(permuted, 1);
        
        /// [6] Prepend the last end of last chunk here, then shift right by 1
        /// we now got [ep, e0, e1, e2]
        __m128i shifted_ends = _mm_alignr_epi8(ends, prev, sizeof(int) * 3);
        
        /// [7] Pair wise subtract: s(n) - e(n -1)
        __m128i diff     = _mm_sub_epi32(starts, shifted_ends);
        
        /// [8] If all results are 0, then we have continous chunk
        if (_mm_testz_si128(diff, diff) == 0) {
            is_valid = false;
            break;
        }
        prev = ends;
    }

NOTE: I think we have a better way to write this loop, but I’ll leave it for now.

The result

I use Google Benchmark to perform comparison, here’s the result.

Test file: test_data/increment_num100_step1_good.txt, array.size()=100
2026-08-12T20:54:49+07:00
Running build/demo
Run on (12 X 4056.45 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x6)
L1 Instruction 32 KiB (x6)
L2 Unified 512 KiB (x6)
L3 Unified 4096 KiB (x2)
Load Average: 0.95, 0.91, 0.88
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
***WARNING*** ASLR is enabled, the results may have unreproducible noise in them.
------------------------------------------------------
Benchmark            Time             CPU   Iterations
------------------------------------------------------
BM_Baseline        462 ns          462 ns      1512998
BM_Simd            310 ns          310 ns      2254144

• This benchmark measure the whole function including the first std::sort before checking continous intervals mention earlier
• O(NlogN) still dominates, but we got around 50ns faster.
• The test data contains 50 intervals starting from 0 until 100, each interval has length of 1. So this is a happy case, I remember that I put random result and the SIMD loop performs worse on some test cases, but I didn’t record that run :P

What I learnt

• First time write a benchmark
• First time writting simd code. Idea is mine, Gemini guide me how to write.

Last updated: 2026-08-12 09:30:00 +0700