Ужасы программирования

lexa - 18/Ноя/2008 17:11

Сортирую записи по 8-байтным ключам в byte order (не в numeric). Записей много (сотни миллионов). Оказывается, сравнивать ключи надо так: 

    unsigned char *p1 = (unsigned char *)d1;

    unsigned char *p2 = (unsigned char *)d2;

#define CMP(i) if(p1[i]!=p2[i]) return p1[i]-p2[i]

    CMP(0); CMP(1); CMP(2); CMP(3); CMP(4);CMP(5); CMP(6); CMP(7);

    return 0;

#undef CMP

А банальный memcmp/__builtin_memcmp оказывается в 2.2 раза медленнее на общее время исполнения qsort(), во сколько раз различается сравнение - боюсь думать.

С numeric-сортировкой тоже весело, естественно наступил на (value2-value1) - это быстро и неверно (а верный вариант - получился не быстрее побайтового).

Comments

Konstantin Sorokin (not verified) - 18/Ноя/2008 17:25

qsort из libc ? А если std::sort и чтобы operator < у сравниваемых элементов инлайнился ?

lexa - 18/Ноя/2008 17:35

Byte order, а не numeric. С числовым порядком все несколько проще.

lexa - 18/Ноя/2008 17:48

А кстати, как в std:vector сделать read() ?

Konstantin Sorokin (not verified) - 18/Ноя/2008 18:38

Гы, а никак по-нормальному :)

lexa - 18/Ноя/2008 19:04

В-общем, в рафинированом случае с 18млн ключей без данных - std::sort быстрее на numeric раза в полтора. Но копирование - довольно существенная часть и в реальном случае, когда на 20 байт данных 8 байт ключа - примерно один хрен.

lexa - 18/Ноя/2008 19:10

Да, и конверсия просто буфера в вектор - это вдвое по памяти, а читать кусочками - тоже никакой радости.

polyestr (not verified) - 18/Ноя/2008 20:26

А в чём вопрос для такого специфического момента ручками закодировать qsort?

lexa - 18/Ноя/2008 20:32

Жизнь коротка. Вот эта хрень, которая выше - это ускорение двое за 5 минут, размялся и приятно.
А реальный варез все равно тормозит при записи на диск (собственно, его то я и пытаюсь ускорить на порядок-другой-третий)

http://notes.so... (not verified) - 18/Ноя/2008 21:28

А в какой операционке ? Во FreeBSD memcmp выглядит так:
do {
if (*p1++ != *p2++) return (*--p1 - *--p2);
} while(--n != 0);
Что есть обощенный вариант вашего решения.

lexa - 18/Ноя/2008 21:49

FreeBSD 6.4 x64

Но вы привели библиотечный memcmp, а естественно gcc будет ставить builtin. В исходних ассемблерный не смотрел, но говорят там repe cmpsb (сужу по выдаче гугла)

Ну а дальше оказывается, например, что loop unrolling при нонешней глубине конвейера - полезен.

lexa - 18/Ноя/2008 22:17

Пардон, писал не проверив.
Библиотечный memcmp в FreeBSD лежит в {amd64,i386}/string/memcmp.S а вовсе не в string/memcmp.c (последний вариант - для совместимости и в реальной жизни никуда не попадет).

И скорее всего на длинных сравнениях он выиграет, как только цена call станет невидной. Но у меня то 8 байт.

mrshurik (not verified) - 18/Ноя/2008 12:46

1. стандартная сортировка C++ (с функтором) может быть быстрее qsort() из C.
2. а если попробовать что-то вроде (для 3-х) return (a1==b1)?((a2==b2)?((a3==b3)?0:a3-b3):a2-b2):a1-b1 ?

lexa - 18/Ноя/2008 13:00

Да, в рафинированном (только ключи) случае std::sort(vector...) быстрее.

Если ключи с данными (данных - больше), то время на копирование съедает выигрыш.

mrshurik (not verified) - 18/Ноя/2008 16:10

ну тогда можно отсортировать сначала индекс, а потом по нему реальный массив. ещё вместо std::vector можно использовать просто динамические массивы (вроде в boost есть).
хотя, все эти "извращения" с оптимизацией не нужны, если сортировка не hot spot.

lexa - 18/Ноя/2008 16:20

У меня оно во входном файле лежит вместе (записями фиксированной длины).

Ну и конечно не hot spot - тестовый файл порождается 3 минуты, сортируется 3 секунды, а вот в индексированный вид (BTree) сейчас пишется 3 часа (ну а моя задача писать в Btree еще за несколько минут, хотя не уверен в возможности, экспериментирую)

