Recently, I’ve been developing the vectorized computing engine for Doris. During the investigation of CPU hotspots, I discovered CPU hotspot issues in the storage layer. Therefore, I attempted to optimize this part of the CPU hotspot code using SIMD instructions, achieving good performance improvements. This note documents the discovery of the issue, the solution process, and some thoughts on performance issues in C/C++ programs, hoping that everyone can gain something from it.
1. Discovery of Hot Code
Recently, while optimizing some queries in Doris, I identified the following hotspots by using perf to locate CPU execution hotspots: 
From perf, we can see that nearly half of the CPU time is spent in BinaryDictPageDecoder::next_batch and BinaryPlainPageDecoder::next_batch. These two parts are responsible for decoding data reading from string columns, so we need to study this part of the code to see if there is any room for optimization. 
By further drilling down into the functions with perf, we can see which parts are consuming a lot of CPU. As shown in the image above, a significant amount of CPU time is spent on memory allocation during decoding. Particularly, the computation in int64_t RoundUpToPowerOf2 is significant; this function is used to calculate memory allocation based on aligned memory allocation logic.
Where Does the Memory Allocation Come From?
First, we need to understand how Doris stores string types at the page level. There are two types of pages:
-
DictPage dictionary encoding, suitable for data with high string redundancy. Doris writes the dictionary into the PlainPage and records the offset of each string. The actual data page stores not the original strings but the offsets. During decoding, memory must be allocated, and the corresponding memory must be copied from the dictionary based on these offsets. This is where the code hotspot arises.
-
PlainPage direct encoding, suitable for data with low string redundancy. Doris automatically converts DictPage to PlainPage. During decoding, memory must also be allocated, and the content of the PlainPage must be copied out. This is also where the code hotspot arises.
Whether it’s DictPage or PlainPage, the decoding process is the same. Doris reads 1024 rows of data each time, so each operation is as follows:
-
Retrieve one row of data
-
Calculate the aligned memory length based on the data length
-
Allocate the corresponding memory
-
Copy data into the allocated memory
2. Using SIMD Instructions to Solve the Problem
Having confirmed the issue, I began researching solutions. Intuitively, simplifying 1024 scattered memory allocations into a single large memory allocation should yield significant performance improvements.
However, this leads to a critical issue: batch memory allocation cannot guarantee memory alignment, which can degrade the performance of subsequent memory access instructions. To ensure memory alignment, the calculation of int64_t RoundUpToPowerOf2 mentioned above cannot be bypassed.
Since we cannot bypass it, we need to find a way to optimize it. This calculation is straightforward, so I tried to see if SIMD instructions could optimize this calculation process.
2.1 What are SIMD Instructions?
SIMD stands for Single Instruction Multiple Data, which means that a single instruction can operate on a batch of data. This approach significantly increases the amount of data that the CPU can process within the same clock cycle.
The image above illustrates a simple multiplication calculation where four numbers need to be multiplied by 3. This requires:
-
4 load memory instructions
-
4 multiplication instructions
-
4 memory write-back instructions
Using SIMD instructions allows us to process data in batches more quickly, as shown in the image. The original 12 instructions are reduced to 3. Modern x86 processors typically support MMX, SSE, AVX, and other SIMD instructions, which accelerate CPU calculations.
Of course, SIMD instructions also have certain costs, as hinted in the above images:
-
Data being processed needs to be contiguous, and aligned memory can yield better performance.
-
Registers occupy more space than traditional SISD CPUs.
For more information about SIMD instructions, please refer to the references I provided at the end of this article.
2.2 How to Generate SIMD Instructions
There are typically two ways to generate SIMD instructions:
Auto Vectorized
Auto vectorization means that the compiler automatically analyzes whether a for loop can be vectorized. If so, it automatically generates vectorized code, usually enabled with the -O3 optimization option.
This method is, of course, the simplest, but compilers are not as intelligent as programmers, so auto vectorization optimization is relatively strict, requiring programmers to write sufficiently friendly code.
Here are some tips for auto vectorization:
-
1. Simple for loops
-
2. Sufficiently simple code, avoiding function calls and branch jumps
-
3. Avoid data dependencies, where the next calculation depends on the result of the previous loop
-
4. Continuous and aligned memory
Handwritten SIMD Instructions
Of course, SIMD is also supported through libraries. We can directly use libraries provided by Intel for vectorized programming, such as SSE‘s API header file xmmintrin.h and AVX‘s API header file immintrin.h. This implementation method is the most efficient but requires programmers to be familiar with SIMD coding, and it is not universal. For example, an AVX vectorization algorithm cannot run on machines that do not support the AVX instruction set and cannot be replaced with the SSE instruction set.
3. Development and Problem Solving
After analyzing SIMD instructions in the previous section, the next step is to develop on Doris’s code and verify the results.
3.1 Code Development
Thinking is the hardest part; writing code is always the easiest. Let’s directly modify Doris’s code:
// use SIMD instruction to speed up call function `RoundUpToPowerOfTwo`
auto mem_size = 0;
for (int i = 0; i < len; ++i) {
mem_len[i] = BitUtil::RoundUpToPowerOf2Int32(mem_len[i], MemPool::DEFAULT_ALIGNMENT);
mem_size += mem_len[i];
}
Here, I utilized GCC’s auto vectorization capability to allow the for loop above to perform vectorized calculations. Since the current default compilation options for Doris do not support the AVX instruction set, and the original BitUtil::RoundUpToPowerOf2 function takes Int64 as a parameter, which makes it difficult for the 128-bit SSE instructions, I implemented the BitUtil::RoundUpToPowerOf2Int32 version to speed up this process.
// speed up function compute for SIMD
static inline size_t RoundUpToPowerOf2Int32(size_t value, size_t factor) {
DCHECK((factor > 0) && ((factor & (factor - 1)) == 0));
return (value + (factor - 1)) & ~(factor - 1);
}
For 32-bit calculations, SSE instructions support 128-bit calculations, meaning that four numbers can be operated on at once.
For the complete code implementation, please refer to the PR here.
3.2 Performance Verification
After coding, I compiled and deployed the changes for testing. I also used perf to observe the hotspot code, and after vectorization, the CPU proportion of the corresponding code significantly decreased, leading to performance improvements.
| No Vectorized | Vectorized | |
|---|---|---|
| DictPage | 23.42% | 14.82% |
| PlainPage | 23.38% | 11.93% |
Subsequently, I tested the effects on a single-machine SSB model, where many previously slow queries in the storage layer showed significant acceleration.
Next, I followed the old method: raised an issue and contributed the code that solved the problem to Doris’s official repository. End of the story!
4. Conclusion
Bingo! At this point, the problem was successfully resolved, and I achieved a certain performance improvement.
This article especially thanks the community partners:
-
@wangbo for the Code Review
-
@stdpain for discussions on memory alignment issues.
Finally, I hope everyone supports Apache Doris and contributes code to Doris. Thank you~~