Почему эта функция С++ выдает так много неверных прогнозов отрасли?

Пусть A - массив, содержащий нечетное число нулей и единиц. Если n - размер A, то A построен таким образом, что первые ceil(n/2) элементы 0, а остальные элементы 1.

Итак, если n = 9, A будет выглядеть так:

0,0,0,0,0,1,1,1,1

Цель состоит в том, чтобы найти сумму 1s в массиве, и мы делаем это, используя эту функцию:

s = 0;
void test1(int curIndex){
    //A is 0,0,0,...,0,1,1,1,1,1...,1

    if(curIndex == ceil(n/2)) return;

    if(A[curIndex] == 1) return;

    test1(curIndex+1);
    test1(size-curIndex-1);

    s += A[curIndex+1] + A[size-curIndex-1];

}

Эта функция довольно глупо для заданной проблемы, но это симуляция другой функции, которую я хочу выглядеть так и производит такое же количество неверных предсказаний.

Вот весь код эксперимента:

#include <iostream>
#include <fstream>

using namespace std;


int size;
int *A;
int half;
int s;

void test1(int curIndex){
    //A is 0,0,0,...,0,1,1,1,1,1...,1

    if(curIndex == half) return;
    if(A[curIndex] == 1) return;

    test1(curIndex+1);
    test1(size - curIndex - 1);

    s += A[curIndex+1] + A[size-curIndex-1];

}


int main(int argc, char* argv[]){

    size = atoi(argv[1]);
    if(argc!=2){
        cout<<"type ./executable size{odd integer}"<<endl;
        return 1;
    }
    if(size%2!=1){
        cout<<"size must be an odd number"<<endl;
        return 1;
    }
    A = new int[size];

    half = size/2;
    int i;
    for(i=0;i<=half;i++){
        A[i] = 0;
    }
    for(i=half+1;i<size;i++){
        A[i] = 1;
    }

    for(i=0;i<100;i++) {
        test1(0);
    }
    cout<<s<<endl;

    return 0;
}

Скомпилируйте, набрав g++ -O3 -std=c++11 file.cpp и запустите, набрав ./executable size{odd integer}.

Я использую процессор Intel Core i5-3470 с частотой 8 ГБ, 8 ГБ оперативной памяти, кеш L1 256 КБ, кеш второго уровня 1 МБ, кеш-память L3 6 МБ.

Запуск perf stat -B -e branches,branch-misses ./cachetests 111111 дает мне следующее:

   Performance counter stats for './cachetests 111111':

    32,639,932      branches                                                    
     1,404,836      branch-misses             #    4.30% of all branches        

   0.060349641 seconds time elapsed

если я удалю строку

s += A[curIndex+1] + A[size-curIndex-1];

Я получаю следующий вывод от perf:

  Performance counter stats for './cachetests 111111':

    24,079,109      branches                                                    
        39,078      branch-misses             #    0.16% of all branches        

   0.027679521 seconds time elapsed

Что эта линия должна делать с предсказаниями ветвей, когда она даже не является выражением if?

Как я вижу это в первых вызовах ceil(n/2) - 1 test1(), оба оператора if будут ложными. В вызове ceil(n/2)-th значение if(curIndex == ceil(n/2)) будет истинным. В остальных вызовах n-ceil(n/2) первый оператор будет ложным, а второй оператор будет истинным.

Почему Intel не может предсказать такое простое поведение?

Теперь посмотрим на второй случай. Предположим, что A теперь имеет чередующиеся нули и единицы. Мы всегда будем начинать с 0. Поэтому, если n = 9 A будет выглядеть так:

0,1,0,1,0,1,0,1,0

Функция, которую мы будем использовать, следующая:

void test2(int curIndex){
    //A is 0,1,0,1,0,1,0,1,....
    if(curIndex == size-1) return;
    if(A[curIndex] == 1) return;

    test2(curIndex+1);
    test2(curIndex+2);

    s += A[curIndex+1] + A[curIndex+2];

}

И вот весь код эксперимента:

#include <iostream>
#include <fstream>

using namespace std;


int size;
int *A;
int s;

void test2(int curIndex){
    //A is 0,1,0,1,0,1,0,1,....
    if(curIndex == size-1) return;
    if(A[curIndex] == 1) return;

    test2(curIndex+1);
    test2(curIndex+2);

    s += A[curIndex+1] + A[curIndex+2];

}

