У меня есть два вопроса.
Копируют ли realloc() и memcpy() записи из массива в другой быстрее, чем просто повторяя каждый элемент O(N) ? Если да, то как вы думаете, в чем его сложность?
Если выделенный размер меньше исходного размера, копирует ли realloc() записи куда-то еще или просто оставляет их, поскольку они уменьшают размер массива?
1 - Нет. Они копируют блок за раз. См. http://www.embedded.com/design/configurable-systems/4024961/Optimizing-Memcpy-improves-speed для довольно хорошего анализа.
2 - Это зависит от реализации. См. http://www.gnu.org/software/libtool/manual/libc/Changing-Block-Size.html для получения подробной информации о glibc. «В некоторых реализациях распределения уменьшение размера блока иногда требует его копирования»
Давайте немного поближе посмотрим на memcpy и, пока мы на нем, на «большой O» или нотацию Ландау.
Во-первых, большой-О. Как я уже говорил в другом месте, стоит запомнить определение большого O, которое заключается в том, что некоторая функция g(n) называется O(f(n)) когда существует константа k, для которой g(n) kf(n). Что делает константа, так это позволяет вам игнорировать мелкие детали в пользу важной части. Как все уже заметили, memcpy из n байтов будут O(n) в большинстве случаев любой нормальной архитектуры, потому что независимо от того, что вам нужно переместить эти n байт, по одной порции за раз. Таким образом, можно было бы написать первую наивную реализацию memcpy на C.
unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
long ix;
for(ix=0; ix < size; ix++)
s1[ix] = s2[ix];
return s1;
}
На самом деле это O(n), и вы можете задаться вопросом, почему мы вообще возимся с библиотечной подпрограммой. однако особенность функций libc заключается в том, что они являются местом, где пишутся специфичные для платформы утилиты; если вы хотите оптимизировать архитектуру, это одно из мест, где вы можете это сделать. Таким образом, в зависимости от архитектуры могут существовать более эффективные варианты реализации; например, в архитектуре IBM 360 есть инструкция MOVL, которая перемещает данные большими порциями, используя очень оптимизированный микрокод. Таким образом, вместо этого цикла реализация memcpy 360 может выглядеть примерно так:
LR 3,S1 LOAD S1 ADDR in Register 3
LR 4,S2
MOVL 3,4,SIZE
(Кстати, нет гарантий, что это правильный 360-градусный код, но он послужит иллюстрацией.) Эта реализация выглядит так, что вместо выполнения n шагов по циклу в качестве Код C сделал, он просто выполняет 3 инструкции.
Однако на самом деле происходит то, что он выполняет O(n) микро инструкций под прикрытием. Что отличается между ними, так это константа k; потому что микрокод намного быстрее, и поскольку в инструкциях всего три шага декодирования, он значительно быстрее, чем наивная версия, но все равно O(n) -- просто константа меньше.
И именно поэтому вы можете эффективно использовать memcpy — он не асимптотически быстрее, но его реализация настолько быстра, насколько это возможно на этой конкретной архитектуре.
Производительность memcpy на самом деле не может быть лучше, чем O(N), но ее можно оптимизировать так, чтобы она превосходила ручное копирование; например, он может скопировать 4 байта за время, необходимое для копирования 1 байта. Многие реализации memcpy написаны на ассемблере с использованием оптимизированных инструкций, которые могут копировать несколько элементов за раз, что обычно быстрее, чем копирование данных по одному байту за раз.
Я не совсем понимаю этот вопрос, если вы используете realloc для уменьшения размера памяти и это удается (возвращает не-NULL), новое местоположение будет содержать те же данные, что и старое местоположение, вплоть до размера нового запроса. Если место в памяти было изменено в результате вызова realloc (не обычно при уменьшении размера), содержимое будет скопировано, в противном случае копирование не требуется, так как память не перемещалась.
Как уже говорилось, это не будет быстрее, чем O (n), но системы памяти часто имеют предпочтительный размер блока, а также можно, скажем, записывать размер строки кэша за раз.
Предполагая, что вы говорите о glibc, и, поскольку ваши вопросы зависят от реализации, вероятно, лучше просто проверить источник:
Как я это читал, ответы будут такими:
У x86 есть специальные инструкции для сканирования и сопоставления байта/слова в блоке памяти, а также инструкция, которую можно использовать для копирования блока памяти (в конце концов, это процессор CISC). Многие компиляторы C, которые реализуют встроенный язык ассемблера и прагму для встраивания целых функций, уже много лет используют это преимущество в своих библиотечных функциях.
Для копирования памяти используются movsb/movsw в сочетании с инструкцией rep.
CMPS/MOVS/SCAS/STOS
REP, REPE, REPNE, REPNZ, REPZ
Программа установки регистрируется с адресами src/trg и счетчиком целых чисел, и все готово.
Некоторые из важных моментов, связанных с realloc(проверьте на dev c++): void *realloc(void *ptr, size_t size);
Функция realloc() должна изменить размер объекта памяти, на который указывает ptr, на размер, указанный параметром size.
Содержимое объекта должно оставаться неизменным до меньшего из нового и старого размеров.
Если новый размер больше, содержимое новой выделенной части объекта не указано.
Если размер равен 0 и ptr не является нулевым указателем, объект, на который указывает указатель, освобождается.
Если ptr является нулевым указателем, realloc() должен быть эквивалентен malloc() для указанного размера.
Если ptr не соответствует указателю, возвращенному ранее функциями calloc(), malloc() или realloc(), или если пространство ранее было освобождено вызовом free() или realloc(), поведение не определено.
