Какова идеальная скорость роста для динамически выделяемого массива?

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

Так что просто очень быстро проверяя, Ruby (1.9.1-p129), кажется, использует 1.5x при добавлении в массив, а Python (2.6.2) использует 1.125x плюс константа (in _ 1_):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize - это количество элементов в массиве. Обратите внимание, что newsize добавляется к new_allocated, поэтому выражение с битовыми сдвигами и тернарным оператором на самом деле просто вычисляет избыточное выделение.

Допустим, вы увеличили размер массива на x. Итак, предположим, вы начали с размера T. В следующий раз, когда вы увеличите массив, его размер будет T*x. Тогда будет T*x^2 и так далее.

Если ваша цель состоит в том, чтобы иметь возможность повторно использовать память, которая была создана ранее, вы должны убедиться, что новая выделяемая вами память меньше суммы предыдущей памяти, которую вы освободили. Следовательно, имеем это неравенство:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

Мы можем удалить букву T с обеих сторон. Получаем вот что:

x^n <= 1 + x + x^2 + ... + x^(n-2)

Неформально мы говорим, что при nth распределении мы хотим, чтобы вся наша ранее освобожденная память была больше или равна потребности в памяти при n-м распределении, чтобы мы могли повторно использовать ранее освобожденную память.

Например, если мы хотим иметь возможность сделать это на 3-м шаге (т.е. n=3), то у нас есть

x^3 <= 1 + x 

Это уравнение верно для всех x таких, что 0 < x <= 1.3 (примерно)

Посмотрите, какой x мы получаем для разных n ниже:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

Обратите внимание, что коэффициент роста должен быть меньше 2 с x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Это действительно зависит от обстоятельств. Некоторые люди анализируют распространенные варианты использования, чтобы найти оптимальное количество.

Я видел 1.5x 2.0x phi x и раньше использовал power of 2.

Если у вас есть распределение по длинам массива и у вас есть функция полезности, которая говорит, насколько вам нравится тратить пространство впустую, а не тратить время, то вы определенно можете выбрать оптимальную стратегию изменения размера (и начального изменения размера).

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

В Scala вы можете переопределить loadFactor для хэш-таблиц стандартной библиотеки с помощью функции, которая смотрит на текущий размер. Как ни странно, массивы с изменяемым размером просто удваиваются, что большинство людей и делает на практике.

Я не знаю никаких массивов с удвоением (или 1.5 * ing), которые действительно вылавливают ошибки памяти и в этом случае становятся меньше. Кажется, что если бы у вас был один огромный массив, вы бы захотели это сделать.

Я бы также добавил, что если вы достаточно долго храните массивы с изменяемым размером и предпочитаете пространство с течением времени, может иметь смысл сначала резко увеличить доступность (для большинства случаев), а затем перераспределить до точно нужного размера, когда вы Выполнено.

Еще два цента

• У большинства компьютеров есть виртуальная память! В физической памяти вы можете иметь случайные страницы повсюду, которые отображаются как единое непрерывное пространство в виртуальной памяти вашей программы. Разрешение косвенного обращения осуществляется аппаратно. Исчерпание виртуальной памяти было проблемой в 32-битных системах, но на самом деле это больше не проблема. Так что заполнение дыры больше не проблема (кроме особых условий). Поскольку Windows 7 даже Microsoft поддерживает 64-битную версию без лишних усилий. @ 2011
• O (1) достигается с любым коэффициентом r> 1. То же математическое доказательство работает не только для параметра 2.
• r = 1.5 можно вычислить с помощью old*3/2, поэтому нет необходимости в операциях с плавающей запятой. (Я говорю /2, потому что компиляторы заменят это сдвигом бит в сгенерированном коде сборки, если сочтут нужным.)
• MSVC выбрал r = 1.5, поэтому есть по крайней мере один основной компилятор, который не использует 2 в качестве отношения.

Как сказал кто-то, 2 чувствует себя лучше, чем 8. А также 2 чувствует себя лучше, чем 1.1.

Я считаю, что 1.5 - хороший вариант по умолчанию. В остальном это зависит от конкретного случая.

Я согласен с Джоном Скитом, даже мой друг-теоретик настаивает на том, что это может быть доказано как O (1), если установить коэффициент равным 2x.

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

Я знаю, что это старый вопрос, но есть несколько вещей, которые всем, кажется, не хватает.

