Пользовательская реализация memcpy, где оптимизировать дальше?

Редактировать:

Добавив ключевое слово restrict, я смог ускорить мой memcpy с реализацией библиотеки (и в этом конкретном тесте, превысив скорость реализации библиотеки). Новые результаты:

Примечание: я также тестировал это как часть более крупной реализации, над которой я работал. Раньше я добивался примерно 20% производительности, заменяя libc memcpy своей собственной, теперь разницы не было.

Обновленный код:

static void
copy_words(void *restrict dst, const void *restrict src, size_t words)
{
    const uint64_t  *restrict src64;
    uint64_t        *restrict dst64;
    uint64_t        pages;
    uint64_t        offset;

    pages = words / 8;
    offset = words - pages * 8;
    src64 = (const uint64_t *restrict)src;
    dst64 = (uint64_t *restrict)dst;
    while (pages--)
    {
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
    }
    while (offset--)
        *dst64++ = *src64++;
}
static void
copy_small(void *restrict dst, const void *restrict src, size_t size)
{
    const uint64_t  *restrict src64;
    uint64_t        *restrict dst64;

    src64 = (const uint64_t *restrict)src;
    dst64 = (uint64_t *restrict)dst;
    *dst64 = *src64;
}
void
*mem_cpy(void *restrict dst, const void *restrict src, const size_t size)
{
    const uint8_t   *restrict src8;
    uint8_t         *restrict dst8;
    size_t          offset;
    size_t          words;
    size_t          aligned_size;

    if (!src || !dst)
        return (NULL);
    if (size <= 8)
    {
        copy_small(dst, src, size);
        return (dst);
    }
    words = size / 8;
    aligned_size = words * 8;
    offset = size - aligned_size;
    copy_words(dst, src, words);
    if (offset)
    {
        src8 = (const uint8_t *restrict)src;
        src8 = &src8[aligned_size];
        dst8 = (uint8_t *restrict)dst;
        dst8 = &dst8[aligned_size];
        while (offset--)
            *dst8++ = *src8++;
    }
    return (dst);
}

В качестве практики оптимизации я пытаюсь сделать свое воссоздание memcpy как можно ближе по скорости к libc. Я использовал следующие методы для оптимизации моего memcpy:

• Приведение данных к как можно большему типу данных для копирования.
• Разворачиваем основной цикл 8 раз.
• Для данных

Мои результаты (для справки я добавил наивный 1 байт memcpy за раз):

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

Вот код, включая тесты, можно скомпилировать как есть:

#include <time.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

const size_t        iters = 100000000;

//-----------------------------------------------------------------------------
// Optimized memcpy
//
static void         copy_words(void *dst, const void *src, size_t words)
{
    const uint64_t  *src64;
    uint64_t        *dst64;
    uint64_t        pages;
    uint64_t        offset;

    pages = words / 8;
    offset = words - pages * 8;
    src64 = (const uint64_t *)src;
    dst64 = (uint64_t *)dst;
    while (pages--)
    {
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
        *dst64++ = *src64++;
    }
    while (offset--)
        *dst64++ = *src64++;
}

static void         copy_small(void *dst, const void *src, size_t size)
{
    const uint64_t  *src64;
    uint64_t        *dst64;

    src64 = (const uint64_t *)src;
    dst64 = (uint64_t *)dst;
    *dst64 = *src64;
}

void                *mem_cpy(void *dst, const void *src, const size_t size)
{
    const uint8_t   *src8;
    uint8_t         *dst8;
    size_t          offset;
    size_t          words;
    size_t          aligned_size;

    if (!src || !dst)
        return (NULL);
    if (size <= 8)
    {
        copy_small(dst, src, size);
        return (dst);
    }
    words = size / 8;
    aligned_size = words * 8;
    offset = size - aligned_size;
    copy_words(dst, src, words);
    if (offset)
    {
        src8 = (const uint8_t *)src;
        src8 = &src8[aligned_size];
        dst8 = (uint8_t *)dst;
        dst8 = &dst8[aligned_size];
        while (offset--)
            *dst8++ = *src8++;
    }
    return (dst);
}

