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

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

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

Прецедент mem_cpy mem_cpy_naive memcpy
большая строка (1000 байт) 2.584988s 3.936075 с 3.952187 с
маленькая строка (8 байтов) 0,025931 с 0,051899 с 0,025807 с

Примечание: я также тестировал это как часть более крупной реализации, над которой я работал. Раньше я добивался примерно 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 раз.
  • Для данных <= 8 байт я обхожу основной цикл.

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

Прецедент mem_cpy mem_cpy_naive memcpy
большая строка (1000 байт) 12.452919с 212.728906с 0,935605 с
маленькая строка (8 байтов) 0,367271 с 1.413559s 0.149886с

Я чувствую, что исчерпал все «низко висящие плоды» с точки зрения оптимизации. Я понимаю, что функция 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

3 ответа
3

Исправить переполнение буфера в 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

  • 1

    Вам также не нужно приводить указатели в C ++, так как вы должны использовать new там, или, возможно, std::vector, вместо malloc(). Если речь идет о компиляции с помощью компилятора C ++, то здесь это не должно работать, потому что restrict не является допустимым ключевым словом C ++.

    – Г. Сон


  • 1

    Вы смотрели на код, который я написал внизу? Я обратился к restrict выпуск (не сложно).

    – Рэй Хэмел

  • 1

    X32 ABI на самом деле не поддерживается, вероятно, в ближайшем будущем он будет устаревшим, и я не думаю, что какие-либо дистрибутивы его поддерживают. Но, может быть, было бы лучше пойти с идеей OP и просто использовать uint64_t для копирования, поскольку он по-прежнему должен быть близок к оптимальному даже на большинстве платформ с исходным размером слова менее 64 бит.

    – Рэй Хэмел

  • 1

    FWIW Я уронил size_t идея, по крайней мере, это облегчает чтение моего кода.

    – Рэй Хэмел

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; читабельнее.

  • Можете ли вы уточнить, как uint_fast64_t помог бы? Что касается совместимости, то вы очень правы. Просто еще не дошло до этого.

    – jkoskela

  • uint_fast64_t определяется, даже если нет типа, равного 64 битам. Так он более портативный. Возможно uintmax_t было бы еще лучшим выбором?

    – Тоби Спейт

  • Что касается копии маленького размера, я думал об этом. Иметь все разные типы и проверять размер 6-8, 4-6 и т. Д. Казалось немного излишним. Насколько я понимаю, malloc в любом случае гарантирует 64-битное смещение. Я играл с идеей по-прежнему копировать данные с битовой маской, чтобы убедиться, что копируются только релевантные данные, хотя я не вижу практического случая, в котором это могло бы стать проблемой.

    – jkoskela

  • Что плохого в простом поэтапном подходе к уменьшенным копиям? Это то, что больше всего memcpy() реализации делать. Да, malloc() должен возвращать память, соответствующим образом выровненную для любого типа, но это не поможет, когда вам нужно скопировать (например) подстроку где-то в середине строки или из / в автоматическое («стек») хранилище.

    – Тоби Спейт

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

    – jkoskela

Если вы попробуете это в 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 и еще один байт.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *