Библиотека SSE Stdlib-esque?

Question

Как правило, все, что мне встречается в сети в связи с SSE / MMX, представляет собой математический материал для векторов и матраций.Однако я ищу библиотеки оптимизированных для SSE «стандартных функций», например, предоставляемые Agner Fog , или некоторые алгоритмы сканирования строк на основе SSE в GCC.

В качестве быстрогообщее изложение: это были бы такие вещи, как memset, memcpy, strstr, memcmp BSR / BSF, то есть stdlib-esque, построенный из интуиций SSE

Я бы предпочел, чтобы они были для SSE1 (формально MMX2) с использованием intrinsicsа не сборка, но либо в порядке.надеюсь, это не слишком широкий спектр.

Обновление 1

После некоторых поисков я наткнулся на несколько многообещающих вещей, одна библиотека попалась на глаза:

• LibFreeVec : кажется, только для mac / IBM (из-за того, что он основан на AltiVec), поэтому он малопригоден (для меня), плюс я не могу найти прямую ссылку для загрузки, и при этом она не указываетминимальная поддерживаемая версия SSE

Я также натолкнулся на статью о нескольких векторизованных строковых функциях (strlen, strstr strcmp).Однако SSE4.2 находится на уровне вне моей досягаемости (как было сказано выше, я бы хотел придерживаться SSE1 / MMX).

Обновление 2

