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

← →
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]
> Хосподиисусе.

Переведи.

← →
DiamondShark © (2011-12-12 21:17) [41]

> Rouse_ © (12.12.11 21:13) [40]
> Переведи.

Зачем на ночь страшные истории рассказываешь?

← →
Rouse_ © (2011-12-12 21:19) [42]

> DiamondShark © (12.12.11 21:17) [41]
>
>
> > Rouse_ © (12.12.11 21:13) [40]
> > Переведи.
>
> Зачем на ночь страшные истории рассказываешь?

Пфф, не понял спича.
Статья вроде как о том, почему гранулярность памяти в 64к о которой ты и упомянул...

← →
Pavia © (2011-12-12 21:23) [43]

> Статья вроде как о том, почему гранулярность памяти в 64к
> о которой ты и упомянул...

Я устал в двух словах можно почему они используют фиксированный размер, а не динамический в зависимости от установленного объёма памяти?

← →
DiamondShark © (2011-12-12 21:27) [44]

> Я устал в двух словах можно почему они используют фиксированный размер

Потому что на Альфе идиотская система команд

← →
DiamondShark © (2011-12-12 21:28) [45]

> Rouse_ © (12.12.11 21:19) [42]
> Статья вроде как о том, почему гранулярность памяти в 64к
> о которой ты и упомянул...

Статья о том, как из шкафа вываливаются пыльные скелеты.

По поводу скелетов
Какая разница: я обращаюсь к двум страницам лежащим далеко или к двум страницам, лежащим близко? Я же в любом случае промахиваюсь по кэшу. Нет ?

Кстати проведите ликбез насчёт кэширования и промахов. Какой размер, какая потеря в тактах

Удалено модератором

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

Как на x86 вычисляется эффективный адрес? Например

MOV EAX, 0x00403012 MOV DWORD [EAX], 2 Итак, нам надо: (1) Взять содержимое регистра CR2, который содержит некоторый физический адрес в памяти X. (2) Прочитать элемент со смещением 2 (0x00403012 / 2M) = 2 (3) Посмотреть, присутствует доступна ли указанная страница (или AV) (4) Посмотреть, присутствует присутствует ли указанная страница в памяти (или прерывание, которое должно подтянуть страницу в память (если надо) и инициализировать элемент каталога) (5) Получить физический адрес каталога второго уровня. (6) Взять третий элемент каталога второго уровня (0x00003012 / 4096) = 3 (7) Посмотреть, присутствует доступна ли указанная страница (или AV) (8) Посмотреть, присутствует присутствует ли указанная страница в памяти (или прерывание, которое должно подтянуть страницу в память (если надо) и инициализировать элемент каталога) (9) Получить физический адрес памяти (10) Добавить туда 0x12 (11) Записать туда 2 Слишком много действий, не правда? Поэтому есть TLB-кэш, который просто сохраняет пары первые 20 бит виртуального адреса => физический адрес. Если мы обращаемся к странице, которая вытеснена из кэша, то выполняем все 11 пунктов. Это TLB-промах. Конечно, если мы меняем элемент каталога, то нам необходимо сбросить TLB-кэш (иначе он будет обращаться к старым страницам). Для этого есть привелегированная команда INVLPG. Например, в системе есть разделяемая память, например 5G. Мы ее проецируем на некоторый адрес. Итого нам надо настроить 1310720 элемент каталога страниц (если используется страницы с размером 4096). Обычно эта настройка осуществляется в обработчиках при первом обращении к новой странице, когда вызывается вся цепочка (1)-(11) плюс обработчики прерывания 0x0E (страничная ошибка) на шагах (4) и (8).

> Mystic © (13.12.11 15:36) [49]

понятно, что ничего не понятно

сколько тактов стоит какой промах ?

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

Это уже детали реализации каждого отдельного проца. Да, есть разные предсказания при доступе по адресам, да, заносят иногда значения парами.

В моем конкретном случае, разница была 40% в случае страниц 4k и 2M. Тесты Oracle дают 20% прироста производительности.

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

Чтобы это понять надо попробовать.
К примеру попробуй взять массив 200 мегабайт и подсчитать суму. Сначала линейно, а потом в случайном порядке. И третий способ наихудший, инвертированный порядок бит в индексе.

