Как работает memchr () под капотом?

Question

Справочная информация: Я пытаюсь создать реализацию функциональности на чистом языке D, которая примерно эквивалентна memchr Си, но использует вместо указателей массивы и индексы. Причина в том, что std.string будет работать с функцией оценки времени компиляции. Для тех из вас, кто не знаком с W / D, функции могут быть оценены во время компиляции, если соблюдены определенные ограничения. Одно ограничение заключается в том, что они не могут использовать указатели. Другое - они не могут вызывать функции C или использовать встроенный язык ассемблера. Работа библиотеки строк во время компиляции полезна для некоторых хаков хаков кода времени компиляции.

Вопрос: Как работает memchr, чтобы работать так же быстро, как и он? На Win32 все, что я смог создать в чистом D с использованием простых циклов, по крайней мере в 2 раза медленнее, даже с очевидными методами оптимизации, такими как отключение проверки границ, развертывание циклов и т. Д. что-то такое простое, как поиск символа в строке?

Answer 1

Я бы посоветовал взглянуть на источник GNU libc . Что касается большинства функций, он будет содержать как общую оптимизированную версию функции на C, так и оптимизированные версии на ассемблере для максимально возможного числа поддерживаемых архитектур, используя преимущества машинно-специфических приемов.

Версия x86-64 SSE2 объединяет результаты из pcmpeqb сразу по всей строке кэша данных (четыре вектора 16B), чтобы амортизировать накладные расходы скорый выход pmovmskb / test / jcc.

gcc и clang в настоящее время не способны автоматически векторизовать циклы с if() break условиями раннего выхода, поэтому они делают наивный байт за раз из очевидной реализации C.

Answer 2

Эта реализация memchr из newlib является одним из примеров чьей-то оптимизации memchr: он читает и тестирует 4 байта за раз (кроме memchr, другие функции в библиотеке newlib здесь ).

Кстати, большая часть исходного кода для библиотеки времени выполнения MSVC доступна как дополнительная часть установки MSVC (так что вы можете посмотреть на это).

Answer 3

Вот мембр FreeBSD (BSD-лицензированный) из memchr.c Онлайновый браузер исходного кода FreeBSD является хорошим справочником для проверенных временем, BSD-лицензированных примеров кода.

void *
memchr(s, c, n)
    const void *s;
    unsigned char c;
    size_t n;
{
    if (n != 0) {
        const unsigned char *p = s;

        do {
            if (*p++ == c)
                return ((void *)(p - 1));
        } while (--n != 0);
    }
    return (NULL);
}

Answer 4

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

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

Answer 5

GNU libc определенно использует версию сборки memchr () (в любом распространенном дистрибутиве Linux). Вот почему это так невероятно быстро.

Например, если мы подсчитываем строки в файле 11 Гб (как это делает « wc -l »), это займет около 2.5 секунд с сборкой версия memchr () из GNU libc. Но если мы заменим вызов ассемблера memchr () на, например, реализацию memchr () C из FreeBSD - скорость уменьшится до 30 секунд.

Это равно замене memchr () просто циклом while, который сравнивает один символ за другим.