Вопрос по arraylist, dynamic-arrays, vector, arrays, math – Какова идеальная скорость роста для динамически размещаемого массива?

72

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

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

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

Ваш Ответ

10   ответов
0

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

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

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

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

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

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

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

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

Это хороший момент. Однако обратите внимание, что за пределами ARM это по крайней мере удваивает количество инструкций. (Многие инструкции ARM, включая инструкцию add, могут сделать необязательный сдвиг для одного из аргументов, позволяя вашему примеру работать в одной инструкции. Однако большинство архитектур не могут этого сделать.) Нет, в большинстве случаев удвоение числа инструкции от одного до двух не являются существенной проблемой, но для более сложных факторов роста, где математика более сложна, это может повлиять на производительность чувствительной программы.
Конечноn + n >> 1 такой же как1.5 * n, Довольно просто придумать подобные трюки для каждого практического фактора роста, о котором вы только можете подумать.
7

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

Например, если мы хотим сделать это на третьем этапе (т.е.n=3), то имеем

x^3 <= 1 + x 

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

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

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

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

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

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

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

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

39

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

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

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

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

37

n & # X2192; & # X221E;),это & APOS; sthe golden ratio: & # x3D5; = 1,618 ...

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

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

+1, надеюсь, вы не против удалить слишком жирный шрифт.
1

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

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

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

ользования, чтобы найти оптимальное число.

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

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

Most computers have virtual memory! In the physical memory you can have random pages everywhere which are displayed as a single contiguous space in your program's virtual memory. The resolving of the indirection is done by the hardware. Virtual memory exhaustion was a problem on 32 bit systems, but it is really not a problem anymore. So filling the hole is not a concern anymore (except special environments). Since Windows 7 even Microsoft supports 64 bit without extra effort. @ 2011 O(1) is reached with any r > 1 factor. Same mathematical proof works not only for 2 as parameter. r = 1.5 can be calculated with old*3/2 so there is no need for floating point operations. (I say /2 because compilers will replace it with bit shifting in the generated assembly code if they see fit.) MSVC went for r = 1.5, so there is at least one major compiler that does not use 2 as ratio.

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

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

11

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

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

Неужели это будет 1,125х плюс константа?
Таким образом, он увеличивает массив с n до n + (n / 8 + (n & lt; 9-3: 6)), что означает, что фактор роста в терминологии вопроса равен 1,25x (плюс константа).
Это верно, 1/8 = 0,125. Виноват.
88

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

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

Say you start with a 16-byte allocation. When you need more, you allocate 32 bytes, then free up 16 bytes. This leaves a 16-byte hole in memory. When you need more, you allocate 64 bytes, freeing up the 32 bytes. This leaves a 48-byte hole (if the 16 and 32 were adjacent). When you need more, you allocate 128 bytes, freeing up the 64 bytes. This leaves a 112-byte hole (assuming all previous allocations are adjacent). And so and and so forth.

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

Start with 16 bytes. When you need more, allocate 24 bytes, then free up the 16, leaving a 16-byte hole. When you need more, allocate 36 bytes, then free up the 24, leaving a 40-byte hole. When you need more, allocate 54 bytes, then free up the 36, leaving a 76-byte hole. When you need more, allocate 81 bytes, then free up the 54, leaving a 130-byte hole. When you need more, use 122 bytes (rounding up) from the 130-byte hole.
Мне нравится этот ответ, потому что он показывает обоснование 1,5х по сравнению с 2х, но технически наиболее справедливо то, как я это сформулировал, у Джона. Я должен был просто спросить, почему 1,5 рекомендовалось в прошлом: p Joseph Garvin
Facebook использует 1,5 в своей реализации FBVector,article here объясняет, почему 1.5 является оптимальным для FBVector.
Случайный пост на форуме, который я нашел (objectmix.com/c/…Причины аналогично. Плакат утверждает, что (1 + sqrt (5)) / 2 является верхним пределом для повторного использования.
@jackmott Правильно, именно так, как отметил мой ответ: «Это, вероятно, не относится к управляемым языкам, где система времени выполнения может перемещать объекты по своему усмотрению».
Если это утверждение верно, то phi (== (1 + sqrt (5)) / 2) действительно является оптимальным числом для использования.

Похожие вопросы