Блог

Я работаю с алгоритмом, который выполняет множество добавлений popcount / sideways до заданного индекса для 32-разрядного типа. Я стремлюсь свести к минимуму операции, необходимые для выполнения того, что я в настоящее время реализовал следующим образом:

 int popcto_test1(unsigned int bitmap[], int idx){
int i = 0,      // index
    count = 0;  // number of set bits
do {
    // Each node contains 8 bitmaps
    if(bitmap[i/32] amp; 1 << (i amp; 31)){
          count;
    }
      i;
} while (i < idx);

return count;
}
  

Я знаю о взломах с подменой битов для 64-разрядных типов, но, похоже, нет быстрого способа сделать это для 32-разрядных типов.

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

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

С тех пор я запустил множество тестов производительности, основанных на предложенных методах и на том, что у меня было выше (протестировано 4 000 000 раз), и получил следующие результаты:

среднее значение popcto_test1 ns = 133
среднее значение popcto_test2 // тест не пройден
среднее значение popcto_test3 ns = 28
среднее значение popcto_test4 ns= 74

где тестовые функции были следующими:
Неудачный тест 2:

 int popcto_test2(unsigned int bitmap[], int idx){
int i = 0,      // index
    count = 0;  // number of set bits
do {
    // Each node contains 8 bitmaps
    count  = (bitmap[i/32] amp; (1 << (i amp; 31)));
      i;
} while (i < idx);

return count;
}
  

popcto_test3 ns=28
Один (возможно) интересный момент, который следует отметить в этом, заключается в том, что, хотя он самый быстрый, при использовании уровней оптимизации 2 или 3 (-O2 / -O3) результат, который он дает, неверен.

 int popcto_test3(unsigned int bitmap[], int idx){
int i = 0,      // index
    count = 0,  // number of set bits
    map = idx/32;
while (i < map){
    // Each node contains 8 bitmaps
    count  = __builtin_popcount(bitmap[i]);
      i;
}

count  = __builtin_popcount(bitmap[map] amp; ((1<<idx)-1));
return count;
}
  

среднее значение popcto_test4 ns=74 (модифицированный метод Питера Вегнера)

 int popcto_test4(unsigned int bitmap[], int idx){
int i = 0,      // index
    j = 0,
    count = 0,  // number of set bits
    map = idx/32;
unsigned int temp = 0;

while (i < map){
    temp = bitmap[i];
    j = 0;
    while(temp){
        temp amp;= temp - 1;
          j;
    }
    count  = j;
      i;
}
temp = bitmap[i] amp; ((1<<idx)-1);
j = 0;
while(temp){
    temp amp;= temp - 1;
      j;
}
return count   j;
}
  

Спасибо всем за предложения, я решил сопоставить все методы, с которыми я столкнулся, поскольку не смог найти никаких похожих тестов.

Примечание. Показанные подсчеты заполнения относятся к индексам до argv[1] , а не к общему количеству argv[1] — 8x 32-разрядных массивов составляют 256 бит. Код, используемый для получения этих результатов, можно увидеть здесь.

В моем Ryzen 1700, для моего использования, самый быстрый подсчет населения был (часто) тем, который приведен на странице 180 Руководства по оптимизации программного обеспечения для процессоров AMD64. Это (часто) остается верным и для больших количеств заполнения.

 unsigned int population_count(int temp){
    // Software Optimization Guide for AMD64 Processors - Page 180
    temp = temp - ((temp >> 1) amp; 0x55555555);
    temp = (temp amp; 0x33333333)   ((temp >> 2) amp; 0x33333333);
    return (((temp   (temp >> 4)) amp; 0xF0F0F0F) * 0x1010101) >> 24;
}
  

У меня нет параллельного сравнения для этого, но если вы используете CUDA; встроенный __popc метод является самым быстрым, за ним вскоре следует метод Вегнера. Метод AMD64 является вторым по скорости (только после побитового), я полагаю, это связано с увеличением занятости / использования регистра по сравнению со всеми другими методами.