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

Question

C ++ имеет std :: vector, а Java имеет ArrayList, и многие другие языки имеют свою собственную форму динамически размещаемого массива. Когда динамическому массиву не хватает места, он перераспределяется в большую область, а старые значения копируются в новый массив. Главный вопрос производительности такого массива заключается в том, насколько быстро увеличивается размер массива. Если вы всегда становитесь достаточно большими, чтобы соответствовать текущему толчку, вы каждый раз будете перераспределяться. Поэтому имеет смысл удвоить размер массива или умножить его, скажем, на 1,5x.

Есть ли идеальный фактор роста? 2x? 1.5x? Под идеалом я подразумеваю математически обоснованную, лучшую производительность балансировки и потерянную память. Я понимаю, что теоретически, учитывая, что ваше приложение может иметь какое-либо потенциальное распределение толчков, это зависит от приложения. Но мне любопытно узнать, есть ли значение, которое «обычно» лучше, или считается лучшим в рамках какого-то строгого ограничения.

Я слышал, что где-то есть бумага об этом, но я не смог ее найти.

Answer 1

Я помню, как читал много лет назад, почему 1.5 предпочтительнее, чем два, по крайней мере, применительно к C ++ (это, вероятно, не относится к управляемым языкам, где система времени выполнения может перемещать объекты по своему желанию).

Аргументация такова:

1. Допустим, вы начинаете с 16-байтового распределения.
2. Когда вам нужно больше, вы выделяете 32 байта, а затем освобождаете 16 байтов. Это оставляет 16-байтовое отверстие в памяти.
3. Когда вам нужно больше, вы выделяете 64 байта, освобождая 32 байта. Это оставляет 48-байтовое отверстие (если 16 и 32 были смежными).
4. Когда вам нужно больше, вы выделяете 128 байтов, освобождая 64 байта. Это оставляет 112-байтовое отверстие (при условии, что все предыдущие выделения смежны).
5. И так, и так далее.

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

1. Начать с 16 байтов.
2. Когда вам нужно больше, выделите 24 байта, затем освободите 16, оставив 16-байтовое отверстие.
3. Когда вам нужно больше, выделите 36 байтов, затем освободите 24, оставив 40-байтовое отверстие.
4. Когда вам нужно больше, выделите 54 байта, затем освободите 36, оставив 76-байтовое отверстие.
5. Когда вам нужно больше, выделите 81 байт, затем освободите 54, оставив дыру в 130 байт.
6. Когда вам нужно больше, используйте 122 байта (округление) из 130-байтового отверстия.

Answer 2

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

Нет такой вещи, как "идеальный фактор роста". Это не просто теоретически зависит от приложения, это определенно зависит от приложения.

2 - довольно распространенный фактор роста - я вполне уверен, что это то, что ArrayList и List<T> используют в .NET. ArrayList<T> в Java использует 1.5.

РЕДАКТИРОВАТЬ: Как указывает Эрих, Dictionary<,> в .NET использует «удвоить размер, а затем увеличить до следующего простого числа», чтобы хэш-значения могли быть разумно распределены между сегментами. (Я уверен, что недавно я видел документацию, в которой говорится, что простые числа не так уж хороши для распределения хэш-блоков, но это аргумент для другого ответа.)

Answer 3

В идеале (в пределах n → ∞), это золотое сечение : ϕ = 1.618 ...

На практике вы хотите что-то близкое, например 1,5.

Причина в том, что вы хотите иметь возможность многократно использовать старые блоки памяти, использовать преимущества кэширования и избегать того, чтобы ОС давала вам больше страниц памяти. Уравнение, которое вы решите, чтобы убедиться, что оно уменьшается до x ^{n - 1} - 1 = x ^{n + 1} - x ⁿ , чье решение приближается к x = ϕ для больших n .

Answer 4

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

Так что, просто проверяя очень быстро, Ruby (1.9.1-p129), по-видимому, использует 1,5x при добавлении в массив, а Python (2.6.2) использует 1,125x плюс константу (в Objects/listobject.c):

/* 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, поэтому выражение с битовыми сдвигами и троичным оператором действительно просто вычисляет перераспределение.

Answer 5

Допустим, вы увеличили размер массива на 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 

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

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

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.

Answer 6

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

Я видел 1.5x 2.0x phi x и мощность 2, использовавшуюся ранее.

Answer 7

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

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

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

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

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

Answer 8

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

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

Answer 9

еще два цента

• Большинство компьютеров имеют виртуальную память! В физической памяти вы можете иметь случайные страницы везде, которые отображаются в виде единого непрерывного пространства в виртуальной памяти вашей программы. Устранение косвенности осуществляется аппаратными средствами. Исчерпание виртуальной памяти было проблемой на 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 - это хороший вариант по умолчанию. Кроме того, это зависит от конкретного случая.

Answer 10

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

Во-первых, это умножение на 2: размер << 1. Это умножение на <em>что угодно между 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 секунд до минуты) вполне подойдет.

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