Почему этот код сборки быстрее?

Я экспериментирую с lexer, и я обнаружил, что переход от цикла while к if-statement и do-while-loop в одной части программы привел к ~ на 20% быстрее кода, что казалось сумасшедшим, Я выделил разницу в коде, сгенерированном компилятором, в эти фрагменты сборки. Кто-нибудь знает, почему быстрый код быстрее?

В сборке "edi" - текущая текстовая позиция, "ebx" - это конец текста, а "isAlpha" - это таблица поиска, которая имеет 1, если символ является алфавитным, и 0 в противном случае.

Медленный код:

slow_loop:
00401897  cmp   edi,ebx 
00401899  je    slow_done (4018AAh) 
0040189B  movzx eax,byte ptr [edi] 
0040189E  cmp   byte ptr isAlpha (4533E0h)[eax],0 
004018A5  je    slow_done (4018AAh) 
004018A7  inc   edi  
004018A8  jmp   slow_loop (401897h) 
slow_done:

Быстрый код:

fast_loop:
0040193D  inc   edi  
0040193E  cmp   edi,ebx 
00401940  je    fast_done (40194Eh) 
00401942  movzx eax,byte ptr [edi] 
00401945  cmp   byte ptr isAlpha (4533E0h)[eax],0 
0040194C  jne   fast_loop (40193Dh) 
fast_done:

Если я запускаю только эти фрагменты сборки с мегабайтом текста, состоящего только из буквы "a", быстрый код на 30% быстрее. Я предполагаю, что медленный код медленный из-за неверного предсказания отрасли, но я думал, что в цикле это будет одноразовая стоимость.

Здесь программа, которую я использовал для проверки обоих фрагментов:

#include <Windows.h>
#include <string>
#include <iostream>

int main( int argc, char* argv[] )
{
    static char isAlpha[256];
    for ( int i = 0; i < sizeof( isAlpha ); ++i )
        isAlpha[i] = isalpha( i ) ? 1 : 0;

    std::string test( 1024*1024, 'a' );

    const char* start = test.c_str();
    const char* limit = test.c_str() + test.size();

    DWORD slowStart = GetTickCount();
    for ( int i = 0; i < 10000; ++i )
    {
        __asm
        {
            mov edi, start
            mov ebx, limit

            inc edi

        slow_loop:
            cmp   edi,ebx
            je    slow_done
            movzx eax,byte ptr [edi]
            cmp   byte ptr isAlpha [eax],0
            je    slow_done
            inc   edi
            jmp   slow_loop

        slow_done:
        }
    }
    DWORD slowEnd = GetTickCount();
    std::cout << "slow in " << ( slowEnd - slowStart ) << " ticks" << std::endl;

    DWORD fastStart = GetTickCount();
    for ( int i = 0; i < 10000; ++i )
    {
        __asm
        {
            mov edi, start
            mov ebx, limit

        fast_loop:
            inc   edi
            cmp   edi,ebx
            je    fast_done
            movzx eax,byte ptr [edi]
            cmp   byte ptr isAlpha [eax],0
            jne   fast_loop

        fast_done:
        }
    }
    DWORD fastEnd = GetTickCount();
    std::cout << "fast in " << ( fastEnd - fastStart ) << " ticks" << std::endl;

    return 0;
}

Выход тестовой программы

slow in 8455 ticks
fast in 5694 ticks

Ответы

Ответ 1

Извините, я не смог воспроизвести ваш код именно на GCC (linux), но у меня есть некоторые результаты, и я думаю, что основная идея была сохранена в моем коде.

Существует инструмент от Intel для анализа производительности фрагмента кода: http://software.intel.com/en-us/articles/intel-architecture-code-analyzer/ (Intel IACA). Его можно загрузить и протестировать.

В моем эксперименте отчет для медленного цикла:

Intel(R) Architecture Code Analyzer Version - 2.0.1
Analyzed File - ./l2_i
Binary Format - 32Bit
Architecture  - SNB
Analysis Type - Throughput

Throughput Analysis Report
--------------------------
Block Throughput: 3.05 Cycles       Throughput Bottleneck: Port5

Port Binding In Cycles Per Iteration:
-------------------------------------------------------------------------
|  Port  |  0   -  DV  |  1   |  2   -  D   |  3   -  D   |  4   |  5   |
-------------------------------------------------------------------------
| Cycles | 0.5    0.0  | 0.5  | 1.0    1.0  | 1.0    1.0  | 0.0  | 3.0  |
-------------------------------------------------------------------------

N - port number or number of cycles resource conflict caused delay, DV - Divide
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred

| Num Of |              Ports pressure in cycles               |    |
|  Uops  |  0  - DV  |  1  |  2  -  D  |  3  -  D  |  4  |  5  |    |
---------------------------------------------------------------------
|   1    |           |     |           |           |     | 1.0 | CP | cmp edi,
|   0F   |           |     |           |           |     |     |    | jz 0xb
|   1    |           |     | 1.0   1.0 |           |     |     |    | movzx ebx
|   2    |           |     |           | 1.0   1.0 |     | 1.0 | CP | cmp cl, b
|   0F   |           |     |           |           |     |     |    | jz 0x3
|   1    | 0.5       | 0.5 |           |           |     |     |    | inc edi
|   1    |           |     |           |           |     | 1.0 | CP | jmp 0xfff

Для быстрого цикла:

Throughput Analysis Report
--------------------------
Block Throughput: 2.00 Cycles       Throughput Bottleneck: Port5

Port Binding In Cycles Per Iteration:
-------------------------------------------------------------------------
|  Port  |  0   -  DV  |  1   |  2   -  D   |  3   -  D   |  4   |  5   |
-------------------------------------------------------------------------
| Cycles | 0.5    0.0  | 0.5  | 1.0    1.0  | 1.0    1.0  | 0.0  | 2.0  |
-------------------------------------------------------------------------

N - port number or number of cycles resource conflict caused delay, DV - Divide
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred

| Num Of |              Ports pressure in cycles               |    |
|  Uops  |  0  - DV  |  1  |  2  -  D  |  3  -  D  |  4  |  5  |    |
---------------------------------------------------------------------
|   1    | 0.5       | 0.5 |           |           |     |     |    | inc edi
|   1    |           |     |           |           |     | 1.0 | CP | cmp edi,
|   0F   |           |     |           |           |     |     |    | jz 0x8
|   1    |           |     | 1.0   1.0 |           |     |     |    | movzx ebx
|   2    |           |     |           | 1.0   1.0 |     | 1.0 | CP | cmp cl, b
|   0F   |           |     |           |           |     |     |    | jnz 0xfff

Таким образом, в медленном цикле JMP является дополнительной инструкцией в Critical Path. Все пары cmp + jz/jnz объединяются (Macro-fusion) в один u-op. И в моей реализации кода критическим ресурсом является Port5, который может выполнять ALU + JMP (и это единственный порт с возможностью JMP).

PS: Если кто-то не знает, где расположены порты, есть фотографии сначала второй; и статья: rwt

PPS: IACA имеет некоторые ограничения; он моделирует только часть процессора (единицы исполнения) и не пропускает кеширование учетной записи, неверные предсказания веток, различные штрафы, изменения частоты/мощности, прерывания ОС, конкуренцию HyperThreading для единиц исполнения и многие другие эффекты. Но это полезный инструмент, потому что он может дать вам быстрый взгляд в самом внутреннем ядре современного процессора Intel. И он работает только для внутренних циклов (как и петли в этом вопросе).

Ответ 2

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