Най-бързото използване на набор от данни от малко над 64 байта?

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

Модел за достъп: Всеки uint64_t всъщност е масив от 4x4x4 бита, като всеки бит представлява наличието или отсъствието на воксел. Това означава, че понякога ще използвам половината от едно парче и половината от друго или дори ъгли на 8 различни 64-битови парчета... Предполагам, че това означава, че има голяма вероятност от липса на подравняване.

Как мога да направя това възможно най-бързо, т.е. без да разбивам кеша?

P.S. Идеята е, че този код в крайна сметка ще работи на доста широк диапазон от архитектури с ширина на реда на кеша поне 64B, така че бих предпочел това да е възможно най-бързо. Това също означава, че не мога да разчитам на MOVNTDQA, което така или иначе може да доведе до спад в производителността си, въпреки зареждането на 9-ия елемент директно в процесора.

P.P.S. Познанията ми в тази област са доста ограничени, така че, моля, бъдете по-спокойни с мен. Но моля, спестете ми преждевременните коментари за оптимизация; бъдете сигурни, че това са 3% от това приложение, което наистина има значение.


c cpu-cache
person Engineer    schedule 18.06.2015    source източник
comment
Наборът от данни обикновено описва общия размер - изглежда, че имате 64B обекта, но колко от тях очаквате?   -  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)


arrow_upward
1
arrow_downward

Сигурни ли сте, че получавате пропуски в кеша? Дори ако стойността за сравнение не е в регистър, мисля, че първият ви масив 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

arrow_upward
2
arrow_downward

Не бих се тревожил за това. Ако вашият набор от данни наистина е само 9 цели числа, повечето от тях вероятно ще бъдат съхранени в регистри така или иначе. Също така, всъщност няма начин да се оптимизира използването на кеша без да се посочи архитектура, тъй като структурата на кеша е зависима от архитектурата. Ако можете да изброите няколко целеви архитектури, може да успеете да намерите някои общи неща, към които можете да оптимизирате, но без да познавате тези архитектури, не мисля, че можем да направим много за вас.

И накрая, това изглежда като добър пример за твърде ранна оптимизация. Предлагам ви да предприемете следните стъпки:

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