Modulo Division Micro-Optimization: Analyzing Assembly
The Introduction
In low-level programming, there's often a trade-off between readability and performance. The solution that is conceptually the simplest sometimes isn't the one that squeezes out the most performance from your processor.
I'm not talking about choosing the right algorithm for your problem - having a better or worse algorithm can have dramatic effects on performance, where some approaches can theoretically solve your problem but could, for example, use multiple orders of magnitude more memory than the optimal choice.
I'm talking about micro-optimizations in code. If choosing algorithms and the way different portions of your program interlink is the strategy of software engineering, then micro-optimizations are the tactics. While discussion of tactics might be the purview of amateurs, it's also a lot of fun.
As such, a lot of people who find themselves in low-level, performance-sensitive software engineering roles really like the idea of writing some tricky piece of code that runs 10% faster than the naive approach. This comes at the cost of readability and maintainability, and is often applied in corners of the program where the extra performance doesn't actually make any difference. It's a trade-off that a lot of us take - probably our neurotypicality.
At the same time, optimizing compilers (read: every compiler you've heard of this century) are really really good at optimizing your code. But the compiler isn't magic, and it can only know what you're trying to do if it can recognize the pattern your code makes once the compiler reduces it to an abstract syntax tree. And, because compilers are written by humans who are usually trying to best optimize the most common cases, compilers often recognize "normal" code more easily than "optimized" code.
And so there's a tension: programmers want to write code that is performant, and sometimes the obvious way isn't the best way. Compilers are much better than the average programmer at optimizing code, but have trouble recognizing the weird tricks programmers use thinking that it's 1980 and that by reusing values they're getting a performance boost. To let go and trust the compiler feels like an abdication of responsibility; to lock in and hone your routines until they are conceptually as fast as possible is time-consuming and often objectively useless.
Luckily, we don't have to operate in the dark. We can see what the compiler actually does and compare between the naive and "optimized" approaches, and we can benchmark.
This post discusses the former approach.
The Setting
I recently wrote some C code similar to the following:
void serialize(unsigned char *buffer, uint16_t bitOffset, uint16_t bitWidth, uint64_t value) {
for (uint16_t i = 0; i < bitWidth; i++) {
uint16_t byteIndex = (uint16_t)((bitOffset + i) / 8);
uint8_t bitIndex = (uint8_t)((bitOffset + i) % 8);
if (value & (1ULL << i)) {
buffer[byteIndex] |= (1 << bitIndex);
} else {
buffer[byteIndex] &= ~(1 << bitIndex);
}
}
}
This code is for serializing a large, diverse struct of bitfield integers. Few values have bitcounts that are a power of two, and padding bits of any kind are not acceptable. There is a specific order the values need to be in.
(It's unfortunate that there aren't easy ways to do this - both clang and gcc have attributes to try and pack bitfield structs, but neither accomplish what the above code does)
The idea is that callers provide a value to serialize, they explicitly tell our function how many bits of the value to use, and then we insert the value into our char buffer one bit at a time. This could be made more performant by being smarter about cases where we're inserting a bunch of bits into the same byte, or everything happens to line up, and other myriad edge cases. Not wanting to prematurely optimize something that looked like it could get pretty hairy, I settled on this basic approach.
To insert a bit at the correct location in the char array, we need to know what byteIndex to use (which is what we use to index into the char array and select the byte to operate on), and what bitIndex to use within that byte. The straightforward way to do this is to do some integer division to find what byteIndex our bitOffset requires, and then some modulo division to find what bitIndex we need to use within that byte.
The Optimization
Showing this code to a coworker, in passing, he remarked that modulo division is slow - that the CPU basically does the same integer division I did, then multiplies it back and subtracts to see what's left over. Having already done the integer division, I can get the result of the modulo division without paying the price of an expensive operation; all I have to do is a subtraction and a division.
The better, optimized, more thoughtfully-considered code is now:
void serialize(unsigned char *buffer, uint16_t bitOffset, uint16_t bitWidth, uint64_t value) {
for (uint16_t i = 0; i < bitWidth; i++) {
uint16_t byteIndex = (uint16_t)((bitOffset + i) / 8);
uint8_t bitIndex = (uint8_t)((bitOffset + i) - (byteIndex * 8));
if (value & (1ULL << i)) {
buffer[byteIndex] |= (1 << bitIndex);
} else {
buffer[byteIndex] &= ~(1 << bitIndex);
}
}
}
This improvement made sense. Any Micro-Optimizer will tell you that this is a good change. I would have told you this was a good change.
The Trial
However, I've seen a dozen too many recordings of Matthew Godbolt conference talks to pass up the opportunity to actually use his tool in anger for once.
By compiling each version using -O3, I can get the assembly produced by both. The assembly produced by the original version, using the modulus operator, is:
"serialize":
test dx, dx
je .L10
movzx r9d, dx
push rbx
mov r8, rdi
mov r10, rcx
movzx esi, si
xor edx, edx
jmp .L5
.L15:
or edi, ebx
add edx, 1
mov BYTE PTR [rax], dil
cmp r9d, edx
je .L1
.L13:
add esi, 1
.L5:
mov eax, esi
mov ecx, esi
mov ebx, 1
and ecx, 7
sar eax, 3
add rax, r8
sal ebx, cl
bt r10, rdx
movzx edi, BYTE PTR [rax]
mov ecx, ebx
jc .L15
not ecx
add edx, 1
and ecx, edi
mov BYTE PTR [rax], cl
cmp r9d, edx
jne .L13
.L1:
pop rbx
ret
.L10:
ret
And the version using the manual multiplication and subtraction:
"serialize":
push rbx
test dx, dx
je .L1
mov r10, rdi
mov r11, rcx
movzx r9d, dx
movzx esi, si
xor edi, edi
jmp .L5
.L12:
or r8d, edx
add edi, 1
mov BYTE PTR [rax], r8b
cmp r9d, edi
je .L1
.L10:
add esi, 1
.L5:
mov edx, esi
mov ecx, esi
sar edx, 3
mov eax, edx
sal edx, 3
sub ecx, edx
mov edx, 1
add rax, r10
sal edx, cl
bt r11, rdi
movzx r8d, BYTE PTR [rax]
jc .L12
not edx
add edi, 1
and edx, r8d
mov BYTE PTR [rax], dl
cmp edi, r9d
jne .L10
.L1:
pop rbx
ret
Unfortunately, changing that one line of code prompts the compiler to slightly re-engineer control flow in the assembly. This makes it hard to directly diff. However, since we know that the only thing that changed is the computation of bitIndex, we can focus in on that.
For the original modulus version, this computation is handled by a single instruction: and ecx, 7 under the .L5 label. We'll come back to how that works in a moment. For the manual version, it's handled by three instructions: sar edx, 3; sal edx, 3; sub ecx, edx. Let's walk through this approach first.
The sar/sal/sub approach basically just implements the math exactly as one would do it by hand. sar is "shift arithmetic right" while sal is "shift arithmetic left". Because we're dividing/multiplying by eight, which is a power of two, the compiler recognizes that we can accomplish the division/multiplication by shifting the binary values accordingly. By right-shifting our bitOffset by three bits (because 2^3=8), whatever remains is the result of bitOffset/8. This is accomplished by simply chopping off the rightmost/least significant three bits of the value - which is also why integer division is so fast, and why it "floors" and you lose remainder information. By then using sal ("shift arithmetic left") left-shifting the resulting value by three bits, multiplying the result of that integer division by eight, we get the nearest multiple of eight that's less than our bitOffset value. Finally we can use sub ("subtract") to subtract that value from our original bitOffset value, leaving us with the modulus value we needed. This is intuitively how you would compute modulus values in the general case - divide by what you're taking the modulus by, round down, multiply that back in, subtract to get the difference. The compiler sees that we're dividing/multiplying by eight, so it wisely uses the shift operations instead of longer-running full division/multiplication operations.
The and approach, in contrast, is now how a human would intuitively compute a modulus. This instruction takes a bitwise AND between two values. I think an example will best illustrate how this works. Let's say we have the value 13. In binary, this is represented as:
1101
We want to find result of doing modulo division by eight. Because eight is a power of two, there is an extremely simple way to find this in binary math: just keep only the bits less than eight. If we could "chop off" eight and anything to the "left" of it, the binary value we'd be left with would be exactly the result we're looking for. And how do we "chop off" portions of a binary value? By masking with bitwise AND operations. You'll never guess what the and instruction does.
The only thing we need is the mask to AND our value with. Because the eight is hardcoded in the source code, the compiler knows it can just subtract one to turn 1000 into 0111. And when we mask 1101 with 0111:
1101 = 13
0111 = 7
____
0101 = 5
We get five, which is 13 % 8. The compiler knows about this trick, and knows that if we're modulo dividing by a power of two, it can simply mask the original value by n-1 (where n is the power of two) to compute the modulus with a single extremely efficient bitwise comparison operation.
The net effect of these differences is that our "optimized" code uses three instructions to compute the value we need, while the "naive, slow" code uses just one instruction.
Checking Agner Fog's excellent instruction tables we can see that on many processors, and is one cycle, sar is one cycle, sal is one cycle, and sub is one cycle. So everything here is a single cycle long. That implies that our naive implementation is three times faster than the "optimized" one.
Of course, this is a micro-optimization so if we applied Amdahl's Law (which I won't be doing) I'm sure we'd find that we're hardly saving much time at all. But being fast is better than being slow, and the "naive" implementation is more readable anyways. There's no reason to use the more complicated "manual" approach, and I'll be keeping the modulus division line.
Another thing to note is that the manual approach introduces a data dependency between byteIndex and bitIndex. bitIndex can't be computed until the instruction computing byteIndex is retired. This could create a small bubble in part of the CPU's execution pipeline, introducing wasted cycles and making the code slower. The naive approach has no such dependency - the and instruction could be issued out-of-order from the sar/sal/sub instructions without issues. This gives the CPU more flexibility and makes it more likely that the single-cycle and can find a reservation station during a part of the execution pipeline that would otherwise be idle, effectively giving us the result for free.
The Fallout
There was no fallout - I told the other engineer because I thought this was a neat result, he said "that's a neat result", and we moved on. I just wanted a dramatic section header.
The Conclusion
There are a few main takeaways here:
- The relationship between the code we write and the code that runs isn't always obvious
- Sometimes when we think we're saving time by doing something complex, we're actually just obfuscating patterns that our compiler would otherwise recognize
- Compilers probably know more about optimization than you do - we want to leverage them as much as we can
- The only reason to try and manually micro-optimize something is if you suspect the compiler isn't seeing your intent; by using a different way to express that intent you might fall into one of the compiler's recognized patterns and unlock extra performance
Thanks for reading. It was interesting to use Compiler Explorer for an actual analysis, even though this analysis is very small potatoes.