Разворот строчки — новый вариант

от ·14 комментариев

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

Вариант для C/C++. Увлеченно используем арифметику указателей.

char* reverse(char *s) {
    char *s0, *s1;

    for (s1 = s; *(s1) != '\0'; s1++);
    s1--;
    for (s0 = s; s0 < s1; s0++ && s1--) {
        char c = *(s0);
        *(s0) = *(s1);
        *(s1) = c;
    }
    return s;
}

Сравнивая производительность с предыдущими вариантами, надо обратить внимание на два момента:

  • фактически первый цикл — это вычисление длины строки, т.е. быстрее или медленнее это место, по сравнению со strlen, зависит от реализации strlen. Не знаю что конкретно там обычно написано, спекулировать не буду. Но думается, что что-то типа того и написано 🙂 С другой стороны, если вдруг окажется, что strlen работает быстрее чем просто поиск конца, в цикле, то никто не мешает нам написать конструкцию вида s1 = s+strlen (s). А дальше продолжить делать как тут.
  • Во время самого обмена значениями мы заметно сокращаем количество вычислений, т.к. вместо s+i и s+len-i, на каждом присваивании, мы все указатели вычисляем один раз, на проход.

На Java так красиво не получится. За отсутствием собственно указателей. Но близко к этому будет вариант с запуском навстречу двух счетчиков массива...

  • Николай

    если изменить сигнатуру на void reverse (char *s) то вместо s0 можно былобы использовать s и ваще не обьявлять s0

    ну и оптимизации которые и так сделает компилятор это замена s1++ на ++s1 и вынос обьявления c из цикла

  • Да, s0 тут исключительно для возможности возврата s.

  • Aleksey Shipilev

    Бх. Доступиться к массиву из java не менее просто. А для String длина уже известна, терминатор искать не надо. Плюс к этому в юникоде есть суррогатные пары, которые тоже надо хендлить, простым wchar_t тут не обойдёшься. См. AbstractStringBuilder.reverse ().

  • Sergey Kuksenko

    «Сравнивая производительность с предыдущими вариантами» — Леха, научи ленинскому прищуру — как производительность мерить. А то мы тут пыхтим, бенчи делаем. 😉

    Ничего, что я занудствую?

  • Aleksey Shipilev

    И кроме того, компилятор в таких хаках по-умнее будет:

    $ gcc -std=c99 -O2 string.c -o string

    $ ./string

    reverseOld: ..., 2060000 clks

    reverseNew: ..., 3320000 clks

    Итого, в 1.6х медленнее.

  • Я ж не меряю. Я прикидываю 🙂

    Операций меньше — производительность выше. Нет?

  • Шли твой код, для проверки. Поиграемся 🙂

  • Sergey Kuksenko

    «Я ж не меряю. Я прикидываю» — Я ж говорю — научи! ;))))

  • Николай

    наверное это связано с тем что тут длина строки считается шаманским циклом вместо мега оптимизированного strlen, собсно о чем и написано в первом моменте, плюс в старом варианте сигнатура метода другая

  • Aleksey Shipilev

    Код: pastebin.com/GmrBQpEf

    Боль и печаль современного перформанса как раз в том, что «меньше инструкций» НЕ означает «быстрее». path length (длина программы в инструкциях) может быть меньше, а эффективный CPI (количество тиков на инструкцию) выше. Общее время определяется как (path length)*(CPI).

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

    И в т.ч. поэтому «предсказывать перформанс по фотографии» нынче невозможно.

  • В общем случае твои рассуждения несомненно верны. Никто с этим и не спорит.

    Другое дело, что во многих, простых, местах вполне можно предположить какой вариант будет быстрее. Например, выбор между одиночным вычислением значения и 50-ю вычислениями того же самого значения, по ходу, ИМХО, вполне себе очевиден.

    Собственно этот новый вариант и сокращает количество вычислений индекса, на каждом проходе основного цикла.

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

    Вот результаты прогона твоего теста, при замене прямого поиска конца цикла на strlen:

    reverseOld: test1234567890onetwothreefourfivesixseveneightnineten, 11510000 clks reverseNew: test1234567890onetwothreefourfivesixseveneightnineten, 9040000 clks

    Т.е. после такой замены, reverseNew таки стал чуть быстрее reverseOld.

    И это показывает, что иногда предположения о производительности кода вполне можно делать 🙂

  • Упс, забыл оптимизацию компилятора включить 🙂

    Но результат не изменился:

    cap@zhelezyaka:~/tmp$ gcc reverse.c -std=c99 -O2 -o reverse cap@zhelezyaka:~/tmp$ ./reverse reverseOld: test1234567890onetwothreefourfivesixseveneightnineten, 2160000 clks reverseNew: test1234567890onetwothreefourfivesixseveneightnineten, 2010000 clks

  • Хреново как-то комменты форматирует... Может на Disqus перейти?

  • Sergey Kuksenko

    «Например, выбор между одиночным вычислением значения и 50-ю вычислениями того же самого значения, по ходу, ИМХО, вполне себе очевиден.» — Опять же нифига не очевиден. Курим такую «относительно новую» (всего лет 10-15) оптимизацию, как рематериализация. 😉