Лучше ли выделять память на двоих? - PullRequest
40 голосов
/ 07 июля 2010

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

//char *ptr= malloc( 200 ); 
char *ptr= malloc( 256 );//instead of 200 we use 256

Если лучше дать размер, который находится в степени двух, то для чего это нужно? Почему это лучше?

Спасибо

Редактировать

Причиной моего замешательства является следующая цитата из блога Джоэла Назад к основам

Умные программисты минимизируют потенциальное нарушение malloc всегда выделяя блоки памяти которые имеют степень 2 в размере. Вы знать, 4 байта, 8 байтов, 16 байтов, 18446744073709551616 байт и т. Д. Для причины, которые должны быть интуитивно понятны любой, кто играет с лего, это минимизирует количество странных фрагментация, которая происходит в свободном цепь. Хотя может показаться так впустую пространство, это также легко увидеть как это никогда не тратит впустую больше чем 50% космос. Так что ваша программа не использует более чем в два раза больше памяти, чем необходимо, что не так уж и велико дело.

Извините, я должен был опубликовать приведенную выше цитату ранее. Мои извинения!

Большинство ответов пока говорят, что выделение памяти в степени двух - плохая идея, тогда в каком сценарии лучше следовать точке зрения Джоэла о malloc()? Почему он это сказал? Вышеуказанное предложение устарело сейчас?

Пожалуйста, объясните это.
Спасибо

Ответы [ 11 ]

54 голосов
/ 07 июля 2010

Просто укажите точный размер, который вам нужен. Единственная причина, по которой размер степени двойки может быть «лучше», состоит в том, чтобы обеспечить более быстрое выделение и / или избежать фрагментации памяти.

Однако любая нетривиальная реализация malloc, которая касается эффективности, будет внутренне округлять распределения таким образом, если и когда это будет уместно. Вам не нужно заботиться о «помощи» malloc; malloc может справиться самостоятельно.

Edit:

В ответ на вашу цитату из статьи о Джоэле о программном обеспечении Джоэл указывает в этом разделе (который трудно правильно разглядеть без контекста, который следует за абзацем, который вы цитировали), что если вы ожидаете частого повторного - выделить буфер, лучше делать это мультипликативно, а не аддитивно. Это именно то, что делают классы std::string и std::vector в C ++ (среди прочих).

Причина, по которой это улучшение, не в том, что вы помогаете malloc, предоставляя удобные номера, а в том, что выделение памяти - это дорогая операция, и вы пытаетесь свести к минимуму количество раз ты делаешь это. Джоэл представляет конкретный пример идеи пространственно-временного компромисса. Он утверждает, что во многих случаях, когда объем необходимой памяти изменяется динамически, лучше тратить некоторое пространство (выделяя вдвое больше, чем нужно при каждом расширении), чтобы сэкономить время , которое потребуется многократно использовать ровно n байтов памяти, каждый раз, когда вам нужно n больше байтов.

Множитель не обязательно должен быть равен двум: вы можете выделить до трех раз больше места, чем вам нужно, и в конечном итоге выделите в степени три, или выделите в пятьдесят семь раз больше места, чем вам нужно и в конечном итоге с распределениями в полномочиях пятьдесят семь. Чем больше перераспределения вы делаете, тем реже вам придется перераспределять, но тем больше памяти вы будете тратить. Распределение по степеням двух, при котором используется не более чем вдвое больше памяти, чем необходимо, просто является хорошим отправным пунктом до тех пор, пока у вас нет лучшего представления о ваших потребностях.

Он мимоходом упоминает, что это помогает уменьшить «фрагментацию в свободной цепочке», но причина этого кроется скорее в количестве и однородности выполняемых распределений, а не в их точном размере. Во-первых, чем больше вы выделяете и освобождаете память, тем больше вероятность того, что вы фрагментируете кучу, независимо от того, какой размер вы выделяете. Во-вторых, если у вас есть несколько буферов, которые вы динамически изменяете с использованием одного и того же алгоритма мультипликативного изменения размера, то вполне вероятно, что если один из них изменяет размер с 32 до 64, а другой изменяет размер с 16 до 32, то перераспределение второго может подходить там, где первый раньше был. Этого не произошло бы, если один из них изменил размеры с 25 до 60, а другой с 16 до 26.