Во-первых, это умножение на 2: size ‹* 1. Это умножение на что угодно от 1 до 2: int (float (size) * x), где x - это число, * - плавающее. точечная математика, и процессор должен запускать дополнительные инструкции для преобразования между float и int. Другими словами, на машинном уровне для определения нового размера для удвоения требуется одна очень быстрая инструкция. Для умножения на что-то от 1 до 2 требуется по крайней мере одна инструкция для преобразования размера в число с плавающей запятой, одна инструкция для умножения (это умножение с плавающей запятой, поэтому, вероятно, потребуется как минимум вдвое больше циклов, если не 4 или даже в 8 раз больше), и одну инструкцию для возврата к int, и это предполагает, что ваша платформа может выполнять вычисления с плавающей запятой в регистрах общего назначения, вместо того, чтобы требовать использования специальных регистров. Короче говоря, вы должны ожидать, что математика для каждого распределения займет как минимум в 10 раз больше времени, чем простой сдвиг влево. Однако, если вы копируете много данных во время перераспределения, это может не иметь большого значения.

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

Мой ответ на вопрос? Нет, идеального числа не существует. Это настолько специфично для приложения, что никто даже не пытается это сделать. Если ваша цель - идеальное использование памяти, вам в значительной степени не повезло. Для производительности лучше использовать менее частое распределение, но если бы мы пошли именно так, мы могли бы умножить на 4 или даже на 8! Конечно, когда Firefox перескакивает с 1 ГБ на 8 ГБ за один раз, люди будут жаловаться, так что это даже не имеет смысла. Вот несколько практических правил, которые я бы придерживался:

Если вы не можете оптимизировать использование памяти, по крайней мере, не теряйте циклы процессора. Умножение на 2 по крайней мере на порядок быстрее, чем вычисления с плавающей запятой. Это может не иметь большого значения, но, по крайней мере, будет иметь какое-то значение (особенно на ранних этапах, во время более частого и меньшего распределения).

Не зацикливайтесь на этом. Если вы потратили 4 часа, пытаясь понять, как сделать что-то, что уже было сделано, вы просто зря потратили время. Честно говоря, если бы был вариант лучше, чем * 2, это было бы сделано в векторном классе C ++ (и во многих других местах) несколько десятилетий назад.

Наконец, если вы действительно хотите оптимизировать, не переживайте по мелочам. В наши дни никого не волнует потеря 4 КБ памяти, если только они не работают со встроенными системами. Когда вы получаете 1 ГБ объектов размером от 1 до 10 МБ каждый, удвоение, вероятно, слишком много (я имею в виду, что это от 100 до 1000 объектов). Если вы можете оценить ожидаемую скорость расширения, вы можете выровнять ее до линейной скорости роста в определенный момент. Если вы ожидаете около 10 объектов в минуту, то увеличение размера от 5 до 10 объектов за шаг (от 30 секунд до минуты), вероятно, будет нормальным.

Все сводится к тому, что не думайте слишком много, оптимизируйте то, что вы можете, и при необходимости настраивайте свое приложение (и платформу).

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

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

В частности, если вы посчитаете ¹, вы обнаружите, что верхний предел по скорости роста - золотое сечение ϕ = 1,618…. Скорость роста больше ϕ (например, 2x) означает, что вы никогда не сможете повторно использовать старые блоки памяти. Скорость роста лишь немного ниже, чем ϕ, означает, что вы не сможете повторно использовать старые блоки памяти до тех пор, пока не будет выполнено много перераспределений, в течение которых вы будете тратить память впустую. Итак, вы хотите быть как можно ниже ϕ, не жертвуя при этом слишком большой производительностью.

Поэтому я бы предложил этих кандидатов для математически обоснованной идеальной скорости роста, лучшей балансировки и потраченной впустую памяти:

• ≈1,466x (решение x ⁴ = 1 + x + x ^{2 ) позволяет повторно использовать память всего после 3 перераспределений, одно раньше, чем позволяет 1,5x, при этом перераспределение выполняется лишь немного чаще.}
• ≈1,534x (решение x ⁵ = 1 + x + x ^{2 + x 3) позволяет повторно использовать память после 4 перераспределений, как и в 1,5 раза, при этом перераспределение происходит немного реже для повышения производительности.}
• ≈1,570x (решение x ⁶ = 1 + x + x ^{2 + x 3 + x 4) разрешает повторное использование памяти только после 5 перераспределений, но будет перераспределяться еще реже для еще большего повышения производительности (едва)}

Очевидно, что здесь наблюдается некоторая убывающая отдача, поэтому я думаю, что глобальный оптимум, вероятно, находится среди них. Также обратите внимание, что 1,5x - отличное приближение к тому, что на самом деле является глобальным оптимумом, и имеет то преимущество, что оно чрезвычайно простое.

¹ Благодарим @ user541686 за этот отличный источник.