Привет котаны-бротаны.
В продолжение
темы бенчмарков
В продолжение
темы бедняги полудуха который так и не получил сатисфакции
а также игрушек Базиста.
Тема 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.
На этом всё.
Это - черновой вариант. Прошу ваши комментарии.