//-----------------------------------------------------------------------------
// Naive memcpy
//
void                *mem_cpy_naive(void *dst, const void *src, size_t n)
{
    const uint8_t   *src8;
    uint8_t         *dst8;

    if (src == NULL)
        return (NULL);
    src8 = (const uint8_t *)src;
    dst8 = (uint8_t *)dst;
    while (n--)
        *dst8++ = *src8++;
    return (dst);
}

//-----------------------------------------------------------------------------
// Tests
//
int         test(int (*f)(), char *test_name)
{   
    clock_t begin = clock();
    f();
    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("%s: %fn", test_name, time_spent);
    return (1);
}

char        *big_data()
{
    char    *out;
    size_t  i;

    out = (char *)malloc(sizeof(char) * 1000);
    i = 0;
    while (i < 1000)
    {
        out[i] = 'a';
        i++;
    }
    return (out);
}

int         test1()
{
    char    *src;
    char    *dst;
    size_t  i;

    src = big_data();
    dst = (char *)malloc(sizeof(char) * 1000);
    i = 0;
    while (i < iters)
    {
        mem_cpy(dst, src, 1000);
        i++;
    }
    return (1);
}


int         test2()
{
    char    *src;
    char    *dst;
    size_t  i;

    src = big_data();
    dst = (char *)malloc(sizeof(char) * 1000);
    i = 0;
    while (i < iters)
    {
        mem_cpy_naive(dst, src, 1000);
        i++;
    }
    return (1);
}

int         test3()
{
    char    *src;
    char    *dst;
    size_t  i;

    src = big_data();
    dst = (char *)malloc(sizeof(char) * 1000);
    i = 0;
    while (i < iters)
    {
        memcpy(dst, src, 1000);
        i++;
    }
    return (1);
}

int         test4()
{
    char    *src;
    char    *dst;
    size_t  i;

    src = "12345678";
    dst = (char *)malloc(sizeof(char) * 8);
    i = 0;
    while (i < iters)
    {
        mem_cpy(dst, src, 8);
        i++;
    }
    return (1);
}

int         test5()
{
    char    *src;
    char    *dst;
    size_t  i;

    src = "12345678";
    dst = (char *)malloc(sizeof(char) * 8);
    i = 0;
    while (i < iters)
    {
        mem_cpy_naive(dst, src, 8);
        i++;
    }
    return (1);
}

int         test6()
{
    char    *src;
    char    *dst;
    size_t  i;

    src = "12345678";
    dst = (char *)malloc(sizeof(char) * 8);
    i = 0;
    while (i < iters)
    {
        memcpy(dst, src, 8);
        i++;
    }
    return (1);
}

int         main(void)
{
    test(test1, "User memcpy (big string)");
    test(test2, "User memcpy naive (big string)");
    test(test3, "Libc memcpy (big string)");
    test(test4, "User memcpy");
    test(test5, "USer memcpy naive");
    test(test6, "Libc memcpy");
}

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

https://godbolt.org/z/Yva9EaPrP

Исправить переполнение буфера в copy_small

Как вы уже написали, и как ранее указывал Тоби, copy_small всегда записывает 8 байтов в dest, даже когда size < 8. Это серьезная ошибка безопасности памяти, поскольку она записывается после конца dest буфер.

void
copy_small(void *restrict dst, const void *restrict src, size_t size)
{
    const uint64_t  *restrict src64;
    uint64_t        *restrict dst64;

    src64 = (const uint64_t *restrict)src;
    dst64 = (uint64_t *restrict)dst;
    *dst64 = *src64; // !DANGER WILL ROBINSON!
}

Вот как бы я написал copy_small. Это безопасно и, я считаю, оптимально.

void copy_small(uint8_t *restrict dst, const uint8_t *restrict src, size_t size)
{
    if (size & 8) {
        *(uint64_t *restrict)dst = *(const uint64_t *restrict)src;
        return;
    }
    if (size & 4) {
        *(uint32_t *restrict)dst = *(const uint32_t *restrict)src;
        dst += 4;
        src += 4;
    }
    if (size & 2) {
        *(uint16_t *restrict)dst = *(const uint16_t *restrict)src;
        dst += 2;
        src += 2;
    }
    if (size & 1)
        *dst = *src;
}

Не время malloc в ваших тестах

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

Укажите аргументы указателя с помощью restrict

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

