Использование realloc в c ++
-
28-09-2019 - |
Вопрос
std::realloc
опасно в c ++, если память malloc'd содержит типы, отличные от pod.Кажется, что Только проблема в том, что std::realloc
не будет вызывать деструкторы типов, если он не может увеличить объем памяти на месте.
Тривиальным обходным путем было бы try_realloc
функция.Вместо того чтобы создавать новую память, если ее нельзя вырастить на месте, она просто вернет false .В этом случае может быть выделена новая память, объекты скопированы (или перемещены) в новую память и, наконец, освобождена старая память.
Это кажется в высшей степени полезным. std::vector
можно было бы с пользой использовать это, возможно, избегая всех копий / перераспределений.
упреждающий огнезащитный состав: Технически, это та же производительность Big-O, но если векторный рост - это бутылочное горлышко в вашем приложении, то увеличение скорости в 2 раза будет приятным, даже если Big-O останется неизменным.
НО я не могу найти ни одного c api, который работал бы как try_realloc
.
Я что-то упускаю?Является try_realloc
не так полезно, как я себе представляю?Есть ли какая-то скрытая ошибка, которая делает try_realloc
непригодный для использования?
А еще лучше, есть ли какой-нибудь менее документированный API, который работает следующим образом try_realloc
?
ПРИМЕЧАНИЕ: Очевидно, что здесь я использую код, специфичный для библиотеки / платформы.Я не волнуюсь так, как try_realloc
это по своей сути оптимизация.
Обновить:
Следующий комментарий Стива Джессопса о том, является ли vector
было бы эффективнее использовать realloc, я написал доказательство концепции для тестирования.Тот Самый realloc-vector
имитирует модель роста вектора, но вместо этого имеет возможность перераспределить его.Я прогнал программу до миллиона элементов в векторе.
Для сравнения a vector
должен выделяться 19 раз при увеличении до миллиона элементов.
Результаты, если realloc-vector
это единственное, что использует кучу, результаты потрясающие, 3-4 выделения при увеличении до размера миллиона байт.
Если realloc-vector
используется вместе с vector
это растет на 66% быстрее, чем скорость realloc-vector
Результаты менее обнадеживающие, выделяются в 8-10 раз за время роста.
Наконец, если realloc-vector
используется вместе с vector
который растет с той же скоростью, что и realloc-vector
распределяет 17-18 раз.Едва ли экономит одно выделение по сравнению со стандартным векторным поведением.
Я не сомневаюсь, что хакер мог бы изменить размеры распределения ресурсов, чтобы увеличить экономию, но я согласен со Стивом в том, что огромные усилия по написанию и поддержке такого распределителя не приносят результата.
Решение
vector
обычно растет большими приростами.Вы не можете делать это повторно без перемещения, если только вы не расположите все тщательно так, чтобы было большое количество свободных адресов чуть выше внутреннего буфера вектора (что фактически требует назначения целых страниц, потому что, очевидно, у вас не может быть других распределений позже на той же странице).
Поэтому я думаю, что для того, чтобы получить здесь действительно хорошую оптимизацию, вам нужно нечто большее, чем "тривиальный обходной путь", который выполняет дешевое перераспределение, если это возможно - вы должны каким-то образом подготовиться к сделать это возможно, и эта подготовка стоит вам адресного пространства.Если вы делаете это только для определенных векторов, которые указывают на то, что они станут большими, то это довольно бессмысленно, потому что они могут указывать с помощью reserve()
что они собираются стать большими.Вы можете сделать это автоматически для всех векторов только в том случае, если у вас обширное адресное пространство, так что вы можете "потратить" большую его часть на каждый вектор.
Насколько я понимаю, причина в том, что Allocator
концепция не имеет функции перераспределения, заключающейся в том, чтобы сделать ее простой.Если std::allocator
имел try_realloc
функция, тогда либо у каждого распределителя должен был бы быть один (который в большинстве случаев не мог бы быть реализован и просто должен был бы всегда возвращать false), либо каждый стандартный контейнер должен был бы быть специализирован для std::allocator
чтобы воспользоваться этим преимуществом.Ни один из вариантов не является отличным интерфейсом распределителя, хотя я полагаю, что разработчикам почти всех классов распределителей не потребовалось бы огромных усилий, чтобы просто добавить ничего не делающий try_realloc
функция.
Если vector
происходит медленно из-за перераспределения, deque
могло бы стать хорошей заменой.
Другие советы
Вы могли бы реализовать что-то вроде try_realloc
вы предложили, используя mmap
с MAP_ANONYMOUS
и MAP_FIXED
и mremap
с MREMAP_FIXED
.
Редактировать:только что заметил, что на справочной странице для mremap даже написано:
mremap() использует схему таблицы страниц Linux .mremap() изменяет сопоставление между виртуальные адреса и страницы памяти.Это может быть использовано для реализации очень эффективного перераспределение (3).
realloc
в C это едва ли больше, чем удобная функция;это дает очень мало преимуществ с точки зрения производительности / уменьшения количества копий.Основное исключение, о котором я могу подумать, - это код, который выделяет большой массив, а затем уменьшает размер, как только известен необходимый размер, но даже это может потребовать перемещения данных в некоторых malloc
реализации (те, которые разделяют блоки строго по размеру), поэтому я рассматриваю это использование realloc
действительно плохая практика.
До тех пор, пока вы не будете постоянно перераспределять свой массив каждый раз, когда добавляете элемент, а вместо этого будете увеличивать массив экспоненциально (напримерна 25%, 50% или 100%) всякий раз, когда у вас заканчивается место, простое ручное выделение новой памяти, копирование и освобождение старой даст примерно такую же (и идентичную, в случае фрагментации памяти) производительность, как при использовании realloc
.Это, безусловно, подход, который используют реализации C ++ STL, поэтому я думаю, что все ваше беспокойство необоснованно.
Редактировать:Единственный (редкий, но не неслыханный) случай, когда realloc
на самом деле это полезно для гигантских блоков в системах с виртуальной памятью, где библиотека C взаимодействует с ядром для перемещения целых страниц по новым адресам.Причина, по которой я говорю, что это редко, заключается в том, что вам нужно иметь дело с очень большими блоками (по крайней мере, несколькими сотнями кБ), прежде чем большинство реализаций даже войдут в сферу работы с распределением страниц по степени детализации, и, вероятно, намного большими (возможно, несколько МБ), прежде чем входить в пространство ядра и выходить из него, чтобы перераспределить виртуальную память дешевле, чем просто выполнять копирование.Конечно try_realloc
здесь это было бы бесполезно, поскольку вся выгода исходит от фактического делаю этот ход недорого.