О сортировке (Ужасы Программирования - 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
Ассемблерный код варианта с bswap гораздо компактнее и красивее, чем то, что порождается из восьми последовательных if:

... инициализация...
	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 секунды.

Comments

> Отгадка оказалась довольно тривиальной

Я думал, что на современных архитектурах, типа x86_64, чтение одного байта по скорости равно чтению 8 байт.

Sorry, подумал ещё раз. Ключи выровняны на границу 8 байт?

Да, конечно выравнены и конечно они в L1 сразу же

Алексей, изменятся ли бенчмарки от такого кода?
#include

static inline int cmp0(uint16_t c1, uint16_t c2)
{
return (c1 > c2) - (c1 < c2);
}

int cmp8(const void *d1,const void *d2)
{
uint16_t *p1 = (uint16_t *)d1;
uint16_t *p2 = (uint16_t *)d2;
#define CMPC(i) cmp0(p1[i],p2[i])
return CMPC(0) || CMPC(1) || CMPC(2) || CMPC(3);
}

ччёрт, как страшно отформатировался. думаю, что идея и так понятна. раз на первые два байта приходится основная масса сравнений, то и сравнивать их лучше в одну операцию.

Ошибку с || вижу, кстати.

Просто bswap - это дико тормозная операция на Core2. Более оптимально было бы через pshufb + pcmpgtq + ptest / movbe + cmp + sbb

Я на ассемблере влет не читаю, попробовал разобраться - и вообще нашел патент про byte swap

Да вроде не дико, нормально тормозная. Вот нашел табличку - 4 такта latency, 1 такт на исполнение. Т.е. два bswap - 5-6 тактов.

http://swox.com/doc/x86-timing.pdf

Самый лучший список таймингов, который можно найти, находится на www.agner.org
Для Core2 4 такта latency - это до черта. Даже
<code>
ror ax, 8
ror eax, 16
ror ax, 8
</code>
несмотря на partial register stall получается быстрее, чем bswap eax

Для одного - быстрее, а для двух - вроде одинаково получается.

Да, а pdf-ки по ссылке - отличные, спасибо!

забыл про be16toh
сорри за флуд :)

всё, на сегодня хватит. пора спать.

static inline uint16_t be16toh(uint16_t be)
{
return (be >> 8)|(be << 8);
}

int cmp8(const void *d1,const void *d2)
{
uint16_t *p1 = (uint16_t *)d1;
uint16_t *p2 = (uint16_t *)d2;
int c;
#define CMPC(i) if(__builtin_expect(c = be16toh(p1[i]) - be16toh(p2[i]),1)) return c
CMPC(0);
CMPC(1);
CMPC(2);
return be16toh(p1[3]) - be16toh(p2[3]);
}

Алексей, как этот вариант?

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

cmp8:
.LFB3:
movzwl (%rdi), %edx
movzwl (%rsi), %eax
rolw $8, %dx
rolw $8, %ax
movzwl %dx, %edx
movzwl %ax, %eax
subl %eax, %edx
movl %edx, %eax
je .L5
.L2:
rep
ret

я, наверное, отстал от жизни, что что означает комбинация rep; ret?

А нельзя вначале поменять byteorder, отсортировать, потом поменять назад?

Я не думаю, что так будет выигрыш по перформансу.

http://developers.slashdot.org/developers/08/11/23/1637219.shtml

"Google has announced that they were able to sort one petabyte of data in 6 hours and 2 minutes across 4,000 computers.

Ага, невообразимо круто.

Интересно, какое у них распределение ключей было. Если равномерное, то жизнь сильно легче.

Дрочим всем офисом!

Add new comment