И снова, ни одно из того, о чем он говорит, не применимо, если вы собираетесь выполнить шаг распределения только один раз.

18 голосов
/ 07 июля 2010

Просто чтобы сыграть роль адвоката дьявола, вот как Qt делает это:

Давайте предположим, что мы добавляем 15000 символов в строку QString.Затем следующие 18 перераспределений (из возможных 15000) происходят, когда QString не хватает места: 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228,12276, 14324, 16372. В конце концов, в QString выделено 16372 символов Юникода, 15000 из которых заняты.

Приведенные выше значения могут показаться немного странными, но вот руководящие принципы:

QString выделяет 4 символа за раз, пока не достигнет размера 20. От 20 до 4084 он увеличивается, удваивая размер каждый раз.Точнее, он переходит к следующей степени два, минус 12. ( Некоторые распределители памяти работают хуже всего, когда запрашиваются точные степени двух , потому что они используют несколько байт на блок для учета.) От 4084включается блоками по 2048 символов (4096 байт).Это имеет смысл, потому что современные операционные системы не копируют все данные при перераспределении буфера ;страницы физической памяти просто переупорядочиваются, и на самом деле необходимо скопировать только данные на первой и последней страницах.

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

6 голосов
/ 07 июля 2010

Это может когда-то было правдой, но, конечно, не лучше.

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

Существует слишком много программ, которые расточают ресурсы - не делайте свою одну из них.

4 голосов
/ 07 июля 2010

Это несколько не имеет значения.

Malloc фактически выделяет немного больше памяти, чем вы запрашиваете, потому что он имеет свои собственные заголовки для работы. Поэтому оптимальное хранилище, вероятно, что-то вроде 4k-12 байтов ... но это зависит от реализации.

В любом случае, у вас нет причин округлять больше памяти, чем нужно в качестве метода оптимизации.

2 голосов
/ 08 июля 2010

Когда я выделяю буфер, который может нуждаться в дальнейшем увеличении для размещения данных пока неизвестного размера, я начинаю с степени 2 минус 1, и каждый раз, когда ему не хватает места, я перераспределяю дважды предыдущий размер плюс 1. Это позволяет мне никогда не беспокоиться о целочисленных переполнениях; размер может быть переполнен только в том случае, если предыдущий размер был SIZE_MAX, и в этот момент выделение уже было бы неудачным, и в любом случае 2*SIZE_MAX+1 == SIZE_MAX.

Напротив, если бы я просто использовал степень 2 и удваивал ее каждый раз, я мог бы успешно получить буфер размером 2 ^ 31 байт, а затем перераспределить его в буфер размером 0 байт в следующий раз, когда я удвоил размер.

Поскольку некоторые люди отмечают, что power-of-2-minus-12 подходит для некоторых реализаций malloc, можно также начать с степени 2 минус 12, затем удвоить ее и добавить 12 на каждом шаге ...

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

2 голосов
/ 07 июля 2010

Вы можете хотите выделить память в терминах размера слова процессора; не любая старая сила 2 сделает.

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

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

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

1 голос
/ 07 июля 2010

Всегда есть тестирование ...

Вы можете попробовать "примерную" программу, которая выделяет память в цикле.Таким образом, вы можете увидеть, магически ли ваш компилятор выделяет память в степени 2. Имея эту информацию, вы можете попытаться выделить тот же объем общей памяти, используя 2 стратегии: блоки произвольного размера и мощность блоков 2 размера.1004 * Я бы ожидал различия, если таковые имеются, только для больших объемов памяти.

1 голос
/ 07 июля 2010

С сегодняшним объемом памяти и ее скоростью я не думаю, что это больше актуально.

Кроме того, если вы собираетесь выделять память часто, лучше подумайте о пуле / предварительном выделении памяти.

1 голос
/ 07 июля 2010

Это полностью зависит от данной libc реализации malloc(3). Именно эта реализация зарезервировала куски кучи в любом порядке, который сочтет нужным.

Чтобы ответить на вопрос - нет, это не «лучше» (здесь под «лучше» вы имеете в виду ...?). Если запрашиваемый вами размер слишком мал, malloc(3) зарезервирует больший кусок внутри, поэтому просто придерживайтесь точного размера.

0 голосов
/ 07 июля 2010

Вы должны использовать realloc () вместо malloc () при перераспределении.http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/

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

...