In our previous lesson, we explored the theoretical underpinnings of CPU performance, establishing why techniques like SIMD are so effective. You learned that by performing a single instruction on multiple data points simultaneously, we can drastically reduce the total instruction count of our program, providing a massive performance lever according to the Iron Law.
Now, we shift from theory to practice. This lesson is about the how. You will take your naive C implementation of Euclidean distance and rewrite it using AVX2 intrinsics. These are special functions that give you direct access to the CPU's powerful vector processing hardware from within your C code. This is a foundational skill for anyone serious about low-level optimization and is the first major step in transforming our vector search from a simple algorithm into a high-performance system.
The Anatomy of an Intrinsic
Before diving into code, let's be clear about what an "intrinsic" is. Intrinsics are functions provided by the compiler that map almost one-to-one with specific CPU assembly instructions. They offer a middle ground between high-level C code, where you rely on the compiler's auto-vectorizer (which can be unreliable), and writing raw assembly, which is complex and not portable. For your interests in system programming and performance, mastering intrinsics is a non-negotiable skill.
The following video provides an excellent overview of what intrinsics are and how they bridge the gap between C and assembly language.
SIMD and vectorization using AVX intrinsic functions (Tutorial)
This segment from Joel Carpenter's tutorial contrasts different ways to achieve vectorization and explains why intrinsics are often the sweet spot for performance and control.
Watch the section explaining the different approaches to vectorization, from compiler optimizations to intrinsics. Pay close attention to the part that compares assembly with an intrinsic function call for a vector addition—it perfectly illustrates the level of abstraction we'll be working at.
To use these functions, you'll need to include a special header:
#include <immintrin.h>
This header file contains the definitions for all the AVX, AVX2, and FMA intrinsics we'll be using.
Vector Data Types and Naming Conventions
With AVX2, we work with 256-bit wide registers. A single-precision float is 32 bits, so a 256-bit register can hold exactly eight floats. The C type for this is __m256. Our entire strategy will revolve around packing our vector data into these __m256 types and using special functions to operate on all eight floats at once.
The intrinsic function names can look intimidating at first, but they follow a logical pattern. Understanding this pattern is key to being able to read and write SIMD code effectively.
SIMD and vectorization using AVX intrinsic functions (Tutorial)
Let's return to the same video to break down the data types and naming scheme.
First, watch the segment covering the special data types used with intrinsics, focusing on __m256. Then, watch the explanation of the function naming convention.
As the video explains, a function like _mm256_add_ps can be decoded:
_mm256: The function operates on 256-bit__m256vector types.add: The operation is addition._ps: The data type is packed singles (i.e., multiplefloatvalues).
With this knowledge, you can now infer the purpose of functions like _mm256_sub_ps or _mm256_mul_ps.
Rewriting Euclidean Distance with AVX2
Let's rebuild our euclidean_distance function. The formula is . We will implement this by striding through our input arrays, processing 8 floats at a time.
The core of our function will be a loop that does the following in each iteration:
- Load 8 floats from array
aand 8 floats from arraybinto__m256registers. - Subtract the two registers element-wise to get the differences.
- Multiply the result register by itself to get the squares of the differences.
- Add the register of squared differences to a running sum accumulator register.
After the loop finishes, we will have an accumulator register containing 8 partial sums. We then need a final step to "horizontally" add those 8 values together to get our final sum, after which we can take the square root.
The following resource provides a clean, complete implementation of this process. Study it carefully.
Calculate Euclidean Distance Between Two Arrays using C++ SIMD
This article from Lindevs provides a clear, side-by-side comparison of a naive implementation and an optimized version using AVX2 intrinsics.
First, quickly review the naive implementation to remind yourself of the baseline. Then, carefully study the optimized AVX2 code. Below the code, the article provides an explanation of the main intrinsics used inside the loop. Focus on understanding these key parts of the implementation: The Main Loop: How it processes 8 elements per iteration. The Reduction: The block of code after the main loop that sums the 8 partial results in the vsum register into a single scalar sum. This is a critical pattern called a "horizontal sum" or "reduction". The Remainder Loop: The final for loop that handles cases where the vector dimension is not a perfect multiple of 8.
Let's visualize the process inside that main SIMD loop.
The reduction part of the code is the most complex. The goal is to take a vector like [s0, s1, s2, s3, s4, s5, s6, s7] and compute s0+s1+...+s7. The code from the article accomplishes this through a series of steps that extract, add, and shuffle the vector's contents to collapse it into a single number.
For another perspective on the same problem, you can review the "Option 3: Write vector code by hand" section of the article by Kevin Chen. It uses a slightly different, but conceptually identical, set of intrinsics to achieve the same result.
Speeding up code with vectorization - Kevin Chen
This article provides an alternative handwritten implementation and shows the resulting assembly code, which might be insightful given your interests.
Read the section titled Option 3. Compare this implementation's reduction strategy with the one in the Lindevs article. Note that both achieve the same goal: summing the 8 float values within the final accumulator register.
By completing this exercise, you have replaced a loop that would have taken scalar instructions (where D is the vector dimension, ignoring loop overhead) with one that takes roughly vector instructions, plus a few extra for the final reduction. This is a concrete application of the Iron Law—dramatically cutting the instruction count to improve performance.
Conclusion
In this lesson, you have bridged the gap between theory and practice, translating the concept of SIMD directly into C code. You have taken a standard mathematical function and accelerated it by manually directing the CPU to use its powerful vector hardware.
Key Takeaways:
- Intrinsics are C functions that provide direct access to CPU assembly instructions, such as those for SIMD.
- AVX2 uses 256-bit registers, represented by the
__m256data type, which can hold 8 single-precision floats. - The core SIMD workflow is to load data into vector registers, perform vector arithmetic, and finally reduce the vector result back to a scalar.
- Horizontal summation is a common and essential pattern for reducing a vector register to a single value.
You now have the tools to vectorize a critical piece of our vector database. In the next lesson, we will continue this work by implementing the dot product function. This will introduce another powerful instruction, the Fused Multiply-Add (FMA), which will be the final building block needed for an ultra-fast Cosine Similarity calculation.