Библиотека SSE Stdlib-esque? - программирование

В общем, все, что я встречаю "по-сети" по отношению к SSE/MMX, появляется как материал математики для векторов и матрасов. Тем не менее, я ищу библиотеки оптимизированных "стандартных функций" SSE, таких как те, которые предоставляются Agner Fog или некоторые из строк на основе SSE алгоритмы сканирования в GCC.

Как быстрое общее изложение: это будут такие вещи, как memset, memcpy, strstr, memcmp BSR/BSF, т.е. stdlib-esque, созданный из SSE-интроктов

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

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

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

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

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

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

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

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

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

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

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

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

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

Возникает вопрос: тогда было бы целесообразно создать проект с открытым исходным кодом, возможно многоплатформенный проект crt/stdlib, создающий различные версии стандартизованных функций, каждый из которых оптимизирован для определенной ситуации, а также " наилучшего варианта/общего использования функции с ветвлением развёртки для скаляра /MMX/SSE/SSE 2 + (à la MSVC) или сканированием времени принудительной компиляции /SIMD swich.

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

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

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

Ответы

Ответ 1

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

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

Ответ 2

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

Ответ 3

Может быть, libSIMDx86?

http://simdx86.sourceforge.net

Ответ 4

Вы можете использовать apple или OpenSolaris libc. Эти реализации 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/

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

strstr трудно оптимизировать, потому что (a)\0-term означает, что вы должны читать каждый байт в любом случае, и (б) он должен быть хорошим во всех случаях кросс.

С учетом сказанного вы можете обыграть стандартную strstr в 10 раз, используя SSE2 ops. Я заметил, что gcc 4.4 использует эти ops для strlen сейчас, но не для другие строки ops. Подробнее о том, как использовать регистры 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;
}

Ответ 8

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

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