Знатокам менеджера памяти. Оптимальный размер блока ?

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

> Можно более умный алгоритм увеличения придумать

А зачем вообще увеличивать? Количество вызовов VirtualAlloc -- совсем не узкое место.

> Смотря на какой машинке.

А дельфи бывает какой-то ещё, кроме Вин32?

> Максимум моя прога выделяет в пике 10 Gb хипа, и это нормально :)

Вот скажи честно: у тебя количество вызовов VirtualAlloc -- настолько узкое место, что его надо оптимизировать даже ценой перерасхода памяти?

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

Мне вот тоже интересно
Есть разница: выделить 4 раза по одной странице или 1 раз 4 страницы ?
мне кажется разницы быть не должно

> DiamondShark © (12.12.11 18:11) [29]

> Количество вызовов VirtualAlloc -- совсем не узкое место.

Да я вообще не про VirtualAlloc изначально говорил, а про всякие там ReallocMem и GetMem. Т.е работу через менеджер памяти. Если использовать VirtualAlloc и выделять каждый раз по странице, то разница конечно несущественна.

> Есть разница: выделить 4 раза по одной странице или 1 раз
> 4 страницы ?
> мне кажется разницы быть не должно

смотря какой алгоритм, если логика построена, что нужно постоянно выделять и освобождать память, то лучше выделить один раз столько сколько нужно и потом плясать в выделенном диапазоне.
Ну т.е. вместо
Alloc + Alloc + Release + Alloc + Release + Release сделать Alloc3 /отработать/ Release3

> Мне вот тоже интересно Есть разница: выделить 4 раза по
> одной странице или 1 раз 4 страницы ?мне кажется разницы
> быть не должно

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

Разница есть. Но вот значительная она или нет зависит от задачи.

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

> А зачем вообще увеличивать? Количество вызовов VirtualAlloc
> -- совсем не узкое место.

Кто знает? У меня был случай, когда просто сегментация по 4096 была узким местом. При увеличении размера страниц до 2Mb, производительность увеличилась на 40% :)

> У меня был случай, когда просто сегментация по 4096 была
> узким местом.

На какой системе?
На Win32 нет смысла выделять по 4096, потому что гранулярность 64К. Вы просто мусорили память и промахивались в кэш.

> На Win32 нет смысла выделять по 4096, потому что гранулярность 64К.

Зы, до кучи к выше сказанному: http://blogs.msdn.com/b/oldnewthing/archive/2003/10/08/55239.aspx

> На какой системе?
> На 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>

Знатокам менеджера памяти. Оптимальный размер блока ? Найти похожие ветки