Использование realloc в С++

Ответ 1

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

Итак, я думаю, что для того, чтобы получить здесь действительно хорошую оптимизацию, вам нужно больше, чем "тривиальное обходное решение", которое делает возможное дешевое перераспределение, если это возможно - вам нужно как-то сделать некоторую подготовку, чтобы сделать это возможным, и что затраты на подготовку вы адресуете пространство. Если вы делаете это только для определенных векторов, которые указывают, что они станут большими, то это довольно бессмысленно, потому что они могут указать с помощью reserve(), что они станут большими. Вы можете делать это автоматически только для всех векторов, если у вас обширное адресное пространство, чтобы вы могли "отбросить" большой кусок его на каждый вектор.

Как я понимаю, причина, по которой концепция Allocator не имеет функции перераспределения, заключается в ее простоте. Если std::allocator имеет функцию try_realloc, то либо каждый Allocator должен иметь один (который в большинстве случаев не может быть реализован, а просто должен всегда возвращать false), либо каждый стандартный контейнер должен быть специализируется на std::allocator, чтобы воспользоваться им. Ни один из вариантов не является отличным интерфейсом Allocator, хотя я полагаю, что это не было бы огромным усилием для разработчиков почти всех классов Allocator просто для добавления функции do-nothing try_realloc.

Если vector является медленным из-за перераспределения, deque может быть хорошей заменой.

Ответ 2

Вы можете реализовать что-то вроде try_realloc, которое вы предложили, используя mmap с MAP_ANONYMOUS и MAP_FIXED и mremap с помощью MREMAP_FIXED.

Изменить: просто заметил, что man-страница для mremap даже говорит:

mremap() использует таблицу страниц Linux схема. mremap() изменяет сопоставление между        виртуальные адреса и страницы памяти. Это можно использовать для реализации очень эффективный        перераспределить (3).

Ответ 3

realloc в C - не более чем удобная функция; он имеет очень мало преимуществ для производительности/сокращения копий. Основное исключение, о котором я могу думать, это код, который выделяет большой массив, а затем уменьшает размер, как только необходимый размер известен, но даже для этого может потребоваться переместить данные в некоторые реализации malloc (те, которые разделяют блоки строго по размеру), поэтому я считаю это использование realloc действительно плохой практики.

Пока вы не постоянно перераспределяете свой массив каждый раз, когда добавляете элемент, но вместо этого увеличиваете его экспоненциально (например, на 25%, 50% или 100%) всякий раз, когда у вас заканчивается свободное пространство, новая память, копирование и освобождение старого приведет к примерно одинаковой (и идентичной, в случае фрагментации памяти) производительности при использовании realloc. Это, безусловно, подход, который использует реализация С++ STL, поэтому я думаю, что вся ваша забота необоснованна.

Изменить: один (редкий, но неслыханный) случай, когда realloc действительно полезен для гигантских блоков в системах с виртуальной памятью, где библиотека C взаимодействует с ядром для перемещения целые страницы на новые адреса. Причина, по которой я говорю это редко, заключается в том, что вам нужно иметь дело с очень большими блоками (по крайней мере, несколько сотен kB), прежде чем большинство реализаций войдут в сферу управления распределением страницы и, вероятно, намного больше (возможно, несколько MB) перед входом и выходом из ядра для переупорядочения виртуальной памяти дешевле, чем просто делать копию. Конечно, try_realloc здесь не будет полезен, так как вся польза исходит из того, что делает движение недорого.