Форум: "Прочее";
Текущий архив: 2012.05.06;
Скачать: [xml.tar.bz2];
ВнизЗнатокам менеджера памяти. Оптимальный размер блока ? Найти похожие ветки
← →
DevilDevil © (2011-12-12 12:24) [0]Для ресурсоёмкой задачи необходимо реализовать максимально быстрый менеджер памяти. Необходимо выделять множество блоков небольшого (константного) размера. 24 байт например. Было решено организовать через односвязный список в рамках большого блока. Вот собственно вопрос. Какой размер большого блока оптимален? 2048, 4096 ?
+ нужно учитывать размер служебной информации
хотелось бы обойтись стандартными средствами менеджера памяти, не прибегая к API той или иной операционной системы. Большие блоки не изменяются в размерах
учитывать хотелось бы как FASTMM, так и менеджер памяти старых версий
← →
Anatoly Podgoretsky © (2011-12-12 12:29) [1]> DevilDevil (12.12.2011 12:24:00) [0]
Измерить.
← →
DevilDevil © (2011-12-12 12:35) [2]> Anatoly Podgoretsky © (12.12.11 12:29) [1]
Здравствуйте, Анатолий
Мы аллоцируем большой блок в стандартном менеджере памяти
Он должен быть:
- относительно большой
- не изменяемый в размерах
- максимально комфортный для менеджера памяти
вот я и спрашиваю, какой это размер
предполагаю нужно уложиться в одну страницу. Но что по этому поводу думает FastMM (и предыдущая версия).
← →
Pavia © (2011-12-12 12:42) [3]Так как размер константа. Проще всего сделать так завести два массива
В первом массиве хранить свои элементы во втором индексы пустых элементов.
Второй массив циклический.
Длину массивов выбрать кратных 2^n. Под задачу оцени к примеру 128*1024.
Если надо выделить памяти больше чем 2^n то просто увеличиваем массив в два раза. Это вызовет копирование. Но таких случаев у тебя будет немного всего не сколько раз.
Так как требования вы особо не указали, то надеюсь совет к месту.
Что надо быстро выделять и освобождать накладные на память не жалеть.
Или к примеру быстрое освобождение, а вот выделение можно и по медленнее.
Вариантов ещё много могу посоветовать.
С учётом современных требований и размером доступной памяти. Размер большого блока оптимален примерно 4МБайта. 4КБ размер маленький, таких блоков будет много надо будет городить многоуровневую структуру. Поэтому 4МБ наиболее оптимально.
← →
DevilDevil © (2011-12-12 12:47) [4]> Pavia © (12.12.11 12:42) [3]
Реализовать хочу по другому. Мой менеджер - это "массив" больших блоков. Большие блоки могут удаляться или создаваться новые. Делается это как раз для избежания копирования. Остаётся вопрос - каков размер максимально удобный для стандартного менеджера памяти, чтобы выделять большой блок. Страница? Если да, то нужно учесть служебную информацию. В общем - этот вопрос как раз для знатоков FastMM и менеджера памяти предыдущей версии, как описано в заголовке.
← →
Pavia © (2011-12-12 12:57) [5]
> Делается это как раз для избежания копирования.
Так как у вас размер элементов константа, то ни о каком копирование речи быть не может. Его тут попросту нет. Если бы у вас были строки или динамические массивы.
> Остаётся вопрос - каков размер максимально удобный для стандартного
> менеджера памяти, чтобы выделять большой блок. Страница?
Для Delphi 7 размер не влияет не посредственно. А вот число освобождение выделений надо бы свести к минимуму. Поэтому чем больше тем лучше.
По поводу FASTMM ему лучше выделять 4КБ-4байта либо опять таки как можно большой кусок.
← →
DevilDevil © (2011-12-12 13:01) [6]> Pavia © (12.12.11 12:57) [5]
> По поводу FASTMM ему лучше выделять 4КБ-4байта либо опять
> таки как можно большой кусок.
Я думаю в FastMM служебная информация больше 4 байт
← →
Pavia © (2011-12-12 13:03) [7]
> Я думаю в FastMM служебная информация больше 4 байт
А ты не думай, а возьми и посмотри.
При выделении хранится только размер выделенной области. Всё другая служебную информацию не используется непосредственно.
А да в размере еще есть пару служебных флагов.
← →
Rouse_ © (2011-12-12 13:09) [8]Меньше страницы все равно не выделишь, поэтому смотри текущий размер страницы и делай кратный оному.
← →
DiamondShark © (2011-12-12 13:12) [9]
> Для ресурсоёмкой задачи необходимо реализовать максимально
> быстрый менеджер памяти.
У вас менеджер памяти -- самое узкое место по быстродействию?
Вы крутые алгоритмисты тогда.
> Было решено организовать через односвязный список в рамках большого блока
Подумайте над проблемой локальности данных.
Хорошо, если часто используемые объекты располагаются в смежных областях памяти. Будет хорошее попадание в кэш.
Хорошо, если объекты не будут пересекать границы страниц, и часто используемые объекты будут находиться на одной странице или на смежных страницах.
Хорошо, если большие пулы объектов кратны гранулярности ОС.
> Вот собственно вопрос. Какой размер большого блока оптимален?
По-барабану абсолютно.
Оптимизируйте по-настоящему узкие места, а не ловите блох.
Если вы выжираете действительно МНОГО памяти, то позаботьтесь лучше о том, чтобы "трогать" как можно меньше страниц и как можно ближе друг к другу.
Промахи кэша и свопинг сожрут всю вашу крохоборскую "оптимизацию".
> не прибегая к API той или иной операционной системы.
Если вам нужно нахапать неизменяемых пулов объектов, то как раз лучше всего взять нужные блоки через VirtualAlloc и не пытаться вытелепатировать внутренние кишки менеджеров.
← →
Mystic © (2011-12-12 14:27) [10]Мне чего-то непонятно. Если блоки памяти константного размера, то можно просто все свободные блоки держать в виде списка. Как-то так:
type
PFreeBlock = ^TFreeBlock;
TFreeBlock = record
Next: PFreeBlock;
end;
var FreeBlocks: PFreeBlock;
function SuperAlloc(): Pointer;
begin
if FreeBlocks = nil then
begin
FreeBlocks := VirtualAlloc(...);
InitBlocks(FreeBlocks);
end;
Result := FreeBlocks;
FreeBlocks := FreeBlocks.Next;
end;
procedure SuperFree(P: Pointer);
var
Tmp: PFreeBlock;
begin
Tmp := P;
Tmp.Next := FreeBlocks;
FreeBlocks := P;
end;
Ну а параметры VirtualAlloc уже в зависимости от условий задачи. В целом проблема только одна может быть: фрагментация. Вся память, которая выделяется в случае пиковой нагрузки, будет занята до конца работы алгоритма.
Есть ты боишься частых вызовов VirtualAlloc, то (1) зарезервируй вначале большой регион памяти (2) Потом вызывай MEM_COMMIT (3) размер памяти в случае нового вызова MEM_COMMIT просто увеличивай в два раза. Первый блок 4096, второй 8192, потом 16384, 65536. Получишь ln(MaxSize) / ln(2) аллокаций.
← →
Mystic © (2011-12-12 14:29) [11]В принципе VirtualAlloc вполне можно заменить на простой GetMem.
← →
DevilDevil © (2011-12-12 14:34) [12]> Есть ты боишься частых вызовов VirtualAlloc, то (1) зарезервируй
> вначале большой регион памяти (2) Потом вызывай MEM_COMMIT
что это за механизм ?
потом я хочу обойтись стандартными средствами Delphi. То есть каждый блок - GetMem. Но опять таки размер. 4096 - 4 ?
← →
Mystic © (2011-12-12 14:36) [13]Первый блок 4096, потом увеличивай в два раза.
Вообще, какое примерно количество памяти нужно?
← →
Rouse_ © (2011-12-12 14:57) [14]Он хочет собственный менеджер, стало быть только VirtualAlloc.
← →
Pavia © (2011-12-12 14:59) [15]
> Он хочет собственный менеджер, стало быть только VirtualAlloc.
Он сам не знает чего хочет.
← →
DevilDevil © (2011-12-12 15:00) [16]> Первый блок 4096, потом увеличивай в два раза.
зачем в 2 раза ?
ОС не пофиг сколько страниц отдавать: 1 или 2 ?
это как-то повлияет на производительность ?
← →
DevilDevil © (2011-12-12 15:11) [17]> Он хочет собственный менеджер, стало быть только VirtualAlloc.
VirtualAlloc - платформозависимая функция
← →
Rouse_ © (2011-12-12 15:20) [18]
> VirtualAlloc - платформозависимая функция
Ну директивы компилера то не отменили {$IFDEF POSIX}__malloc()
← →
Mystic © (2011-12-12 15:33) [19]
> зачем в 2 раза ?
> ОС не пофиг сколько страниц отдавать: 1 или 2 ?
> это как-то повлияет на производительность ?
Это уменьшит количество обращений к GetMem (логарифмическая зависимость от размера) при том, что как минимум треть выделенной памяти будет использоваться.
← →
DVM © (2011-12-12 15:35) [20]
> DevilDevil © (12.12.11 15:00) [16]
> > Первый блок 4096, потом увеличивай в два раза.
>
> зачем в 2 раза ?
> ОС не пофиг сколько страниц отдавать: 1 или 2 ?
> это как-то повлияет на производительность ?
Затем чтобы потом в следующие разы не перевыделять память. Повлияет, причем может быть очень сильно.
← →
DevilDevil © (2011-12-12 15:47) [21]Посмотрел сейчас "сорсы" менеджеров памяти
если я правильно понял - не получится уместить эти 4кб-сл.часть в одной странице
потому что если я правильно понял, менеджер выделяет сразу несколько страниц и укладывает мой блок на границе
что делать ?
> Затем чтобы потом в следующие разы не перевыделять память.
> Повлияет, причем может быть очень сильно.
я не делаю realloc памяти. какая разница ?
← →
DVM © (2011-12-12 16:01) [22]
> DevilDevil © (12.12.11 15:47) [21]
> я не делаю realloc памяти. какая разница ?
Погоди, если я правильно понял, ты сам выделяешь большой блок, потом работаешь внутри него? Так? Если место внутри большого блока заканчивается, то что ты делаешь? Выделяешь еще один блок или меняешь размер первого? И то и другое весьма затратная операция, поэтому ее надо избегать по возможности, поэтому если уж выделяешь, то выделяй с запасом, чтобы в следующий раз еще одно такое выделение (а может и не одно) пропустить. Т.е с запасом x2 или x4.
← →
DevilDevil © (2011-12-12 16:24) [23]> DVM © (12.12.11 16:01) [22]
вот я и исхожу из позиции, что выделить страницу памяти например
не должно быть сложно
когда блок заканчивается - выделяешь новый блок
← →
DiamondShark © (2011-12-12 16:32) [24]
> DevilDevil © (12.12.11 15:11) [17]
> VirtualAlloc - платформозависимая функция
А дельфи -- весь такой прям платформонезависимый.
← →
DevilDevil © (2011-12-12 16:50) [25]> А дельфи -- весь такой прям платформонезависимый.
Windows, Mac OS, iOS, (Linux)
← →
DiamondShark © (2011-12-12 16:56) [26]Знахарей-то, знахарей набежало.
> Есть ты боишься частых вызовов VirtualAlloc, то (1) зарезервируй
> вначале большой регион памяти (2) Потом вызывай MEM_COMMIT
> (3) размер памяти в случае нового вызова MEM_COMMIT просто
> увеличивай в два раза. Первый блок 4096, второй 8192, потом
> 16384, 65536.
А последний раз -- 1Гиб. Который с вероятностью 99.666% обломится.
Предпоследний, впрочем, тоже.
Мы выделим, если сильно повезёт, где-то половину теоретически возможной памяти. Зато сэкономим 1мс на вызовах VirtualAlloc.
Спали деревню! Сэкономь на спичках!
> поэтому ее надо избегать по возможности,
Гранулярность выделения памяти в виндус -- 64киб, меньшими блоками выделять нет смысла.
Чтобы сожрать 2Гиб пользовательского пространства блоками по 64киб, надо 32768 вызовов.
При экспоненциальном выделении мы сделаем 15 вызовов.
Вопрос: сколько миллисекунд мы сэкономим ценой отправки в мусор половины памяти?
← →
Mystic © (2011-12-12 17:18) [27]
> А последний раз -- 1Гиб. Который с вероятностью 99.666%
> обломится.
> Предпоследний, впрочем, тоже.
Смотря на какой машинке. Если речь идет конкретно про винду, да еще 32-х разрядную, то этот 1 гиг можно зарезервировать. Но это зависимость от платформы. Ну а так это при условии, что уже выделено полгига не хватило.
Опять же, вместо коэффициента 2 можно использовать 1.5 или 1.25 в зависимости от сценария. Все настраивается.
Максимум моя прога выделяет в пике 10 Gb хипа, и это нормально :)
← →
DVM © (2011-12-12 17:33) [28]
> DiamondShark © (12.12.11 16:56) [26]
> При экспоненциальном выделении мы сделаем 15 вызовов.
Ну, во-первых, ему и не понадобится 15 вызовов. Это раз. А если понадобится, то ему не поможет ни этот способ, ни какой другой.
Во-вторых, необязательно умножать каждый раз на 2. Можно более умный алгоритм увеличения придумать, в зависимости от предыдущих статистических данных.
← →
DiamondShark © (2011-12-12 18:11) [29]
> Можно более умный алгоритм увеличения придумать
А зачем вообще увеличивать? Количество вызовов VirtualAlloc -- совсем не узкое место.
> Смотря на какой машинке.
А дельфи бывает какой-то ещё, кроме Вин32?
> Максимум моя прога выделяет в пике 10 Gb хипа, и это нормально :)
Вот скажи честно: у тебя количество вызовов VirtualAlloc -- настолько узкое место, что его надо оптимизировать даже ценой перерасхода памяти?
← →
DevilDevil © (2011-12-12 18:22) [30]> Во-вторых, необязательно умножать каждый раз на 2. Можно
> более умный алгоритм увеличения придумать, в зависимости
> от предыдущих статистических данных.
Мне вот тоже интересно
Есть разница: выделить 4 раза по одной странице или 1 раз 4 страницы ?
мне кажется разницы быть не должно
← →
DVM © (2011-12-12 18:29) [31]
> DiamondShark © (12.12.11 18:11) [29]
> Количество вызовов VirtualAlloc -- совсем не узкое место.
Да я вообще не про VirtualAlloc изначально говорил, а про всякие там ReallocMem и GetMem. Т.е работу через менеджер памяти. Если использовать VirtualAlloc и выделять каждый раз по странице, то разница конечно несущественна.
← →
Rouse_ © (2011-12-12 19:12) [32]
> Есть разница: выделить 4 раза по одной странице или 1 раз
> 4 страницы ?
> мне кажется разницы быть не должно
смотря какой алгоритм, если логика построена, что нужно постоянно выделять и освобождать память, то лучше выделить один раз столько сколько нужно и потом плясать в выделенном диапазоне.
Ну т.е. вместо
Alloc + Alloc + Release + Alloc + Release + Release сделать Alloc3 /отработать/ Release3
← →
Pavia © (2011-12-12 19:13) [33]
> Мне вот тоже интересно Есть разница: выделить 4 раза по
> одной странице или 1 раз 4 страницы ?мне кажется разницы
> быть не должно
Вот приехали. Если ты этого не знаешь. То говорить о том что тебе нужен более шустрый менеджер памяти бессмысленно. Так как где узкое место ты не определил.
Разница есть. Но вот значительная она или нет зависит от задачи.
← →
Rouse_ © (2011-12-12 19:18) [34]Вообще задача менеджера память не в быстром выделении/освобождении памяти, а в быстром определении области необходимого размера на уже выделенном участке (и выделении нового участка, если свободных не осталось)
← →
Mystic © (2011-12-12 20:20) [35]
> А зачем вообще увеличивать? Количество вызовов VirtualAlloc
> -- совсем не узкое место.
Кто знает? У меня был случай, когда просто сегментация по 4096 была узким местом. При увеличении размера страниц до 2Mb, производительность увеличилась на 40% :)
← →
DiamondShark © (2011-12-12 20:43) [36]
> У меня был случай, когда просто сегментация по 4096 была
> узким местом.
На какой системе?
На Win32 нет смысла выделять по 4096, потому что гранулярность 64К. Вы просто мусорили память и промахивались в кэш.
← →
Rouse_ © (2011-12-12 20:49) [37]
> На Win32 нет смысла выделять по 4096, потому что гранулярность 64К.
Зы, до кучи к выше сказанному: http://blogs.msdn.com/b/oldnewthing/archive/2003/10/08/55239.aspx
← →
Mystic © (2011-12-12 21:12) [38]
> На какой системе?
> На Win32 нет смысла выделять по 4096, потому что гранулярность
> 64К. Вы просто мусорили память и промахивались в кэш.
OS тут не причем, это возможности железа (проца). У семейства x86 на каталог страниц указывает CR2, далее каждый элемент указывает на блоки по 2Mb, далее на блоки по 4096. Ну и на втором уровне есть флажок, указывающий, что элемент каталога является физическим адресом, в не указателем на подкаталог третьего уровня. А вот у SPARK-ов вообще достаточно широкий выбор размеров страниц.
В винде особо управлять нечем, а в Solaris у sunstudio есть специальный флажок при работе с разделяемой памятью, плюс флаг компилятора (-xpagesize=2M), какой размер страниц используется. Соответственно, в случае страниц по 4096, обработка промаха занимала куда соизмеримое количество времени с обработкой данных.
На последних AMD есть гигабайтные страницы, в планах потестировать и этот размер :)
x86
<pre>
$ pagesize -a
4096
2097152
1073741824
</pre>
SPARK
<pre>$ pagesize -a
8192
65536
524288
4194304
</pre>
← →
DiamondShark © (2011-12-12 21:12) [39]
> Rouse_ © (12.12.11 20:49) [37]
Хосподиисусе.
← →
Rouse_ © (2011-12-12 21:13) [40]
> DiamondShark © (12.12.11 21:12) [39]
> Хосподиисусе.
Переведи.
Страницы: 1 2 вся ветка
Форум: "Прочее";
Текущий архив: 2012.05.06;
Скачать: [xml.tar.bz2];
Память: 0.58 MB
Время: 0.005 c