strlcpy, или как CPU противоречат здравому смыслу

Один из моих старых постов о strlcpy недавно вызвал обсуждения на различных форумах. Вероятно, с этим как-то связан выпуск новой версии POSIX. Многие авторы приводили один контраргумент, который я слышал и раньше:

• В общем случае, когда исходная строка умещается в конечный буфер, strlcpy будет обходить строку только один раз, а strlen + memcpy будут обходить её дважды.

Под этим аргументом скрывается допущение о том, что однократный обход строки выполняется быстрее. И, честно говоря, это вполне разумное допущение. Но справедливо ли оно? Об этом мы и поговорим в статье.

CPU и здравый смысл

У компьютеров нет здравого смысла. Компьютеры удивляют.
- Энтони Хоар

Приведённый ниже код взят из openbsd, где и появилась strlcpy (код немного сокращён).

size_t strlcpy(char *dst, const char *src, size_t dsize)
{
    const char *osrc = src;
    size_t nleft = dsize;

    if (nleft != 0) while (--nleft != 0) { /* Копируе as many bytes as will fit. */
        if ((*dst++ = *src++) == '')
            break;
    }

    if (nleft == 0) { /* Not enough room in dst, add NUL and traverse rest of src. */
        if (dsize != 0) *dst = ''; /* NUL-terminate dst */
        while (*src++) ;
    }

    return(src - osrc - 1);	/* count does not include NUL */
}

Сначала в нём выполняется максимально возможное копирование из src в dst, и если данные приходится урезать из-за недостаточного размера dst, то выполняется обход оставшейся части src, чтобы получить значение strlen(src) для его возврата. То есть если исходная строка умещается, то обход будет выполняться только один раз.

Если же взглянуть на реализацию strlcpy из glibc, то можно сразу заметить. что первая строка выглядит так:

    size_t src_length = strlen (src);

... а далее следует остальной код, в котором для копирования используется memcpy. Это уже разрушает иллюзию о том, что strlcpy выполняет обход строки единожды, такого требования нет, и как вы видите на практике, одна из значимых libc всегда обходит строку дважды, по одному разу в strlen и в memcpy.

Но прежде чем вы откроете баг-репорт glibc из-за её неэффективности, взгляните на бенчмарк многократного копирования 512-байтовой строки в цикле:

512 byte
openbsd:      242us
glibc:         12us

Возможно, строка настолько мала, что этот двойной обход не так важен? Тогда как насчёт строки на 1 МиБ?

1MiB
openbsd:   501646us
glibc:      31793us

Здесь ситуация для версии openbsd становится только хуже, а не лучше. Откровенно говоря, это огромное ускорение возникает благодаря тому, что glibc передаёт всю работу strlen и memcpy, которые в glibc SIMD-оптимизированы. Тем не менее, мы уже видим, что делать что-то дважды, но быстро — это быстрее, чем делать один раз, но медленно.

Сравниваем сравнимое

Чтобы выполнить правильное сравнение, я написал следующую реализацию strlcpy, которая очень близка к реализации glibc, если не считать того, что вызовы strlen и memcpy записаны в циклы for.

size_t bespoke_strlcpy(char *dst, const char *src, size_t size)
{
    size_t len = 0;
    for (; src[len] != ''; ++len) {} // strlen() loop

    if (size > 0) {
        size_t to_copy = len < size ? len : size - 1;
        for (size_t i = 0; i < to_copy; ++i) // memcpy() loop
            dst[i] = src[i];
        dst[to_copy] = '';
    }
    return len;
}

Важно отметить. что для настоящего сравнения нужно добавить при компиляции -fno-builtin. В противном случае gcc поймёт, что «цикл strlen» можно оптимизировать до вызова strlen, и сгенерирует его. -fno-builtin позволяет избежать этого и делает сравнение честным.

Как же проявит себя эта версия, выполняющая обход src дважды, по сравнению с вариантом openbsd, обходящим src только один раз?

512 byte
openbsd:      237us
bespoke:      139us

Почти в два раза быстрее. А как насчёт строк подлиннее?

1MiB
openbsd:   488469us
bespoke:   277183us

Всё равно примерно вдвое быстрее. Как же так получилось?

Зависимости

