Доработка контейнера vector для работы с большими объемами данных

В процессе чтения статьи «Облегчённая» реализация контейнера 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*K, т.е. 32 килобайта
  • в этот новый блок копируется содержимое вектора
  • старый блок уничтожается
  • в вектор физически добавляется наш 1025-й элемент

Так вот проблема состоит в том что в какой-то момент времени занятым оказывается объем памяти равный size + size*K, т.е. и старый блок и новый — 48 килобайт в нашем случае.
На малых списках это не играет роли, но представьте подобную операцию со списком в несколько десятков тысяч элементов. Использование reserve не спасает ситуацию поскольку картина получается почти аналогичной — старый блок + новый, немного больший старого, копирование, удаление — 32 килобайта.
Также выяснилось что это же было и причиной «подвисаний» — выделение больших объемов памяти с последующим копированием данных требует недюжинных усилий.

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

Думаю что будет лишним описывать все внутренности этой несложной обертки и приводить какой-либо код.
Скажу только что в нашем случае нормальный размер внутреннего вектора составлял 1000 элементов, а удаление/добавление элементов в произвольную точку массива использовалось настолько редко что им можно было пренебречь и не бояться что один из внутренних векторов снова разрастется до невероятных размеров.

Таким образом удалось заменить работу с большим блоком памяти на работу с набором более мелких ( несколько векторов по 1000 элементов ).

Подход не претендует на звание идеального, но с поставленной задачей справился на 100%.

