[C] тест на эффективность кэшей

Блочный обмен данными с памятью?

При размерах блока, равных обьемам L1/L2/L3 кешей, будут провалы.

Ммм, ты имешь в виду memmove/memcpy кусками? А можешь привести пример на псевдокоде?

Вот к чему это? Если интересует оптимизация, потрать время на улучшение алгоритма/структур данных и получишь гарантированное улучшение производительности вместо зависимости от размера L2, который варьируется от процессора к процессору.

Или вообще есть готовые тесты этого?

cachegrind?

или Вас больше интересует туториал по написанию cache-effective программ?

Напиши блочное умножение матриц и поиграйся с размером блока.

вспомнил, натыкался какое то время назад на измышления одного кренделя, вот, может поможет

http://ccfit.nsu.ru/~kireev/ 5 и 6 работы. Могу исходники поискать.

cachegrind?

не, это инструмент, а мне нужны программы и алгоритмы где видно разницу в скорости в зависимости от, например, размера входных данных или объёма кешей.

или Вас больше интересует туториал по написанию cache-effective программ?

Не, спасибо. Я на эту тему читал(частично) Ульриха Дрипера «What every programmer should know about memory» и разные доки от интеля и амд. Теперь хочу увидеть своими глазами. Причём, желательно, на примере простой программы.

Могу исходники поискать.

Если не сложно то поищи пожалуйста. Чтобы мне не вбивать.

Напиши блочное умножение матриц и поиграйся с размером блока.

спасибо, так и сделаю.

вот, может поможет

спасибо, почитаю.

Блочное умножение матриц.

> но random() прилично ресурсов жрёт

первое, что приходит в голову — просто в начале нагенерить рандомных индексов, а затем уже последовательно брать эти индексы и ходить по ним по массиву.

время генерации рандомных индексов, очевидно, в тесте не учитывать.

>нагенерить рандомных индексов

Э... А seed у ГСЧ уже отменили? :)

Да я думаю тут это не особо влияет. Впрочем, померяю - узнаю.

Не совсем уловил. Какое отношение seed имеет к предложенному способу исключить генерацию рандомной последовательности из теста?

2true_admin: Я же правильно понял, ты хочешь эмпирически подобрать размер сплошной области памяти, такой, что её будет нельзя увеличить без существенного увеличения количества промахов кеша данных при условии случайного доступа к этой области памяти? И проблема с рандом заключалась в том, что он сильно влиял на результат?

кстати, кешграйнд я бы всё же заюзал, т.к. засекать время будет очень уж неточно. А у кешграйнда даже метрика подходящая есть — количество промахов кеша (данных/инструкций) для определённого куска кода

Вообще хочу посмотреть влияние одних процессов в системе на другие. Кэш-то общий для всех программ. При переключении контекста данные одной программы могут быть вытеснены, что и происходит на практике.

кешграйнд я бы всё же заюзал

А я его активно юзаю :).

засекать время будет очень уж неточно.

Нуу, надо просто в тестах учитывать неточность часов. Уж с точностью до 0.1с любой таймер сгодится.

>Нуу, надо просто в тестах учитывать неточность часов. Уж с точностью до 0.1с любой таймер сгодится.

ненене, я про другого рода неточность- про ту, которая вызвана многозадачностью системы.

Вообще хочу посмотреть влияние одних процессов в системе на другие. Кэш-то общий для всех программ. При переключении контекста данные одной программы могут быть вытеснены, что и происходит на практике.

хм. Даже и не знаю, что бы я на твоем месте делал. Поделись, плиз, результатами, как закончишь

про ту, которая вызвана многозадачностью системы.

результаты стабильны даже если не убивать браузер и скайп. Хотя я щас остановил всё что смог и выполняю тесты удалённо. Даже вывод программ в /dev/null отправил т.к. это сильно влияет при большом выводе.

результатами

Нуу отправная точка такая: есть 4 процесса запущенных core 2 duo с 3m кеша: два cache-aware и два нет. Это программы по data mining, что-то там обсчитывают. Делают одно и тоже, только написаны по-разному. Так вот неоптимизированные процессы на ~40% снижают нормализованную скорость cache-aware прог. При том что сами они падения производительности не показывают. Тут много что влияет, например, настройки планировщика задач.

Собстно какую я решаю задачу: хочу детально разобраться в вопросе потому что та прога что написали прогеры очень сильно лагает на больших датасетах. Нужно решить проблему. Я двигаюсь в двух направлениях: 1) уменьшить потребляемую память(чтоб в кэш лучше влезло) 2) сделать memory access более линейным и предсказуемым путём изменения структуры данных и алгоритмов обработки. Щас прога внутри сильно прыгает по указателям(всё хранится в графе) и очень страдает от cache misses. Я подозреваю что это можно оптимизировать. Короче, стараюсь подойти со всех фронтов.