* str и * str ++

Question

У меня есть этот код (моя функция strlen)

size_t slen(const char *str)
{
    size_t len = 0;
    while (*str)
    {
        len++;
        str++;
    }
    return len;
}

При выполнении while (*str++), как показано ниже, время выполнения программы намного больше:

while (*str++)
{
    len++;
}

Я делаю это, чтобы проверить код

int main()
{
    double i = 11002110;
    const char str[] = "long string here blablablablablablablabla"
    while (i--)
        slen(str);

    return 0;
}

В первом случае время выполнения составляет около 6,7 секунды, а во втором (с использованием *str++) время составляет около 10 секунд!

Почему такая большая разница?

Answer 1

Возможно, потому что оператор постинкремента (используемый в условии оператора while) предполагает сохранение временной копии переменной со старым значением.

Что действительно означает while (*str++):

while (tmp = *str, ++str, tmp)
  ...

Напротив, когда вы пишете str++; как отдельный оператор в теле цикла while, он находится в пустом контексте, поэтому старое значение не выбирается, потому что оно не нужно.

Подводя итог, в случае *str++ у вас есть назначение, 2 приращения и переход в каждой итерации цикла.В другом случае у вас есть только 2 шага и прыжок.

Answer 2

Испытывая это на ideone.com, я получаю около 0,5 с выполнения с * str ++ здесь . Без, это занимает чуть более секунды ( здесь ). Использование * str ++ было быстрее. Возможно, с оптимизацией на * str ++ можно сделать более эффективно.

Answer 3

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

Сначала нам понадобится программа. Наш план таков: мы сгенерируем строки, длина которых равна степени двух, и попробуем все функции по очереди. Мы проходим один раз, чтобы заполнить кэш, а затем отдельно проводим 4096 итераций, используя самое высокое разрешение, доступное для нас. Как только мы закончим, мы рассчитаем некоторую базовую статистику: минимальную, максимальную и простую скользящую среднюю и выгрузим ее. Затем мы можем сделать некоторый элементарный анализ.

В дополнение к двум алгоритмам, которые вы уже показали, я покажу третий вариант, который вообще не предусматривает использование счетчика, а вместо этого положит вычитание, и я все перепутаю, добавив std::strlen, просто чтобы посмотреть, что происходит. Это будет интересный бросок.

Благодаря магии телевидения наша маленькая программа уже написана, поэтому мы компилируем ее с gcc -std=c++11 -O3 speed.c, и мы начинаем криво производить некоторые данные. Я сделал два отдельных графика, один для строк, размер которых составляет от 32 до 8192 байт, а другой для строк, размер которых составляет от 16384 до 1048576 байт. На следующих графиках ось Y - это время, потраченное в наносекундах , а на оси X показана длина строки в байтах.

Без лишних слов давайте посмотрим на производительность для «маленьких» строк размером от 32 до 8192 байт:

Теперь это интересно. Мало того, что функция std::strlen превосходит все по всем направлениям, она делает это с удовольствием, так как ее производительность намного стабильнее.

Изменится ли ситуация, если мы посмотрим на более крупные строки, от 16384 до 1048576 байт?

Вроде. Разница становится еще более заметной. Что касается наших пользовательских функций huff-and-puff, std::strlen продолжает работать превосходно.

Интересно отметить, что вы не можете обязательно переводить количество инструкций C ++ (или даже количество инструкций по сборке) в производительность, поскольку функции, тела которых состоят из меньшего количества инструкций, иногда выполняются дольше.

Еще более интересное и важное наблюдение состоит в том, чтобы заметить, насколько хорошо работает функция str::strlen.

Так что же нам все это дает?

Первый вывод: не изобретай велосипед. Используйте стандартные функции, доступные вам. Мало того, что они уже написаны, но они очень сильно оптимизированы и почти наверняка превзойдут все, что вы можете написать, если вы не Agner Fog .

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

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

Ваш первоначальный вопрос был: «Почему функция slen2 медленнее, чем slen1?» Я мог бы сказать, что ответить без большого количества информации нелегко, и даже тогда это может быть намного дольше и более сложным, чем вы заботитесь. Вместо этого я скажу следующее:

Кого это волнует, почему? Почему ты вообще беспокоишься об этом? Используйте std::strlen - что лучше, чем все, что вы можете настроить - и переходите к решению более важных проблем - потому что я уверен, что не самая большая проблема в вашем приложении.

Answer 4

Это зависит от вашего компилятора, флагов компилятора и вашей архитектуры. С Apple LLVM gcc 4.2.1 я не получаю заметного изменения в производительности между двумя версиями, и действительно не должно быть. Хороший компилятор превратит версию *str в нечто вроде

IA-32 (AT & T синтаксис):

slen:
        pushl %ebp             # Save old frame pointer
        movl  %esp, %ebp       # Initialize new frame pointer
        movl  -4(%ebp), %ecx   # Load str into %ecx
        xor   %eax, %eax       # Zero out %eax to hold len
loop:
        cmpb  (%ecx), $0       # Compare *str to 0
        je    done             # If *str is NUL, finish
        incl  %eax             # len++
        incl  %ecx             # str++
        j     loop             # Goto next iteration
done:
        popl  %ebp             # Restore old frame pointer
        ret                    # Return

Версия *str++ может быть скомпилирована точно так же (поскольку изменения str не видны за пределами slen, когда фактически происходит приращение, что не важно), или тело цикла может быть:

loop:
        incl  %ecx             # str++
        cmpb  -1(%ecx), $0     # Compare *str to 0
        je    done             # If *str is NUL, finish
        incl  %eax             # len++
        j     loop             # Goto next iteration