Постоянно подчёркивается важность промахов кэша (и с полным на то основанием), но о зависимостях говорят не так часто. У CPU есть несколько ядер, и у каждого ядра есть несколько портов (или логических блоков), способных исполнять команды. Это означает. что если у нас есть подобные команды (на псевдоассемблере, где заглавные буквы обозначают регистр):

A  <- add  B, C
X  <- add  Y, Z
E  <- add  A, X

то вычисления A и X не зависят друг от друга, а значит, могут выполняться параллельно. Однако вычисление E требует результата A и X, а потому не может быть распараллелено. Такой процесс, позволяющий исполнять независимые команды одновременно, называется параллелизмом уровня команд (instruction-level-parallelism, ILP). И его криптонитом становятся зависимости.

Если мы попытаемся профилировать нашу самодельную версию strlcpy, то заметим, что почти 100% времени CPU тратится на «цикл strlen», в то время как цикл copy практически свободен. И в самом деле, если заменить «вызов strlen» настоящим вызовом strlen (напоминание: в glibc она SIMD-оптимизирована), то самодельная версия достаточно неплохо начинает конкурировать с версией glibc, хотя мы не используем оптимизированную memcpy. Чтобы понять, почему это происходит, давайте рассмотрим «цикл strlen», написанный в многословном стиле:

len = 0;
while (true) {
    if (src[len] == '')
        break;  // <- это влияет на следующую итерацию
    else
        ++len;
}

В показанном выше цикле то, будет ли выполняться следующая итерация цикла, зависит от результата предыдущей итерации (имело ли src[len]  значение nul или нет). Мы расплачиваемся за это в нашем цикле strlen. Но наш цикл memcpy не имеет таких привносимых циклом зависимостей, текущая итерация происходит вне зависимости от того, что происходило в предыдущей.

for (size_t i = 0; i < to_copy; ++i) // memcpy() loop
    dst[i] = src[i]; // <- НЕ зависит от предыдущей итерации

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

while (--nleft != 0) {  // цикл копирования openbsd
    if ((*dst++ = *src++) == '') // <- выбранное здесь ветвление влияет на следующую итерацию
        break;
}

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

Дополнение: не избавляйтесь от длины

Секрет создания быстрых программ заключается в том, чтобы они практически ничего не делали.
- Майк Хэртел, why GNU grep is fast

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

• Длина строки — это бесценная информация.

Без знания длины строка становится больше похожей на связанный список, заставляя нас использовать паттерн последовательного доступа, а не на массив с возможностью произвольного доступа. Многие популярные функции работы со строками можно удобнее выразить (а значит, и совершить меньше ошибок), когда длину можно узнать малозатратным образом. С другой стороны, строки с завершающим нулём в конце мотивируют постоянно отказываться от этой ценной информации, что приводит к необходимости беспричинно вычислять её снова, и снова, и снова (при этом всегда вспоминается инцидент с экраном загрузки GTA [перевод на Хабре]).

• Возможность иметь подстроки без копирования — это огромное преимущество.

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

Помня об этих двух пунктах, сегодня я просто использую sized string (что-то в стиле std::string_view языка C++) и преобразую их в nul-string только тогда, когда этого требует внешний API. Эта тема заслуживает отдельной статьи, поэтому здесь я упоминаю её только по касательной.

Но здорово то, что вне группы пользователей C, сильно подверженной логическому искажению «умолчания» (если что-то используется по умолчанию, то использовать это правильно и нужно), подавляющее число разработчиков более-менее осознало, что строки с завершающим нулём были ошибкой. Это очевидно, если взглянуть на большинство других языков программирования, в том числе и многие новые, предназначенные для системного программирования: в них nul-string не используются по умолчанию (если вообще используются). Даже языки, наследующие от C, отходят от применения nul-string — вспомним, например, string_view из C++.

Заключение

При обсуждении производительности важно чётко определиться, говорим ли мы о ней в научном смысле, или в практическом, потому что CPU не заботят здравый смысл и «большое O». Современные CPU невероятно сложны и полны сюрпризов. Поэтому скорость алгоритма зависит не только от высокоуровневых алгоритмических факторов: необходимо также принимать во внимание и низкоуровневые факторы, например, промахи кэша, ILP, ошибочное прогнозирование ветвления и так далее. Многие вещи, которые с точки зрения здравого смысла могут казаться быстрыми, на практике оказываются медленнее, и наоборот.