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

84

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

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

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

Джозеф Гарвин
источник

Ответы:

44

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

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

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

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

Джон Скит
источник
104

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

Причина в следующем:

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

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

  1. Начните с 16 байтов.
  2. Когда вам нужно больше, выделите 24 байта, затем освободите 16, оставив 16-байтовое отверстие.
  3. Когда вам нужно больше, выделите 36 байтов, затем освободите 24, оставив 40-байтовое отверстие.
  4. Когда вам нужно больше, выделите 54 байта, затем освободите 36, оставив 76-байтовую дыру.
  5. Когда вам нужно больше, выделите 81 байт, затем освободите 54, оставив 130-байтовое отверстие.
  6. Когда вам нужно больше, используйте 122 байта (округляя в большую сторону) из 130-байтового отверстия.
Крис Джестер-Янг
источник
5
Случайное сообщение на форуме, которое я нашел ( objectmix.com/c/… ), объясняет то же самое . Плакат утверждает, что (1 + sqrt (5)) / 2 - это верхний предел для повторного использования.
Naaff 08
19
Если это утверждение верно, то phi (== (1 + sqrt (5)) / 2) действительно является оптимальным числом для использования.
Крис Джестер-Янг,
1
Мне нравится этот ответ, потому что он раскрывает разумное значение 1,5х против 2х, но Джона технически наиболее верен в том смысле, в котором я его сформулировал. Мне следовало просто спросить, почему в прошлом рекомендовали 1.5: p
Джозеф Гарвин
6
Facebook использует 1.5 в своей реализации FBVector, статья здесь объясняет, почему 1.5 оптимален для FBVector.
csharpfolk
2
@jackmott Правильно, как отмечалось в моем ответе: «это, вероятно, не относится к управляемым языкам, где система времени выполнения может перемещать объекты по своему желанию».
Крис Джестер-Янг,
48

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

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

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

пользователь541686
источник
15

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

Итак, просто очень быстро проверяя, Ruby (1.9.1-p129), похоже, использует 1,5x при добавлении в массив, а Python (2.6.2) использует 1,125x плюс константа (in 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, поэтому выражение с битовыми сдвигами и тернарным оператором на самом деле просто вычисляет избыточное распределение.

Джейсон Крейтон
источник
Таким образом, он увеличивает массив от n до n + (n / 8 + (n <9? 3: 6)), что означает, что коэффициент роста, в терминологии вопроса, составляет 1,25x (плюс константа).
ShreevatsaR 08
Разве это не было бы 1,125x плюс константа?
Джейсон Крейтон
10

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

CEGRD
источник
Вы, кажется, утверждаете, что уже можете повторно использовать ранее освобожденную память при втором выделении с коэффициентом 1,5. Это не так (см. Выше). Сообщите мне, если я вас неправильно понял.
awx
При 2-м распределении вы выделяете 1,5 * 1,5 * T = 2,25 * T, в то время как общее освобождение, которое вы будете делать до этого, составляет T + 1,5 * T = 2,5 * T. Так что 2,5 больше 2,25.
CEGRD
Ах, я должен прочитать внимательнее; все, что вы говорите, это то, что общая освобожденная память будет больше, чем выделенная память при n-м распределении, а не о том , что вы можете повторно использовать ее при n-м распределении.
awx
4

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

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

Неизвестно
источник
Пхи! Это хорошее число для использования. Я должен начать использовать его с этого момента. Благодаря! +1
Крис Джестер-Янг
Я не понимаю ... почему фи? Какие свойства делают его подходящим для этого?
Джейсон Крейтон
4
@Jason: phi соответствует последовательности Фибоначчи, поэтому следующий размер распределения - это сумма текущего и предыдущего размера. Это обеспечивает умеренную скорость роста, быстрее 1,5, но не 2 (см. Мой пост о том, почему> = 2 не является хорошей идеей, по крайней мере, для неуправляемых языков).
Крис Джестер-Янг,
1
@Jason: Также, по словам комментатора моего сообщения, любое число> phi на самом деле плохая идея. Я сам не делал математических расчетов, чтобы подтвердить это, так что относитесь к этому с недоверием.
Крис Джестер-Янг,
2

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

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

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

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

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

Джонатан Грель
источник
2

Еще два цента

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

Notinlist
источник
3
Лучше бы использовать n + n/2для задержки переполнения. Использование n*3/2сокращает вашу возможную емкость наполовину.
owacoder
@owacoder Верно. Но когда n * 3 не подходит, а n * 1.5 подходит, мы говорим о большом количестве памяти. Если n - 32-битное беззнаковое обозначение, то n * 3 переполняется, когда n равно 4G / 3, то есть примерно 1,333G. Это огромное количество. Это много памяти, которую нужно выделить за один раз. Еще больше, если элементы не 1 байт, а, например, 4 байта каждый. Интересно о
варианте
3
Это правда, что это может быть крайний случай, но крайние случаи обычно кусаются. Привыкнуть искать возможное переполнение или другое поведение, которое может намекать на лучший дизайн, никогда не является плохой идеей, даже если в настоящее время это может показаться надуманным. В качестве примера возьмем 32-битные адреса. Теперь нам нужно 64 ...
owacoder
0

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

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

Том
источник
2
Чтобы уточнить, удвоение размера массива означает, что вы получаете амотизированные вставки O (1). Идея состоит в том, что каждый раз, когда вы вставляете элемент, вы также копируете элемент из старого массива. Допустим, у вас есть массив размером m с m элементами. При добавлении элемента m + 1 места нет, поэтому вы выделяете новый массив размером 2m . Вместо того, чтобы копировать все первые m элементов, вы копируете один каждый раз, когда вставляете новый элемент. Это минимизирует дисперсию (за исключением распределения памяти), и после того, как вы вставите 2 м элементов, вы скопируете все элементы из старого массива.
hvidgaard
-1

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

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

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

Рыбек Аретдар
источник
11
Конечно n + n >> 1же, как 1.5 * n. Достаточно легко придумать аналогичные приемы для каждого практического фактора роста, о котором вы только можете подумать.
Бьорн Линдквист,
Это хороший момент. Обратите внимание, однако, что вне ARM это как минимум удваивает количество инструкций. (Многие инструкции ARM, включая инструкцию добавления, могут выполнять необязательный сдвиг одного из аргументов, позволяя вашему примеру работать в одной инструкции. Однако большинство архитектур не могут этого сделать.) Нет, в большинстве случаев, удвоение числа Количество инструкций от одного до двух не является существенной проблемой, но для более сложных факторов роста, где математика более сложна, это может повлиять на производительность чувствительной программы.
Rybec Arethdar
@Rybec - Хотя могут быть некоторые программы, которые чувствительны к изменениям времени одной или двумя инструкциями, очень маловероятно, что любая программа, использующая динамическое перераспределение, когда-либо будет обеспокоена этим. Если ему нужно точно контролировать время, он, вероятно, будет использовать вместо этого статически выделенное хранилище.
owacoder
Я занимаюсь играми, где одна или две инструкции могут существенно повлиять на производительность в неправильном месте. Тем не менее, если распределение памяти обрабатывается правильно, это не должно происходить достаточно часто, чтобы несколько инструкций имели значение.
Rybec Arethdar