Здравствуйте, VladFein, Вы писали:
VF>А может ну его тогда, такой компилятор?
Ко всему прочему, он ещё в полтора-два раза сливает обычному Ц, даже при табличном доступе.
А мышки плакали, кололись, но продолжали...
Впрочем, это уже похоже на оффтоп и языкосрач
Здравствуйте, cures, Вы писали:
C>Здравствуйте, VladFein, Вы писали:
VF>>А может ну его тогда, такой компилятор?
C>Ко всему прочему, он ещё в полтора-два раза сливает обычному Ц, даже при табличном доступе.
C>А мышки плакали, кололись, но продолжали...
C>Впрочем, это уже похоже на оффтоп и языкосрач
А кто в языковом мире не сливает обычному Ц?
Здравствуйте, Sharov, Вы писали:
S>А кто в языковом мире не сливает обычному Ц?
Нет таких, даже Ц сам себе сливает
Хотя есть ассемблер, но и на нём надо очень постараться, чтобы обогнать.
Вопрос только в том, насколько сливает. Диез в этом плане не так плох, примерно как жаба, только чуть удобнее, так как есть value-type структуры. Планируется ещё Julia над шлангом, совмещающая скорость и всепрощение к неумеющим работать с памятью, но там индексы с единицы — не взлетит.
Здравствуйте, cures, Вы писали:
C>Кстати, вот ещё один варант функции F:
C>C>return (byte) (((0x321010 >> ((i << 2) & 20)) ^ (0xc84040 >> ((i >> 2) & 20))) & 0xf);
C>
C>Немножко извращённый, но вроде бы делает то же самое, но чуть быстрее. Тут 4 сдвига, 3 энда и один ксор.
Пример, конечно, интересный, но почему быстрее? Из-за числа инструкций что-ли? Так скорость не только от их количества зависит. Более длинная программа может значительно обгонять короткую.
C>Если они могут выполняться по 3 за такт,
Посмотри на код, тут используется аж два сдвига на переменную, а не на постоянную величину. На intel это традиционный тормоз по меркам побитовых операций.
C> то вычисление на sse2 может уложиться в 3 такта, а не в 4
Ну какое ещё sse2?
Нет для этого кода никакого будущего на sse — он крайне плохо подходит для векторизации.
Во-первых, тут сдвигаются большие числа (вроде 0xc84040) для их хранения тебе не хватит ни 8, ни 16 бит, а следовательно в xmm регистр поместятся лишь 4 операнда за раз. Плюс ещё понадобится код для распаковки байтов в эти 32х битные операнды. Хотя есть куда более простой код (см. далее), который прекрасно обрабатывает сразу 16 байтами за раз, полностью используя весь регистр.
Во-вторых, в sse2 нельзя сдвинуть значения xmm регистра на различные величины. Только на константу, либо на переменную, но одинаковую для всего регистра. А произвольный сдвиг ни на sse2, ни на sse3, sse4 или avx сделать нельзя. Только в avx2 впервые появилась инструкция параллельного сдвига (vpsrlvd). Да, довольно поздно для банального побитового сдвига, но так уж есть.
А ещё, если всё же взять процессоры с avx2, то там рядом будет набор набор инструкций bmi2, в котором есть инструкция pext — она вообще решает исходную задачу в одно действие —
pext eax, 0x55 (и больше ничего не нужно). На фоне этого связываться с векторизацией вышеприведённой реализации функции — совсем сомнительная затея.
Если уж хочется использовать sse для быстрого преобразования, то делать нужно не так.
Нужно сначала написать обычный код для байта, желательно получше чем в первом сообщении, например, такой:
ui8 dz1(ui8 u) {
u &= 0x55;
u |= u >> 1;
u &= 0x33;
u |= u >> 2;
u &= 0x0f;
return u;
}
И обобщить его на вектор из байт. Можно под вектором подразумевать не обязательно xmm регистр, а даже взять обычный 32/64 битный регистр общего назначения:
ui32 dz4(ui32 u) {
u &= 0x55555555;
u |= u >> 1;
u &= 0x33333333;
u |= u >> 2;
u &= 0x0f0f0f0f;
return u;
}
Либо всё же xmm:
#include "emmintrin.h"
__m128i dz16(__m128i u) {
u = _mm_and_si128(u, _mm_set1_epi8(0x55));
u = _mm_or_si128(u, _mm_srli_epi32(u, 1));
u = _mm_and_si128(u, _mm_set1_epi8(0x33));
u = _mm_or_si128(u, _mm_srli_epi32(u, 2));
u = _mm_and_si128(u, _mm_set1_epi8(0x0f));
return u;
}
Вот так.
При использовании компилятора gcc-4.8 в простеньком тесте на ноутбуке вариант со сдвигом констант 0x321010 и 0xc84040 обрабатывает 0.617*10
9 элементов в секунду. Вариант с lookup-table работает значительно быстрее и обрабатывает уже 2.593*10
9 элементов в секунду. А последние два варианта (dz4 и dz16) обрабатывают по 5.970*10
9 элементов в секунду (разницы между использованием в коде 32 и 128 битных регистров нет из-за того, что у gcc хороший автовекторизатор, и компилятор сам переписал цикл с функцией dz4 на sse2, получив почти аналог dz16).
В общем, получается так, что вариант с sse2 действительно быстрее. И при компиляции в нативный код обгоняет lookup-table где-то в 2.3 раза. Причём для его использования не обязательно даже писать simd код, а достаточно просто взять хороший компилятор и выставить соответствующие настройки оптимизации. Но зато вариант с LUT, хоть и медленнее, но удобнее в использовании — он не требует особой организации данных как вариант с sse2. Да и из C# дергать его сподручнее чем sse2 код.