Структуры данных на практике. Глава 8: Динамические массивы и управление памятью

«Преждевременная оптимизация — корень всех зол, но преждевременная пессимизация является им не в меньшей степени». — Андрей Александреску
Проблема перераспределения
Динамические массивы (векторы C++, ArrayList в Java) — одна из самых полезных структур данных. Они сочетают в себе удобство для кэша, присущее массивам, с гибкостью динамического изменения размера.
Однако у них есть скрытые затраты, связанные с перераспределением.
Однажды я работал над агрегатором логов встраиваемой системы. Система накапливала сообщения логов в динамическом массиве и периодически скидывала их на флэш-накопитель. Кажется, всё просто, не так ли?
Но производительность была ужасной. Система тратила 60% времени на realloc().


