Пол Р побудил меня сделать небольшой тест, поэтому, к сожалению, мой опыт кодирования сборки SSE близок к zip, я использовал чужой (http://www.mindcontrol.org/~hplus/) код тестирования и добавил к нему. Все тесты (кроме оригинала,VC6 SP5), скомпилированный под VC9 SP1 с полной / настраиваемой оптимизацией и включенным /arch:SSE.

Первый тест был на моей домашней машине (AMD Sempron 2200+ 512 МБ DDR 333) с ограничением по SSE1 (таким образом, нетвекторизация MSVC memcpy):

comparing P-III SIMD copytest (blocksize 4096) to memcpy
calculated CPU speed: 1494.0 MHz
  size  SSE Cycles      thru-sse    memcpy Cycles   thru-memcpy     asm Cycles      thru-asm
   1 kB 2879        506.75 MB/s     4132        353.08 MB/s     2655        549.51 MB/s
   2 kB 4877        598.29 MB/s     7041        414.41 MB/s     5179        563.41 MB/s
   4 kB 8890        656.44 MB/s     13123       444.70 MB/s     9832        593.55 MB/s
   8 kB 17413       670.28 MB/s     25128       464.48 MB/s     19403       601.53 MB/s
  16 kB 34569       675.26 MB/s     48227       484.02 MB/s     38303       609.43 MB/s
  32 kB 68992       676.69 MB/s     95582       488.44 MB/s     75969       614.54 MB/s
  64 kB 138637      673.50 MB/s     195012      478.80 MB/s     151716      615.44 MB/s
 128 kB 277678      672.52 MB/s     400484      466.30 MB/s     304670      612.94 MB/s
 256 kB 565227      660.78 MB/s     906572      411.98 MB/s     618394      603.97 MB/s
 512 kB 1142478     653.82 MB/s     1936657     385.70 MB/s     1380146     541.23 MB/s
1024 kB 2268244     658.64 MB/s     3989323     374.49 MB/s     2917758     512.02 MB/s
2048 kB 4556890     655.69 MB/s     8299992     359.99 MB/s     6166871     484.51 MB/s
4096 kB 9307132     642.07 MB/s     16873183        354.16 MB/s     12531689    476.86 MB/s

полные тесты

Второй тестовый пакет был выполнен на рабочей станции университета (Intel E6550, 2,33 ГГц, 2 ГБ DDR2 800?)

VC9 SSE/memcpy/ASM:
comparing P-III SIMD copytest (blocksize 4096) to memcpy
calculated CPU speed: 2327.2 MHz
  size  SSE Cycles      thru-sse    memcpy Cycles   thru-memcpy     asm Cycles      thru-asm
   1 kB 392         5797.69 MB/s    434         5236.63 MB/s    420         5411.18 MB/s
   2 kB 882         5153.51 MB/s    707         6429.13 MB/s    714         6366.10 MB/s
   4 kB 2044        4447.55 MB/s    1218        7463.70 MB/s    1218        7463.70 MB/s
   8 kB 3941        4613.44 MB/s    2170        8378.60 MB/s    2303        7894.73 MB/s
  16 kB 7791        4667.33 MB/s    4130        8804.63 MB/s    4410        8245.61 MB/s
  32 kB 15470       4701.12 MB/s    7959        9137.61 MB/s    8708        8351.66 MB/s
  64 kB 30716       4735.40 MB/s    15638       9301.22 MB/s    17458       8331.57 MB/s
 128 kB 61019       4767.45 MB/s    31136       9343.05 MB/s    35259       8250.52 MB/s
 256 kB 122164      4762.53 MB/s    62307       9337.80 MB/s    72688       8004.21 MB/s
 512 kB 246302      4724.36 MB/s    129577      8980.15 MB/s    142709      8153.80 MB/s
1024 kB 502572      4630.66 MB/s    332941      6989.95 MB/s    290528      8010.38 MB/s
2048 kB 1105076     4211.91 MB/s    1384908     3360.86 MB/s    662172      7029.11 MB/s
4096 kB 2815589     3306.22 MB/s    4342289     2143.79 MB/s    2172961     4284.00 MB/s

полные тесты

Как видно, SSE очень быстро работает в моей домашней системе, но падает на машине Intel (возможно, из-за плохого кодирования?Мой вариант сборки x86 идет вторым на моей домашней машине, а второй на Intel Syствол (но результаты выглядят немного противоречивыми, одно объятие блокирует доминирование над версией SSE1).MSVC memcpy выигрывает тестирование системы Intel на практике, это связано с векторизацией SSE2, хотя на моем домашнем компьютере она терпит неудачу, даже ужасные __movsd бьют ее ...

ловушки: память былавсе выровненные полномочия 2. кеш был (надеюсь) очищен.Для синхронизации использовался rdtsc.

. Интересные места: MSVC имеет (не во всех ссылках) __ movsd , он выводит тот же код ассемблера, который я использую, но он терпит неудачу (даже когда встроено!).Вероятно, поэтому его нет в списке.

VC9 memcpy можно принудительно векторизовать на моей машине, не относящейся к sse 2, однако это приведет к повреждению стека FPU, и, похоже, также содержит ошибку.

Этоявляется полным исходным кодом к тому, что я использовал для проверки (включая мои изменения, опять же, кредит http://www.mindcontrol.org/~hplus/ для оригинала).Двоичные файлы проекта доступны по запросу.

В заключение, кажется, что вариант переключения может быть лучшим, подобно MSVC crt, только намного более надежный с большим количеством опций и один раз-off проверяет (через встроенные указатели функций? или что-то более коварное, например, внутреннее исправление прямого вызова), однако для вставки, вероятно, придется использовать лучший метод вместо

Обновление 3

Вопрос, заданный Эшаном, напомнил о чем-то полезном и связанном с этим, хотя только для наборов битов и операций с битами, BitMagic и весьма полезен для больших наборов битов, он даже имеетхорошая статья по SSE2 (бит) оптимизации .К сожалению, это все еще не библиотека типов CRT / stdlib esque.Кажется, что большинство этих проектов посвящено небольшому разделу (проблем).

В связи с этим возникает вопрос, стоит ли тогда создавать проект crt / stdlib с открытым исходным кодом, возможно, многоплатформенный, с различными версиями стандартизированных функций, каждая из которых оптимизирована для определенной ситуации, а такжевариант функции «наилучший случай» / общего использования с ветвлением во время выполнения для скаляра / MMX / SSE / SSE2 + (как MSVC) или скаляром принудительной компиляции / SIMD swich.

Это может быть полезно дляHPC, или проекты, в которых учитывается каждый бит производительности (например, игры), освобождая программиста от беспокойства о скорости встроенных функций, требуя лишь небольшой настройки для поиска оптимального оптимизированного варианта.

Обновление 4

Я думаю, что природу этого вопроса следует расширить, чтобы включить методы, которые можно применять с использованием SSE / MMX для оптимизации для не векторных / матричных приложений, это, вероятно, можно использовать для32/64-битный скалярный код.Хорошим примером является то, как проверить наличие байта в данном 32/64/128/256-битном типе данных, используя скалярные методы (манипулирование битами), MMX и SSE / SIMD

. Также,Я вижу много ответов в духе «просто используй ICC», и это хороший ответ, это не мой вид ответа, так как, во-первых, ICC - это не то, что я могу использовать постоянно (если у Intel нет бесплатной студенческой версии для windows ), из-за 30 проб.во-вторых, и, что более важно, я интересуюсь не только самими библиотеками, но и методами, используемыми для оптимизации / создания содержащихся в них функций, для моей личной разработки и совершенствования, и поэтому я могу применять такие методы и принципы в своем собственном коде.(при необходимости), в сочетании с использованием этих библиотек.надеюсь, это прояснит эту часть:)

Answer 1

Вот статья о том, как использовать инструкции SIMD для векторизации подсчета символов:

http://porg.es/blog/ridiculous-utf-8-character-counting

Answer 2

strstr трудно оптимизировать, потому что (a) \ 0-termination означает, что вы все равно должны прочитать каждый байт, и (b) это должно быть хорошо и для всех крайних случаев.Тем не менее, вы можете побить стандартный strstr в 10 раз, используя SSE2 ops.Я заметил, что gcc 4.4 теперь использует эти операции для strlen, но не для других операций со строками.Подробнее о том, как использовать регистры SSE2 для strlen, strchr, strpbrk и т. Д., См. mischasan.wordpress.com .Прошу прощения за мой супер-краткий код.

#include <emmintrin.h> // Other standard #includes you can figure out...

static inline unsigned under(unsigned x)
    { return (x - 1) & ~x; }
static inline __m128i xmfill(char b)
    { return _mm_set1_epi8(b); }
static inline __m128i xmload(void const*p)
    { return _mm_load_si128((__m128i const*)p); }
static inline unsigned xmatch(__m128i a, __m128i b)
    { return _mm_movemask_epi8(_mm_cmpeq_epi8(a, b)); }

char const *sse_strstr(char const *tgt, char const *pat)
{
    unsigned    len = sse_strlen(pat);
    if (len == 0) return tgt;
    if (len == 1) return sse_strchr(tgt,*pat);
    __m128i     x, zero = {};
    __m128i     p0 = _m_set1_epi8(pat[0]), p1 = _m_set1_epi8(pat[1]);
    uint16_t    pair = *(uint16_t const*)pat;
    unsigned    z, m, f = 15 & (uintptr_t)tgt;
    char const* p;

    // Initial unaligned chunk of tgt:
    if (f) {
        z = xmatch(x = xmload(tgt - f), zero) >> f;
        m = under(z) & ((xmatch(x,p0) & (xmatch(x,p1) >> 1)) >> f);
        for (; m; m &= m - 1)
             if (!memcmp((p = tgt+ffs(m)-1)+2, pat+2, len-2))
                return p;
        if (z)
            return NULL;
        tgt += 16 - f;
        if (*(uint16_t const*)(tgt - 1) == pair
                && !memcmp(tgt+1, pat+2, len-2))
            return tgt - 1;
    }

    // 16-byte aligned chunks of tgt:
    while (!(z = xmatch(x = xmload(tgt), zero))) {
        m = xmatch(x,p0) & (xmatch(x,p1) >> 1);
        for (; m; m &= m - 1)
             if (!memcmp((p = tgt+ffs(m)-1)+2, pat+2, len-2))
                return p;
        tgt += 16;
        if (*(uint16_t const*)(tgt - 1) == pair && !memcmp(tgt+1, pat+2, len-2))
            return tgt - 1;
    }

    // Final 0..15 bytes of tgt:
    m = under(z) & xmatch(x,p0) & (xmatch(x,p1) >> 1);
    for (; m; m &= m - 1)
        if (!memcmp((p = tgt+ffs(m)-1)+2, pat+2, len-2))
            return p;

    return NULL;
}

Answer 3

Вот быстрая реализация memcpy в C, которая при необходимости может заменить стандартную библиотечную версию memcpy:

http://www.danielvik.com/2010/02/fast-memcpy-in-c.html

Answer 4

Честно говоря, я бы просто установил компилятор Intel C ++ и изучил различные доступные флаги автоматической оптимизации SIMD.У нас был очень хороший опыт оптимизации производительности кода путем простой компиляции его с помощью ICC.

Имейте в виду, что вся библиотека STL в основном просто заголовочные файлы, поэтому все это скомпилировано в ваш exe / lib / dllи как таковой может быть оптимизирован, как вам угодно.

ICC имеет много опций и позволяет вам указать (в самом простом), какие уровни SSE будут целевыми.Вы также можете использовать его для генерации двоичного файла с несколькими путями кода, так что, если оптимальная конфигурация SSE, с которой вы скомпилированы, недоступна, он запустит другой набор (все еще оптимизированный) кода, настроенный для менее мощного SIMD-процессора.

Answer 5

Вы можете использовать libc от Apple или OpenSolaris. Эти реализации libc содержат то, что вы ищете. Я искал подобные вещи около 6 лет назад, и мне пришлось мучительно писать это трудным путем.

Много лет назад я помню, как проходил конкурс кодов под названием « fastcode ». В то время они сделали потрясающую оптимизацию, используя Delphi. Смотрите их страницу результатов. Поскольку это написано в быстрой модели вызова функций Pascal (копирование аргументов в регистры), преобразование в модели вызовов функций stdc на языке C (проталкивание по стеку) может быть немного неудобным. Этот проект не имеет обновлений, так как долгое время, особенно, для SSE4.2 не написан код.

Solaris -> src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/lib/libc/

Apple -> www.opensource.apple.com/source/Libc/Libc-594.9.1/

Answer 6

Может быть libSIMDx86?

http://simdx86.sourceforge.net

Answer 7

Для простых операций, таких как memset, memcpy и т. Д., Где очень мало вычислений, мало смысла в оптимизации SIMD, поскольку пропускная способность памяти обычно является ограничивающим фактором.

Answer 8

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

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