Pull to refresh

Comments 39

А оптимизации-то какие использовались?
В смысле оптимизации компилятора, конечно…
Оптимизации компилятора — никаких. Как только оптимизатор замечает что функция вызывается N раз, а результат используется только один(ну в смысле в циклах для замера времени) — он делает один вызов вместо N. И все засекание времени накрывается.
UFO landed and left these words here
Тогда тест нерепрезентативен. Используйте результат как-то, например, считайте их сумму или проверяйте на равенство с 42 и выходите из цикла и т. д.

Чтобы подавить элиминацию цикла, делай в цикле


__asm__ __volatile__ ("");

Но только с GCC прокатит. Clang и это оптимизирует. А результат функции


if (x == func(a, b)) {
    __asm__ __volatile__ ("");
}

Но блин. Всё равно какие-то из циклов получаются на удивление короткими начиная с 02. Я делал сложение результата я с глобальной переменной, а входные данные генерировал рандомом во время работы. Но всё равно не уверен в результатах с -O3 и -Ofast

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

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

Компиляторы уже давно генерируют практически оптимальный код, и от того, что вы выполните работу компилятора, ничего особо не изменится.
Один и тот же алгоритм при замене только *части* кода ассемблерными вставками выполняется почти в полтора(1,41) раза быстрее. Из моего опыта, если заменить еще цикл и ветвления — то будет все 2 раза.
Это без включенных оптимизаций компилятора, конечно же. Я прав?
Я уже писал про оптимизации компилятора. Она работает несколько иначе. Код оптимизирован под процессор(я вводил core2) но не использовались -O — потому что они анализируют код убирая «лишние» вызовы и т.п., при этом особо не трогает тело функции. В С я работаю исключительно с памятью. И компилятор старается тоже так делать. А в ассемблерной вставке — регистры. Кроме того несколько уменьшается количество команд.
Ну, то есть оптимизации компилятора не было, потому что она накрывала раком ваш красивый и простой тест.

В таком случае, соглашусь — ассемблерная вставка зачастую будет быстрее неоптимизированного кода.
Простите пожалуйста, перефразирую ваши слова: в таком случае, соглашусь — ассемблерная вставка зачастую будет быстрее изначально кривого кода на языке высокого уровня который даже компилятор понять не может.
UFO landed and left these words here
Где можно почитать о том, что функция search1 хуже регулярок? Когда только начал читать, то казалось, что search1 будет быстрой.
«Алгоритмические трюки для программистов» Г. Уоррен. Алгоритмы поиска одного символа в строке. Там рассмотрено на примере нулевого.
Она будет быстрой если использовать флаги оптимизации компилятора.
она и есть быстрая:

./a.out
Function strchr used 0.880 seconds 9072
Function strchr used 0.580 seconds 9072
Function strchr used 0.360 seconds 9072
Function strchr used 0.290 seconds 9072

это компилировалось gcc -O3. Первый результат — regexp, второй — search1. третий — тот же search1, но тупо с четырьмя проверками на итерацию:

  for (i=0;i<l;i+=4){
    if ((str[i] >= '0') && (str[i] <= '9'))          return (i);
    if ((str[i+1] >= '0') && (str[i+1] <= '9')) return (i+1);
    if ((str[i+2] >= '0') && (str[i+2] <= '9')) return (i+2);
    if ((str[i+3] >= '0') && (str[i+3] <= '9')) return (i+3);
  }


четвертый — search2, а вариант с ассемблерными вставками падал сразу, и мне было лень его чинить.
А еще можно итерировать указатель.
Если уж лезти в дебри, то иттерировать его на 4 или 8, правда я н е уверен, что компилятор догадается загнать слово в регист и проверять по частям. Да и это может быть менее выгодно, с учетом возможности паралельности комманд на процесморе
Функция 1 не может быть хуже регулярок (конечного автомата).
Причина банальная: библиотека собрана с оптимизацией, код — без.
Думаю, компилятор лучше программиста учтет все особенности арифмитического блока профессора с сгенерирует еще более оптимальный код.

Автору минимум стоит посмотреть листинг ассемблера для его архитектуры.
Если надо уж совсем быстро, то О3 в помощь
Одно меня удивила, что скорость регулярок сравнима с оптимизированным алгоритмом даже с использованием ассемблерных вставок? Быть может стоит лучше посмотреть какие там используются алгоритмы, а не городить свой велосипед, который, как я подозреваю, все равно не оптимален.
На дворе уже почти 2012 год, и не использовать SIMD в HPC коде есть преступление!