int main(int argc, char* argv[]){

    size = atoi(argv[1]);
    if(argc!=2){
        cout<<"type ./executable size{odd integer}"<<endl;
        return 1;
    }
    if(size%2!=1){
        cout<<"size must be an odd number"<<endl;
        return 1;
    }
    A = new int[size];
    int i;
    for(i=0;i<size;i++){
        if(i%2==0){
            A[i] = false;
        }
        else{
            A[i] = true;
        }
    }

    for(i=0;i<100;i++) {
        test2(0);
    }
    cout<<s<<endl;

    return 0;
}

Я запускаю perf, используя те же команды, что и раньше:

    Performance counter stats for './cachetests2 111111':

    28,560,183      branches                                                    
        54,204      branch-misses             #    0.19% of all branches        

   0.037134196 seconds time elapsed

И удаление этой строки еще немного улучшило ситуацию:

   Performance counter stats for './cachetests2 111111':

    28,419,557      branches                                                    
        16,636      branch-misses             #    0.06% of all branches        

   0.009977772 seconds time elapsed

Теперь, если мы проанализируем функцию, if(curIndex == size-1) будет false n-1 раз, а if(A[curIndex] == 1) будет чередоваться от true к false.

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

Ответы

Ответ 1

Вот мои мысли об этом, глядя на него некоторое время. Прежде всего, проблема легко воспроизводится с помощью -O2, поэтому лучше использовать это как ссылка, поскольку он генерирует простой нерасширенный код, который легко анализировать. Проблема с -O3 по существу одинакова, она немного менее очевидна.

Итак, для первого случая (полу-нули с полуподобным рисунком) компилятор генерирует этот код:

 0000000000400a80 <_Z5test1i>:
   400a80:       55                      push   %rbp
   400a81:       53                      push   %rbx
   400a82:       89 fb                   mov    %edi,%ebx
   400a84:       48 83 ec 08             sub    $0x8,%rsp
   400a88:       3b 3d 0e 07 20 00       cmp    0x20070e(%rip),%edi        #
   60119c <half>
   400a8e:       74 4f                   je     400adf <_Z5test1i+0x5f>
   400a90:       48 8b 15 09 07 20 00    mov    0x200709(%rip),%rdx        #
   6011a0 <A>
   400a97:       48 63 c7                movslq %edi,%rax
   400a9a:       48 8d 2c 85 00 00 00    lea    0x0(,%rax,4),%rbp
   400aa1:       00 
   400aa2:       83 3c 82 01             cmpl   $0x1,(%rdx,%rax,4)
   400aa6:       74 37                   je     400adf <_Z5test1i+0x5f>
   400aa8:       8d 7f 01                lea    0x1(%rdi),%edi
   400aab:       e8 d0 ff ff ff          callq  400a80 <_Z5test1i>
   400ab0:       89 df                   mov    %ebx,%edi
   400ab2:       f7 d7                   not    %edi
   400ab4:       03 3d ee 06 20 00       add    0x2006ee(%rip),%edi        #
   6011a8 <size>
   400aba:       e8 c1 ff ff ff          callq  400a80 <_Z5test1i>
   400abf:       8b 05 e3 06 20 00       mov    0x2006e3(%rip),%eax        #
   6011a8 <size>
   400ac5:       48 8b 15 d4 06 20 00    mov    0x2006d4(%rip),%rdx        #
   6011a0 <A>
   400acc:       29 d8                   sub    %ebx,%eax
   400ace:       48 63 c8                movslq %eax,%rcx
   400ad1:       8b 44 2a 04             mov    0x4(%rdx,%rbp,1),%eax
   400ad5:       03 44 8a fc             add    -0x4(%rdx,%rcx,4),%eax
   400ad9:       01 05 b9 06 20 00       add    %eax,0x2006b9(%rip)        #
   601198 <s>
   400adf:       48 83 c4 08             add    $0x8,%rsp
   400ae3:       5b                      pop    %rbx
   400ae4:       5d                      pop    %rbp
   400ae5:       c3                      retq   
   400ae6:       66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
   400aed:       00 00 00

Очень просто, что бы вы ожидали - две условные ветки, две звонки. Он дает нам эту (или аналогичную) статистику по Core 2 Duo T6570, AMD Phenom II X4 925 и Core i7-4770:

$ perf stat -B -e branches,branch-misses ./a.out 111111
5555500

 Performance counter stats for './a.out 111111':

        45,216,754      branches                                                    
         5,588,484      branch-misses             #   12.36% of all branches        

       0.098535791 seconds time elapsed

