Оптимизация в реализации Memcpy

Эта статья, посвященная интересной теме, не дает правильных примеров. Опубликованный код упоминается как Исходный код новой библиотеки GNU. И проект GNU, и команда newlib будут удивлены, узнав об этом неожиданном заявлении о конвергенции! newlib не является проектом GNU, и большая часть его исходного кода не находится под лицензией GPL.

Эта реализация memcpyоптимизированный непереносима, неоптимальна и во многих аспектах неверна.

Тест if (!(src & 0xFFFFFFFC) && !(dst & 0xFFFFFFFC)) пытается определить, совпадают ли адреса src и dst на границах long. Это громоздко и непереносимо по нескольким причинам и, как вы заметили, совершенно неверно:

• неявное преобразование из void * в int некрасиво и определяется реализацией. Указатели должны иметь вид (uintptr_t) для лучшей переносимости.
• 0xFFFFFFFC предполагает, что тип long составляет 4 байта. Это может быть неверно, и действительно, тип long имеет длину 8 байт в 64-битных системах Linux и Mac.
• src & 0xFFFFFFFC не является проверкой на выравнивание и вряд ли будет 0, предполагаемый тест на выравнивание по 4-байтовым границам - это src & 3.

Кроме того, код не может оптимизировать случай, когда src и dst имеют одинаковое выравнивание, но не выравниваются по границам long.

Другие возможные улучшения включают развертывание циклов, использование переключателя для малых значений len, объединение байтов, считанных из src, в long для записи в dst после его выравнивания по границам long ...

Вот улучшенная альтернатива:

#include <stdint.h>

void *memcpy(void *dst, void const *src, size_t len) {
    unsigned char *pcDst = (unsigned char *)dst;
    unsigned char const *pcSrc = (unsigned char const *)src;

    if (len >= sizeof(long) * 2
    &&  ((uintptr_t)src & (sizeof(long) - 1)) == ((uintptr_t)dst & (sizeof(long) - 1))) {
        while (((uintptr_t)pcSrc & (sizeof(long) - 1)) != 0) {
            *pcDst++ = *pcSrc++;
            len--;
        }
        long *plDst = (long *)pcDst;
        long const *plSrc = (long const *)pcSrc;
        /* manually unroll the loop */
        while (len >= sizeof(long) * 4) {
            plDst[0] = plSrc[0];
            plDst[1] = plSrc[1];
            plDst[2] = plSrc[2];
            plDst[3] = plSrc[3];
            plSrc += 4;
            plDst += 4;
            len -= sizeof(long) * 4;
        }
        while (len >= sizeof(long)) {
            *plDst++ = *plSrc++;
            len -= sizeof(long);
        }
        pcDst = (unsigned char *)plDst;
        pcSrc = (unsigned char const *)plSrc;
    }
    while (len--) {
         *pcDst++ = *pcSrc++;
    }
    return dst;
}

Обратите внимание, что приведение из void * не требуется в C, но требуется в C++.

Вот некоторые важные моменты, о которых следует помнить при попытке оптимизировать код для повышения скорости:

• никаких компромиссов в отношении правильности. Быстрый код, который не работает даже в пограничных случаях, бесполезен.
• остерегайтесь проблем с переносимостью: решения, зависящие от размера типа и / или порядка байтов, могут создавать проблемы с переносимостью.
• бенчмаркинг покажет, что работает, а что нет: вы должны тщательно рассчитать время для различных альтернатив в различных тестовых примерах.
• идеального решения не существует: более быстрый код на одной архитектуре может быть медленнее на другой, в том числе и наиболее проблематично на будущей. Тестирование на разных архитектурах.
• бороться со сложностью: избегайте запутанных решений, которые не приносят существенных улучшений, их правильность сложнее доказать и поддерживать.
• memcpy обычно оптимизируется в сборке или реализуется как встроенный в современных компиляторах.