Самое быстрое использование набора данных размером чуть более 64 байт?

Структура: у меня есть 8 64-битных целых чисел (512 бит = 64 байта, предполагаемая ширина строки кэша), которые я хотел бы сравнить с другим, одним 64-битным целым числом, в свою очередь, без кэш-промахов . Набор данных, к сожалению, абсолютно негибкий — он уже максимально мал.

Шаблон доступа: каждый uint64_t фактически является массивом битов 4x4x4, каждый бит представляет наличие или отсутствие вокселя. Это означает, что иногда я буду использовать половину одного фрагмента и половину другого или даже углы 8 разных 64-битных фрагментов... Я предполагаю, что это означает, что существует высокая вероятность отсутствия выравнивания.

Как это сделать как можно быстрее, т. е. без перегрузки кеша?

P.S. Идея состоит в том, что этот код в конечном итоге будет работать на довольно широком диапазоне архитектур с шириной строки кэша не менее 64 байт, поэтому я бы предпочел, чтобы это было максимально быстро. Это также означает, что я не могу полагаться на MOVNTDQA, который в любом случае может привести к снижению производительности, несмотря на загрузку 9-го элемента непосредственно в ЦП.

П.П.С. Мои познания в этой области довольно ограничены, поэтому, пожалуйста, будьте со мной полегче. Но, пожалуйста, избавьте меня от преждевременных комментариев по оптимизации; будьте уверены, что это 3% этого приложения, которые действительно имеют значение.


person Engineer    schedule 18.06.2015    source источник
comment
Набор данных обычно описывает общий размер — кажется, у вас есть объекты размером 64 байта, но сколько их вы ожидаете?   -  person Leeor    schedule 18.06.2015
comment
@Leeor у меня 9x uint64_t = 68B всего. Я считаю дополнительный, с которым я сравниваю остальные восемь, отдельным для концептуальных целей. Хм, просто думаю о структуре памяти... см. редактирование.   -  person Engineer    schedule 18.06.2015
comment
Это зависит от вашей целевой архитектуры.   -  person too honest for this site    schedule 18.06.2015


Ответы (2)


Вы уверены, что получаете кэш-промахи? Даже если сравниваемое значение не находится в регистре, я думаю, что ваш первый массив uint64 должен находиться на одном этапе кеша (или как бы он ни назывался), а ваши другие данные - на другом. Ваш кеш, безусловно, имеет некоторую n-стороннюю ассоциативность, которая предотвращает удаление вашей строки данных из кеша только путем доступа к вашему значению сравнения.

Не теряйте время на микрооптимизации. Улучшите свои алгоритмы и структуры данных.

person vlad_tepesch    schedule 18.06.2015
comment
Он не сказал, что восемь uint64 находятся в массиве. Если n меньше 8 и эти 8 целых чисел расположены по адресам, которые находятся ровно в SizeOfCacheLine*2^M байтах друг от друга, действительно может возникнуть конфликт кеша. Этого не произойдет, если они совершенно случайно разбросаны в памяти или расположены близко друг к другу, как массив, но может произойти в таких ситуациях, как между строками изображения, размер строки которых равен SizeOfCacheLine*2^M. - person user3528438; 18.06.2015

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

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

  1. Решите, каково ваше максимально приемлемое время выполнения.
  2. Закончите свою программу на C
  3. Компиляция для всех ваших целевых архитектур
  4. Для тех платформ, которые не соответствуют вашим спецификациям скорости, вручную оптимизируйте промежуточные файлы сборки и перекомпилируйте, пока не достигнете своих спецификаций.
person skrrgwasme    schedule 18.06.2015
comment
Вы делаете несколько важных выводов. Однако я хотел бы напомнить вам полную цитату: Программисты тратят огромное количество времени, думая или беспокоясь о скорости некритических частей своих программ, и эти попытки повысить эффективность на самом деле имеют сильное негативное влияние, когда отладка и обслуживание считается. Мы должны забыть о малой эффективности, скажем, примерно в 97% случаев: преждевременная оптимизация — корень всех зол. Тем не менее, мы не должны упускать наши возможности в отношении этих критических 3%. Эти 3% имеют значение. ИИ, физика, рендеринг — все зависит от того, что это БЫСТРО. - person Engineer; 18.06.2015
comment
@ArcaneEngineer Приношу свои извинения за предположение, что вы еще не выполнили профилирование для идентификации этого сегмента кода. Я видел слишком много вопросов по оптимизации на SO, где ОП не проделал никакой работы, чтобы определить правильные 3%, поэтому я отвечал немного привычно. Это была моя ошибка. - person skrrgwasme; 18.06.2015
comment
Не казаться неблагодарным; Спасибо за вашу помощь, я проголосовал за полезные части вашего ответа. - person Engineer; 18.06.2015
comment
@ArcaneEngineer Спасибо! - person skrrgwasme; 18.06.2015