Learnings from Redis # 3 / Arithmetic Operations
Before diving into this optimisation technique, if you haven’t read the previous post around strings do take a look at it here.
This time around I wanted to talk about numbers. In a database, the most commonly occurring data type is number. And based on the number’s size we want to handle it in a different manner to be able to store it in an optimised manner.
In order to understand the below algorithm, we need to understand that the speed of execution of a comparison operation is much higher than speed of execution of a division/multiplication operation.
In order to find the number of digits in an unsigned integer, we could simply write an algorithm to divide the integer by 10 until we reach 0 and count the no. of iteration(s).
/* Return the number of digits of 'v' when converted to string in radix 10. */
uint32_t digits10(uint64_t v) {
int count = 0;
while (v) {
count++;
v/=10;
}
return count;
}This looks all good and will definitely work perfectly fine in a normal situation, however for a database, we should always strive for better performance, we could combine comparison operation and division operation to achieve faster performance to compute the same. Let’s have a look at the modified code.
/* Return the number of digits of 'v' when converted to string in radix 10. */
uint32_t digits10(uint64_t v) {
int count = 0;
while (v) {
if (v < 10) return count + 1;
if (v < 100) return count + 2;
if (v < 1000) return count + 3;
count += 4;
v = v / 10000;
}
return count;
}You can find the similar code here in Redis : https://github.com/redis/redis/blob/95d6297db868fc5400fb833c6753c8d25da486c7/src/util.c#L276-L294
Over here, we do comparison of a number with (10, 100, 1000) and we skip 3 division operation on each iteration. And the performance gain with this simple change of the main operation i.e. from division to comparison is outstanding. Have a look at this graph by FB engineering team measuring the performance.
The horizontal axis is the number of digits and the vertical axis is relative performance of the new function against the old one. The new digits10 is 1.7x to 6.5 faster.
You can find similar code optimisation here in Redis :
Do use this optimisation in your system if you’re not doing it already and let me know if you have achieved such gains in performance by understanding the basic of the compiler abilities.
