Бенчмаркая 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.

Всем удачи и до новых встреч!