Если вы хотите внести это изменение, переместите назначение перед рекурсивными вызовами:

 --- file.cpp.orig  2016-09-22 22:59:20.744678438 +0300
 +++ file.cpp   2016-09-22 22:59:36.492583925 +0300
 @@ -15,10 +15,10 @@
      if(curIndex == half) return;
      if(A[curIndex] == 1) return;

 +    s += A[curIndex+1] + A[size-curIndex-1];
      test1(curIndex+1);
      test1(size - curIndex - 1);

 -    s += A[curIndex+1] + A[size-curIndex-1];

  }

Изображение меняется:

 $ perf stat -B -e branches,branch-misses ./a.out 111111
 5555500

  Performance counter stats for './a.out 111111':

         39,495,804      branches                                                    
             54,430      branch-misses             #    0.14% of all branches        

        0.039522259 seconds time elapsed

И да, как уже отмечалось, он напрямую связан с хвостовой рекурсией оптимизация, потому что, если вы хотите скомпилировать исправленный код с помощью -fno-optimize-sibling-calls вы получите те же "плохие" результаты. Итак, начнем посмотрите, что у нас есть в сборке с оптимизацией хвостового вызова:

 0000000000400a80 <_Z5test1i>:
   400a80:       3b 3d 16 07 20 00       cmp    0x200716(%rip),%edi        #
   60119c <half>
   400a86:       53                      push   %rbx
   400a87:       89 fb                   mov    %edi,%ebx
   400a89:       74 5f                   je     400aea <_Z5test1i+0x6a>
   400a8b:       48 8b 05 0e 07 20 00    mov    0x20070e(%rip),%rax        #
   6011a0 <A>
   400a92:       48 63 d7                movslq %edi,%rdx
   400a95:       83 3c 90 01             cmpl   $0x1,(%rax,%rdx,4)
   400a99:       74 4f                   je     400aea <_Z5test1i+0x6a>
   400a9b:       8b 0d 07 07 20 00       mov    0x200707(%rip),%ecx        #
   6011a8 <size>
   400aa1:       eb 15                   jmp    400ab8 <_Z5test1i+0x38>
   400aa3:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
   400aa8:       48 8b 05 f1 06 20 00    mov    0x2006f1(%rip),%rax        #
   6011a0 <A>
   400aaf:       48 63 d3                movslq %ebx,%rdx
   400ab2:       83 3c 90 01             cmpl   $0x1,(%rax,%rdx,4)
   400ab6:       74 32                   je     400aea <_Z5test1i+0x6a>
   400ab8:       29 d9                   sub    %ebx,%ecx
   400aba:       8d 7b 01                lea    0x1(%rbx),%edi
   400abd:       8b 54 90 04             mov    0x4(%rax,%rdx,4),%edx
   400ac1:       48 63 c9                movslq %ecx,%rcx
   400ac4:       03 54 88 fc             add    -0x4(%rax,%rcx,4),%edx
   400ac8:       01 15 ca 06 20 00       add    %edx,0x2006ca(%rip)        #
   601198 <s>
   400ace:       e8 ad ff ff ff          callq  400a80 <_Z5test1i>
   400ad3:       8b 0d cf 06 20 00       mov    0x2006cf(%rip),%ecx        #
   6011a8 <size>
   400ad9:       89 c8                   mov    %ecx,%eax
   400adb:       29 d8                   sub    %ebx,%eax
   400add:       89 c3                   mov    %eax,%ebx
   400adf:       83 eb 01                sub    $0x1,%ebx
   400ae2:       39 1d b4 06 20 00       cmp    %ebx,0x2006b4(%rip)        #
   60119c <half>
   400ae8:       75 be                   jne    400aa8 <_Z5test1i+0x28>
   400aea:       5b                      pop    %rbx
   400aeb:       c3                      retq   
   400aec:       0f 1f 40 00             nopl   0x0(%rax)

Он имеет четыре условные ветки с одним вызовом. Поэтому проанализируйте данные мы до сих пор.

Прежде всего, что такое ветвящаяся инструкция с точки зрения процессора? Это любой из call, ret, j* (включая прямой jmp) и loop. call и jmp немного неинтуитивны, но они имеют решающее значение для правильного подсчета.

В целом, мы ожидаем, что эту функцию будем называть 11111100 раз, по одному для каждого элемент, что примерно 11M. В версии с оптимизированной не-хвостом мы видим 45M, инициализация в main() всего 111K, все остальные вещи незначительны, поэтому основной вклад в это число приходит наша функция. Наша функция call -ed, она вычисляет первый je, который является истинным во всех случаях, кроме одного, затем он вычисляет второй je, который является истинной половиной времени, а затем он либо называет себя рекурсивно ( но мы уже подсчитали, что функция вызывается 11M раз) или возвращает (как и после рекурсивных вызовов). Так что 4 команды ветвления на 11M-вызовы, именно то число, которое мы видим. Из них около 5.5M-ветвей пропущено, что предполагает, что эти промахи проистекают из одной неверно предсказанной инструкции, либо то, что оценивалось 11M раз, так и пропущено примерно в 50% случаев или что-то, что оценивалось в течение половины времени и всегда упускалось.

