Бенчмаркая CSE: подстава на uint — деление считается дважды
Уважаемые читатели, в этом посте я хочу разобраться, что компилятор делает с парой / и %, и представить свои выводы.
Возьмём число 47 и делитель 10. Деление даёт 4, остаток — 7. Компилятор деление не выполняет: он умножает 47 на подобранное число и сдвигает, получая 4. Дальше для остатка хватает вычитания: 47 − 4 × 10 = 7. Одно умножение на оба ответа.
Так на int. На uint компилятор получает 4, умножает на 10, вычитает — а потом заново считает те же 4 из 47, вторым умножением.
Ответ верный и там, и там. CSE, common subexpression elimination, находит повторяющиеся вычисления и считает их один раз. Оба умножения в паре считают одно и то же, и на int проход их склеивает. На uint не склеивает — отсюда и обращение в трекер.
int value = ints[i]; total += value / 10 + value % 10; // одно умножение uint value = uints[i]; total += value / 10 + value % 10; // три умножения
Замер на 1 024 значениях, .NET 10, три машины. Значения положительные: у знакового деления отрицательные идут другой веткой.
Из таблицы можно сделать выводы:
на int пара занимает столько же времени, сколько одно деление, на uint — вдвое больше;
беззнаковое деление быстрее знакового в 1,54–1,60 раза: знаковому нужна коррекция для отрицательных значений;
проседает не тип, а пара операций.
Вот как это выглядит в машинном коде, Xeon W-2255. У int одно умножение на всю пару:
mov edx, 0xD1FFAB1E ; подобранное число imul edx:eax, r9d ; единственное умножение, вышло 4 sar edx, 2 ; деление готово lea edx, [rax+4*rax] ; 4 x 5 add edx, edx ; ещё x2, вышло 40 sub r9d, edx ; 47 - 40 = 7, остаток
У uint то же самое, но в конце деление идёт второй раз:
mov r10d, 0xD1FFAB1E ; то же число imul r10, r9 ; первое умножение, вышло 4 shr r10, 35 ; деление готово imul r10d, r10d, 10 ; второе: 4 x 10 = 40 sub r9d, r10d ; 47 - 40 = 7, остаток mov r10d, 0xD1FFAB1E ; снова оно imul r8, r10 ; третье: те же 4 заново shr r8, 35 ; и тот же сдвиг
Были проверены ещё три случая, разницы между int и uint в них нет. Делитель 16, степень двойки: деление сводится к сдвигу, остаток берётся из младших битов, умножений ноль у обоих. Делитель в переменной: работает машинная команда деления, она выдаёт оба ответа разом, 2 714 против 2 716 нс. Тип ulong: на .NET 8 и .NET 9 было три умножения, на .NET 10 осталось одно, а у uint три.
Что делать на практике:
в горячих циклах вроде разбора числа по цифрам, форматирования и хэшей пара идёт на каждом витке, а с ней и лишнее умножение;
Math.DivRem возвращает к одному умножению: быстрее пары в 1,13–1,76 раза. Внутри для
uintто же вычитание:
// dotnet/runtime, Math.cs public static (uint Quotient, uint Remainder) DivRem(uint left, uint right) { uint quotient = left / right; return (quotient, left - (quotient * right)); }
вычитание, записанное явно, value - value / 10 * 10, быстрее пары в 1,23–1,80 раза — для тех, кому не нужен кортеж из Math.DivRem;
на int менять нечего: там деление с остатком уже собрано в одно умножение;
лишнее умножение забирает часть того, что uint даёт на делении, но не всё: на разборе числа по цифрам он остаётся быстрее int — 0,81–0,86.
Проход описан в документации: Common Subexpression Elimination, код в optcse.cpp, реализация Math.DivRem — в Math.cs. Обращение открыто с августа 2025, help wanted: dotnet/runtime#119131. Замеры, отчёты и листинги: DivRemProof.
Всем удачи и до новых встреч!
