Лучше выделить память в питании два?
Когда мы используем malloc() для выделения памяти мы должны дать размер, который у власти из два? Или мы просто даем точный размер, в котором мы нуждаемся?
Как
//char *ptr= malloc( 200 );
char *ptr= malloc( 256 );//instead of 200 we use 256
Если лучше дать размер, который находится в питании два, какова причина этого? Почему это лучше?
Спасибо
Править
Причина моего беспорядка следует за кавычкой от Назад к основам блога Joel
Умные программисты минимизируют потенциал distruption malloc, всегда выделяя блоки памяти, которые являются полномочиями 2 в размере. Вы знаете, 4 байта, 8 байтов, 16 байтов, 18446744073709551616 байтов, и т.д. По причинам, которые должны быть интуитивными любому, кто играет с Lego, это минимизирует объем странной фрагментации, которая продолжается в свободной цепочке. Хотя может казаться, что это тратит впустую пространство, также легко видеть, как это никогда не тратит впустую больше чем 50% пространства. Так Ваше использование программы не больше, чем вдвое больше памяти, поскольку это должно, который не является что большой соглашение.
Извините, я должен был отправить вышеупомянутую кавычку ранее. Мои извинения!
Большинство ответов, до сих пор, говорит, что выделение памяти в питании два является плохой идеей, затем в который сценарий лучше, чтобы неотступно следовать за точкой Joel malloc()? Почему он говорил это? Является устаревшим вышеупомянутое заключенное в кавычки предложение теперь?
Любезно объясните это.
Спасибо
11 ответов
Просто укажите точный размер, который вам нужен. Единственная причина, по которой размер, равный двум целым, может быть "лучше" - это возможность более быстрого выделения и/или избежание фрагментации памяти.
Однако любая нетривиальная реализация malloc, которая заботится о своей эффективности, будет внутренне округлять выделения таким образом, если и когда это уместно. Вам не нужно заботиться о "помощи" malloc; malloc прекрасно справляется сам по себе.
Edit:
В ответ на вашу цитату из статьи Joel on Software, суть Джоэла в этом разделе (которую трудно правильно понять без контекста, следующего за процитированным вами абзацем) в том, что если вы ожидаете часто пере-распределять буфер, то лучше делать это мультипликативно, а не аддитивно. Фактически, именно так поступают классы std::string и std::vector в C++ (среди прочих).
Причина, по которой это улучшение, не в том, что вы помогаете malloc, предоставляя удобные числа, а в том, что выделение памяти - это дорогая операция, и вы пытаетесь минимизировать количество раз, когда вы ее выполняете. Джоэл приводит конкретный пример идеи компромисса между временем и пространством. Он утверждает, что во многих случаях, когда объем необходимой памяти меняется динамически, лучше потратить немного места (выделяя в два раза больше, чем нужно при каждом расширении), чтобы сэкономить время, которое потребуется для многократного добавления ровно n байт памяти каждый раз, когда вам нужно n больше байт.
Множитель не обязательно должен быть равен двум: вы можете выделить в три раза больше места, чем вам нужно, и в итоге получить распределение в три раза больше, или выделить в пятьдесят семь раз больше места, чем вам нужно, и в итоге получить распределение в пятьдесят семь раз больше. Чем больше перераспределение, тем реже вам придется перераспределять, но тем больше памяти вы потратите впустую. Распределение в степени два, которое использует максимум в два раза больше памяти, чем нужно, просто является хорошим компромиссом на начальном этапе, пока вы не будете иметь лучшего представления о том, каковы ваши потребности".
Он вскользь упоминает, что это помогает уменьшить "фрагментацию в свободной цепочке", но причина этого скорее в количестве и равномерности выполняемых выделений, чем в их точном размере. Во-первых, чем больше раз вы выделяете и отделяете память, тем больше вероятность фрагментации кучи, независимо от того, какой размер вы выделяете. Во-вторых, если у вас есть несколько буферов, размер которых вы динамически изменяете, используя один и тот же алгоритм мультипликативного изменения размера, то вполне вероятно, что если один из них изменит размер с 32 до 64, а другой - с 16 до 32, то перераспределение второго может поместиться прямо на месте первого. Этого не произойдет, если один изменит размер с 25 до 60, а другой - с 16 до 26.
И опять же, ничего из того, о чем он говорит, не применимо, если вы собираетесь делать шаг распределения только один раз.
Вы можете захотеть выделить память в терминах размера слова процессора; подойдет не любая старая степень 2.
Если процессор имеет 32-битное слово (4 байта), то выделяйте память в единицах по 4 байта. Выделение в 2 байта может оказаться бесполезным, поскольку процессор предпочитает, чтобы данные начинались на границе 4 байт.
С другой стороны, это может быть микрооптимизацией. Большинство библиотек выделения памяти настроены на возврат памяти, которая выровнена по правильной позиции и оставляет наименьшее количество фрагментации. Если вы выделили 15 байт, библиотека может выровнять и выделить 16 байт. Некоторые распределители памяти имеют различные пулы в зависимости от размера выделяемой памяти.
В общем, выделяйте тот объем памяти, который вам нужен. Пусть библиотека/менеджер выделения памяти обрабатывает фактический объем за вас. Вкладывайте больше энергии в корректность и надежность, чем беспокойтесь об этих тривиальных проблемах.
Чтобы сыграть в адвоката дьявола, вот как 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 символа Unicode, 15000 из которых заняты.
Приведенные выше значения могут показаться немного странно, но вот руководящие принципы:
QString выделяет 4 символа в время, пока не достигнет размера 20. От 20 до 4084, он увеличивается за счет удвоения размер каждый раз. Точнее, это переходит в следующую степень двойки, минус 12. ( Некоторые распределители памяти работать хуже, когда запрашивается точный степени двойки , потому что они используют несколько байт на блок для бухгалтерского учета.) Начиная с 4084 года, он продвигается блоками по 2048 символов (4096 байт). Этот имеет смысл, потому что современные операционные системы не копируют все данные при перераспределении буфера ; в страницы физической памяти просто переупорядочены, и только данные на первая и последняя страницы действительно должны скопировать.
Мне нравится, как они предвидят особенности операционной системы в коде, который предназначен для хорошей работы от смартфонов до серверных ферм. Учитывая, что они умнее меня, я предполагаю, что указанная функция доступна во всех современных ОС.
Когда-то это возможно было правдой, но теперь это точно не лучше.
Просто выделяйте память, которая вам нужна, когда она вам нужна, и освобождайте ее, как только закончите.
Существует слишком много программ, которые расточительно относятся к ресурсам - не делайте свою программу одной из них.
Это в некоторой степени несущественно.
Malloc фактически выделяет немного больше памяти, чем вы запрашиваете, потому что у него есть собственные заголовки, с которыми нужно работать. Следовательно, оптимальное хранилище, вероятно, составляет примерно 4k-12 байт ... но это зависит от реализации.
В любом случае, нет причин для округления до большего объема хранилища, чем необходимо, в качестве метода оптимизации.
Это полностью зависит от данной libc реализации malloc(3). Это зависит от этой реализации, чтобы зарезервировать куски кучи в том порядке, который она считает нужным.
Чтобы ответить на вопрос - нет, это не "лучше" (здесь под "лучше" вы подразумеваете ...?). Если запрашиваемый вами размер слишком мал, malloc(3) зарезервирует больший кусок внутри, так что просто придерживайтесь своего точного размера.
Когда я выделяю буфер, который может нуждаться в дальнейшем увеличении для размещения данных еще неизвестного размера, я начинаю с степени 2 минус 1, и каждый раз, когда она заканчивается пространства, я перераспределяю, увеличивая вдвое предыдущий размер плюс 1. Это позволяет мне не беспокоиться о целочисленных переполнениях; размер может быть переполнен только тогда, когда предыдущий размер был SIZE_MAX, в этот момент распределение уже было бы неудачным, и в любом случае 2 * SIZE_MAX + 1 == SIZE_MAX .
Напротив, если бы я просто использовал степень 2 и каждый раз удваивал ее, я мог бы успешно получить буфер размером 2 ^ 31 байта, а затем перераспределить его в буфер 0 байтов в следующий раз, когда я удвоил размер.
Поскольку некоторые люди отмечали, что степень степени 2-минус-12 хороша для определенных реализаций malloc, можно также начать с степени 2 минус 12, затем удвоить ее и прибавить 12 на каждом шаге ...
С другой стороны, если вы просто выделяете небольшие буферы, которые не должны увеличиваться, запрашивайте именно тот размер, который вам нужен. Не пытайтесь угадать, что хорошего в malloc.
При сегодняшнем объеме памяти и ее скорости я не думаю, что это уже актуально.
Более того, если вы собираетесь часто выделять память, вам лучше подумать о пользовательском объединении памяти / предварительном выделении.
При перераспределении следует использовать realloc () вместо malloc (). http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/
Всегда использовать степень двойки? Это зависит от того, что делает ваша программа. Если вам нужно повторно обработать всю структуру данных, когда она вырастет до степени двойки, да, это имеет смысл. В противном случае просто выделите то, что вам нужно, и не тратите память.
Если вы выделяете какой-то расширяемый буфер, где вам нужно выбрать какое-то число для начального распределения, тогда да, степени двойки - хорошие числа для выбора. Если вам нужно выделить память для struct foo, просто malloc (sizeof (struct foo)). Рекомендация по распределению мощности двойки проистекает из неэффективности внутренней фрагментации, но современные реализации malloc, предназначенные для многопроцессорных систем, начинают использовать локальные пулы ЦП для выделений, достаточно малых, чтобы это имело значение, что предотвращает конфликт блокировок, который раньше результат, когда несколько потоков будут пытаться выполнить malloc в одно и то же время и тратить больше времени на блокировку из-за фрагментации.
Выделяя только то, что вам нужно, вы гарантируете, что структуры данных будут более плотно упакованы в памяти, что увеличивает частоту попаданий в кэш, что оказывает гораздо большее влияние на производительность, чем внутренняя фрагментация. Существуют сценарии с очень старыми реализациями malloc и высокопроизводительными многопроцессорными системами, в которых явное заполнение выделения может обеспечить ускорение, но ваши ресурсы в этом случае лучше потратить на создание лучшей реализации malloc, работающей в этой системе. Предварительное заполнение также делает ваш код менее переносимым и не позволяет пользователю или системе выбирать поведение malloc во время выполнения программно или с помощью переменных среды.
Преждевременная оптимизация - корень всех зол.
Всегда есть тестирование ...
Вы можете попробовать "образец" программы, которая распределяет память в цикле. Таким образом, вы можете увидеть, волшебным образом ли ваш компилятор выделяет память в степени 2. Обладая этой информацией, вы можете попытаться выделить такой же объем общей памяти, используя 2 стратегии: блоки случайного размера и мощность блоков двух размеров.
Я бы ожидал отличий, если они есть, только для больших объемов памяти.