Прежде чем погрузиться в эту технику оптимизации, если вы не читали предыдущий пост о строках, посмотрите его здесь.
На этот раз я хотел поговорить о числах. В базе данных наиболее часто встречающимся типом данных является число. И в зависимости от размера числа мы хотим обрабатывать его по-другому, чтобы иметь возможность хранить его оптимизированным образом.
Чтобы понять приведенный ниже алгоритм, нам нужно понимать, что скорость выполнения операции сравнения намного выше, чем скорость выполнения операции деления/умножения.
Чтобы найти количество цифр в беззнаковом целом, мы могли бы просто написать алгоритм, который будет делить целое число на 10, пока мы не достигнем 0 и не подсчитаем число. итераций.
/* 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;
}
Все это выглядит хорошо и определенно будет отлично работать в обычной ситуации, однако для базы данных мы всегда должны стремиться к лучшей производительности, мы могли бы объединить операцию сравнения и операцию деления, чтобы добиться более высокой производительности для вычисления того же. Давайте посмотрим на измененный код.
/* 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
Здесь мы сравниваем число с (10, 100, 1000) и пропускаем 3 операции деления на каждой итерации. И прирост производительности при таком простом изменении основной операции, т.е. с деления на сравнение, выдающийся. Взгляните на этот график команды инженеров FB, измеряющий производительность.
Горизонтальная ось — это количество цифр, а вертикальная ось — относительная производительность новой функции по сравнению со старой. Новые цифры 10 в 1,7–6,5 раз быстрее.
Вы можете найти аналогичную оптимизацию кода здесь, в Redis:
Используйте эту оптимизацию в своей системе, если вы еще этого не сделали, и дайте мне знать, достигли ли вы такого прироста производительности, поняв основные возможности компилятора.
