В процессе чтения статьи «Облегчённая» реализация контейнера vector вспомнился свой опыт борьбы с вектором. Собственно этим опытом я и хотел бы поделиться.
Да, при размерности массива 10000 элементов, лишний указатель в реализации элемента доставит ощутимые неудобства, но настоящая проблема памяти при использовании vector в полной мере проявляется несколько иначе.
Собственно проблема состоит в выделении памяти под новые элементы.
В недалеком прошлом я работал над проектом в котором приходилось обрабатывать большие массивы данных ( порядка 20 — 30 тысяч элементов на массив, по ~24 байта статики на элемент ). Весьма удобно было использовать для этого вектора. Сразу оговорюсь что в проекте производительность не была узким местом.
Обычно никто не задумывается что происходит в момент вызова push_back(). Мы тоже не задумывались об этом пока не был введен лимит памяти для нашего приложения. И вот здесь грабли нанесли первый удар. А именно — пришлось обратить внимание на то что график использования памяти напоминает кардиограмму. Т.е. в некоторые, на первый взгляд случайные, моменты времени на нем появляются весьма существенные пики на весьма несущественное время и пики эти выходят за лимит. Кроме того наконец было замечено что у приложения есть проблема со спонтанными «подвисаниями» на небольшое время. Время было несущественным, но все же оставалось неясным почему вызовы одного и того же метода занимают то 1-2 миллисекунды то 1-2 секунды.
Разбирательство привело нас к тому самому push_back().
В процессе разбирательства я узнал ( от более подкованного коллеги ) что память в векторе выделяется логарифмически, а именно:
— если при добавлении элемента под него нет зарезервированной памяти, то резервируется size*K памяти, где size — текущий размер вектора, а K — коэффициент, зависящий от реализации вектора и обычно это 2 ( более подробно можно почитать например у Алены Сагалаевой ).
Таким образом получаем следующее:
Допустим у нас в векторе уже находится 1024 элемента. При вызове push_back() размер вектора будет увеличен до 2048 ( при K=2, для простоты будем считать что так оно и есть всегда ), но реально храниться там будет всего 1025 элементов. Конечно лишнюю зарезервированную память можно освободить, например с помощью swap trick, но вроде как правильнее не выделять лишнего, т.е. использовать reserve.
Сказано — сделано. Добавили, пересобрали и начали тестировать и вернулись к началу поскольку кардиограмма упорно продолжала иметь место быть, равно как и «подвисания».
В конце концов, после длительных размышлений о смысле бытия, принципах работы вектора и системы выделения памяти справедливость восторжествовала.
Вернемся к нашему вектору в котором уже находится 1024 элемента.
Для наглядности допустим что размер элемента равен 16 байтам.
Тогда объем памяти, занимаемой таким вектором ( без учета накладных расходов самого вектора и динамической части элементов ) составит 16 килобайт.
Поскольку вектор всегда располагается в непрерывной памяти, при попытке добавить в него злосчастный 1025-й элемент происходит следующее:
Так вот проблема состоит в том что в какой-то момент времени занятым оказывается объем памяти равный size + size*K, т.е. и старый блок и новый — 48 килобайт в нашем случае.
На малых списках это не играет роли, но представьте подобную операцию со списком в несколько десятков тысяч элементов. Использование reserve не спасает ситуацию поскольку картина получается почти аналогичной — старый блок + новый, немного больший старого, копирование, удаление — 32 килобайта.
Также выяснилось что это же было и причиной «подвисаний» — выделение больших объемов памяти с последующим копированием данных требует недюжинных усилий.
Можно долго общаться на тему оптимизации самих элементов и различных сферических коней в вакууме, но в нашем случае решением проблемы стала имплементация MultyVector ( как мы его назвали ) — класса повторяющего необходимый интерфейс оргинального вектора, хранящего данные в векторе векторов, имеющего внутреннюю логику преобразования индексов и динамического расширения/очистки.
Думаю что будет лишним описывать все внутренности этой несложной обертки и приводить какой-либо код.
Скажу только что в нашем случае нормальный размер внутреннего вектора составлял 1000 элементов, а удаление/добавление элементов в произвольную точку массива использовалось настолько редко что им можно было пренебречь и не бояться что один из внутренних векторов снова разрастется до невероятных размеров.
Таким образом удалось заменить работу с большим блоком памяти на работу с набором более мелких ( несколько векторов по 1000 элементов ).
Подход не претендует на звание идеального, но с поставленной задачей справился на 100%.
UPD. Я, собственно, не совсем понимаю причину холливара в коментах, посему:
1. Специфика проекта не позволяла использовать ничего стороннего. Все самое необходимое предоставлялось фреймворком. Среди подходящего необходимого был только вектор и лист. Вектор был удобнее поскольку о том что придется работать с такими объемами данных узнали только к завершению проекта. По той же причине сначала не задумывались о памяти.
2. Насчет сферических коней в вакууме и идиотов в коментариях я уже писал выше.
Да, при размерности массива 10000 элементов, лишний указатель в реализации элемента доставит ощутимые неудобства, но настоящая проблема памяти при использовании vector в полной мере проявляется несколько иначе.
Собственно проблема состоит в выделении памяти под новые элементы.
В недалеком прошлом я работал над проектом в котором приходилось обрабатывать большие массивы данных ( порядка 20 — 30 тысяч элементов на массив, по ~24 байта статики на элемент ). Весьма удобно было использовать для этого вектора. Сразу оговорюсь что в проекте производительность не была узким местом.
Обычно никто не задумывается что происходит в момент вызова push_back(). Мы тоже не задумывались об этом пока не был введен лимит памяти для нашего приложения. И вот здесь грабли нанесли первый удар. А именно — пришлось обратить внимание на то что график использования памяти напоминает кардиограмму. Т.е. в некоторые, на первый взгляд случайные, моменты времени на нем появляются весьма существенные пики на весьма несущественное время и пики эти выходят за лимит. Кроме того наконец было замечено что у приложения есть проблема со спонтанными «подвисаниями» на небольшое время. Время было несущественным, но все же оставалось неясным почему вызовы одного и того же метода занимают то 1-2 миллисекунды то 1-2 секунды.
Разбирательство привело нас к тому самому push_back().
В процессе разбирательства я узнал ( от более подкованного коллеги ) что память в векторе выделяется логарифмически, а именно:
— если при добавлении элемента под него нет зарезервированной памяти, то резервируется size*K памяти, где size — текущий размер вектора, а K — коэффициент, зависящий от реализации вектора и обычно это 2 ( более подробно можно почитать например у Алены Сагалаевой ).
Таким образом получаем следующее:
Допустим у нас в векторе уже находится 1024 элемента. При вызове push_back() размер вектора будет увеличен до 2048 ( при K=2, для простоты будем считать что так оно и есть всегда ), но реально храниться там будет всего 1025 элементов. Конечно лишнюю зарезервированную память можно освободить, например с помощью swap trick, но вроде как правильнее не выделять лишнего, т.е. использовать reserve.
Сказано — сделано. Добавили, пересобрали и начали тестировать и вернулись к началу поскольку кардиограмма упорно продолжала иметь место быть, равно как и «подвисания».
В конце концов, после длительных размышлений о смысле бытия, принципах работы вектора и системы выделения памяти справедливость восторжествовала.
Вернемся к нашему вектору в котором уже находится 1024 элемента.
Для наглядности допустим что размер элемента равен 16 байтам.
Тогда объем памяти, занимаемой таким вектором ( без учета накладных расходов самого вектора и динамической части элементов ) составит 16 килобайт.
Поскольку вектор всегда располагается в непрерывной памяти, при попытке добавить в него злосчастный 1025-й элемент происходит следующее:
- выделяется новый блок памяти размером size*K, т.е. 32 килобайта
- в этот новый блок копируется содержимое вектора
- старый блок уничтожается
- в вектор физически добавляется наш 1025-й элемент
Так вот проблема состоит в том что в какой-то момент времени занятым оказывается объем памяти равный size + size*K, т.е. и старый блок и новый — 48 килобайт в нашем случае.
На малых списках это не играет роли, но представьте подобную операцию со списком в несколько десятков тысяч элементов. Использование reserve не спасает ситуацию поскольку картина получается почти аналогичной — старый блок + новый, немного больший старого, копирование, удаление — 32 килобайта.
Также выяснилось что это же было и причиной «подвисаний» — выделение больших объемов памяти с последующим копированием данных требует недюжинных усилий.
Можно долго общаться на тему оптимизации самих элементов и различных сферических коней в вакууме, но в нашем случае решением проблемы стала имплементация MultyVector ( как мы его назвали ) — класса повторяющего необходимый интерфейс оргинального вектора, хранящего данные в векторе векторов, имеющего внутреннюю логику преобразования индексов и динамического расширения/очистки.
Думаю что будет лишним описывать все внутренности этой несложной обертки и приводить какой-либо код.
Скажу только что в нашем случае нормальный размер внутреннего вектора составлял 1000 элементов, а удаление/добавление элементов в произвольную точку массива использовалось настолько редко что им можно было пренебречь и не бояться что один из внутренних векторов снова разрастется до невероятных размеров.
Таким образом удалось заменить работу с большим блоком памяти на работу с набором более мелких ( несколько векторов по 1000 элементов ).
Подход не претендует на звание идеального, но с поставленной задачей справился на 100%.
UPD. Я, собственно, не совсем понимаю причину холливара в коментах, посему:
1. Специфика проекта не позволяла использовать ничего стороннего. Все самое необходимое предоставлялось фреймворком. Среди подходящего необходимого был только вектор и лист. Вектор был удобнее поскольку о том что придется работать с такими объемами данных узнали только к завершению проекта. По той же причине сначала не задумывались о памяти.
2. Насчет сферических коней в вакууме и идиотов в коментариях я уже писал выше.