Что у нас есть в версии с оптимизацией хвоста? У нас есть функция, называемая около 5,5 М раз, но теперь каждый вызов вызывает один call, изначально две ветки (первая из них истинна во всех случаях, кроме одного, а вторая всегда ложна из-за наших данных), затем jmp, затем вызов (но мы уже подсчитали, что у нас есть вызовы 5.5M), затем ветвь в 400ae8 и ветка в 400ab6 (всегда истинная из-за наших данных), а затем возвращаемся. Таким образом, в среднем, что четыре условных ветки, один безусловный прыжок, вызов и одна непрямая ветвь (возврат от функции), 5,5 М раз 7, дают нам общий подсчет около 39М ветвей, как мы видим в первичном выходе.

Что мы знаем, так это то, что у процессора нет никаких проблем при прогнозировании событий в потоке с помощью одного вызова функции (хотя эта версия имеет более условные ветки), и у нее есть проблемы с двумя вызовами функций. Таким образом, это говорит о том, что проблема заключается в возвратах функции.

К сожалению, мы очень мало знаем о деталях того, как именно отрасль предикторов наших современных процессоров. Лучший анализ, который я смог найти это, и это говорит о том, что у процессоров есть буфер стека возврата около 16 записей. Если мы снова вернемся к нашим данным с этим находкой, все начнет немного разъяснять.

Когда у вас есть пол-нули с половинным рисунком, вы рекурсивно глубоко в test1(curIndex+1), но затем вы начинаете возвращаться назад и вызов test1(size-curIndex-1). Эта рекурсия никогда не бывает глубже, чем одна вызовом, поэтому для него предсказаны результаты. Но помните, что мы теперь 55555 вызовов в глубину, и процессор помнит последние 16, так что это не удивительно, что он не может догадаться о наших возвращениях, начиная с глубины 55539 уровня, более удивительно, что он может сделать это с помощью оптимизированной с помощью хвоста версии.

Собственно, поведение версии, оптимизированной для хвоста, предполагает, что отсутствует любая другая информация о возврате, процессор просто предполагает, что право один из них - последний. Это также подтверждается поведением версия, оптимизированная для не-хвостов, поскольку она имеет 55555 вызовов вглубь test1(curIndex+1), а затем по возвращении он всегда получает один уровень вглубь test1(size-curIndex-1), поэтому, когда мы находимся от 55555 глубины до 55539 глубины (или независимо от вашего буфера возврата процессора), он вызывает test1(size-curIndex-1), возвращается от этого и не имеет абсолютно никакого информацию о следующем возврате, поэтому он предполагает, что мы должны вернуться к последний увиденный адрес (который является адресом для возврата к test1(size-curIndex-1)), и это, очевидно, неверно. 55539 раз неправильно. С 100 циклов функции, что в точности предсказание ветвления 5.5M мы видим.

Теперь давайте перейдем к вашему альтернативному шаблону и коду для этого. Этот код на самом деле очень разные, если вы хотите проанализировать, как это происходит в глубина. Здесь у вас есть test2(curIndex+1), который всегда возвращается немедленно и ваш test2(curIndex+2), чтобы всегда идти глубже. Таким образом, доходы от test2(curIndex+1) всегда предсказаны отлично (они просто не углубляются достаточно), и когда мы закончим нашу рекурсию в test2(curIndex+2), это всегда возвращается в ту же точку, все 55555 раз, поэтому процессор не имеет проблемы с этим.

Это может быть подтверждено этим небольшим изменением на ваши исходные полуоси с кодом полужидов:

--- file.cpp.orig       2016-09-23 11:00:26.917977032 +0300
+++ file.cpp    2016-09-23 11:00:31.946027451 +0300
@@ -15,8 +15,8 @@
   if(curIndex == half) return;
   if(A[curIndex] == 1) return;

-  test1(curIndex+1);
   test1(size - curIndex - 1);
+  test1(curIndex+1);

   s += A[curIndex+1] + A[size-curIndex-1];

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

$ perf stat -B -e branches,branch-misses ./a.out 111111 
5555500

 Performance counter stats for './a.out 111111':

        45 308 579      branches                                                    
            75 927      branch-misses             #    0,17% of all branches        

       0,026271402 seconds time elapsed

