О сортировке (Ужасы Программирования - 2)

В комментариях к предыдущей записи Влад Шабанов предложил, казалось бы, отличное решение для лексикографической сортировки 8-байтных ключей (функция сравнения для qsort()):

#include "sys/endian.h";

int cmp(const void *d1,const void *d2)

{

    uint64_t a1 = be64toh(* ((uint64_t *)d1));

    uint64_t a2 = be64toh(* ((uint64_t *)d2));

    return (a1  > a2) - (a1 < a2);

}

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

Будучи зацеплен словами про cmov, я безуспешно искал версию gcc, которая делала бы код с такими инструкциями, однако поиски оказались безуспешными: gcc 3.4, 4.1 и 4.3 для всех 64-битных процессоров делает одно и то же (при оптимизациях -O2/O3, без оптимизации там ужас-ужас):

... инициализация
	bswap %rdx
	bswap %rcx
	cmpq	%rdx, %rcx
	seta	%al
	cmpq	%rdx, %rcx
	setb	%dl
	movzbl	%dl, %edx
	subl	%edx, %eax
	ret

... инициализация...
	movzbl	(%rdi), %edx
	movzbl	(%rsi), %eax
	cmpb	%al, %dl
       je .CONT
.L20:
....   тут возврат
.CONT:
	movzbl	1(%rdi), %edx
	movzbl	1(%rsi), %eax
	cmpb	%al, %dl
	jne	.L20
и так еще 6 раз.

Понятно, что 8 инструкций, которые частично параллелятся, не должны бы быть быстрее 32 инструкций (которые тоже параллелятся, по меньшей мере вычислительная часть). Однако скучная линейная последовательность mov/mov/ cmp/jne оказывается быстрее даже вместе с оверхедом qsort и вызова callbacks, собственно код сравнения должен быть быстрее в разы.

Отгадка оказалась довольно тривиальной: ключи длинные, распределены равномерно, поэтому до 2-го и далее сравнений доходит не всегда. Можно наплевать на производительность, добавить 3 строчки кода и посчитать:

• Первое сравнение делается на моем тестовом множестве (18 млн ключей) 449 млн. раз.
• Второе - 302 млн.
• Третье - 146 млн.
• Четвертое - 10 млн.
• С пятого по седьмое - примерно по миллиону раз каждое.

Упражнения делались на Core 2 Q9300 (6 мегабайт кэша, но вроде бы каждой паре ядер доступна только половина), суммарный объем сортируемых данных - 140 мегабайт, типичные времена - 2.5-4 секунды.