Автор Тема: Ускорение линейного поиска  (Прочитано 5419 раз)

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Ускорение линейного поиска
« : Июнь 09, 2012, 07:53:05 pm »
Применил технику оптимизации из A6 для ускорения обычного линейного поиска.

Ускорилось на 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.

DIzer

  • Гость
Re: Ускорение линейного поиска
« Ответ #1 : Июнь 09, 2012, 08:07:51 pm »
то есть-  овчинка выделки не стоит?

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Ускорение линейного поиска
« Ответ #2 : Июнь 09, 2012, 08:34:49 pm »
то есть-  овчинка выделки не стоит?
Овчинка выделки стоит если оформить это библиотекой (шаблонной).
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Ускорение линейного поиска
« Ответ #3 : Июнь 10, 2012, 12:27:38 pm »
Ускорение зависит от размера переменной.

При трёх ифах (затем прыжок на 4 позиции) получаются следующие улучшения:

byte   5.8%
int16 11.7%
int32 15.9%
int64  5.8%

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Ускорение линейного поиска
« Ответ #4 : Январь 15, 2015, 03:08:47 pm »
Вот этот код на моём процессоре (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 букв вперёд.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Ускорение линейного поиска
« Ответ #5 : Январь 15, 2015, 05:25:51 pm »
Так конец строки-то он так и не находит.
Точнее, находит с погрешностью от 0 до 6.

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Ускорение линейного поиска
« Ответ #6 : Январь 16, 2015, 02:50:14 pm »
Ну как же не находит, всё находит. Сначала надо проверить что размер буфера достаточно большой, уж точно больше 7 букв. Заменить седьмую букву сзади на '\n' запомнив её настоящее значение. Применить указанный цикл. Вернуть седьмой букве сзади прежнее значение. Применить обычный одношаговый поиск с проверкой на переполнение буфера, чтоб проверить оставшиеся 7 букв. Вуаля.

Рассказал об этом на работе. Меня попросили сравнить скорость моего семимильного изврата с обычной стандартной memchr. Получилась история как в анекдоте про чукчу-не-читателя. Предопределённая memchr оказалась примерно в три раза быстрее моего поделья. Я был потрясён. Как такое возможно ??? ??? ???