Как и ожидалось, теперь наш первый вызов всегда возвращается немедленно, а второй - 55555, а затем возвращается только в ту же точку.

Теперь, когда это решит, позвольте мне показать что-то в моем рукаве. В одной системе и то есть Core i5-5200U, оригинальные полунуки с оптимизацией без хвоста с половинной версией показывают следующие результаты:

 $ perf stat -B -e branches,branch-misses ./a.out 111111
 5555500

  Performance counter stats for './a.out 111111':

         45 331 670      branches                                                    
             16 349      branch-misses             #    0,04% of all branches        

        0,043351547 seconds time elapsed

Итак, по-видимому, Бродвелл легко справляется с этим шаблоном, что возвращает нас к вопрос о том, насколько мы знаем о логике прогнозирования ветвей нашего современных процессоров.

Ответ 2

Удаление строки s += A[curIndex+1] + A[size-curIndex-1]; позволяет оптимизировать хвостовую рекурсию. Эта оптимизация может произойти только тогда, когда рекурсивный вызов находится в последней строке функции.

https://en.wikipedia.org/wiki/Tail_call

Ответ 3

Интересно, что в первом исполнении у вас на 30% больше ветвей, чем во втором исполнении (32M ветки против 24 Mbranches).

Я создал код сборки для вашего приложения, используя gcc 4.8.5 и те же флаги (плюс -S), и существует значительная разница между сборками. Код с конфликтующим утверждением составляет около 572 строк, а код без одного и того же оператора - всего 409 строк. Ориентируясь на символ _Z5test1i - оформленное имя С++ для test1), подпрограмма длится 367 строк, а второй случай занимает всего 202 строки. Из всех этих строк первый случай содержит 36 ветвей (плюс 15 инструкций вызова), а второй случай содержит 34 ответвления (плюс 1 команда вызова).

Интересно также, что компиляция приложения с помощью -O1 не подвергает этому расхождению между двумя версиями (хотя неверный прогноз ветки выше, около 12%). Использование -O2 показывает разницу между двумя версиями (12% против 3% от неверных прогнозов ветвления).

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

Ответ 4

проблема такова:

if(A[curIndex] == 1) return;

каждый вызов тестовой функции чередует результат этого сравнения из-за некоторых оптимизаций, так как массив является, например, 0,0,0,0,0,1,1,1,1

Другими словами:

curIndex = 0 → A [0] = 0
test1 (curIndex + 1) → curIndex = 1 → A [1] = 0

Но тогда процессорная архитектура МОЖЕТ (это может сильно повлиять, потому что для меня эта оптимизация отключена - i5-6400) имеют функцию runahead (выполняемую по предсказанию ветвления) который выполняет остальные инструкции в конвейере перед входом в ветвь; поэтому он выполнит test1(size - curIndex -1) перед инструкцией о нарушении.

При удалении атрибуции, он вводит другую оптимизацию, как сказал пользователь1850903.

Ответ 5

Следующий фрагмент кода является хвостовым рекурсивным: последняя строка функции не требует вызова, просто ветвь до точки, где функция начинает использовать первый аргумент:

void f(int i) {
    if (i == size) break;
    s += a[i];
    f(i + 1);
}

Однако, если мы сломаем это и сделаем его не-хвостом рекурсивным:

void f(int i) {
    if (i == size) break;
    f(i + 1);
    s += a[i];
}

Существует несколько причин, по которым компилятор не может вывести последний как хвост-рекурсивный, но в примере, который вы указали,

test(A[N]);
test(A[M]);
s += a[N] + a[M];

действуют те же правила. Компилятор не может определить, что это хвост рекурсивный, но тем более он не может этого сделать из-за двух вызовов (см. до и после).

То, что вы ожидаете от компилятора, - это функция, которая выполняет пару простых условных ветвей, два вызова и некоторые загрузки/добавления/хранилища.

Вместо этого компилятор разворачивает этот цикл и генерирует код, который имеет много точек ветвления. Это делается частично потому, что компилятор считает, что он будет более эффективным таким образом (с меньшим количеством ветвей), но отчасти потому, что он уменьшает глубину рекурсии во время выполнения.

int size;
int* A;
int half;
int s;

void test1(int curIndex){
  if(curIndex == half || A[curIndex] == 1) return;
  test1(curIndex+1);
  test1(size-curIndex-1);
  s += A[curIndex+1] + A[size-curIndex-1];
}

дает:

test1(int):
        movl    half(%rip), %edx
        cmpl    %edi, %edx
        je      .L36
        pushq   %r15
        pushq   %r14
        movslq  %edi, %rcx
        pushq   %r13
        pushq   %r12
        leaq    0(,%rcx,4), %r12
        pushq   %rbp
        pushq   %rbx
        subq    $24, %rsp
        movq    A(%rip), %rax
        cmpl    $1, (%rax,%rcx,4)
        je      .L1
        leal    1(%rdi), %r13d
        movl    %edi, %ebp
        cmpl    %r13d, %edx
        je      .L42
        cmpl    $1, 4(%rax,%r12)
        je      .L42
        leal    2(%rdi), %ebx
        cmpl    %ebx, %edx
        je      .L39
        cmpl    $1, 8(%rax,%r12)
        je      .L39
        leal    3(%rdi), %r14d
        cmpl    %r14d, %edx
        je      .L37
        cmpl    $1, 12(%rax,%r12)
        je      .L37
        leal    4(%rdi), %edi
        call    test1(int)
        movl    %r14d, %edi
        notl    %edi
        addl    size(%rip), %edi
        call    test1(int)
        movl    size(%rip), %ecx
        movq    A(%rip), %rax
        movl    %ecx, %esi
        movl    16(%rax,%r12), %edx
        subl    %r14d, %esi
        movslq  %esi, %rsi
        addl    -4(%rax,%rsi,4), %edx
        addl    %edx, s(%rip)
        movl    half(%rip), %edx
.L10:
        movl    %ecx, %edi
        subl    %ebx, %edi
        leal    -1(%rdi), %r14d
        cmpl    %edx, %r14d
        je      .L38
        movslq  %r14d, %rsi
        cmpl    $1, (%rax,%rsi,4)
        leaq    0(,%rsi,4), %r15
        je      .L38
        call    test1(int)
        movl    %r14d, %edi
        notl    %edi
        addl    size(%rip), %edi
        call    test1(int)
        movl    size(%rip), %ecx
        movq    A(%rip), %rax
        movl    %ecx, %edx
        movl    4(%rax,%r15), %esi
        movl    %ecx, %edi
        subl    %r14d, %edx
        subl    %ebx, %edi
        movslq  %edx, %rdx
        addl    -4(%rax,%rdx,4), %esi
        movl    half(%rip), %edx
        addl    s(%rip), %esi
        movl    %esi, s(%rip)
.L13:
        movslq  %edi, %rdi
        movl    12(%rax,%r12), %r8d
        addl    -4(%rax,%rdi,4), %r8d
        addl    %r8d, %esi
        movl    %esi, s(%rip)
.L7:
        movl    %ecx, %ebx
        subl    %r13d, %ebx
        leal    -1(%rbx), %r14d
        cmpl    %edx, %r14d
        je      .L41
        movslq  %r14d, %rsi
        cmpl    $1, (%rax,%rsi,4)
        leaq    0(,%rsi,4), %r15
        je      .L41
        cmpl    %edx, %ebx
        je      .L18
        movslq  %ebx, %rsi
        cmpl    $1, (%rax,%rsi,4)
        leaq    0(,%rsi,4), %r8
        movq    %r8, (%rsp)
        je      .L18
        leal    1(%rbx), %edi
        call    test1(int)
        movl    %ebx, %edi
        notl    %edi
        addl    size(%rip), %edi
        call    test1(int)
        movl    size(%rip), %ecx
        movq    A(%rip), %rax
        movq    (%rsp), %r8
        movl    %ecx, %esi
        subl    %ebx, %esi
        movl    4(%rax,%r8), %edx
        movslq  %esi, %rsi
        addl    -4(%rax,%rsi,4), %edx
        addl    %edx, s(%rip)
        movl    half(%rip), %edx
.L18:
        movl    %ecx, %edi
        subl    %r14d, %edi
        leal    -1(%rdi), %ebx
        cmpl    %edx, %ebx
        je      .L40
        movslq  %ebx, %rsi
        cmpl    $1, (%rax,%rsi,4)
        leaq    0(,%rsi,4), %r8
        je      .L40
        movq    %r8, (%rsp)
        call    test1(int)
        movl    %ebx, %edi
        notl    %edi
        addl    size(%rip), %edi
        call    test1(int)
        movl    size(%rip), %ecx
        movq    A(%rip), %rax
        movq    (%rsp), %r8
        movl    %ecx, %edx
        movl    %ecx, %edi
        subl    %ebx, %edx
        movl    4(%rax,%r8), %esi
        subl    %r14d, %edi
        movslq  %edx, %rdx
        addl    -4(%rax,%rdx,4), %esi
        movl    half(%rip), %edx
        addl    s(%rip), %esi
        movl    %esi, %r8d
        movl    %esi, s(%rip)