#include <intrin.h>

const char* find_digit(const char* str) {
    static const __m128i str_mask[16] = {
        _mm_set_epi32(0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00FFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x0000FFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x000000FF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x00FFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x0000FFFF, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x000000FF, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x00000000, 0x00FFFFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x00000000, 0x0000FFFF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x00000000, 0x000000FF, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0xFFFFFFFF),
        _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x00FFFFFF),
        _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x0000FFFF),
        _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x000000FF)
    };
    static const __m128i str_offset = _mm_set1_epi8(127 - '9');
    static const __m128i str_threshold = _mm_set1_epi8(127 - 10);
    const size_t str_misalignment = ((size_t)str) & ((size_t)15);
    const __m128i* str_aligned = (const __m128i*)(((size_t)str) - str_misalignment);
    __m128i str_vector = _mm_load_si128(str_aligned);
    str_vector = _mm_and_si128(str_vector, str_mask[str_misalignment]);
    str_vector = _mm_add_epi8(str_vector, str_offset);
    int str_bitmask = _mm_movemask_epi8(_mm_cmpgt_epi8(str_vector, str_threshold));
    unsigned long index;
    _BitScanForward(&index, str_bitmask);
    while (str_bitmask == 0) {
        str_aligned += 1;
        str_vector = _mm_load_si128(str_aligned);
        str_vector = _mm_add_epi8(str_vector, str_offset);
        str_bitmask = _mm_movemask_epi8(_mm_cmpgt_epi8(str_vector, str_threshold));
        _BitScanForward(&index, str_bitmask);
    }
    return ((const char*)str_aligned) + index;
}
Интересно было бы посмотреть на сравнение скорости этого алгоритма с теми, что были предложены в топике.
Намёк понял =)

На моей машине цифры получились такие:

search1 used 4.547 seconds 9100
search2 used 1.059 seconds 9100
find_digit used 0.365 seconds 9100

Т.е. аппроксимируя результаты автора топика, ваш вариант примерно в 2 раза быстрее, чем search3 с ассемблерной оптимизацией.

Ну подобными джедайскими техниками далеко не каждый обладает :)
Скажем, лично я знал, что так в теории можно, но как это на практике используют узнал только сейчас из вашего кода. Но правда HPC не мой конек, хотя наверно те, кому надо это все знают.
Ну не такая и джидайская, по сравнению с прямым ассемблером
Это как я понимаю gcc и встроенные функции?
Неужели хоть кто-то догадался их использовать
Это MSVC и intrinsics. SIMD intrinsics поддерживаются всеми приличными компиляторами одинаково, а вот не-SIMD тоже поддерживаются, но у каждого компилера называются по-своему.
в начале файла забыли комментарий
// счастливой отладки
Ну и кодовые страницы бывают разные у строк, что делает всякие ассемблерные трюки еще более неуниверсальными.
А еще больше жопа с портированием на x64 асм вставок (особенно если используется VS)
Без strlen() на самописная ф-ция быстрее на ~30%:

search1 531
search1_no_strlen 297
search2 172
find_digit 63

find_digit с интринзиками действительно скоростная, но сигнатура у неё отличается от предыдущих, правильность её не подтверждаетсяя экспериментами.

Код (под win): codepad.org/7wx4aW0Y
l = strlen(str); — жестоко. Тут у вас двойной прогон по строке. В первой итерации (которая в strlen) прогоняется вся строка в поисках символа 0x00, а потом опять прогоняется строка в поисках цифры. Не проще ли было бы сделать так:
int search1(char *str)
{
char* p = str;
while (*p)
{
if (*p >= '0' && *p <= '9') return (p - str);
p++;
}

return (-1);
}

Что-то в предпросмотре код выглядел нормально, а тот его разворотило.
ассемблерные вставки — конечно круто, но Алгоритм 1 можно оптимизировать проще:
strlen() — функция не нужна — это по сути второй не нужный цикл.

используем один цикл  while и проверяем:
а) на вхождение нулевого символа
б) на диапазон 30-39 Символы 0-9

Уверен, что скорость будет раза в два быстрее чем по Алгоритм 1
Only those users with full accounts are able to leave comments. Log in, please.