Полировка глюкал

[spamsink]

Рассмотрим целочисленное деление, точнее, вычисление остатка. Эта операция долгая, многотактная, поэтому при каждой удобной возможности - например, при вычислении остатка от деления на константу - ее нужно оптимизировать. Тривиальный случай остатка от деления на степень двойки исключаем; а деление 32-битного целого на произвольное наперед заданное число M делается просто: умножаем на "обратную величину" - число 2^N/M операцией, дающей в результате 64-битное число, и берем старшие разряды (N и количество старших разрядов определяются общим количеством бит M и количеством младших нулевых бит в нем, вручную это делать не нужно, компилятор уже сам умеет). Если нужно найти остаток, то умножаем результат на M и вычитаем из исходного числа. К примеру,

unsigned mod(unsigned x) {
    return x % 2037795097;
}

с помощью весьма нового GCC 4.7.2 превращается в

	movl	4(%esp), %ecx
	movl	$-2031890883, %edx
	movl	%ecx, %eax
	mull	%edx                    ; умножаем на "обратную величину"
	shrl	$30, %edx               ; берем старшие разряды
	imull	$2037795097, %edx, %edx ; умножаем частное на аргумент
	subl	%edx, %ecx              ; вычитаем
	movl	%ecx, %eax
	ret

Нетрудно проверить, что -2031890883 - это то же самое, что и 2³²-2031890883 = 2263076413, а 2⁶²/2037795097 = 2263076412.94.
Казалось бы, круто. Миллиард таких вычислений остатка делается около 4 с четвертью секунд на моем ноутбуке трехлетней давности под виртуальной машиной, чего еще желать?

Оказывается, еще есть, чего. Если вычисляется остаток от деления на "большое" число, почти под обрез разрядной сетки, то ничего ни на что умножать не надо, а достаточно лишь несколько раз аккуратно вычесть:

unsigned mod(unsigned x) {
	unsigned a;
	a = x - 2037795097;
	if (a < x) x = a;
	a = x - 2037795097;
	if (a < x) x = a;
	return x;
}

что выходит из-под пресса как

	movl	4(%esp), %eax
	leal	-2037795097(%eax), %edx
	cmpl	%eax, %edx
	cmovbe	%edx, %eax
	leal	-2037795097(%eax), %edx
	cmpl	%eax, %edx
	cmovbe	%edx, %eax
	ret

Ни единого разрыва потока команд, прошу заметить. Три секунды ровно.

До этой оптимизации, которая годится для нахождения остатка от деления на любое число, помещающееся в разрядной сетке не более 3 раз, гнутые товарищи не дотумкали.

Comments

[lider.livejournal.com]

На том же где и 4 сек, 3 сек. ;)


unsigned mod(unsigned x) {
if(2037795097>х)
return x;
return x % 2037795097;
}


а потом вот такое:
#define mod(х) ((2037795097>х)?х:х%2037795097)

[spamsink]

См. коммент и добавление к нему ниже.