Comments 39
спасибо К.О.
-8
А оптимизации-то какие использовались?
+3
Оптимизации компилятора — никаких. Как только оптимизатор замечает что функция вызывается N раз, а результат используется только один(ну в смысле в циклах для замера времени) — он делает один вызов вместо N. И все засекание времени накрывается.
0
UFO just landed and posted this here
Тогда тест нерепрезентативен. Используйте результат как-то, например, считайте их сумму или проверяйте на равенство с 42 и выходите из цикла и т. д.
0
Чтобы подавить элиминацию цикла, делай в цикле
__asm__ __volatile__ ("");
Но только с GCC прокатит. Clang и это оптимизирует. А результат функции
if (x == func(a, b)) {
__asm__ __volatile__ ("");
}
Но блин. Всё равно какие-то из циклов получаются на удивление короткими начиная с 02. Я делал сложение результата я с глобальной переменной, а входные данные генерировал рандомом во время работы. Но всё равно не уверен в результатах с -O3 и -Ofast
0
А откуда вообще пошла байка о мистических ассемблерных вставках, которые можно использовать для фундаментального ускорения?
Есть некоторые задачи, которые можно ускорить за счет векторных инструкций, и это единственный пример, когда разница в производительности действительно поражает.
Компиляторы уже давно генерируют практически оптимальный код, и от того, что вы выполните работу компилятора, ничего особо не изменится.
Есть некоторые задачи, которые можно ускорить за счет векторных инструкций, и это единственный пример, когда разница в производительности действительно поражает.
Компиляторы уже давно генерируют практически оптимальный код, и от того, что вы выполните работу компилятора, ничего особо не изменится.
+6
Один и тот же алгоритм при замене только *части* кода ассемблерными вставками выполняется почти в полтора(1,41) раза быстрее. Из моего опыта, если заменить еще цикл и ветвления — то будет все 2 раза.
0
Это без включенных оптимизаций компилятора, конечно же. Я прав?
+3
Я уже писал про оптимизации компилятора. Она работает несколько иначе. Код оптимизирован под процессор(я вводил core2) но не использовались -O — потому что они анализируют код убирая «лишние» вызовы и т.п., при этом особо не трогает тело функции. В С я работаю исключительно с памятью. И компилятор старается тоже так делать. А в ассемблерной вставке — регистры. Кроме того несколько уменьшается количество команд.
-4
Ну, то есть оптимизации компилятора не было, потому что она накрывала раком ваш красивый и простой тест.
В таком случае, соглашусь — ассемблерная вставка зачастую будет быстрее неоптимизированного кода.
В таком случае, соглашусь — ассемблерная вставка зачастую будет быстрее неоптимизированного кода.
+11
А где алгоритм с lookup table?
+2
UFO just landed and posted this here
Где можно почитать о том, что функция search1 хуже регулярок? Когда только начал читать, то казалось, что search1 будет быстрой.
0
«Алгоритмические трюки для программистов» Г. Уоррен. Алгоритмы поиска одного символа в строке. Там рассмотрено на примере нулевого.
+1
Она будет быстрой если использовать флаги оптимизации компилятора.
0
она и есть быстрая:
./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, но тупо с четырьмя проверками на итерацию:
четвертый — search2, а вариант с ассемблерными вставками падал сразу, и мне было лень его чинить.
./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, а вариант с ассемблерными вставками падал сразу, и мне было лень его чинить.
+1
Функция 1 не может быть хуже регулярок (конечного автомата).
Причина банальная: библиотека собрана с оптимизацией, код — без.
Думаю, компилятор лучше программиста учтет все особенности арифмитического блока профессора с сгенерирует еще более оптимальный код.
Автору минимум стоит посмотреть листинг ассемблера для его архитектуры.
Если надо уж совсем быстро, то О3 в помощь
Причина банальная: библиотека собрана с оптимизацией, код — без.
Думаю, компилятор лучше программиста учтет все особенности арифмитического блока профессора с сгенерирует еще более оптимальный код.
Автору минимум стоит посмотреть листинг ассемблера для его архитектуры.
Если надо уж совсем быстро, то О3 в помощь
+1
Одно меня удивила, что скорость регулярок сравнима с оптимизированным алгоритмом даже с использованием ассемблерных вставок? Быть может стоит лучше посмотреть какие там используются алгоритмы, а не городить свой велосипед, который, как я подозреваю, все равно не оптимален.
0
На дворе уже почти 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;
}
+11
Интересно было бы посмотреть на сравнение скорости этого алгоритма с теми, что были предложены в топике.
0
Я не против, посмотрите =)
0
Ну подобными джедайскими техниками далеко не каждый обладает :)
Скажем, лично я знал, что так в теории можно, но как это на практике используют узнал только сейчас из вашего кода. Но правда HPC не мой конек, хотя наверно те, кому надо это все знают.
Скажем, лично я знал, что так в теории можно, но как это на практике используют узнал только сейчас из вашего кода. Но правда HPC не мой конек, хотя наверно те, кому надо это все знают.
0
Это как я понимаю gcc и встроенные функции?
Неужели хоть кто-то догадался их использовать
Неужели хоть кто-то догадался их использовать
0
в начале файла забыли комментарий
// счастливой отладки
+1
Без strlen() на самописная ф-ция быстрее на ~30%:
search1 531
search1_no_strlen 297
search2 172
find_digit 63
find_digit с интринзиками действительно скоростная, но сигнатура у неё отличается от предыдущих, правильность её не подтверждаетсяя экспериментами.
Код (под win): codepad.org/7wx4aW0Y
search1 531
search1_no_strlen 297
search2 172
find_digit 63
find_digit с интринзиками действительно скоростная, но сигнатура у неё отличается от предыдущих, правильность её не подтверждаетсяя экспериментами.
Код (под win): codepad.org/7wx4aW0Y
+1
UFO just landed and posted this here
ассемблерные вставки — конечно круто, но Алгоритм 1 можно оптимизировать проще:
strlen() — функция не нужна — это по сути второй не нужный цикл.
используем один цикл while и проверяем:
а) на вхождение нулевого символа
б) на диапазон 30-39 Символы 0-9
Уверен, что скорость будет раза в два быстрее чем по Алгоритм 1
strlen() — функция не нужна — это по сути второй не нужный цикл.
используем один цикл while и проверяем:
а) на вхождение нулевого символа
б) на диапазон 30-39 Символы 0-9
Уверен, что скорость будет раза в два быстрее чем по Алгоритм 1
0
Sign up to leave a comment.
Оптимизация скорости исполнения кода