Oberon space
General Category => Общий раздел => Тема начата: Губанов Сергей Юрьевич от Июнь 09, 2012, 07:53:05 pm
-
Применил технику оптимизации из A6 (http://oberspace.dyndns.org/index.php/topic,253.msg6395.html#msg6395) для ускорения обычного линейного поиска.
Ускорилось на 11%.
Эталонный алгоритм:
static long L1 (char* begin)
{
char* p = begin;
while (*p != 0)
{
p++;
}
return (long)(p - begin);
}
Ускоренный алгоритм:
static long L2 (char* begin)
{
char* p = begin;
while (*p != 0)
{
if (*(p + 1) == 0)
{
p++;
}
else if (*(p + 2) == 0)
{
p += 2;
}
else
{
p += 3;
}
}
return (long)(p - begin);
}
Прогнал сто раз по массиву из миллиарда букв:
L1 27.9264553 секунд
L2 24.9913335 секунд
Добавление более двух веток if-else результата не изменило. Использование всего одной ветки if-else результат только ухудшило.
Для маленьких массивов целиком убирающихся в кэш процессора ускорение составило всего 1%.
Win 7 64bit, .Net 4.0, i7 3770K.
-
то есть- овчинка выделки не стоит?
-
то есть- овчинка выделки не стоит?
Овчинка выделки стоит если оформить это библиотекой (шаблонной).
-
Ускорение зависит от размера переменной.
При трёх ифах (затем прыжок на 4 позиции) получаются следующие улучшения:
byte 5.8%
int16 11.7%
int32 15.9%
int64 5.8%
-
Вот этот код на моём процессоре (Tilera)
while ((*c != '\n') & (*(c+1) != '\n') & (*(c+2) != '\n') & (*(c+3) != '\n') & (*(c+4) != '\n') & (*(c+5) != '\n') & (*(c+6) != '\n'))
{
c += 7;
}
на больших массивах ищет конец строки по меньшей мере в 2.44 раза быстрее чем
while (*c != '\n')
{
c++;
}
Подходящих SIMD инструкций аналогичных Интеловским SSE в Тилере нету, так что сделать линейный поиск конца строки ещё более быстрым видимо не получится.
А с SSE прикольно было бы, можно было бы скакать сразу на 16 букв вперёд.
-
Так конец строки-то он так и не находит.
Точнее, находит с погрешностью от 0 до 6.
-
Ну как же не находит, всё находит. Сначала надо проверить что размер буфера достаточно большой, уж точно больше 7 букв. Заменить седьмую букву сзади на '\n' запомнив её настоящее значение. Применить указанный цикл. Вернуть седьмой букве сзади прежнее значение. Применить обычный одношаговый поиск с проверкой на переполнение буфера, чтоб проверить оставшиеся 7 букв. Вуаля.
Рассказал об этом на работе. Меня попросили сравнить скорость моего семимильного изврата с обычной стандартной memchr. Получилась история как в анекдоте про чукчу-не-читателя. Предопределённая memchr оказалась примерно в три раза быстрее моего поделья. Я был потрясён. Как такое возможно ??? ??? ???