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

https://stackoverflow.com/questions/1100311

11-09-2019
|

Вопрос

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

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

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

Решение

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

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

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

Редактировать:Как указывает Эрих, Dictionary<,> в .NET используется "удвоить размер, затем увеличить до следующего простого числа", чтобы хэш-значения могли быть разумно распределены между сегментами.(Я уверен, что недавно видел документацию, предполагающую, что простые числа на самом деле не так уж хороши для распространения хэш-блоков, но это аргумент в пользу другого ответа.)

Другие советы

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

Рассуждения таковы:

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

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

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

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

На практике вам нужно что-то близкое, например 1.5.

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

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

Итак, просто проверяю очень быстро, 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, таким образом, выражение с битовыми сдвигами и троичным оператором на самом деле просто вычисляет избыточное распределение.

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

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

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

Мы можем удалить буквы "Т" с обеих сторон.Итак, мы получаем это:

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), которые на самом деле улавливают ошибки нехватки памяти и в этом случае растут меньше.Кажется, что если бы у вас был огромный единый массив, вы бы захотели это сделать.

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

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

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

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

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

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

Еще два цента

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow