Сотрудник 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
