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

← →
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]

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

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

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

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

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

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