Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Предварительные слушанья по Memory+Cache (Part-2)  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Привет котаны-бротаны.

В продолжение темы бенчмарков
В продолжение темы бедняги полудуха который так и не получил сатисфакции
а также игрушек Базиста.

Тема 2015 года с бенчмарком ЯП и процессоров завершена. Де-факто. Мы получили
то что хотели. Дальше развивать ее нет смысла. Разве что появится новый революционный компиллятор
и мы что-то там соберем чтоб посмотреть.

Но мне не даёт покоя другая часть задачи которая связана с бенчмарком
memory + cache.
Тема в нашем форуме уже нашла отклик и вызвала падение кирпичей
и некоторую долю гнева. В самом деле. Нам сложно придумать под нее кейс.

Понимая и осознавая что тема - скорее нужная. Считаю что нам стоит ее возобновить
не взирая на ее очевидную флеймовость и антинаучность. Если она - антинаучна,
давайте превнесем в нее ровно столько наукообразности чтоб сбить этот стереотип.

Я рассматриваю создание 2-й части темы Пятничных Бенчмарков Memory+Cache
в разрезе структур данных таких как.
- R&B tree
- B-Tree (произвольного порядка)

- Прочие виды деревьев. Тернарные. R-деревья пространственного поиска. M-деревья. Префиксные. HashArray.

Но основное сравнение будет идти между первыми двумя.

FAQ
Q: Почему в качестве структуры данных выбраны именно деревья?
A: Потому что только деревья имеют характерный (когеретный) доступ к памяти на чем
мы можем "сыграть" и провести оптимизацию структур таким образом чтобы access path
проходил по L1/L2/L3. Если-бы мы взяли хеш-таблицы - мы испортили-бы картину
доступа к памяти не только последовательной выборке ключей но даже на последовательном
insert.

Primary Goal
- разработать B-Tree для работы in-memory. Учитывать технологии и архитектуры
- типы данных и ключей - примитивы (int, long64, double, char[8] - короткие строки)
- строки более чем 8 символов - рассмотреть отдельно как невысокий процентиль от всех данных
- разработать экономные способы хранения (указатель/данные как union)


Secondary Goal
- Проверить насколько неэффективно R&B tree по памяти. Есть предположение что оно - расточительно использует
полезную память.
- Рассмотреть реализацию стандартных R&B trees в С++/STL/Boost. Учитывают ли они моё пожелание по эффективности
использования памяти? Какими гранулами аллоцируется память?
- Рассмотреть влияние страничной памяти Windows/Linux на структуры данных.



Некоторые хештеги по технологиям и просто записки чтоб не забыть
- cache line
- 4kb page size
- posix_memalign(..)
- https://stackoverflow.com/questions/48360238/how-can-the-l1-l2-l3-cpu-caches-be-turned-off-on-modern-x86-amd64-chips
- Ulrich Drepper - What Ever Programmer Should Know About Memory

В дальнейшем наше исследуемое дерево будем называть X-Tree.

FAQ
Q: Зачем нам обсуждать модификации R-Tree когда существует быстрый и проверенный R&B?
A: Я ищу оптимальное соотношение память/производительность. Даже условный проигрыш
X-Tree может быть зачтён как положительный результат если мы увидим или докажем
что мы теряем 20% скорости при 60% экономии памяти.
Q: На чем мы сэкономим?
A: Мы увеличим объём данных в узле. Фактически R+Tree (n-того порядка). Разумеется с сохранением
кратности кеш-линиям.

Тестовые сценарии
- создание экземпляра X-Tree
- вставка случайных ключей.
- загрузка серий последовательных ключей.
- полная загрузка (ETL) на максимальнйо пропускной способности
- те-же сценарии с чтением.
- те-же сценарии со смешанным подходом. Добавление + чтение.
- мультипоточность (опционально)

ЯП
С/C++/Assembler
ну можно и другие. Delphi.

На этом всё.

Это - черновой вариант. Прошу ваши комментарии.
17 июл 20, 20:50    [22169510]     Ответить | Цитировать Сообщить модератору
 Re: Предварительные слушанья по Memory+Cache (Part-2)  [new]
Dima T
Member

Откуда:
Сообщений: 14886
ИМХО непонятно что конкретно тестить. Одно и тоже дерево в зависимости от занятого объема может как целиком поместиться в кэш проца, так и быть огромным и постоянно вытесняться из кэша.

Как вариант, вместо деревьев взять любую встраиваемую СУБД, например SQLite. По сути там теже деревья, но уже оптимизированные для постраничного чтения.
21 июл 20, 08:38    [22170813]     Ответить | Цитировать Сообщить модератору
 Re: Предварительные слушанья по Memory+Cache (Part-2)  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Разумеется оно не поместится.
21 июл 20, 09:15    [22170836]     Ответить | Цитировать Сообщить модератору
 Re: Предварительные слушанья по Memory+Cache (Part-2)  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
По поводу SQLite - идея хорошая но учитывая возраст этого продукта мне сложновато будет разбирать его исходный код.

Хотя.... его можно использовать в качестве некого эталона. Из таковых:

- C++/STL/Boost R&B trees
- SQLite
- BerkeleyDb
- LevelDb

И разумеется на одинаковых конфигурациях таблицы. Key + Value одного типа.
21 июл 20, 13:51    [22171025]     Ответить | Цитировать Сообщить модератору
 Re: Предварительные слушанья по Memory+Cache (Part-2)  [new]
MX-9
Member

Откуда: LIBAVA
Сообщений: 470
mayton,

деревья растут в Cache ( IRIS ) Intersystems.

можно протестировать.

===========
23 июл 20, 08:54    [22172099]     Ответить | Цитировать Сообщить модератору
 Re: Предварительные слушанья по Memory+Cache (Part-2)  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Я думаю что это мне не понадобится.
23 июл 20, 08:57    [22172100]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить