Шанс оптимизации для следующих битовых операций? - PullRequest
Новая
       16

Шанс оптимизации для следующих битовых операций?

12 голосов
/ 24 ноября 2010

Как вы думаете, есть ли место для оптимизации в функции haswon (см. Ниже)?

Я понял, что изменение типа аргумента с __int64 на unsigned __int64 сделало функцию быстрее, поэтому, возможно, я думаю,еще есть шанс для оптимизации.

Более подробно: Я пишу подключить четыре игры.Недавно я использовал Profiler Very Sleepy и понял, что функция haswon использует большую часть процессорного времени.Функция использует представление бит-доски для соединения четырех плат для одного игрока.Саму функцию я обнаружил в источниках теста fourstones .Представление на доске выглядит следующим образом: 

.  .  .  .  .  .  .  TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2  9 16 23 30 37 44
1  8 15 22 29 36 43
0  7 14 21 28 35 42  BOTTOM

Функция: 

// return whether newboard includes a win
bool haswon(unsigned __int64 newboard)
{
    unsigned __int64 y = newboard & (newboard >> 6);
    if (y & (y >> 2 * 6)) // check \ diagonal
        return true;
    y = newboard & (newboard >> 7);
    if (y & (y >> 2 * 7)) // check horizontal -
        return true;
    y = newboard & (newboard >> 8);
    if (y & (y >> 2 * 8)) // check / diagonal
        return true;
    y = newboard & (newboard >> 1);
    if (y & (y >> 2))     // check vertical |
        return true;
    return false;
}

Спасибо!

Редактировать: Процессор x86, 32-битная архитектураЯ использую компилятор из Visual Studio 2008 Express Edition.Флаги оптимизации: / O2 / Oi /GL.

Я попробовал функцию haswon2, которую предложил Бен Джексон.Сборки от компилятора Microsoft, с флагами оптимизации по умолчанию для версий выпуска (/ O2 / Oi / GL), практически не отличаются во время выполнения.Похоже, что VC-компилятор по сравнению с gcc не может воспользоваться тем, что он не должен оценивать каждое условие в строгом порядке.

Результаты: имеет оригинальный: haswon

haswon2 от Бена Джексона: haswon2

Edit2: Сборка haswon: 

00401A10  mov         eax,dword ptr [esp+4] 
00401A14  mov         ecx,dword ptr [esp+8] 
00401A18  push        ebx  
00401A19  push        esi  
00401A1A  push        edi  
00401A1B  mov         edx,eax 
00401A1D  mov         edi,ecx 
00401A1F  shrd        edx,edi,6 
00401A23  mov         esi,edx 
00401A25  shr         edi,6 
00401A28  and         esi,eax 
00401A2A  and         edi,ecx 
00401A2C  mov         edx,esi 
00401A2E  mov         ebx,edi 
00401A30  shrd        edx,ebx,0Ch 
00401A34  shr         ebx,0Ch 
00401A37  and         edx,esi 
00401A39  and         ebx,edi 
00401A3B  or          edx,ebx 
00401A3D  je          `anonymous namespace'::haswon+35h (401A45h) 
00401A3F  mov         al,1 
00401A41  pop         edi  
00401A42  pop         esi  
00401A43  pop         ebx  
00401A44  ret              
00401A45  mov         edx,eax 
00401A47  mov         edi,ecx 
00401A49  shrd        edx,edi,7 
00401A4D  mov         esi,edx 
00401A4F  shr         edi,7 
00401A52  and         esi,eax 
00401A54  and         edi,ecx 
00401A56  mov         edx,esi 
00401A58  mov         ebx,edi 
00401A5A  shrd        edx,ebx,0Eh 
00401A5E  shr         ebx,0Eh 
00401A61  and         edx,esi 
00401A63  and         ebx,edi 
00401A65  or          edx,ebx 
00401A67  jne         `anonymous namespace'::haswon+2Fh (401A3Fh) 
00401A69  mov         edx,eax 
00401A6B  mov         edi,ecx 
00401A6D  shrd        edx,edi,8 
00401A71  mov         esi,edx 
00401A73  shr         edi,8 
00401A76  and         esi,eax 
00401A78  and         edi,ecx 
00401A7A  mov         edx,esi 
00401A7C  mov         ebx,edi 
00401A7E  shrd        edx,ebx,10h 
00401A82  shr         ebx,10h 
00401A85  and         edx,esi 
00401A87  and         ebx,edi 
00401A89  or          edx,ebx 
00401A8B  jne         `anonymous namespace'::haswon+2Fh (401A3Fh) 
00401A8D  mov         edx,eax 
00401A8F  mov         esi,ecx 
00401A91  shrd        edx,esi,1 
00401A95  shr         esi,1 
00401A97  and         esi,ecx 
00401A99  and         edx,eax 
00401A9B  mov         eax,edx 
00401A9D  mov         ecx,esi 
00401A9F  shrd        eax,ecx,2 
00401AA3  shr         ecx,2 
00401AA6  and         eax,edx 
00401AA8  and         ecx,esi 
00401AAA  or          eax,ecx 
00401AAC  jne         `anonymous namespace'::haswon+2Fh (401A3Fh) 
00401AAE  pop         edi  
00401AAF  pop         esi  
00401AB0  xor         al,al 
00401AB2  pop         ebx  
00401AB3  ret

1 Ответ

17 голосов
/ 24 ноября 2010

Идея этой версии заключается в том, чтобы избежать строгого порядка тестирования (промежуточные возвраты заставляют компилятор оценивать условия по одному по порядку), а также ветвления, связанные с несколькими операторами if: 

// return whether newboard includes a win
bool haswon2(uint64_t newboard)
{
    uint64_t y = newboard & (newboard >> 6);
    uint64_t z = newboard & (newboard >> 7);
    uint64_t w = newboard & (newboard >> 8);
    uint64_t x = newboard & (newboard >> 1);
    return (y & (y >> 2 * 6)) | // check \ diagonal
           (z & (z >> 2 * 7)) | // check horizontal -
           (w & (w >> 2 * 8)) | // check / diagonal
           (x & (x >> 2));      // check vertical |
}

При достойном уровне оптимизации вы действительно можете рассматривать w, x, y и z как «псевдонимы» для сдвинутых значений.Это означает, что последний оператор return бросает всю операцию в большой суп для компилятора.В моей системе эта версия занимает только 65% времени выполнения оригинала (включая накладные расходы на генерацию случайной позиции каждый раз).Он может выиграть в большем проценте, если доски в основном не выигрывают.

Если посмотреть на разборку каждой (от gcc -O3), оригинальная версия на самом деле короче, так что, скорее всего, отсутствие разветвлениятесная внутренняя петля, которая действительно помогает.

...