Author: Yu Yisai
Part One: Introduction
Game engines are filled with a large number of calculations, among which the most typical are vector operations, matrix operations, and quaternion operations.
They share a common point: in most cases, data is grouped into sets of 4 numbers, with one or more calculations performed between two sets of data to obtain the final result.
Suppose we need to write a function (or macro) to calculate the addition of two four-dimensional vectors:
Back in the days of Quake III, the addition of this 4D vector was written as follows:
As we can see, to compute the sum of two four-dimensional vectors, we need to perform 4 addition operations.
For example, consider matrix multiplication:
In Quake III, this is how the multiplication of three-dimensional matrices was implemented:
To obtain the product of two three-dimensional matrices, we need to perform 9 groups of operations, each group containing 3 multiplications and 3 additions, which is a very time-consuming task.
However, such calculations may need to be called thousands of times per frame. Improving computational efficiency is crucial for game performance.
Now let’s try to optimize our calculation function.
In the addition of four-dimensional vectors, since the calculations of each dimension are independent, we consider whether we can use 4 threads, each calculating one dimension of the vector, and finally wait for all threads to finish to obtain the result:
We place each independent calculation into a separate context, that is, each thread calculates one dimension, thus achieving parallel computation and improving efficiency.
Unfortunately, this approach is not feasible.
The reason is that the time taken to create threads far exceeds the time taken to compute the addition, and repeatedly calling this function would actually slow down the computation, while non-atomic operations would make the threads unsafe.
Although parallel computing for vectors and matrices through multithreading is not feasible, fortunately, the CPU provides support for parallel computing, which is what we will discuss next: SIMD.
Part Two: Overview of SIMD
SIMD stands for Single Instruction, Multiple Data, allowing for parallel computation of 4 pairs of floating-point numbers through a single CPU instruction.
In 1994, Intel introduced the Multimedia Extensions (MMX) instruction set into the Pentium CPU, followed by several versions of the Streaming SIMD Extensions (SSE), which use 128-bit registers to store data.
These 128-bit SSE registers are divided into 4 groups, each 32 bits (4 bytes). Since the size of one float is exactly 4 bytes, we can think of the SSE register as capable of storing a 4D float vector. For convenience, we call it:
x (32 bits)
y (32 bits)
z (32 bits)
w (32 bits)
The cleverness of SSE lies in that x, y, z, and w can be computed in parallel, calculating all four dimensions simultaneously with one instruction, and the CPU instruction can return its value to memory.
Part Three: Using SSE
Using SSE in Visual Studio is quite easy.
Visual Studio has built-in __m128 types to store SSE, and when using __m128 types, the variables must be 16-byte aligned; otherwise, a runtime crash may occur.
We can use the xmmintrin.h header file in VS to operate on the __m128 type. These functions all start with _mm_.
Here are two important functions:
1. _mm_load_ps: Loads a float array from memory into __m128:
The above example loads [0,1,0,1] into the __m128 type variable.
2. _mm_store_ps: Returns the values from the __m128 type back to an array:
It is important to note that the array address must also be 16-byte aligned, so we use __declspec to modify this variable.
Unless you can ensure that automatic variables will be allocated at an address divisible by 16 bytes, it is better to add alignment modifiers.
Next, we introduce two operation functions, assuming that a and b in the code are both 16-byte aligned.
1. _mm_add_ps(v1, v2): Represents the addition of two vectors.
2. _mm_mul_ps(v1, v2): Represents the multiplication of corresponding dimensions of two vectors.
With these basic concepts, we can write a hardware-accelerated vector addition function as follows:
Part Four: Practice
Now let’s implement a more complex operation: vector × matrix.
This operation is very common in game programming, and as you can imagine, this method will be called many times in each frame, so optimization is crucial for game performance.
The formula for vector × matrix is as follows:
Our approach is to calculate the following 4 vectors separately:
Then we can use _mm_add_ps to sum them up, thus obtaining the desired result.
To obtain the above 4 vectors, we need to
“multiply”
This “multiplication” can be implemented using _mm_mul_ps, and the final problem becomes how to obtain the following 4 vectors:
Fortunately, SSE has a shuffle instruction, shufps, corresponding to the function _mm_shuffle_ps, which can extract components from a vector and recombine them into a new vector.
We can extract the required 4 vectors from a certain vector as follows:
Finally, the entire function looks like this:
The test code is as follows:
Part Five: Conclusion
SSE includes a large number of instructions; the above is just the tip of the iceberg. I hope students can have a basic impression of SIMD after reading this. In the Bullet3 physics engine library, its built-in linear algebra library has already handled SIMD, implementing dot products, cross products, and more using SSE.
Additionally, OpenGL Math (gml) also supports SIMD, and interested students can copy the code from GitHub. The code from this article has been submitted to the following address, and everyone is welcome to discuss and exchange ideas.
https://github.com/froser/tech
Highlights of the Xishanju Technology Salon (video recap available on the live platform):
① Session One: Liu Yu, The Art of Storytelling in Presentations
② Session Two: Gu Lu and Liu Moliang, Lua Performance Optimization Strategies
③ Session Three: Li Xiangwei, Resource Configuration in Unity, Resource Management in Projects
④ Session Four: Li Xiangwei, Runtime Resource Management – Unity
⑤ Session Five: Li Xiangwei, C# Memory and Performance Optimization
⑥ Session Six: Wang Yongzhi, Applications of Optical Motion Capture
⑦ Session Seven: Xiao Xing, Unity Girls | Rapid Production of the “Flappy Bird” Mini-Game
⑧ Session Eight: Wang Haiyin, Game Experience Design, Creating Emotional Appeal
⑨ Session Nine: Feng Liuhong, Positioning and Designing Factions from the Perspective of Original Art
Reward Upgrade! Earn 200 yuan for one article, plus points to exchange for a Xiaomi 6!Click 【Read the Original】 to check out the event!
Long press the QR code to follow Xishanju Technology