Для «справедливости», если вы еще этого не сделали, добавьте restrict к аргументам указателя mem_cpy_naive. Обратите внимание, что вам нужно будет скомпилировать с опцией -fno-tree-loop-distribute-patterns чтобы предотвратить оптимизацию GCC mem_cpy_naive к вызову libc memcpy.

Микрооптимизации

• Вы заявили copy_words а также copy_small с участием static связь, предположительно потому, что вы хотите, чтобы они были встроены, но в этом случае вы также должны объявить их inline (т.е. static inline). Вопреки популярному мифу, inline спецификатор делает сделать компилятор более вероятным для встраивания функции.
• Передача нулевого указателя на memcpy является неопределенное поведение, это означает, что вам не нужно обращаться с этим изящно. Итак, это /if (!src || !dst) return (NULL)/ не требуется. Я бы заменил это утверждением /assert(src && dst)/ и скомпилировать с -DNDEBUG для тестов. Вы также можете объявить свои функции с помощью __attribute__((nonnull)), который сообщает GCC: 1) выдавать предупреждение, если он обнаруживает, что в функцию передается нулевой указатель, и 2) выполнять оптимизацию в предположении, что аргументы указателя никогда не равны нулю.
• Деление и умножение на степени 2 эквивалентны сдвигу битов вправо или влево на эту степень (которые быстрее). Итак, все экземпляры x / 8 в вашем коде можно заменить на x >> 3 и все x * 8 можно заменить на x << 3. Компилятор, вероятно, достаточно умен, чтобы сделать это сам, но вы также можете сделать это явным.
• В if (offset) ветвь не нужна, и цикл, который она содержит, можно заменить вызовом copy_small. И вы можете внести это изменение, пока только звоните copy_small однажды в mem_cpy. Вы видите как?

Предложения по стилю

• copy_words а также copy_small не обязательно следовать memcpy API точно. Это будет намного менее многословно, если их dest а также src аргументы соответственно uint64_t* а также uint8_t* вместо void*.
• Объявление группы неинициализированных переменных в верхней части функции было необходимо в ANSI C, но в современном C это плохой стиль и потенциально опасно, если вы забудете инициализировать одну из них. По возможности обе переменные должны быть объявлены (как const когда они не изменяются) и инициализируются непосредственно перед их использованием.
• Как сказал Тоби, ненужные скобки вокруг возвращаемых значений сбивают читателя с толку.
• Как также сказал Тоби, использование термина pages для чего-то другого, кроме страницы, сбивает с толку. Я бы заменил это на chunks или похожие.

Разногласия с Тоби

• Я бы не стал беспокоиться об экзотических / несуществующих платформах, где CHAR_BIT != 8 или же uint64_t не поддерживается. Если бы вы на самом деле реализовывали memcpy для GCC вам, возможно, придется побеспокоиться об этом. Но в остальном нет.
• Когда я пишу код на C, я стараюсь сделать его совместимым с C ++, если это возможно. Итак, поскольку этого требует C ++, я выступаю за приведение вызовов к malloc на тип указателя, которому они назначаются.

Ваш код, как я бы его написал:

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

#if !defined(__GNUC__) && !defined(__attribute__) // no GCC attribute syntax
#define __attribute__(X)
#endif

