Я только что реализовал свой memcpy
функция без предварительного поиска.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void * copy ( void * destination, const void * source, size_t num )
{
if ((destination != NULL) && (source != NULL))
{
unsigned int *dst = destination;
const unsigned int *src = source;
unsigned int blocks = num/sizeof(unsigned int);
unsigned int left = num%sizeof(unsigned int);
while(blocks--){
*dst++ = *src++;
}
if (left){
unsigned char *cdst = (unsigned char *)dst;
const unsigned char *csrc = (const unsigned char *)src;
while(left--)
*cdst++ = *csrc++;
}
}
return destination;
}
При просмотре других реализаций memcpy я обнаружил некоторые отличия:
- невыровненный адрес не обрабатывается
- использование длинный вместо беззнаковое целое
Я не понял пункта №2. Насколько я знаю int всегда будет размером CPU WORD, т.е. для 16 бит будет 2 байта, а для 32 бит — 4 байта. Но долгое время он должен быть минимум 32 бита.
3 ответа
Выравнивание
unsigned int *dst = destination;
терпит неудачу, когда destination
не согласован для unsigned
. То же самое для src
. (OP, кажется, в некоторой степени осведомлен об этом «невыровненном адресе, который не обрабатывается»)
Сглаживание
Возможно строгое нарушение псевдонима. Видеть Что такое строгое правило псевдонима?
Не работает при перекрытии буферов
Без restrict
, буфер может перекрываться, и код плохо справляется с перекрытиями в обоих направлениях.
Рекомендуем использовать restrict
подобно memcpy()
.
void *memcpy(void * restrict s1, const void * restrict s2, size_t n);
Размер СЛОВА ЦП
«Я знаю, что int всегда будет размером CPU WORD» скидка на 8-битные процессоры (обычно во встроенном коде). По тем, int
как минимум 16-битный, а не 8-битный.
Размер низкоуровневой копии обычно связан с размером слова ЦП, но большая часть этого зависит от реализации.
Обычно unsigned
хорошо или лучше, но нужно профилировать реализацию, чтобы знать наверняка.
Незначительный: ненужный код
Испытание left
не лишний как позже while(left--)
делает свою работу.
// if (left)
NULL
Тестирование
Общий для нет проверка на нулевое значение. memcpy()
не требуется этого делать, и при этом не требуется не тестировать NULL
. Что делать, зависит от общих целей кодирования, так что решать вам.
Использовать size_t
последовательно
С num
относится к типу size_t
, убедитесь, что вы используете это для всех других размеров, счетчиков и индексов, связанных с этим.
Ненужный if(left)
Нет необходимости проверять left
будучи ненулевым, while()
петля внутри if
-block также выполнит эту проверку.
Не проверяйте NULL
указатели
Я бы избегал проверок на NULL
указатели. Вызывающий должен быть обязан убедиться, что действительные параметры передаются вашей функции. Если вас это беспокоит, рекомендую использовать assert()
заявления вместо этого:
void *copy(void *destination, const void *source, size_t num)
{
assert(destination != NULL);
assert(source != NULL);
...
}
Таким образом, в отладочных сборках будет напечатано правильное сообщение об ошибке. В сборках выпуска (с -DNDEBUG
), assert()
заявления ничего не сделают. Если NULL
-поинтер передан, программа получит ошибку сегментации. Это, возможно, лучше, чем эта функция, которая молча игнорирует проблему, поскольку это может привести к продолжению работы программы с возможно худшими последствиями.
Невыровненные адреса
На самом деле вы не обрабатываете указатели, которые не выровнены по int
требования. Это означает, что если вы используете эту функцию в архитектуре ЦП, которая не допускает невыровненный доступ, ваша программа, вероятно, выйдет из строя из-за ошибки шины или чего-то подобного.
Размер слова
Трудно сказать, как лучше всего скопировать большой блок памяти. На некоторых процессорах int
может быть идеального размера, но для других — нет. Попробуйте использовать long
или даже long long
, и измерьте время, необходимое для работы вашей машины. Помните, что на других машинах результаты могут быть другими.
На x86 использование регистров SSE или AVX может быть даже более эффективным, чем использование обычного целого числа, но некоторые процессоры также имеют специальные инструкции для обработки копирования больших объемов данных, независимо от размера регистра. Однако, если вы хотите, чтобы ваш код был переносимым, вам, вероятно, не следует использовать эти методы.
long
или жеlong long
сделает код очень медленным во встроенных системах начального уровня.— Лундин
@Lundin Почему? Единственная причина, по которой я могу думать, это то, что у вас процессор с нехваткой регистров, а компилятор не оптимизирует копию и без надобности переносит во временное хранилище. В противном случае компилятору пришлось бы сгенерировать несколько инструкций загрузки, но на самом деле это нормально, потому что в основном это просто эквивалентно небольшому развертыванию цикла.
— Г. Сон
- 1
Потому что
long
имеет не менее 32 бит, и если он используется на ЦП с менее чем 32-битными инструкциями данных, вы получите медленный код. В случае 8-битного процессора вы получите очень медленный код. И да, они обычно «испытывают нехватку регистров», так что вы можете в конечном итоге использовать стек в качестве посредника.— Лундин
Я пробовал это на Godbolt (см. godbolt.org/z/qxcrT7). GCC генерирует довольно эффективный код для процессоров MSP430 и Atmel, но у них много регистров. Однако код, созданный cc65 для MOS6502, выглядит ужасно (godbolt.org/z/8EM5na), как для
long int
иchar
версия.— Г. Сон
Код AVR тоже выглядит ужасно. Примерно так же плохо должно выглядеть на PIC, HC08, STM8, 8051, Z80 и других. Большинство вещей под названием MSP430 — это 16 биттеров, поэтому я ожидал, что они будут работать намного лучше.
— Лундин
К сожалению, эта функция довольно наивно написана до такой степени, что вам было бы намного лучше с простым побайтовым циклом:
for(size_t i=0; i<size; i++)
{
src[i] = dst[i];
}
Тестируйте и разбирайте! Если вы не можете превзойти указанную выше производительность с вашей собственной версией, то вам не следует писать свою собственную версию.
Как указывалось в других обзорах, у вас есть серьезная ошибка в виде несогласованного доступа в начале копии, вы, кажется, обрабатываете несоосность только в конце.
Также есть строгие нарушения псевдонимов. Фактически строгий псевдоним означает, что
memcpy
не может быть эффективно реализован в стандартном C — вы должны компилировать что-то вродеgcc -fno-strict-aliasing
или компилятор может выйти из строя. Многие традиционные компиляторы встроенных систем не злоупотребляют строгим псевдонимом, но gcc уже давно это делает, и он становится все более популярным.restrict
квалификация указателей поможет исправить ошибки сглаживания указателей и, возможно, немного оптимизировать код. Это стандартная библиотека memcpy:void *memcpy(void * restrict s1, const void * restrict s2, size_t n);
Развертывание собственного
memcpy
вероятно означает, что это должно бытьstatic inline
и помещается в заголовок, иначе он по определению всегда будет намного медленнее, чем стандартная библиотека.Вам нужно минимизировать количество веток. Единственные ветви, которые должны существовать в этой функции, если таковые имеются, — это те, которые корректируют несовпадение адресов в начале и в конце данных. Ветви очень плохи, поскольку они, вероятно, являются основными узкими местами здесь — если ЦП не может использовать кеш данных и инструкций, тогда весь алгоритм бессмыслен, поскольку тогда он почти наверняка намного хуже, чем ранее упомянутый цикл for, по крайней мере, на всех высокопроизводительные процессоры. Даже на средних и младших процессорах без кеша есть конвейерная обработка инструкций и может быть полезно отсутствие ветвлений.
В частности, проверки на NULL — это просто бессмысленное раздувание, которое не должно существовать в библиотечной функции, но должно выполняться вызывающим, если это вообще необходимо.
unsigned int
не гарантируется, что это будет самый быстрый из поддерживаемых выровненных типов — это верно для 16-32-битных систем, но не для 64-битных систем. Правильный тип для использования в этом случае для максимальной переносимости:uint_fast16_t
. Он охватывает все системы с требованиями к выравниванию от 16 до 64 битных систем.Однако 16-битные системы с требованиями к выравниванию довольно редки, я думаю, что у некоторых чудаков он есть, но у многих 16-битных нет, поэтому подумайте, действительно ли вам нужна переносимость для тех, которые есть. Иначе
uint_fast32_t
должно сработать. Точно так же переносимость на 64-битные программы может быть неактуальной, если вы ориентируетесь только на встроенные системы.ВАЖНЫЙ: Большинство 8- и 16-битных систем не имеют требований к выравниванию, и нет очевидной выгоды от создания 16-битных копий размером с слово на 8-битных системах. В таких системах такие реализации memcpy с «выровненными фрагментами» — это просто медленное раздувание — простой побайтный
for
цикл там был бы намного быстрее. Если вы хотите настроить таргетинг на такие системы, вам придется развернуть совершенно другую реализацию.Избегать
/
и%
если у вас нет причин полагать, что компиляция может их оптимизировать. Разделение очень сильно нагружает процессор, особенно на младших системах. В этом случае она вам не понадобится, подсчет «количества порций» не добавляет ничего значимого для алгоритма. Это типичный случай «писать код так, чтобы программист понимал, что происходит», что обычно хорошо, но не при написании кода библиотечного качества. Вместо этого просто проверяйте конечный адрес при итерации.copy
— плохое имя функции, поскольку различные библиотечные функции с таким именем существовали на протяжении многих лет.Не включайте заголовки библиотеки, которые вы не используете.
Замечание о строгом псевдониме означает, что библиотека memcpy никогда не может быть скомпилирована со стандартными совместимыми настройками. Все правило об эффективном типе указывает даже на memcpy, так что его, очевидно, нельзя применить к внутреннему устройству memcpy.
— Лундин