.L20:
        movslq  %edi, %rdi
        movl    4(%rax,%r15), %esi
        movl    %ecx, %ebx
        addl    -4(%rax,%rdi,4), %esi
        subl    %r13d, %ebx
        addl    %r8d, %esi
        movl    %esi, s(%rip)
.L16:
        movslq  %ebx, %rbx
        movl    8(%rax,%r12), %edi
        addl    -4(%rax,%rbx,4), %edi
        addl    %edi, %esi
        movl    %esi, s(%rip)
        jmp     .L4
.L45:
        movl    s(%rip), %edx
.L23:
        movslq  %ebx, %rbx
        movl    4(%rax,%r12), %ecx
        addl    -4(%rax,%rbx,4), %ecx
        addl    %ecx, %edx
        movl    %edx, s(%rip)
.L1:
        addq    $24, %rsp
        popq    %rbx
        popq    %rbp
        popq    %r12
        popq    %r13
        popq    %r14
        popq    %r15
.L36:
        rep ret
.L42:
        movl    size(%rip), %ecx
.L4:
        movl    %ecx, %ebx
        subl    %ebp, %ebx
        leal    -1(%rbx), %r14d
        cmpl    %edx, %r14d
        je      .L45
        movslq  %r14d, %rsi
        cmpl    $1, (%rax,%rsi,4)
        leaq    0(,%rsi,4), %r15
        je      .L45
        cmpl    %edx, %ebx
        je      .L25
        movslq  %ebx, %rsi
        cmpl    $1, (%rax,%rsi,4)
        leaq    0(,%rsi,4), %r13
        je      .L25
        leal    1(%rbx), %esi
        cmpl    %edx, %esi
        movl    %esi, (%rsp)
        je      .L26
        cmpl    $1, 8(%rax,%r15)
        je      .L26
        leal    2(%rbx), %edi
        call    test1(int)
        movl    (%rsp), %esi
        movl    %esi, %edi
        notl    %edi
        addl    size(%rip), %edi
        call    test1(int)
        movl    size(%rip), %ecx
        movl    (%rsp), %esi
        movq    A(%rip), %rax
        movl    %ecx, %edx
        subl    %esi, %edx
        movslq  %edx, %rsi
        movl    12(%rax,%r15), %edx
        addl    -4(%rax,%rsi,4), %edx
        addl    %edx, s(%rip)
        movl    half(%rip), %edx
.L26:
        movl    %ecx, %edi
        subl    %ebx, %edi
        leal    -1(%rdi), %esi
        cmpl    %edx, %esi
        je      .L43
        movslq  %esi, %r8
        cmpl    $1, (%rax,%r8,4)
        leaq    0(,%r8,4), %r9
        je      .L43
        movq    %r9, 8(%rsp)
        movl    %esi, (%rsp)
        call    test1(int)
        movl    (%rsp), %esi
        movl    %esi, %edi
        notl    %edi
        addl    size(%rip), %edi
        call    test1(int)
        movl    size(%rip), %ecx
        movl    (%rsp), %esi
        movq    A(%rip), %rax
        movq    8(%rsp), %r9
        movl    %ecx, %edx
        movl    %ecx, %edi
        subl    %esi, %edx
        movl    4(%rax,%r9), %esi
        subl    %ebx, %edi
        movslq  %edx, %rdx
        addl    -4(%rax,%rdx,4), %esi
        movl    half(%rip), %edx
        addl    s(%rip), %esi
        movl    %esi, s(%rip)
.L28:
        movslq  %edi, %rdi
        movl    4(%rax,%r13), %r8d
        addl    -4(%rax,%rdi,4), %r8d
        addl    %r8d, %esi
        movl    %esi, s(%rip)
.L25:
        movl    %ecx, %r13d
        subl    %r14d, %r13d
        leal    -1(%r13), %ebx
        cmpl    %edx, %ebx
        je      .L44
        movslq  %ebx, %rdi
        cmpl    $1, (%rax,%rdi,4)
        leaq    0(,%rdi,4), %rsi
        movq    %rsi, (%rsp)
        je      .L44
        cmpl    %edx, %r13d
        je      .L33
        movslq  %r13d, %rdx
        cmpl    $1, (%rax,%rdx,4)
        leaq    0(,%rdx,4), %r8
        movq    %r8, 8(%rsp)
        je      .L33
        leal    1(%r13), %edi
        call    test1(int)
        movl    %r13d, %edi
        notl    %edi
        addl    size(%rip), %edi
        call    test1(int)
        movl    size(%rip), %ecx
        movq    A(%rip), %rdi
        movq    8(%rsp), %r8
        movl    %ecx, %edx
        subl    %r13d, %edx
        movl    4(%rdi,%r8), %eax
        movslq  %edx, %rdx
        addl    -4(%rdi,%rdx,4), %eax
        addl    %eax, s(%rip)