#ifdef __cplusplus // C++
extern "C" {

#define CINLINE constexpr

#if defined(__GNUC__) || defined(_MSC_VER) || defined(__restrict)
#define restrict __restrict
#elif !defined(restrict) // restrict or __restrict not supported in C++
#define restrict
#endif

#else // C
#define CINLINE inline
#define constexpr
#endif

static CINLINE __attribute__((nonnull))
void copy_small(uint8_t *restrict dst, const uint8_t *restrict src, size_t size)
{
    if (size & 8) {
        *(uint64_t *restrict)dst = *(const uint64_t *restrict)src;
        return;
    }
    if (size & 4) {
        *(uint32_t *restrict)dst = *(const uint32_t *restrict)src;
        dst += 4;
        src += 4;
    }
    if (size & 2) {
        *(uint16_t *restrict)dst = *(const uint16_t *restrict)src;
        dst += 2;
        src += 2;
    }
    if (size & 1)
        *dst = *src;
}

static CINLINE __attribute__((nonnull))
void copy64(uint64_t *restrict dst, const uint64_t *restrict src, size_t n) {
    size_t chunks = n >> 3;
    size_t offset = n - (chunks << 3);

    while (chunks--) {
        *dst++ = *src++;
        *dst++ = *src++;
        *dst++ = *src++;
        *dst++ = *src++;
        *dst++ = *src++;
        *dst++ = *src++;
        *dst++ = *src++;
        *dst++ = *src++;
    }
    while (offset--)
        *dst++ = *src++;
}

constexpr __attribute__((nonnull))
void *mem_cpy(void *restrict dst, const void *restrict src, size_t size) {
    assert(dst && src);

    uint8_t *dst8 = (uint8_t*)dst;
    const uint8_t *src8 = (const uint8_t*)src;

    if (size > 8) {
        const size_t qwords = size >> 3;

        copy64((uint64_t*)dst, (const uint64_t*)src, qwords);

        const size_t aligned_size = qwords << 3;

        size -= aligned_size;
        dst8 += aligned_size;
        src8 += aligned_size;
    }

    copy_small(dst8, src8, size);

    return dst;
}

/* GCC optimizes this to a call to libc memcpy unless compiled with
 * -fno-tree-loop-distribute-patterns
 */
constexpr __attribute__((nonnull))
void *mem_cpy_naive(void *restrict dst, const void *restrict src, size_t size) {
    assert(dst && src);

    uint8_t *restrict dst8 = (uint8_t*)dst;
    const uint8_t *restrict src8 = (const uint8_t*)src;

    while (size--)
        *dst8++ = *src8++;

    return dst;
}

#ifdef __cplusplus
}
#endif

const uint64_t  *restrict src64;

Проблема переносимости — uint64_t определяется только в том случае, если платформа имеет тип ровно 64 бита. Рассмотрите возможность использования uint_fast64_t (или возможно uintmax_t) вместо.

pages = words / 8;
offset = words - pages * 8;

Еще одна проблема переносимости — предполагает CHAR_BIT 64/8 = 8. Используйте sizeof *src64 вместо.

Терминология странная и запутанная. Почему мы называем байты «словами», а слова «страницами»?

src64 = (const uint64_t *restrict)src;
dst64 = (uint64_t *restrict)dst;

Я не понимаю, где этот код гарантирует, что src64 а также dst64 соответственно выровнены для чтения и записи как 64-битные величины. Это означает, что код будет работать на некоторых архитектурах (возможно, с проблемами производительности) и полностью отказываться от других (возможно, повышая SIGBUS если повезет).

Явные приведения не нужны, учитывая, что src а также dst оба void*, который неявно преобразуется в любой указатель на объект. И не нужно декларировать отдельно от инициализации.

Я не понимаю как copy_small чтит его size аргумент. Всегда кажется, что копирует полную uint64_t, что потенциально может привести к большему количеству запросов, чем было запрошено (и, возможно, к записи, выходящей за допустимые пределы).

С тестами тоже есть проблемы. Давайте посмотрим на test1() в качестве репрезентативного примера:

int         test1()
{
    char    *src;
    char    *dst;
    size_t  i;

Опять же, объявите, где мы инициализируем.

    src = big_data();
    dst = (char *)malloc(sizeof(char) * 1000);

Нет необходимости писать явное приведение для преобразования из void*. Умножение на 1 не действует.

Почему мы продолжаем, если распределение возвращает нам нулевой указатель? Это очень глупо.

Что еще более важно, почему мы включаем malloc() позвонить в наши расписания? Это будет доминировать над результатом.

    i = 0;
    while (i < iters)
    {
        mem_cpy(dst, src, 1000);
        i++;
    }

Это было бы более читабельно как обычное for петля.

    return (1);
}

Почему бессмысленные скобки вокруг возвращаемого значения? return 1; читабельнее.

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

Memcpy на моем текущем компьютере использует векторные инструкции, использует инструкции кеширования, недоступные в C, и все приемы, описанные в книге. У вас практически нет шансов победить его. И если вы победите его на одном компьютере, он не будет работать на другом.

Что касается вашего кода: сначала вы должны попытаться выровнять указатели.

If count >= 1 and dst is not two-byte aligned -> copy 1 byte. 
If count >= 2 and dst is not four-byte aligned -> copy 2 byte.
If count >= 4 and dst is not eight-byte aligned -> copy 4 byte.

Затем вы копируете восемь байтов за раз, затем еще 4, если необходимо, еще 2 и еще один байт.