UPD. Я, собственно, не совсем понимаю причину холливара в коментах, посему:
1. Специфика проекта не позволяла использовать ничего стороннего. Все самое необходимое предоставлялось фреймворком. Среди подходящего необходимого был только вектор и лист. Вектор был удобнее поскольку о том что придется работать с такими объемами данных узнали только к завершению проекта. По той же причине сначала не задумывались о памяти.
2. Насчет сферических коней в вакууме и идиотов в коментариях я уже писал выше.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 48

    +3
    Было бы интересно посмотреть как вы это реализовали.
      +2
      Мне кажется тут главное, чтобы вектор при достижении некоторого размера ресайзился уже не тупым пересозданием в новом месте, а ремаппингом страниц, когда это возможно. И, соответственно, был выровнен на страницу.
        0
        Такое сейчас реализовано где-нибудь? Что делать на архитектурах, где страницы по 4MB?
          0
          Посмотрел в моно — там не реализовано. Можно им идею подкинуть (если не забуду).

          На вопрос ответ очевиден: применять эту технику только для векторов с вместимостью больше или равной 4 МБ или, в общем случае, размеру страницы.
            0
            Желательно, чтобы ОС имела интерфейс в помощь миграции листов памяти. Иначе все преимущество на контекстных переключениях съестся.
        0
        А итераторы тоже реализовали?
          +1
          И для альтернативных расположений данных в памяти можно использовать аллокаторы.
          +16
          идиоты, про std::deque никогда не слышали
            –4
            Ну deque тут не поможет. Обычно у STL-ного deque тоже переаллокация с копированием элементов происходит. Например в gcc используется реализация с вектором и циклической индексацией. Т.е. когда место в векторе закончится, то будет все то же самое.
              +7
              у std::deque push_back имеет O(1) скорость выполнения, топикреатер просто нешарит в языке на котором пишет- вот и высирает вылосипеды, ну высирыает и высирает, это ещё полбеды- но когда свой высер на обозрение общественности выставляет- это уже плохо.
                0
                Да, немного неправильно выразился. Сами элементы не копируются, копируется таблица мэппинга индексов при переаллокации. Т.е. всплески могут быть все-равно и они будут O(n). Но константа, конечно, сильно меньше, чем в векторе.
                • UFO just landed and posted this here
                +5
                Не будет.

                «A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle. „
                  0
                  С deque могут начаться тормоза если часто необходим последовательный доступ к элементам, но это уже от зависит от того как работают с контейнером, конечно.
                +2
                Отчего же сразу идиоты, они просто еще не Senior и не читали Кнута и Мейерса, либо пролистали просто.
                Кроме того, не сильно ясно какие у них задачи, может им только вектор и подходит. Посему не стоит так критично, каждый контейнер на свою задачу, к тому же если бы deque равнозначно заменял vector, он был бы не нужен, посему тут нужно просто полистать Мёртвого Страуса и Мейерса, выбрать контейнер. Если выбор не определился, то полистать более серьёзную литературу и выбрать правильный аллокатор.
                Они по сути простенький хэш сделали своим «ветором векторов», может им бы банальное дерево подошло, кто знает, что у них там за потребности.
                • UFO just landed and posted this here
                    0
                    Я тоже листал комменты в надежде что скоро встречу именно этот. Очень удивился, что он не был первым.
                  +7
                  Беда, инструментом пользуетесь, а как он работает не знаете. Скажите честно, сколько рабочих часов потратили на то, чтобы выявить ошибку и выяснить как работает банальный std::vector?
                    –4
                    Вы знаете как работает АБС в машине, к-рую водите? Или гидроусилитель?
                    Что удерживает мотоцикл от падения на скорости?
                    Как данные обрабатываются на видеокарте прежде, чем попасть на экран?
                    Я пользуюсь Хабром (что тоже инструмент), но не вникаю во внутренний механизм его работы (даже если б имел такую возможность) — потому, что не вижу в этом потребности.

                    У автора до некоторого момента не возникала потребность в знании реализации контейнера. Появилась — выяснил.
                      +2
                      использование того или иного контейнера основывается как раз таки на его преимуществах\недостатках, надо знать сильные и слабые стороны, дабы для конкретной задачи подбирать более подходящее решение. именно такие вещи и надо знать.
                        –1
                        В большинстве случаей не правильный выбор контейнера не проявит себя на скорости выполнения никак.
                        Ну считываете вы параметры программы из ini файла. Ну пусть вы использовали vector/deque/list вместо map? Если в программе менее сотни конфигурационных параметров, каждый из к-рых считывается скажем раз в пару секунд — на современной машине вы даже с секундомером не увидите разницы, несмотря на линейную скорость поиска против логарифмической
                          0
                          так бы и сказали, что не сталкиваетесь с задачами которые требуют производительности…
                          на ГД.ру была тема где человек перешел от сета, к сортировке вектора и снизил время кадра с 40 до 6 мс, что согласитесь заметно, даже без секундомера…
                      • UFO just landed and posted this here
                          0
                          Почти никогда не пользовался буффером вектора напрямую.
                          • UFO just landed and posted this here
                      0
                      Интересно, а реализация Vector в AS3 это тупое зеркало? Плеер то на плюсах, наверно, написан. Мне бы большим подспорьем стало. Массивы хоть не такие большие (до 1000), но думается, если элемент вектора весит по 50кб, то оптимизация будет ощутима.
                        0
                        Вообще-то vector изначально не оптимален для частого добавления элементов. И доролнительная проблема с часто растущими векторами, как и в предыдущей статье — фрагментация памяти. Был кусок size, стал size + K*size, потом оригинальную size освободили, но не факт что оптимально удастся ее использовать.
                          +10
                          Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.

                          RTFM.
                            0
                            реализация вектора и логарифмическое выделение памяти соответсвует все академическим каннонам. именно так нас учили в универе пистать динамические массивы. вывод — общий случай не работает везде
                              0
                              Ну не знаю, часто бывает, что использование вектора для частых добавлений это просто ошибка проектирования, мне приходилось работать со списками данных с 2 и более миллионами записей, использовал list, проблем не обнаруживал вообще. Нормально и добавлял и бегал и получал доступ к нужным элементам, делал частичный индекс и многое другое и прожил без vector.

                              Если бы вы сначала описали, зачем вам понадобился именно vector. Было бы интереснее, да и может быть предложили бы другой вариант. А стандартный контейнер я переписывал только 1 раз, мне нужна была репликация данных на диск при изменении.
                              • UFO just landed and posted this here
                                  0
                                  Мне не важно сколько перераспределяет раз, все зависит от реализации, а их много и может отличаться. А list для этих целей подходит отлично.
                                  • UFO just landed and posted this here
                                      0
                                      Ну элементы в векторе частенько менялись и вставлялись не только в конец.
                                      • UFO just landed and posted this here
                                –7
                                Целая статья из проблемы, которая решается за пару минут, комментарии «используй list/deque», от людей, не знающих, что у list/deeque среднее время доступа O(N), а у вектора O(1)…

                                «бида-бида, грусть — пичаль»

                                авторы, почитайте про stlxxl
                                • UFO just landed and posted this here
                                    0
                                    Вот вы сейчас в корне убили в зародыше статью «Сегодня наши очумелые ручки делают Стл-образный велосипед», которая непременно была бы на главной.
                                    • UFO just landed and posted this here
                                  –1
                                  Выделение памяти прежде всего зависит от условий задачи, и лишь уж потом — от используемых в ней инструментов (алгоритмов, библиотек и прочего). Данная задача выбивается из ряда обычных, поэтому и недовольство аллокатором или наслоенным поверх него темплейтом становится более вероятным. Серебряной пули нет. Правила русской рулетки того и не требуют.
                                  • UFO just landed and posted this here
                                      0
                                      Конкретно против этого высказывания спорить не буду. Но и вы спорите не со мной.
                                    0
                                    Звучит как реализация sparce array (разреженный массив)
                                      0
                                      sparse
                                        0
                                        да, точно :-) спасибо
                                      +5
                                      «STL для самых маленьких» на Хабре :)
                                        +1
                                        А им, знаете ли, тоже нужно учиться. И, честно говоря, не всегда хорошо учиться на своих ошибках.
                                        Ясно что и нам нужно было учиться раньше и нужно было обращать внимание на «мелочи» ( специально взял в кавычки чтобы избежать очередного холливара о мелочах в программировании ), но ведь всегда есть достаточно веские причины вроде специфики проекта, особенностей реализации под конкретную платформу и просто человеческого фактора.
                                        К слову, когда-то, много лет назад, мне приходилось писать нативную либу для работы с COM-портом в Java просто потому как таковая хоть и существовала, но была в настолько непотребном состоянии, что использовать ее не представлялось возможным. И там уже не стоял вопрос о знании языка, радиусе кривизны рук и длине костылей — нужно было просто быстро найти выход из сложившейся ситуации иначе финиш.
                                        Собственно такая ситуация описана была и здесь. И, глядишь, кто-нибудь из этих «самых маленьких» благодаря умению читать и любви к хабру обойдет такие грабли стороной и скажет спасибо хабру или, чем черт не шутит, мне.
                                          0
                                          > «STL для самых маленьких» на Хабре :)

                                          Поправочка:

                                          «STL для самых маленьких» из песочницы.

                                        Only users with full accounts can post comments. Log in, please.