Intereting Posts
Определение строки неизвестной длины Как написать собственный код генератора для gcc? Самый большой и маленький из четырех целых чисел (без массивов, никаких функций, наименьших «если») В чем разница между «включенными опциями» и «опциями, переданными» usind gcc -Q -v Спецификатор sprintf% g дает слишком мало цифр после точки Заполните переменное число единиц Зачем использовать (условие) вместо (условие)? какой алгоритм используется для функции pow () в c Как написать приложение, которое использует терминал в качестве графического интерфейса? (в С) решение двух линейных уравнений в программе Как читать строку из файла? Мод с отрицательными номерами дает отрицательный результат в Java и C error: expected ‘=’, ‘,’, ‘;’, ‘asm’ или ‘__attribute__’ перед токеном ‘*’ в C Почему WIFSIGNALED (статус) не может обнаружить сигналы при отслеживании процесса с помощью ptrace? memcpy (), каково должно быть значение параметра размера?

Лучше ли распределять память во власти двух?

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

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

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

Спасибо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы играть адвоката дьявола, вот как это делает 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 байт … но это зависит от реализации.

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

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

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

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

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

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

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

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

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

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

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

Вы можете попробовать программу «sample», которая выделяет память в цикле. Таким образом, вы можете узнать, как ваш компилятор магически распределяет память по степеням 2. С помощью этой информации вы можете попытаться выделить ту же сумму общей памяти, используя 2 страtagsи: блоки случайного размера и мощность блоков размером 2.

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

Если вы выделяете какой-то расширяемый буфер, где вам нужно выбрать некоторое количество для начальных распределений, то да, полномочия 2 – это хорошие числа, которые нужно выбрать. Если вам нужно выделить память для struct foo, тогда просто malloc (sizeof (struct foo)). Рекомендация по распределению мощности 2 объясняется неэффективностью внутренней fragmentации, но современные реализации malloc, предназначенные для многопроцессорных систем, начинают использовать локальные пулы CPU для достаточно малых ресурсов, чтобы это имело значение, что предотвращает конфликт блокировок, который использовался для результат, когда несколько streamов будут пытаться malloc в одно и то же время и тратить больше времени на блокировку из-за fragmentации.

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

Преждевременная оптимизация – это корень всего зла.

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

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