Пользователь
81,4
рейтинг
4 ноября 2014 в 16:00

Разработка → Почему буфер должен расти экспоненциально tutorial

Сотрудник Mozilla Николас Нетеркот опубликовал заметку с очень чётким объяснением, почему размер буфера памяти для программы нужно увеличивать экспоненциально, а не линейно.

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

Так вот. Представим, что наш изначальный 1-байтный буфер растёт по 1 байту до тех пор, пока не достигнет размера 1 МиБ. Сколько памяти мы задействовали для него кумулятивно?

1 + 2 + 3 + … + 1,048,575 + 1,048,576 = 549,756,338,176 байт

Неслабо, да?

Опытным программистам этот нюанс давно известен, так что линейное увеличение буфера кто-то даже считает «типичной ошибкой новичка».

Суть в том, что если новый массив всегда больше предыдущего на постоянную величину, то общая работа составит O(n2). Если же новый массив увеличивать на постоянный множитель N, то общая работа составит O(n). Под «работой» подразумеваются обращения к функциям malloc() и realloc() с последующим перераспределением и копированием значений в памяти, то есть общая нагрузка на систему.

Конечно, есть ситуации, например, со встроенными прошивками для аппаратного обеспечения, которые можно рассматривать как исключения из правила. Но для десктопных систем это практически закон. Вопрос только в том, какой множитель использовать: 2 или 1,5.

Николас Нетеркот добавляет к своему примеру, что на практике общее потребление памяти будет, конечно, меньше, потому что менеджер памяти округляет размер буфера. Например, менеджер того же Firefox (старая, сильно модифицированная версия jemalloc) округляет запросы на выделение памяти между 4 КиБ и 1 МиБ до ближайшего множителя 4 КиБ. То есть в нашем примере для буфера с итоговым объёмом 1 МиБ получится всего лишь:

4,096 + 8,192 + 12,288 + … + 1,044,480 + 1,048,576 = 134,742,016 байт

Для сравнения, если бы мы сразу использовали множитель 2:

4,096 + 8,192 + 16,384 + 32,768 + 65,536 + 131,072 + 262,144 + 524,288 + 1,048,576 = 2,093,056 байт