.L33:
        subl    %ebx, %ecx
        leal    -1(%rcx), %edi
        call    test1(int)
        movl    size(%rip), %ecx
        movq    A(%rip), %rax
        movl    %ecx, %esi
        movl    %ecx, %r13d
        subl    %ebx, %esi
        movq    (%rsp), %rbx
        subl    %r14d, %r13d
        movslq  %esi, %rsi
        movl    4(%rax,%rbx), %edx
        addl    -4(%rax,%rsi,4), %edx
        movl    s(%rip), %esi
        addl    %edx, %esi
        movl    %esi, s(%rip)
.L31:
        movslq  %r13d, %r13
        movl    4(%rax,%r15), %edx
        subl    %ebp, %ecx
        addl    -4(%rax,%r13,4), %edx
        movl    %ecx, %ebx
        addl    %esi, %edx
        movl    %edx, s(%rip)
        jmp     .L23
.L44:
        movl    s(%rip), %esi
        jmp     .L31
.L39:
        movl    size(%rip), %ecx
        jmp     .L7
.L41:
        movl    s(%rip), %esi
        jmp     .L16
.L43:
        movl    s(%rip), %esi
        jmp     .L28
.L38:
        movl    s(%rip), %esi
        jmp     .L13
.L37:
        movl    size(%rip), %ecx
        jmp     .L10
.L40:
        movl    s(%rip), %r8d
        jmp     .L20
s:
half:
        .zero   4
A:
        .zero   8
size:
        .zero   4

Для случая переменных значений, предполагая размер == 7:

test1(curIndex = 0)
{
    if (curIndex == size - 1) return;  // false x1
    if (A[curIndex] == 1) return;  // false x1

    test1(curIndex + 1 => 1) {
        if (curIndex == size - 1) return;  // false x2
        if (A[curIndex] == 1) return;  // false x1 -mispred-> returns
    }

    test1(curIndex + 2 => 2) {
        if (curIndex == size - 1) return; // false x 3
        if (A[curIndex] == 1) return;  // false x2
        test1(curIndex + 1 => 3) {
            if (curIndex == size - 1) return;  // false x3
            if (A[curIndex] == 1) return;  // false x2 -mispred-> returns
        }
        test1(curIndex + 2 => 4) {
            if (curIndex == size - 1) return;  // false x4
            if (A[curIndex] == 1) return; // false x3
            test1(curIndex + 1 => 5) {
                if (curIndex == size - 1) return; // false x5
                if (A[curIndex] == 1) return; // false x3 -mispred-> returns
            }
            test1(curIndex + 2 => 6) {
                if (curIndex == size - 1) return; // false x5 -mispred-> returns
            }
            s += A[5] + A[6];
        }
        s += A[3] + A[4];
    }
    s += A[1] + A[2];
}

И давайте представим случай, когда

size = 11;
A[11] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0 };

test1(0)
  -> test1(1)
       -> test1(2)
            -> test1(3)  -> returns because 1
            -> test1(4)
                 -> test1(5)
                      -> test1(6)
                           -> test1(7) -- returns because 1
                           -> test1(8)
                                -> test1(9) -- returns because 1
                                -> test1(10) -- returns because size-1
                      -> test1(7) -- returns because 1
                 -> test1(6)
                   -> test1(7)
                   -> test1(8)
                        -> test1(9) -- 1
                        -> test1(10) -- size-1
       -> test1(3)  -> returns
  -> test1(2)
       ... as above

или

size = 5;
A[5] = { 0, 0, 0, 0, 1 };

test1(0)
  -> test1(1)
       -> test1(2)
            -> test1(3)
                 -> test1(4)  --  size
                 -> test1(5)  --  UB
            -> test1(4)
       -> test1(3)
            -> test1(4)  -- size
            -> test1(5)  -- UB
  -> test1(2)
       ..

Два случая, которые вы выделили (чередующиеся и полу-шаблоны), являются оптимальными крайними значениями, а компилятор выбрал промежуточный пример, который он попытается обработать наилучшим образом.