Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2012.05.06;
Скачать: CL | DM;

Вниз

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

 
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к
> о которой ты и упомянул...

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


 
Rouse_ ©   (2011-12-12 21:33) [46]


> DiamondShark ©   (12.12.11 21:28) [45]
> Статья о том, как из шкафа вываливаются пыльные скелеты.

Дык ктож спорит то?


 
DevilDevil ©   (2011-12-12 23:53) [47]

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

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


 
DevilDevil ©   (2011-12-13 14:23) [48]

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


 
Mystic ©   (2011-12-13 15:36) [49]

Промахи разные бывают, в данном случае я говорил про 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).


 
DevilDevil ©   (2011-12-13 15:47) [50]

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

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

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

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


 
Mystic ©   (2011-12-13 18:12) [51]

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

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


 
Pavia ©   (2011-12-13 19:29) [52]

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

Чтобы это понять надо попробовать.
К примеру попробуй взять массив 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 такт.


 
DevilDevil ©   (2011-12-13 19:52) [53]

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

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


 
Дмитрий С ©   (2011-12-13 20:49) [54]

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


 
Pavia ©   (2011-12-13 21:21) [55]


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

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


 
Mystic ©   (2011-12-14 15:28) [56]


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


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

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


 
DevilDevil ©   (2011-12-14 16:34) [57]

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


 
Pavia ©   (2011-12-15 06:32) [58]

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

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

На другой машине тесты аналогичные, но задержки в 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


 
DevilDevil ©   (2011-12-15 10:03) [59]

> Pavia ©   (15.12.11 06:32) [58]
а почему у тебя время для 400мб, 4мб  и 40байт - одинаковое ?


 
Pavia ©   (2011-12-15 11:08) [60]


> а почему у тебя время для 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.

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


 
DevilDevil ©   (2011-12-15 11:14) [61]

> Pavia ©   (15.12.11 11:08) [60]
а как ты случайность организуешь ?
я думаю random() жрёт такты


 
Pavia ©   (2011-12-15 21:01) [62]


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

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

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

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

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


 
DevilDevil ©   (2011-12-29 06:13) [63]

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


 
Pavia ©   (2011-12-29 13:17) [64]

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


 
DevilDevil ©   (2011-12-29 18:17) [65]

> Pavia ©   (29.12.11 13:17) [64]

http://zalil.ru/32402579
Delphi6
приятно удивлён кстати стандартным аллокатором !!!



Страницы: 1 2 вся ветка

Текущий архив: 2012.05.06;
Скачать: CL | DM;

Наверх




Память: 0.68 MB
Время: 0.006 c
2-1325855150
Anthony
2012-01-06 17:05
2012.05.06
Иконка для приложения


2-1325799180
Gu
2012-01-06 01:33
2012.05.06
опции компилятора


2-1326069317
Gu
2012-01-09 04:35
2012.05.06
x64 str


15-1325361710
Anatoly Podgoretsky
2012-01-01 00:01
2012.05.06
С Новым Годом


2-1325802985
Дмитрий
2012-01-06 02:36
2012.05.06
Scheduler