C ++, способы сравнения улучшений локальности кэша? - PullRequest
8 голосов
/ 17 июня 2009

У меня есть реализация класса X, которая имеет два указателя на две части информации. Я написал новую реализацию, класс Y, которая имеет только один указатель на структуру, которая содержит две части информации вместе в качестве смежных членов. Методы X и Y обычно должны манипулировать только одним из фрагментов информации, но предоставляют метод get (), который возвращает указатель на второй фрагмент (в этом случае класс X просто возвращает свой указатель на этот фрагмент, а класс Y возвращает адрес второго члена структуры). При обычном использовании вызовы методов X и Y будут чередоваться с вызовами get () и выполнением работы над возвращенным вторым фрагментом.

Я ожидаю, что в реальных ситуациях должно произойти улучшение производительности, теперь, когда две части информации находятся рядом друг с другом в памяти в реализации класса Y (потому что они являются смежными членами структуры), но я ' я не вижу никакой разницы в написанных мною тестах (перемежая вызовы методов X и Y с работой над их вторыми частями в больших циклах). Я подозреваю, что это потому, что в моих тестах в любом случае все помещается в кэш. Я не хочу пробовать это в моем реальном приложении, потому что семантика X и Y отличается другими тонкими способами, не связанными с этой оптимизацией, и портирование используемого приложения будет некоторой работой, и эти тесты должны помочь оправдать это работа в первую очередь.

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

Ответы [ 3 ]

8 голосов
/ 17 июня 2009

Если вы работаете в Linux, то использование Cachegrind в сочетании с KCacheGrind может дать более полное представление о том, как ведет себя ваш кэш.

2 голосов
/ 17 июня 2009

Вы можете разработать эталонный тест специально для разрушения кэша. Например, выделите указанные блоки данных таким образом, чтобы они все гарантированно находились в разных строках кэша (скажем, с помощью специального распределителя памяти, который распределяет выделения как минимум на несколько сотен байтов). Затем многократно выполняйте итерацию по нескольким объектам, слишком большим, чтобы вместить все, даже в кэш L2 (очень зависит от платформы, поскольку это зависит от количества строк в кэше, но 1 миллион будет охватывать большинство архитектур и потребовать всего несколько сотен мегабайт ОЗУ всего).

Это даст вам верхний предел прироста производительности при переходе с X на Y. Но это достигается за счет снижения производительности X до уровня ниже любого вероятного реального использования. И чтобы доказать ваш случай, вам нужна оценка нижнего предела, а не оценка верхнего предела. Поэтому я не уверен, что вы многого добьетесь, если только не обнаружите, что даже этот наихудший случай все еще не имеет существенного значения, и вам не нужно беспокоиться об оптимизации.

Даже если вы не стремитесь к теоретической производительности X для наихудшего случая, любой тест, рассчитанный на превышение кеша, просто выбирает произвольную точку плохой производительности X и смотрит, лучше ли Y. Это не так уж далеко от фальсификации теста, чтобы Y выглядел хорошо. Это действительно не имеет значения, как ваш код работает в хитрых тестах, за исключением, может быть, для целей маркетинга ложь литература.

Лучший способ оценить разницу в производительности в реальном мире - это измерить реального клиента вашего класса. Вы говорите, что «семантика X и Y отличается другими тонкими способами, не связанными с этой оптимизацией», и в этом случае я могу только рекомендовать вам написать класс Z, который отличается от X только в отношении этого оптимизации и используйте это в своем приложении для сравнения.

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

Все это говорит о том, что если это имеет логический смысл (то есть код не делает код более удивительным), то я бы рекомендовал минимизировать количество выделений кучи в C ++ просто как практическое правило. Это не приводит к ухудшению скорости или общего использования памяти, а также упрощает обработку ресурсов. Практическое правило, конечно, не оправдывает переписывание рабочего кода.

0 голосов
/ 17 июня 2009

Если я правильно понимаю вашу ситуацию (и, пожалуйста, исправьте меня, если нет), то это шесть из одного или полдюжины из другого.

В классе X вам нужен один указатель для поискалюбая часть информации.В классе Y вам нужен один поиск для первого и два (получить первое, а затем смещение) для второго.Это приносит в жертву "местность" для другого доступа к памяти.К сожалению, компиляторы по-прежнему очень хорошо тратят время на поиск слов в оперативной памяти.

Если это возможно, вы получите наилучшие результаты, если две части целевой информации будут храниться непосредственно в рассматриваемом классе (т. е. каждый член своего класса), вместо того, чтобы использовать эти указатели для ненужного косвенного обращения.Не видя никакого кода, это почти все, что я могу сказать.

Во всяком случае, вы получите лот больше производительности при изучении алгоритмической сложности вашего приложения, чем когда-либо.с микрооптимизацией двух переменных в определении класса.Также отличная идея - использовать инструмент профилирования, чтобы увидеть (объективно), где находятся ваши узкие места (gprof обычно в * nix системах).Есть ли конкретная причина, по которой вы хотите увеличить кеширование локальности?

...