Оптимизация скорости исполнения кода

[@Yakud]

спасибо К.О.

[@EaS]

А оптимизации-то какие использовались?

[@EaS]

В смысле оптимизации компилятора, конечно…

[@Harkonnen]

#include <regex.h>

[@shadoof]

Оптимизации компилятора — никаких. Как только оптимизатор замечает что функция вызывается N раз, а результат используется только один(ну в смысле в циклах для замера времени) — он делает один вызов вместо N. И все засекание времени накрывается.

[@gribozavr]

Тогда тест нерепрезентативен. Используйте результат как-то, например, считайте их сумму или проверяйте на равенство с 42 и выходите из цикла и т. д.

[@deep_orange]

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

__asm__ __volatile__ ("");

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

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

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

[@bobermaniac]

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

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

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

[@shadoof]

Один и тот же алгоритм при замене только *части* кода ассемблерными вставками выполняется почти в полтора(1,41) раза быстрее. Из моего опыта, если заменить еще цикл и ветвления — то будет все 2 раза.

[@bobermaniac]

Это без включенных оптимизаций компилятора, конечно же. Я прав?

[@shadoof]

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

[@bobermaniac]

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

В таком случае, соглашусь — ассемблерная вставка зачастую будет быстрее неоптимизированного кода.

[@ElleSolomina]

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

[@gribozavr]

А где алгоритм с lookup table?

[@sdevalex]

Где можно почитать о том, что функция search1 хуже регулярок? Когда только начал читать, то казалось, что search1 будет быстрой.

[@shadoof]

«Алгоритмические трюки для программистов» Г. Уоррен. Алгоритмы поиска одного символа в строке. Там рассмотрено на примере нулевого.

[@gribozavr]

Она будет быстрой если использовать флаги оптимизации компилятора.

[@petropavel]

она и есть быстрая:

./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, а вариант с ассемблерными вставками падал сразу, и мне было лень его чинить.

[@namezys]

А еще можно итерировать указатель.
Если уж лезти в дебри, то иттерировать его на 4 или 8, правда я н е уверен, что компилятор догадается загнать слово в регист и проверять по частям. Да и это может быть менее выгодно, с учетом возможности паралельности комманд на процесморе

[@namezys]

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

Автору минимум стоит посмотреть листинг ассемблера для его архитектуры.
Если надо уж совсем быстро, то О3 в помощь

[@remal]

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

[@Maratyszcza]

На дворе уже почти 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;
}

[@Funbit]

Интересно было бы посмотреть на сравнение скорости этого алгоритма с теми, что были предложены в топике.

[@Maratyszcza]

Я не против, посмотрите =)

[@Funbit]

Намёк понял =)

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

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

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

[@FINTER]

Ну подобными джедайскими техниками далеко не каждый обладает :)
Скажем, лично я знал, что так в теории можно, но как это на практике используют узнал только сейчас из вашего кода. Но правда HPC не мой конек, хотя наверно те, кому надо это все знают.

[@namezys]

Ну не такая и джидайская, по сравнению с прямым ассемблером

[@namezys]

Это как я понимаю gcc и встроенные функции?
Неужели хоть кто-то догадался их использовать

[@Maratyszcza]

Это MSVC и intrinsics. SIMD intrinsics поддерживаются всеми приличными компиляторами одинаково, а вот не-SIMD тоже поддерживаются, но у каждого компилера называются по-своему.

[@Fragster]

в начале файла забыли комментарий
// счастливой отладки

[@Fragster]

Ну и кодовые страницы бывают разные у строк, что делает всякие ассемблерные трюки еще более неуниверсальными.

[@runnig]

Без strlen() на самописная ф-ция быстрее на ~30%:

search1 531
search1_no_strlen 297
search2 172
find_digit 63

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

Код (под win): codepad.org/7wx4aW0Y

[@akalend]

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

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

Уверен, что скорость будет раза в два быстрее чем по Алгоритм 1

[@akalend]

увы :( опередили уже.