lexa - 18/Ноя/2008 16:22

В смысле, я к тому что это все 5-минутное развлечение, давшее неожиданный результат (начал я с того, что переполнил int в numeric sort и у меня количество уникальных ключей не расходилось в маленьких тестах, но расходилось на миллионах - тоже, обычные такие грабли, но не каждый день бываают)

jattar (not verified) - 18/Ноя/2008 19:39

прости за дельтанский вопрос а не будет ли быстрее сравнивать два лонга (или четыре инта)?

тоесть за сколько тактов они сравниваются на ассемблер современных процов

lexa - 19/Ноя/2008 01:17

Потому что это byte order, а не численный.

Байты в лонгах-интах идут не подряд и порядок (результат) сортировки для двух способов сравнения получается разный.

o-rdonly.ya.ru (not verified) - 19/Ноя/2008 07:03

Может я неправильно понял задачу: а radix sort тут не поможет?

lexa - 19/Ноя/2008 07:18

Да может и поможет, но где реализация в stdlib?

shahmatiuga (not verified) - 19/Ноя/2008 00:26

простите,
не догоняю, почему вместо if(a!=b) return a-b не писать сразу a-b?

lexa - 19/Ноя/2008 01:17

Re: простите,
А если эти байты равны?

shahmatiuga (not verified) - 19/Ноя/2008 10:06

Re: простите,
будет 0. не вижу пока проблемы.

lexa - 19/Ноя/2008 14:03

Re: простите,
Ну и как перейти к следующему байту без if, если мы побайтно сравниваем ?

Но Шабановский вариант мне конечно больше нравится, сейчас я его изучу.

shahmatiuga (not verified) - 19/Ноя/2008 14:45

вообще-то всё зависит от задачи. Грубо можно так, наверное
unsigned int64 *p1 = (unsigned int64 *)d1;
unsigned int64 *p2 = (unsigned int64 *)d2;
return p1[0]-p2[0];

lexa - 19/Ноя/2008 14:54

Еще раз:
мне нужно отсортировать не по числовому значению, а как "8-байтовые строки".

На x86 (в широком понимании, включая сюда и x64) - это разные сортировки.

v_shabanoff (not verified) - 19/Ноя/2008 07:27

сравнение как

return (a > b) - (b > a)

генерирует 2 команды cmove и ни одного jmp. cmove тоже, конечно, не сахар, спекулятивно исполнять процессору трудно, но лучше чем jmp.

Ещё помогает htonl каакой-нить, он инлайнится в одну команду bswap на 64 битах.

Короче, я за

a1 = betoh64(a);
b1 = betoh64(b);
return (a1 > b1) - (a1 < b1);

mrshurik (not verified) - 19/Ноя/2008 07:44

а как из них цепочку составить?

v_shabanoff (not verified) - 19/Ноя/2008 07:45

а зачем цепочку? Сравниваем 8-байтные числа и всё.

mrshurik (not verified) - 19/Ноя/2008 07:58

см. выше, это не правильно.

v_shabanoff (not verified) - 19/Ноя/2008 09:06

куда выше?
сравниваем 2 восьмибайтных ключа. Где здесь цепочка?

mrshurik (not verified) - 19/Ноя/2008 15:01

ок. вы правы.
просто это не общее решение, допустим, если надо поменять лексикографический порядок, то нужно будет переставлять биты.

lexa - 19/Ноя/2008 14:00

А там не надо цепочки, мне же нужно просто сравнить два 8-байтных ключа в byte order.

lexa - 19/Ноя/2008 14:02

А эти betoh64 - оно где так называется?

А то на FreeBSD оно be64toh. и естественно bswap64 на интеле и ничего на "мотороле" (в смысле - Сане)

v_shabanoff (not verified) - 19/Ноя/2008 14:56

это я перепутал, лень было грепать /usr/include/machine

lexa - 19/Ноя/2008 15:56

Тьфу, пропасть, как же скормить "меньше" комментариям? Третья попытка

А я проверил, мне не жалко.

18млн ключей (никаких других данных нет)

2300 msec (округляю до 100ms) - мой вариант
3900 msec - твой вариант.

Возможное объяснение в том, что пространство ключей большое, распределены они случайно (ибо это хэши fnv64), поэтому первое же сравнение дает разницу в 255 из 256 случаев.

При этом, сама схема с cmove - хорошая, для numeric sort:
(a>b)-(a &lt; b) - 3500 msec
а мой тупой вариант
(a>b)?1:((a &lt; b)?-1:0)) - 3800 msec.