Говорят, что «типичная ошибка новичка» проявляется в очень многих проектах, когда любая задача ввода/вывода не масштабирует размер буфера. Нетеркот сходу нашёл соответствующие фрагменты неоптимального кода в реализациях алгоритмов в XDRBuffer, nsTArray и SQLite.
Анатолий Ализар @alizar
карма
751,5
рейтинг 81,4
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (50)

  • +9
    Стоит, наверное, добавить, что множитель 2 — не самый оптимальный.

    Допустим, у нас был выделен блок 4 МБ. Потом он вырос вдвое, до 8 МБ.
    И пусть так сложилось, что между этими двумя выделениями не было других обращений за памятью. Т.е. эти 4 МБ и 8 МБ, скорее всего, расположены друг за другом.
    И теперь, когда будем увеличивать блок до 16 МБ, никак не получится использовать эти освободившиеся блоки.

    Хотя, если бы, например, фактор роста был равен 1.5, то блоки были бы 4 МБ и 6 МБ.
    И грамотный аллокатор смог бы выделить 9 МБ блок (6 * 1.5) прямо поверх этих 4+6 = 10 МБ.

    Решив квадратное уравнение, получим, что оптимальное значение коэффициента равно… золотому сечению — 1.618
    • 0
      Золотое сечение не годится — чтобы сработал realloc, нам могут потребоваться одновременно два буфера — старый и новый. Разве что, у нас очень умный аллокатор, который умеет для realloc удлиннять буфер «с головы», если там свободно.
    • 0
      И теперь, когда будем увеличивать блок до 16 МБ, никак не получится использовать эти освободившиеся блоки.

      С чего бы?
      Как раз одна из тактик — просмотреть соседние блоки на возможность слияния, и присоединения следующего.
      Если, конечно, это не bottleneck :)
      • 0
        Мне кажется, тут речь была не о простом realloc'е, а о ситуации, когда мы сначала malloc'ом выделяем буфер нового размера, потом каким-то нетривиальный образом перемещаем в него данные, а затем вызываем для старого участка free (так, например, делает vector в С++ для нетривиально копируемых типов, так как он обязан вызвать для каждого элемента конструктор перемещения). Потому что в случае realloc'a описанной ситуации:
        Т.е. эти 4 МБ и 8 МБ, скорее всего, расположены друг за другом.
        быть не может, на предыдущем шаге наш участок памяти просто расширился бы с 4 мб до 8ми.
        • 0
          а о ситуации, когда мы сначала malloc'ом выделяем буфер нового размера,

          Ага, и я о том же: сначала просмотреть имеющиеся блоки, потом уже принимать решение что делать.
          В условиях, когда требования к памяти действительно важны, это осмысленный путь. А когда нет — хоть какие формулы выводи, упрёшься в другое :)
          • +2
            Не очень понял, что вы хотели сказать. Смотрите, пусть мы действуем вышеописанным способом: делаем malloc для буфера нового размера, потом free для старого. Кроме того, больше никто аллокатором не пользуется. Тогда при malloc'e аллокатор каждый раз будет выдавать нам кусок памяти, непосредственно следующий за текущим куском, то есть наша память будет выглядеть следующим образом:

            | ранее использовавшаяся память | старый буфер | новый буфер |

            И так будет продолжаться до тех пор, пока кусок ранее использовавшейся памяти не станет достаточно велик, чтобы вместить буфер нового размера. Математически можно показать, что для того, чтобы это хоть когда-нибудь произошло, требуется, чтобы наша константа была меньше золотого сечения.
            • 0
              делаем malloc для буфера нового размера

              Нет, сначала мы смотрим на размер требуемого блока, проходимся по уже имеющимся освобождённым, и только если среди них не находим слившихся подходящих, тогда выделяем новый.
              (я с точки зрения аллокатора)
              • 0
                Я об этом выше писал, все эти рассуждения (вида: пусть никто не больше не пользуется аллокатором памяти, тогда ...) имеют смысл только если мы делаем не realloc, а malloc нового блока, а затем free старого.
                • 0
                  пусть никто не больше не пользуется аллокатором памяти

                  Ну почему же.
                  На самом деле разработчики универсальных аллокаторов поставлены в известную позу, это очевидно. Но они вынуждены это делать, и тут уже работает (или должно работать) гауссовское распределение: если в пределах пика оно удовлетворяет, то и хорошо :)
                  • 0
                    Ну почему же.
                    Так это наше предположение, моделируемая ситуация, если хотите.
                    И пусть так сложилось, что между этими двумя выделениями не было других обращений за памятью.
                    • 0
                      Не совсем понимаю, о чём это?
                      • 0
                        Это цитата из самого первого комментария этой ветки. Всю нашу дискуссию я пытаюсь вам объяснить, в каких условиях рассуждения, приведенные в этом комментарии, имеют смысл (иными словами, какую ситуацию мы моделируем).
                        • 0
                          Я понял, сначала вы выделяете память для нового блока, потом решаете что делать.
  • +2
    Есть мнение, что множитель должен быть x=1.3. Для него выполняется условие x^3<x+1, поэтому после захвата буферов длиной 1,x,x^2 (и освобождения первых двух) буфер длиной x^3 захватится снова в начале памяти — на участке, который занимали 1 и x. Кроме того, объём неиспользуемой захваченной памяти будет меньше.
    • +6
      Мне кажется, что этот вопрос должен решаться теми, кто проектирует систему выделения памяти в стандартной библиотеке. Вдруг там блоки каждого фиксированного размера (допустим, степени двойки) выделяются из своего пула.
    • +2
      Ну 1.5 не сильно хуже в данном плане, нужно просто «отложить» побольше места.

      Для любого x < φ найдётся такое k, что
      xk < xk-2 + … + 1

      Это следует из тех соображений, что

      xk < xk-2 + … + 1
      эквивалентно
      xk (x-1) < xk-1 — 1
      xk+1 — xk — xk-1 + 1 < 0
      xk-1(x2 — x — 1) + 1 < 0

      Очевидно, что если мы подствим x = φ, то получим 1 < 0, что неверно для любого k. Но если x = φ — ɛ, то первое слагаемое отрицательно, а для достаточно большого k ещё и очень велико по модулю за счёт экспоненциального роста xk-1

      Так, для x = 1.5 нужно взять k=5. Подступаться к φ, конечно, не стоит ибо для x=1.61803398 мы получим k=38.
      • 0
        Ну 1.5 не сильно хуже в данном плане, нужно просто «отложить» побольше места.

        Так ведь «побольше» может и не найтись…
        • 0
          Ну память штука конечная, её всегда может не найтись.

          Вот, кстати, интересно посмотреть на какую-нибудь схему с убывающим коэффициентом роста. Допустим, начинать с 2 с шагом в 0.1 после каждой реаллокации и насыщением на, допустим, 1.3
    • +3
      Это очень сильно зависит от того, как работает аллокатор. У современных «быстрых» аллокаторов (tcmalloc от гугла или jemalloc от Facebook и Mozilla), блоки разного размера (до некоторых пределов) выделяются из разных пулов и перееиспользовать освобожденную память не получится. Более того, эти аллокаторы особенно эффективны для размеров равных степени двойки.

      В частности, реализация вектора от Facebook использует удвоение до определённого размера, а дальше — увеличение в полтора раза.
      • 0
        Более того, эти аллокаторы особенно эффективны для размеров равных степени двойки.

        А степени двойки должен быть равен размер, выделяемый пользователю, или физический размер буфера (включая поля, нужные аллокатору)?
  • –49
    Рукожопые быдлокодеры тормозилы пытаются отмазаться, почему у них память течет?

    P.S. Кто мне скажет, как показывать потоковое видео jpeg'ами, чтобы не приходилось каждые несколько минут перегружать iframe с видео?
    • 0
      Вы про mjpeg?
      Если да, то проверьте FF 34 (а ещё лучше — текущую dev ветку). multipart response довольно заковыристый стандарт, его реализация довольно закрученная (насколько я понимаю, ответ может быть совершенно произвольным, после картинки может придти HTML-страничка), но недавно пофиксили некоторые баги, связанные с ним.

      Вообще, несмотря на распространённость данного формата в области стриминга с различных веб-камер, я бы посоветовал использовать что-то более «мейнстримовое», что используется медиаресурсами для онлайн-стриминга видео. Конкретных советов, к сожалению, дать не могу.
      • –29
        FF 34 — рукожопое вырвиглазное дерьмо. Оно выглядит как хромоногая порнография, и тупит так же. У меня сейчас 24.8.0, это последний стабильный огнелис, не зараженный говномесами.

        А память как текла, так и течет. И delete() в жабоскрипте объекты не удаляет!

        Надо будет, конечно, попробовать стриминг через вебсокеты, но я читал на форумах, что этот способ тоже вызывает утечку памяти.

        P.S. Интересно: сколько гомосятины минусующей набежало…
        • +5
          И delete() в жабоскрипте объекты не удаляет!


          Может это в вашем жабоскрипте циклические ссылки из за которых и течет память? :)
  • +2
    А что делать, если буфер уже размером в гигабайт и нам не хватает 1-4килобайт на операцию? Удвоим не глядя? Конечно, это граничный случай и зачастую такого не бывает… как и описанного в статье.
    • 0
      В статье же описан случай, когда мы вообще не можем даже предполагать что и как будет выделяться. То есть самая сложная и непредсказуемая ситуация :)
    • +1
      Можно немного по-другому об этом подумать. Есть баланс между тем, как аккуратно используется память, и сколько времени занимает добавление одного элемента в среднем. Скажем, если память увеличивать в 2 раза, то добавление элемента будет стоить 4 условных такта, а если в 1.01 — то примерно 100 таких условных тактов.
  • +11
    При наличии MMU realloc не производит копирований и по сути является бесплатной операцией. Все свои выкладки относительно большого количества «кумулятивно задействованной памяти» можете выбрасывать.
    • 0
      Этот механизм поможет только для больших блоков (больше страницы памяти). По приведенной вами ссылке написано:

      Для очень больших запросов (>= 128 Кб по умолчанию) используются системные средства сопоставления памяти, если они поддерживаются


      И кроме того, такой механизм требует вызова ядра, что само по себе не быстро.
      • 0
        И кроме того, такой механизм требует вызова ядра, что само по себе не быстро

        Отсутствие затрат на копирование должно покрывать такой overhead.
        • +1
          Только начиная с некоторого размера. Именно поэтому порог довольно большой — 128 кБ.
          • 0
            И отлично. Тут без поллитры пересекающихся графиков не обойтись — скорее всего, в точке 128к как раз наступает равновесие.
      • 0
        Этот механизм поможет только для больших блоков (больше страницы памяти)
        Именно. А маленькие блоки копируются быстро.
        • 0
          Имхо при аддитивной стратегии (каждый раз увеличивать размер на некоторую фиксированную константу) вы на одних вызовах аллокатора просядете, даже если копирование у вас будет дешевым или вообще никогда не будет происходить. Например, если вы будете увеличивать размер со 128 кб до 256 блоками по 64 байта (допустим у нас массив int32 и мы добавляем по 16 элементов каждый раз), то вместо одного-двух вызовов аллокатора вы сделаете 128 * 1024 / 64 = 2048 вызовов, не говоря уж о том, когда счет пойдет на десятки-сотни мегабайт. Так что без какого-либо масштабирования константы такая стратегия в общем случае имхо обречена.
          • 0
            Ну, это уже про игру «обобщённый аллокатор пытается угадать, как его будут использовать». Касательно этого момента посыл был про то, что для перемещения больших блоков в другое место их не надо полностью копировать. Это играет роль в «плохом» случае, когда аллокатор не оказался достаточно сообразительным™ и ему надо что-то перемещать вместо простого сравнения и инкремента. Суть в том, что плохой случай не такой уж и плохой, каким его рисуют, и особенно не такой плохой для больших объёмов данных.
            • 0
              Согласен, но аддитивную стратегию сей факт лучше не делает (о чем собственно и статья). Даже если одно перемещение недорогое, нам придется делать их много, но даже если нам сказочно повезет и ничего никогда перемещать не придется, то все равно имхо мы должны сильно просесть за счет частоты вызова аллокатора.
    • +1
      Это для Linux'а же.
      • 0
        Не-а :)
        • +1
          Почему неа? Windows умеет realloc in-place делать?
          • –2
            При чём тут ОС?
            • +4
              Потому что по той ссылке речь идёт о том, что можно реализовать realloc так, чтобы он не копировал память, а вместо этого в ядре перемапить те же страницы в новое место. Для этого необходима поддержка со стороны ядра, конкретно в том случае для этого используется вызов mremap, который является Linux-специфичным.
            • 0
              При том, что ОС следит за распределением памяти и должна помнить, что у какого процесса куда отображается. Нельзя просто так взять и из своего драйвера поправить таблички MMU, ничего не поменяв в объектах системы. У Linux структурки известны и модуль может их спокойно поправить, если ему надо. У Windows кишки ядерного API не документированы, а публичных функций нет, так что поправить тоже можно, но байтики и смещения придётся реверсить.
              • 0
                Во-первых, кишки винды документированы, и вполне неплохо (да, да, я не сравниваю с Линуксом. Неплохо для проприетарной ос).
                Во-вторых, в Линуксе модуль структурки не правит, это делается все равно через ядро и стандартный вызов, насколько я понимаю.
                В Win есть Mdl, с которыми можно поиграться, но это на уровне драйверов/ядра.
                • 0
                  Я как раз про уровень ядра.

                  У Линуксового ядерного модуля есть документированный интерфейс к этим структуркам и даже если бы в ядре не было системного вызова mremap(), я могу написать модуль, который реализует этот функционал, и отправлять ему запросы из юзерленда через специальный файлик в /proc/self или ещё что, получив таким образом свой эразац-сисколл.

                  А вот для драйвера под Виндоус, судя по документации на MDL, такого интерфейса нет. Конечно, он может поиграться с байтиками, поредактировать какую-то память, и оно может даже заработает, но…
                  • +1
                    Возможно, я совсем-совсем ошибаюсь, но мне кажется, что мы можем описать mdlкой ряд страниц, смапить в виртуальное пространство, потом при расширении, смапить на следующие вирт. адреса встык новый кусок новой Mdlкой. Но может это работает только для драйверов, только для nonpaged памяти — не уверен. Так, чисто в порядке бреда.

                    О документированности: вот, пожалуйста, виндовые структурки:
                    //
                    // I/O system definitions.
                    //
                    // Define a Memory Descriptor List (MDL)
                    //
                    // An MDL describes pages in a virtual buffer in terms of physical pages.  The
                    // pages associated with the buffer are described in an array that is allocated
                    // just after the MDL header structure itself.  In a future compiler this will
                    // be placed at:
                    //
                    //      ULONG Pages[];
                    //
                    // Until this declaration is permitted, however, one simply calculates the
                    // base of the array by adding one to the base MDL pointer:
                    //
                    //      Pages = (PULONG) (Mdl + 1);
                    //
                    // Notice that while in the context of the subject thread, the base virtual
                    // address of a buffer mapped by an MDL may be referenced using the following:
                    //
                    //      Mdl->StartVa | Mdl->ByteOffset
                    //
                    
                    
                    typedef struct _MDL {
                        struct _MDL *Next;
                        CSHORT Size;
                        CSHORT MdlFlags;
                        struct _EPROCESS *Process;
                        PVOID MappedSystemVa;
                        PVOID StartVa;
                        ULONG ByteCount;
                        ULONG ByteOffset;
                    } MDL, *PMDL;
                    
                    
      • 0
        На Windows можно попробовать сэмулировать подобное поведение, выделяя память с помощью CreateFileMapping(), отображая её себе с помощью MapViewOfFileEx(), а потом UnmapViewOfFile() и снова MapViewOfFileEx() в новое место. (Ни разу не разработчик под Windows, только бегло просмотрел MSDN. Может, там есть нативный вызов, который делает это быстрее.)
        • 0
          Это я знаю; в той статье уже участвовал в этом обсуждении.
      • –5
        А зачем пользователям прошивки игровых приставок браузер? Да и вообще программировать под эту прошивку, если только они не игропейсатели?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.