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



    Данная статья о том, как классические алгоритмы позволяют сделать наш код быстрее. Мы рассмотрим алгоритм поиска нулевого бита и то как он нам может помочь повысить эффективность алгоритма поиска символа из диапазона (например найти первое вхождение символа из диапазона 0-9 в строке).
    Т.е. просто сферический конь в вакууме довольно распространенная ситуация при обработке текста, когда необходимо найти положение первой цифры в произвольном тексте. То, с чего многие начинают учить регулярные выражения.
    В статье описывается использование gcc. При желании все можно повторить под другие компиляторы и языки с небольшими переделками. Осторожно, под катом есть ассемблер!

    Для решения этой задачи мы можем воспользоваться такими путями:
    1) Воспользоваться библиотекой регулярных выражений.
    2) Написать функцию для поиска самостоятельно.
    В случае если строки маленькие, вопрос об оптимизации не возникает. Данная задача становиться интересной когда длинна строк увеличивается, либо имеет место большое количество проверок.
    Время исполнения будем замерять при помощи функции clock() из подключаемого файла <time.h>.

    Используем REGEX

    Рассмотрим способ с использованием регулярных выражений. Один из первых методов который приходит в голову — воспользоваться библиотекой REGEX. Регулярное выражение будет выглядеть так:
    "[[:digit:]]"
    Код для использования этой библиотеки может быть таким:
    clock_t tbefore;
        long i;    
        double eplased;    
        int pmatch[1];
        regex_t regex;
        int reti;
    ….
    /*REGEXP usage*/
       tbefore = clock();
       reti = regcomp( & regex, "[[:digit:]]", 0);   
       for (i=1;i<100000;i++){
            reti = regexec(& regex, test_string, 1, pmatch, 0);	
       }   
       eplased=clock()-tbefore;
       printf("Function strchr used %.3f seconds %d\n", eplased/CLOCKS_PER_SEC, pmatch[0]);    
       regfree( & regex);
    /**************/
    

    Скорость исполнения: 1.74 сек.
    В данном коде я намеренно убрал проверки на успешность компиляции и поиска, т. е. использовать данный код для решения реальных задач нельзя. Но для проверки скорости в «тепличных» условиях — самое то. Кроме того, я замеряю время исполнения с учетом компиляции регулярного выражения и освобождения памяти после его использования.

    Своя функция для поиска

    Попробуем воспользоваться традиционным подходом — в лоб. Функция поиска
    будет выглядеть таким образом (Алгоритм 1):
    int search1(char *str){
      int l=0;
      int i;
      
      l = strlen(str);
      for (i=0;i<l;i++){
        if ((str[i] >= '0') && (str[i] <= '9')){
          return (i);
        }
      }  
      
      return (-1);
    }
    

    Скорость исполнения: 7.19 сек.
    И результаты замеров показывают более чем в четыре раза меньшую скорость исполнения! Чего и следовало ожидать.

    Оптимизированный алгоритм

    Попробуем оптимизировать. Когда-то в руки мне попалась книга «Алгоритмические трюки для программистов» Г. Уоррена. И в этой книге было описание алгоритмов поиска нулевого символа в строке. Эти алгоритмы используются например в языке С для поиска конца строки. Также в одном из абзацев предложено обобщение одного из таких алгоритмов для описка диапазона.
    Идея алгоритма заключается в том, что для поиска индекса символа в строке перебирают не по по дному символу, а сразу по четыре, считывая из массива двойные слова(dword = 4 byte). Т.е. В терминах языка С мы из массива символов (char) считываем длинные целые (unsigned).
    После этого этого со словом проводятся арифметические действия. Для диапазона от нуля до девяти это выглядит таким образом:
    int zbytel3(unsigned z) {
       unsigned y;
       x = z ^ 0x30303030;  
                             				// Original byte: 00 80 other
       y = (x & 0x7F7F7F7F) + 0x76767676; // 7F 7F 1xxxxxxx
       y = ~(y | x | 0x7F7F7F7F);         // 80 00 00000000
                                          // These steps map:
       if (y == 0) return 4;              // 00000000 ==> 4,
       else if (y > 0x0000FFFF)           // 80xxxxxx ==> 0,
          return (y >> 31) ^ 1;           // 0080xxxx ==> 1,
       else                               // 000080xx ==> 2,
          return (y >> 15) ^ 3;           // 00000080 ==> 3.
    }
        


    т. е. x = z ^ 0x30303030 — операция исключающее или, которая превращает минимальное число диапазона „0“ — 0x30 в 0. 0x76 = 0x7F-9, где 9=n-1, где n — количество символов в диапазоне.
    Далее простая байтовая арифметика, в результате которой можно получить число, которое обрабатыватеся в ветвлении, и в результате мы получаем цифры от 1 до 4. Т.е. если символ не найден — то 4.
    Теперь наша функция примет такой вид:
    int search2( char *str){
      int n, j = 0;  
      unsigned x, y, *r;
      const char *c_ptr;
      //Проверяем посимвольно первые байты, пока не выровняем.
       for (c_ptr=str; ((unsigned long int)c_ptr & (sizeof(x) - 1)) != 0; ++c_ptr)
        if ((*c_ptr >= '0') && (*c_ptr <= '9'))
          return c_ptr - str;
      
      r = (unsigned *) c_ptr;
      j = c_ptr - str ;  
      while (1){            
          x = *r ^ 0x30303030;                                           	    
          y = (x & 0x7F7F7F7F) + 0x76767676;
          y = ~(y | x | 0x7F7F7F7F);         
          
          // These steps map:
          if (y == 0) n = 4;              // 00000000 ==> 4,
          else if (y > 0x0000FFFF)        // 80xxxxxx ==> 0,
          n= (y >> 31) ^ 1;               // 0080xxxx ==> 1,
          else                            // 000080xx ==> 2,
          n= (y >> 15) ^ 3;               // 00000080 ==> 3.            
          j=j+n ;
          if (n<4) {j =j +3 -2*n; break;}      
          r++;
      }        
      return (j);
    }
    

    Скорость исполнения: 1.71 сек.
    Результаты замеров показывают скорость близкую к regexp. Можем ли мы сделать быстрее? Да!
    Воспользуемся ассемблерными вставками. Сила описанного метода в том, что он позволяет уменьшить количество тактов которые тратит процессор на выполнение за счет применения элементарных арифметических операций. Программирование на языке высокого уровня не до конца позволяет реализовать возможности этого алгоритма.
    А потому, теперь наша функция примет такой вид:
    int search3( char *str){
      int n, j = 0;
      unsigned x, y, *r;
      const char *c_ptr;    
      for (c_ptr=str; ((unsigned long int)c_ptr & (sizeof(x) - 1)) != 0; ++c_ptr)
        if ((*c_ptr >= '0') && (*c_ptr <= '9'))
          return c_ptr - str;
       
      r = (unsigned *) c_ptr;
      j = c_ptr - str ;
      while (1){
          __asm__(
           "movl $5, %%edx\n"
           "movl (%%ebx), %%eax\n"
           "xor $0x30303030, %%eax\n" //
           "and $0x7F7F7F7F, %%eax\n"
           "add $0x76767676, %%eax\n"
           "movl %%eax, %%ecx\n"
           "or %%eax, %%ecx\n"
           "or $0x7F7F7F7F, %%ecx\n"
           "notl %%ecx\n"                   
          :"=c"(y)
          :"b"( r )
          );
          
           // These steps map:
          if (y == 0) n = 4;              // 00000000 ==> 4,
          else if (y > 0x0000FFFF)        // 80xxxxxx ==> 0,
          n= (y >> 31) ^ 1;               // 0080xxxx ==> 1,
          else                            // 000080xx ==> 2,
          n= (y >> 15) ^ 3;               // 00000080 ==> 3.            
          j=j+n ;
          if (n<4) {j =j +3 -2*n; break;}      
          r++;
      }        
      return (j);
    }
    

    Скорость исполнения: 1.23 сек.
    Я заменил ассемблерной вставкой только арифметические операции. Ветвление тоже можно заменить ассемблерным кодом, но я не уверен в значительном выигрыше, но несколько ветвлений с метками значительно усложнят процесс отладки.
    Выигрыш присутствует, но не в разы по сравнению с regexp. В принципе, оптимизируя ассемблерными вставками можно еще улучшать код, но это все влечет усложнение процесса отладки. Если оптимизировать ветвления и цикл, то можно добиться увеличения скорости еще раза в полтора. Но отлаживать код будет значительно труднее. Еще можно оптимизировать этот алгоритм для 64 бит вместо 32, попытаться распараллелить процесс.

    Итого, получаем:
    Regex 1.74
    Алгоритм 1 7.19
    Алгоритм 2 1.71
    Алгоритм 2+asm 1.23


    Вывод напрашивается сам: Изобретение велосипедов не приветствуется, и не всегда выигрыш от ассемблерной оптимизации может быть столь значим.

    Ссылка на архив с исходниками:
    webfile.ru/5706721

    UPD:
    Оптимизация под архитектуру процессора была указана, добавляю параметр -O 2.
    Также добавляю суммирование внутрь тестовых функций, чтобы как-либо использовать результат.
    Результат:

    Regex 4.56
    Алгоритм 1 2.99
    Алгоритм 2 1
    Алгоритм 2+asm 1.7*


    *С ключем -O2 правильно работать перестал, __volatile_ не помогло, результат с ключем -O1 но с добавленным суммированием.

    UPD 2:

    Пользователем Maratyszcza (спасибо ему!) предложен еще более быстрый вариант с использованием SIMD-расширений.

    #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;
    }
    


    Пока это самый быстрый вариант.
    Поделиться публикацией

    Комментарии 39

      –8
      спасибо К.О.
        +3
        А оптимизации-то какие использовались?
          +1
          В смысле оптимизации компилятора, конечно…
            0
            #include <regex.h>
          0
          Оптимизации компилятора — никаких. Как только оптимизатор замечает что функция вызывается N раз, а результат используется только один(ну в смысле в циклах для замера времени) — он делает один вызов вместо N. И все засекание времени накрывается.
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              Тогда тест нерепрезентативен. Используйте результат как-то, например, считайте их сумму или проверяйте на равенство с 42 и выходите из цикла и т. д.
                0

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


                __asm__ __volatile__ ("");

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


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

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

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

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

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

                        В таком случае, соглашусь — ассемблерная вставка зачастую будет быстрее неоптимизированного кода.
                          0
                          Простите пожалуйста, перефразирую ваши слова: в таком случае, соглашусь — ассемблерная вставка зачастую будет быстрее изначально кривого кода на языке высокого уровня который даже компилятор понять не может.
                  +2
                  А где алгоритм с lookup table?
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Где можно почитать о том, что функция search1 хуже регулярок? Когда только начал читать, то казалось, что search1 будет быстрой.
                        +1
                        «Алгоритмические трюки для программистов» Г. Уоррен. Алгоритмы поиска одного символа в строке. Там рассмотрено на примере нулевого.
                          0
                          Она будет быстрой если использовать флаги оптимизации компилятора.
                            +1
                            она и есть быстрая:

                            ./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, а вариант с ассемблерными вставками падал сразу, и мне было лень его чинить.
                              0
                              А еще можно итерировать указатель.
                              Если уж лезти в дебри, то иттерировать его на 4 или 8, правда я н е уверен, что компилятор догадается загнать слово в регист и проверять по частям. Да и это может быть менее выгодно, с учетом возможности паралельности комманд на процесморе
                            +1
                            Функция 1 не может быть хуже регулярок (конечного автомата).
                            Причина банальная: библиотека собрана с оптимизацией, код — без.
                            Думаю, компилятор лучше программиста учтет все особенности арифмитического блока профессора с сгенерирует еще более оптимальный код.

                            Автору минимум стоит посмотреть листинг ассемблера для его архитектуры.
                            Если надо уж совсем быстро, то О3 в помощь
                            0
                            Одно меня удивила, что скорость регулярок сравнима с оптимизированным алгоритмом даже с использованием ассемблерных вставок? Быть может стоит лучше посмотреть какие там используются алгоритмы, а не городить свой велосипед, который, как я подозреваю, все равно не оптимален.
                              +11
                              На дворе уже почти 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;
                              }
                              
                                0
                                Интересно было бы посмотреть на сравнение скорости этого алгоритма с теми, что были предложены в топике.
                                  0
                                  Я не против, посмотрите =)
                                    +7
                                    Намёк понял =)

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

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

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

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

                                        search1 531
                                        search1_no_strlen 297
                                        search2 172
                                        find_digit 63

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

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

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

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

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

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

                                            Самое читаемое