Ну и std::sort для numeric - 2300 ms - включая инициализацию std::vector,
а если ее не считать - то 1800ms - инлайнинг и алгоритм считается получше чем qsort.

v_shabanoff (not verified) - 19/Ноя/2008 18:21

ммм... мы на других данных получили противоположный результат, но у нас было 2 сравнения (16 байт) и отсортированные ключи, поэтому различия были обычно не в первом байте.

А ведь не выравнено? Возможно, два be32toh быстрее будут, т.к. при чтении 8 байт процессор может за двумя строками полезть.

Если не в лом, кинь чтоли дизассемблированный код обоих вариантов на гмыло vlad.shabanov. Самому интересно стало.

lexa - 20/Ноя/2008 01:15

Я по дизасемблеру отдельный пост напишу, только детей в школу сдам...

lexa - 20/Ноя/2008 05:43

С чего ему быть невыровненым, если malloc возвращает aligned на 16 (а в данном тесте вообще адрес буфера кончается на d00000)?

Потом я туда read прямо из файла, где 8-байтовые штуки лежат вплотную. Получается, всегда выровнено на 8 байт, ровнее не бывает.

(вот кстати реальные данные, а не просто ключи - 20-байтные + 8 байт ключа, интересно, будет ли быстрее, если подровнять).

dk42 (not verified) - 19/Ноя/2008 21:32

А пока я не полез профайлить, почему ты считаешь что для *современного* интела cmove лучше чем jmp (не indirect, конечно)? Мне представляется что это одно и то же, и оба спекулятивно исполняются.

v_shabanoff (not verified) - 20/Ноя/2008 04:20

Чисто интуитивно, при cmove у процессора только непонятки со значением регистра, а при jmp -- с тканью судьбы.

Если сгенерировался хороший код исходного варианта (mov; cmp; jmp; mov; cmp; jmp; ...), то получается 24 команды, в которых mov и cmp prefetch-ится, но толком не параллелятся, будем считать, что в среднем исполняется 12 штук. А если сгенерировался хороший код (mov; bswap; mov; bswap; cmp; cmovl; cmova; sub), то 5 команд, т.к. 1 и 3, 2 и 4, 6 и 7 могут параллелиться.

Когда первые байты сильно различаются, то на тысячной итерации всё предсказано и получаются 3 команды, что, конечно, бъёт наповал.

Только мне кажется, что оба варианта говённо скомпилировались и дело в волшебных пузырьках.
Ждём постинга с дизассемблированным кодом.

lexa - 20/Ноя/2008 04:31

Ну вот для первого варианта так и получилось примерно (mov,mov,cmp,jne).

А вот cmove пытаюсь получить по твоему варианту, пока никак. Уже третий вид gcc компилирую (попробовал 3.4 и 4.1, сейчас компилирую 4.3). Все что получалось пока - cmpq/seta/cmpq/setb/mov/sub)

Если и 4.3 не сделает твоего варианта - буду подробных показаний спрашивать.

v_shabanoff (not verified) - 20/Ноя/2008 04:51

а bswap правильно заинлайнился?

lexa - 20/Ноя/2008 04:56

Да, bswap - правильно.

Но даже с gcc43 -O3 -mtune=core2 -march=core2 получается (все в регистрах)
cmpq
seta
cmpq
setb
movzbl
subl
ret

Может я каких ключей недодал? Хотя код вполне разумный на самом деле....

v_shabanoff (not verified) - 20/Ноя/2008 05:17

да ладно, это как в анекдоте про преферансистов.

cmova/cmovb вряд ли отличается по времени от seta/setb а как заставить компилятор не делать лишнего сравнения я не знаю. Даже если заставить, всё равно будет не 3 команды.

lexa - 20/Ноя/2008 05:26

Ну, мне скорее интересно, откуда таки взялось cmov. Ибо для всех 64-битных архитектур gcc43 делает совершенно одинаковый код с -O2/O3 (для меньшей оптимизации начинаются всякие фокусы, -O0 - просто чудо природы).

А так - конечно пофигу.

v_shabanoff (not verified) - 20/Ноя/2008 05:42

cmov я руками писал когда-то, ещё в прошлой жизни. Распаковывал координаты в Рамблеровском индексе.

lexa - 20/Ноя/2008 05:44

Присвоить звание "слесарь-компилятор шестого разряда"

lexa - 20/Ноя/2008 04:33

И, кстати, интересная мысля - посчитать частоты исполнения кусочков первого варианта. Тоже сделаю....