Для инвертирования можешь воспользоваться кодом.
c:=i; for j:=0 to 7 do // 7 это для байта begin ReverseTabe[i]:= ReverseTabe[i] shl 1+c and 1; c:=c shr 1; end;

Чтобы прочувствовать эффект более лучше попробуй по изменять исходный размер массива.

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

Или вот ещё пример. Блочное транспонирование матриц. Разбиваешь массив на блоки. Эти блоки делишь на еще под блоки. И так далее пока к примеру не станет 10 на 10.
Вот 10х10 транспонируешь обычным способом. А вот блоки уже транспонируешь между собой.
И сравни это с классическим. Исходный размер матрицы возьми так чтобы была 100 мегабайт.

По поводу задержек HDD 1-10 мс SSD 1000-100 мкс
RAM 30-150 нс
L3 50-90 тактов
L2 10-30 тактов
L1 3 - такта
Цифры примерные и зависят от железа. Если промаха нет, то задержка 1 такт.

> Mystic © (13.12.11 18:12) [51]

хотел бы поблагодарить за столь ценные советы )
хочу уточнить. Правильно ли я понял что:
1) и 2, и даже 4 страницы могут без проблем уместиться в кэше первого уровня. и тогда разницы вообще нет
2) запись mov [eax], 1 равна по скорости mov eax, 1 - то есть одному такту

Вот интересно, а попытки "помочь" кешу или менеджеру памяти не мешают ему?

> Вот интересно, а попытки "помочь" кешу или менеджеру памяти
> не мешают ему?

Что вы имеете в виду? Каким способом помочь?

> 1) и 2, и даже 4 страницы могут без проблем уместиться в
> кэше первого уровня. и тогда разницы вообще нет

Зависит от проца, если брать K8, то там в кэше L1 находятся TLB для данных, TLB для кода, кэш инструкций и кэш данных. Кэш данных содержит фрагменты по 64 байта, а не страницы. Вообще, обычно кэш ничего не знает про страничную адресацию памяти, он напрямую связан с физической памятью.

А сколько по тактам мне сказать сложно :)

ясно
может быть позже выложу сюда свою реализацию

По поводу кэша

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

На другой машине тесты аналогичные, но задержки в 2 раза больше.

******** массив в 400 Мбайт
0,320000-Линейное;
3,210000-Cлучайное+линейное;
6,900000-Случайное;
7,160000-Инвертное;
******** массив в 4 Мбайт
0,310000-Линейное;
1,570000-Cлучайное+линейное;
2,610000-Случайное;
3,180000-Инвертное;

******** массив в 40 байт
0,310000-Линейное; 0
0,920000-Cлучайное+линейное; 0
1,830000-Случайное; 0
1,720000-Инвертное; 0

> а почему у тебя время для 400мб, 4мб и 40байт - одинаковое
> ?

Специально выравнено. Чтобы видеть эффект кэша.
Для 400МБ делается 1 цикл для 4мб делается 100 циклов для 40 байт берётся 10000000 циклов и время берётся суммарное для всех циклов.

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

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

6,900000-Случайное 400 М; Почти всегда промахи из за большого размера задержка определяется задержкой по доступу к ОЗУ.
2,610000-Случайное 4М; Промахов меньше, задержка меньше. Видно что КЭШ работает в данном CPU L2=4МБайтам.

1,830000-Случайное; Данные целиком умещаются в кэше первого уровня L1=64 кб. Но вот почему цифра большая еще надо подумать, но всё же она меньше чем для L2.

Измерения косвенные поэтому точную картину не отображают. Но примерно оценить порядки можно.

> я думаю random() жрёт такты

Через него. Ну такты ест, но не много.

Сделал тест без обращения к памяти только циклы и изменения индекса. Но так как процессор выполняет команды параллельно, то будет некоторая погрешность.

0,320000-Линейное;
0,850000-Cлучайное+линейное;
1,620000-Случайное;
1,810000-Инвертное;

Так что уточнять модель измерения я пока не намерен.

кому интересно - вот что получилось
http://zalil.ru/32399300
объект TRecordHeap

А пример с демонстрацией превосходства над обычным менеджером выложите?

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