C ++ битовая маска / оптимизация условных переходов
Я пытаюсь сократить время выполнения оператора if, показанного ниже (второй блок кода). Он включает битовую маску, где массив масок содержит 8 целых чисел, используемых в качестве масок, и настраивается следующим образом:
static unsigned int masks[8];
void setupMasks() {
int mask = 3; // 0000 0000 0000 0000 0000 0000 0000 0011
for(unsigned int i=0; i < 8; i++) {
masks[i] = (mask << (i * 4));
}
}
Каждое целое число в testarr ниже фактически содержит 8 результатов. Каждый результат представляет собой 4 бита 32-разрядного типа int, и я хочу знать только, является ли какой-либо из младших двух из 4-х битов единицей. Приведенный ниже код выполняется внутри другого цикла for, который обновляет resultnum. failcount — это локально определенный массив int. Я хотел бы избежать маскировки, но данные в testarr поступают из API, который я не могу изменить. В любом случае, я думаю, что оператор if занимает больше времени, чем маскировка, но я могу ошибаться. Кто-нибудь видит способ оптимизации?
for(unsigned int i = 0; i < 8 && dumped < numtodump; i++, dumped++) { //8 results per 32-bit value
unsigned int fails = 0;
for(unsigned int j = 0; j < 32; j++) {
if((testarr[j * numintsperpin + resultnum] & masks[i]) && failcount[j]++ <= 10000) { //have a fail
failingpins[fails++] = &pins[j];
}
}
}
Извините, если мой предыдущий пост не был понятным. Ниже приведена полная функция. Я постарался максимально упростить постановку задачи как можно раньше. Извините, если я пропустил полезные детали.
void process(vector<int> &testarr, vector<unsigned int> &failcount, vector<pin> &pins, vector<unsigned int> &muxaddr, unsigned int base, StopWatch &acc1) {
unsigned int labeloffset = 400;
unsigned int startindex = 50;
unsigned int numtodump = 1000;
unsigned int numintsperpin = testarr.size() / pins.size();
pin** failingpins = new pin*[32];
acc1.start();
int count = 0;
unsigned int dumped = 0;
unsigned int resultnum = 0;
while(dumped < numtodump) {
for(unsigned int i = 0; i < 8 && dumped < numtodump; i++, dumped++) { //8 results per 32-bit value
unsigned int currentindex = labeloffset + dumped + startindex;
unsigned int fails = 0;
for(unsigned int j = 0; j < pins.size(); j++) {
if((testarr[j * numintsperpin + resultnum] & masks[i]) && failcount[j]++ <= 10000) { //have a fail
failingpins[fails++] = &pins[j];
}
}
unsigned int saddr = muxaddr[currentindex];
if(fails > 0) {
logFails(fails, muxaddr[currentindex] - base, failingpins);
}
}
resultnum++;
}
acc1.accumulate();
}
Решение
Посмотрим, имею ли я это право:
Каждая запись в testarr является 32-битным значением, содержащим 8 х 4-битных полей
Вы хотите знать, имеет ли какое-либо поле один из двух младших битов, т.е. вы хотите замаскировать каждое 32-битное значение с помощью:
0011 0011 0011 0011 0011 0011 0011 0011
так почему не:
for( int i=0; i<testarr_length; i++ )
if( testarr[i] & 0x33333333 )
// do something !
Если вам нужно знать, во сколько полей установлены эти биты, то
for( int i=0; i<testarr_length; i++ )
{
unsigned int dword= testarr[i];
for( int field=0; field<8; field++ )
{
if( dword & 0x3 )
// do something
dword= dword >> 4;
}
}
Другие решения
Вы можете попробовать следующее
inline int count(int x)
{
static int mask1 = 0x11111111;
static int mask2 = 0x22222222;
return __builtin_popcount(x & mask1 | x & mask2 << 1);
}
// ...
unsigned int fails = 0;
for(unsigned int j = 0; j < 32; j++) {
int c = count(testarr[j * numintsperpin + resultnum]);
if(c && (failcount[j]+=c) <= 10000) { //have a fail
failingcols[fails+=c] = &column[j];
}
}
где я разделил маску на две отдельные маски, и я использовал функцию __builtin_popcount который считает биты заданного целого числа только за одну операцию ЦП, таким образом избегая зацикливания i в целом.
__builtin_popcount должен быть предоставлен компилятором, например пример выше работает с Clang и GCC с опцией -msse4.2, Насколько я помню, компилятор MS соответственно предоставляет функцию __popcnt,
Я не знаю, какова роль dumped но это не видно внутри вашего цикла, поэтому я просто проигнорировал это.
РЕДАКТИРОВАТЬ
Теперь я видел обновленный вопрос, где кажется, что dumped играет существенную роль в перекодировании фактической позиции отказов помимо их количества. В этом случае мое решение не применяется. Эта новая проблема гораздо сложнее оптимизировать.
detector