Сотрудник Mozilla Николас Нетеркот опубликовал заметку с очень чётким объяснением, почему размер буфера памяти для программы нужно увеличивать экспоненциально, а не линейно.
Предположим, что у нас есть структура данных, для которой нужно всё больше памяти, например, строка или вектор. Если новые элементы не помещаются в буфере, то создаётся новый буфер, туда копируются всё содержимое из старого, а затем старый буфер освобождается. Обычное этим занимается realloc().
Так вот. Представим, что наш изначальный 1-байтный буфер растёт по 1 байту до тех пор, пока не достигнет размера 1 МиБ. Сколько памяти мы задействовали для него кумулятивно?
1 + 2 + 3 + … + 1,048,575 + 1,048,576 = 549,756,338,176 байт
Неслабо, да?
Читать полностью »