Могут ли современные компиляторы развертывать циклы for, выраженные с помощью итераторов начала и конца?

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

STL, полностью состоящий из шаблонов, имеет весь код inline. Итак, итераторы произвольного доступа сводятся к указателям уже тогда, когда компилятор начинает применять оптимизации. Одна из причин создания STL заключалась в том, что программисту не нужно было перехитрить компилятор. Вы должны полагаться на то, что STL сделает все правильно, пока не будет доказано обратное.

Конечно, вы все равно должны выбрать правильный инструмент из STL для использования...

Изменить: обсуждался вопрос о том, выполняет ли g++ развертывание цикла. В версиях, которые я использую, развертывание цикла не является частью -O, -O2 или -O3, и я получаю идентичную сборку для последних двух уровней со следующим кодом:

void foo (std::vector<int> &v) {
    volatile int c = 0;
    const std::vector<int>::const_iterator end = v.end();
    for (std::vector<int>::iterator i = v.begin(); i != end; ++i) {
        *i = c++;
    }
}

С соответствующей сборкой -O2 сборки:

_Z3fooRSt6vectorIiSaIiEE:
.LFB435:
        movq    8(%rdi), %rcx
        movq    (%rdi), %rax
        movl    $0, -4(%rsp)
        cmpq    %rax, %rcx
        je      .L4
        .p2align 4,,10
        .p2align 3
.L3:
        movl    -4(%rsp), %edx
        movl    %edx, (%rax)
        addq    $4, %rax
        addl    $1, %edx
        cmpq    %rax, %rcx
        movl    %edx, -4(%rsp)
        jne     .L3
.L4:
        rep
        ret

С добавлением опции -funroll-loops функция расширяется до гораздо большего размера. Но документация предупреждает об этом варианте:

Развернуть циклы, количество итераций которых можно определить во время компиляции или при входе в цикл. -funroll-loops подразумевает -frerun-cse-after-loop. Он также включает полное удаление циклов (т. е. полное удаление циклов с небольшим постоянным числом итераций). Этот параметр увеличивает размер кода и может ускорить его выполнение, а может и нет.

В качестве еще одного аргумента, чтобы отговорить вас от развертывания циклов самостоятельно, я закончу этот ответ иллюстрацией применения Duff's Device к функции foo выше:

void foo_duff (std::vector<int> &v) {
    volatile int c = 0;
    const std::vector<int>::const_iterator end = v.end();
    std::vector<int>::iterator i = v.begin();
    switch ((end - i) % 4) do {
    case 0: *i++ = c++;
    case 3: *i++ = c++;
    case 2: *i++ = c++;
    case 1: *i++ = c++;
    } while (i != end);
}

GCC имеет еще один флаг оптимизации цикла:

-ftree-loop-optimize
Оптимизация циклов для деревьев. Этот флаг включен по умолчанию в -O и выше.

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

Я бы предположил, что независимо от того, МОЖЕТ ли компилятор развернуть цикл с современными конвейерными архитектурами и кэшами, если только ваши «действия» не тривиальны, от этого мало пользы, и во многих случаях это будет ХИТ производительности вместо этого. благо. Если ваши действия нетривиальны, развертывание цикла создаст несколько копий этого нетривиального кода, загрузка которого в кеш займет дополнительное время, что значительно замедлит первую итерацию развернутого цикла. В то же время он удалит из кеша больше кода, который мог быть необходим для выполнения «дела», если он делает какие-либо вызовы функций, которые затем нужно будет снова перезагрузить в кеш. Цель развертывания циклов имела большой смысл до появления конвейерных архитектур без кеша без прогнозирования ветвления, цель которых состояла в том, чтобы уменьшить накладные расходы, связанные с логикой цикла. В настоящее время с аппаратным обеспечением с прогнозированием ветвлений на основе кэша ваш процессор будет хорошо конвейеризирован в следующую итерацию цикла, спекулятивно выполняя код цикла снова, к тому времени, когда вы обнаружите условие выхода i==end, после чего процессор выдаст из этого окончательного спекулятивно выполненного набора результатов. В такой архитектуре развертывание цикла имеет очень мало смысла. Это приведет к дальнейшему раздуванию кода практически без пользы.

Краткий ответ: да. Он будет разворачиваться настолько, насколько это возможно. В вашем случае это зависит от того, как вы, очевидно, определяете end (я предполагаю, что ваш пример является общим). Мало того, что большинство современных компиляторов разворачиваются, они также векторизуют и выполняют другие оптимизации, которые часто выбивают ваши собственные решения из воды.

Итак, я говорю: не оптимизируйте преждевременно! Просто шучу :)

Простой ответ: обычно НЕТ! По крайней мере, когда дело доходит до полного развертывания цикла.

Давайте проверим развертывание цикла на этой простой структуре с грязным кодом (в целях тестирования).

struct Test
{
    Test(): begin(arr), end(arr + 4) {}

    double * begin;
    double * end;
    double arr[4];
};

Сначала возьмем цикл со счетчиком и скомпилируем его без каких-либо оптимизаций.

double counted(double param, Test & d)
{
    for (int i = 0; i < 4; i++)
        param += d.arr[i];
    return param;
}

Вот что выдает gcc 4.9.

counted(double, Test&):
    pushq   %rbp
    movq    %rsp, %rbp
    movsd   %xmm0, -24(%rbp)
    movq    %rdi, -32(%rbp)
    movl    $0, -4(%rbp)
    jmp .L2
.L3:
    movq    -32(%rbp), %rax
    movl    -4(%rbp), %edx
    movslq  %edx, %rdx
    addq    $2, %rdx
    movsd   (%rax,%rdx,8), %xmm0
    movsd   -24(%rbp), %xmm1
    addsd   %xmm0, %xmm1
    movq    %xmm1, %rax
    movq    %rax, -24(%rbp)
    addl    $1, -4(%rbp)
.L2:
    cmpl    $3, -4(%rbp)
    jle .L3
    movq    -24(%rbp), %rax
    movq    %rax, -40(%rbp)
    movsd   -40(%rbp), %xmm0
    popq    %rbp
    ret

Как и ожидалось, цикл не был развёрнут, а так как оптимизаций не производилось, код в целом очень многословный. Теперь включим флаг -O3. Произведена разборка:

counted(double, Test&):
    addsd   16(%rdi), %xmm0
    addsd   24(%rdi), %xmm0
    addsd   32(%rdi), %xmm0
    addsd   40(%rdi), %xmm0
    ret

Вуаля, на этот раз цикл развернулся.

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

double iterated(double param, Test & d)
{
  for (double * it = d.begin; it != d.end; ++it)
    param += *it;
  return param;
}

По-прежнему используя флаг -O3, давайте посмотрим на дизассемблирование.

iterated(double, Test&):
    movq    (%rdi), %rax
    movq    8(%rdi), %rdx
    cmpq    %rdx, %rax
    je  .L3
.L4:
    addsd   (%rax), %xmm0
    addq    $8, %rax
    cmpq    %rdx, %rax
    jne .L4
.L3:
    rep ret

Код выглядит лучше, чем в самом первом случае, т.к. оптимизации были проведены, но на этот раз цикл не развернут!

А как насчет флагов funroll-loops и funroll-all-loops? Они будут давать результат, подобный этому

iterated(double, Test&):
    movq    (%rdi), %rsi
    movq    8(%rdi), %rcx
    cmpq    %rcx, %rsi
    je  .L3
    movq    %rcx, %rdx
    leaq    8(%rsi), %rax
    addsd   (%rsi), %xmm0
    subq    %rsi, %rdx
    subq    $8, %rdx
    shrq    $3, %rdx
    andl    $7, %edx
    cmpq    %rcx, %rax
    je  .L43
    testq   %rdx, %rdx
    je  .L4
    cmpq    $1, %rdx
    je  .L29
    cmpq    $2, %rdx
    je  .L30
    cmpq    $3, %rdx
    je  .L31
    cmpq    $4, %rdx
    je  .L32
    cmpq    $5, %rdx
    je  .L33
    cmpq    $6, %rdx
    je  .L34
    addsd   (%rax), %xmm0
    leaq    16(%rsi), %rax
.L34:
    addsd   (%rax), %xmm0
    addq    $8, %rax
.L33:
    addsd   (%rax), %xmm0
    addq    $8, %rax
.L32:
    addsd   (%rax), %xmm0
    addq    $8, %rax
.L31:
    addsd   (%rax), %xmm0
    addq    $8, %rax
.L30:
    addsd   (%rax), %xmm0
    addq    $8, %rax
.L29:
    addsd   (%rax), %xmm0
    addq    $8, %rax
    cmpq    %rcx, %rax
    je  .L44
.L4:
    addsd   (%rax), %xmm0
    addq    $64, %rax
    addsd   -56(%rax), %xmm0
    addsd   -48(%rax), %xmm0
    addsd   -40(%rax), %xmm0
    addsd   -32(%rax), %xmm0
    addsd   -24(%rax), %xmm0
    addsd   -16(%rax), %xmm0
    addsd   -8(%rax), %xmm0
    cmpq    %rcx, %rax
    jne .L4
.L3:
    rep ret
.L44:
    rep ret
.L43:
    rep ret

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

Однако повторный цикл будет развернут, если объект Test не является аргументом функции.

double iteratedLocal(double param)
{
  Test d;
  for (double * it = d.begin; it != d.end; ++it)
    param += *it;
  return param;
}

Разборка производится только с флагом -O3:

iteratedLocal(double):
    addsd   -40(%rsp), %xmm0
    addsd   -32(%rsp), %xmm0
    addsd   -24(%rsp), %xmm0
    addsd   -16(%rsp), %xmm0
    ret

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

Однако структура Test размещается статически. Сложнее обстоит дело с динамически размещаемыми структурами, такими как std::vector. Из моих наблюдений над измененной структурой Test, которая напоминает динамически размещаемый контейнер, похоже, что gcc изо всех сил пытается развернуть циклы, но в большинстве случаев сгенерированный код не так прост, как приведенный выше.

Поскольку вы просите другие компиляторы, вот вывод clang 3.4.1 (флаг -O3)

counted(double, Test&):                      # @counted(double, Test&)
    addsd   16(%rdi), %xmm0
    addsd   24(%rdi), %xmm0
    addsd   32(%rdi), %xmm0
    addsd   40(%rdi), %xmm0
    ret

iterated(double, Test&):                     # @iterated(double, Test&)
    movq    (%rdi), %rax
    movq    8(%rdi), %rcx
    cmpq    %rcx, %rax
    je  .LBB1_2
.LBB1_1:                                # %.lr.ph
    addsd   (%rax), %xmm0
    addq    $8, %rax
    cmpq    %rax, %rcx
    jne .LBB1_1
.LBB1_2:                                # %._crit_edge
    ret

iteratedLocal(double):                     # @iteratedLocal(double)
    leaq    -32(%rsp), %rax
    movq    %rax, -48(%rsp)
    leaq    (%rsp), %rax
    movq    %rax, -40(%rsp)
    xorl    %eax, %eax
    jmp .LBB2_1
.LBB2_2:                                # %._crit_edge4
    movsd   -24(%rsp,%rax), %xmm1
    addq    $8, %rax
.LBB2_1:                                # =>This Inner Loop Header: Depth=1
    movaps  %xmm0, %xmm2
    cmpq    $24, %rax
    movaps  %xmm1, %xmm0
    addsd   %xmm2, %xmm0
    jne .LBB2_2
    ret

Intel icc 13.01 (флаг -O3)

counted(double, Test&):
        addsd     16(%rdi), %xmm0                               #24.5
        addsd     24(%rdi), %xmm0                               #24.5
        addsd     32(%rdi), %xmm0                               #24.5
        addsd     40(%rdi), %xmm0                               #24.5
        ret                                                     #25.10
iterated(double, Test&):
        movq      (%rdi), %rdx                                  #30.26
        movq      8(%rdi), %rcx                                 #30.41
        cmpq      %rcx, %rdx                                    #30.41
        je        ..B3.25       # Prob 50%                      #30.41
        subq      %rdx, %rcx                                    #30.7
        movb      $0, %r8b                                      #30.7
        lea       7(%rcx), %rax                                 #30.7
        sarq      $2, %rax                                      #30.7
        shrq      $61, %rax                                     #30.7
        lea       7(%rax,%rcx), %rcx                            #30.7
        sarq      $3, %rcx                                      #30.7
        cmpq      $16, %rcx                                     #30.7
        jl        ..B3.26       # Prob 10%                      #30.7
        movq      %rdx, %rdi                                    #30.7
        andq      $15, %rdi                                     #30.7
        je        ..B3.6        # Prob 50%                      #30.7
        testq     $7, %rdi                                      #30.7
        jne       ..B3.26       # Prob 10%                      #30.7
        movl      $1, %edi                                      #30.7
..B3.6:                         # Preds ..B3.5 ..B3.3
        lea       16(%rdi), %rax                                #30.7
        cmpq      %rax, %rcx                                    #30.7
        jl        ..B3.26       # Prob 10%                      #30.7
        movq      %rcx, %rax                                    #30.7
        xorl      %esi, %esi                                    #30.7
        subq      %rdi, %rax                                    #30.7
        andq      $15, %rax                                     #30.7
        negq      %rax                                          #30.7
        addq      %rcx, %rax                                    #30.7
        testq     %rdi, %rdi                                    #30.7
        jbe       ..B3.11       # Prob 2%                       #30.7
..B3.9:                         # Preds ..B3.7 ..B3.9
        addsd     (%rdx,%rsi,8), %xmm0                          #31.9
        incq      %rsi                                          #30.7
        cmpq      %rdi, %rsi                                    #30.7
        jb        ..B3.9        # Prob 82%                      #30.7
..B3.11:                        # Preds ..B3.9 ..B3.7
        pxor      %xmm6, %xmm6                                  #28.12
        movaps    %xmm6, %xmm7                                  #28.12
        movaps    %xmm6, %xmm5                                  #28.12
        movsd     %xmm0, %xmm7                                  #28.12
        movaps    %xmm6, %xmm4                                  #28.12
        movaps    %xmm6, %xmm3                                  #28.12
        movaps    %xmm6, %xmm2                                  #28.12
        movaps    %xmm6, %xmm1                                  #28.12
        movaps    %xmm6, %xmm0                                  #28.12
..B3.12:                        # Preds ..B3.12 ..B3.11
        addpd     (%rdx,%rdi,8), %xmm7                          #31.9
        addpd     16(%rdx,%rdi,8), %xmm6                        #31.9
        addpd     32(%rdx,%rdi,8), %xmm5                        #31.9
        addpd     48(%rdx,%rdi,8), %xmm4                        #31.9
        addpd     64(%rdx,%rdi,8), %xmm3                        #31.9
        addpd     80(%rdx,%rdi,8), %xmm2                        #31.9
        addpd     96(%rdx,%rdi,8), %xmm1                        #31.9
        addpd     112(%rdx,%rdi,8), %xmm0                       #31.9
        addq      $16, %rdi                                     #30.7
        cmpq      %rax, %rdi                                    #30.7
        jb        ..B3.12       # Prob 82%                      #30.7
        addpd     %xmm6, %xmm7                                  #28.12
        addpd     %xmm4, %xmm5                                  #28.12
        addpd     %xmm2, %xmm3                                  #28.12
        addpd     %xmm0, %xmm1                                  #28.12
        addpd     %xmm5, %xmm7                                  #28.12
        addpd     %xmm1, %xmm3                                  #28.12
        addpd     %xmm3, %xmm7                                  #28.12
        movaps    %xmm7, %xmm0                                  #28.12
        unpckhpd  %xmm7, %xmm0                                  #28.12
        addsd     %xmm0, %xmm7                                  #28.12
        movaps    %xmm7, %xmm0                                  #28.12
..B3.14:                        # Preds ..B3.13 ..B3.26
        lea       1(%rax), %rsi                                 #30.7
        cmpq      %rsi, %rcx                                    #30.7
        jb        ..B3.25       # Prob 50%                      #30.7
        subq      %rax, %rcx                                    #30.7
        cmpb      $1, %r8b                                      #30.7
        jne       ..B3.17       # Prob 50%                      #30.7
..B3.16:                        # Preds ..B3.17 ..B3.15
        xorl      %r8d, %r8d                                    #30.7
        jmp       ..B3.21       # Prob 100%                     #30.7
..B3.17:                        # Preds ..B3.15
        cmpq      $2, %rcx                                      #30.7
        jl        ..B3.16       # Prob 10%                      #30.7
        movq      %rcx, %r8                                     #30.7
        xorl      %edi, %edi                                    #30.7
        pxor      %xmm1, %xmm1                                  #28.12
        lea       (%rdx,%rax,8), %rsi                           #31.19
        andq      $-2, %r8                                      #30.7
        movsd     %xmm0, %xmm1                                  #28.12
..B3.19:                        # Preds ..B3.19 ..B3.18
        addpd     (%rsi,%rdi,8), %xmm1                          #31.9
        addq      $2, %rdi                                      #30.7
        cmpq      %r8, %rdi                                     #30.7
        jb        ..B3.19       # Prob 82%                      #30.7
        movaps    %xmm1, %xmm0                                  #28.12
        unpckhpd  %xmm1, %xmm0                                  #28.12
        addsd     %xmm0, %xmm1                                  #28.12
        movaps    %xmm1, %xmm0                                  #28.12
..B3.21:                        # Preds ..B3.20 ..B3.16
        cmpq      %rcx, %r8                                     #30.7
        jae       ..B3.25       # Prob 2%                       #30.7
        lea       (%rdx,%rax,8), %rax                           #31.19
..B3.23:                        # Preds ..B3.23 ..B3.22
        addsd     (%rax,%r8,8), %xmm0                           #31.9
        incq      %r8                                           #30.7
        cmpq      %rcx, %r8                                     #30.7
        jb        ..B3.23       # Prob 82%                      #30.7
..B3.25:                        # Preds ..B3.23 ..B3.21 ..B3.14 ..B3.1
        ret                                                     #32.14
..B3.26:                        # Preds ..B3.2 ..B3.6 ..B3.4    # Infreq
        movb      $1, %r8b                                      #30.7
        xorl      %eax, %eax                                    #30.7
        jmp       ..B3.14       # Prob 100%                     #30.7
iteratedLocal(double):
        lea       -8(%rsp), %rax                                #8.13
        lea       -40(%rsp), %rdx                               #7.11
        cmpq      %rax, %rdx                                    #33.41
        je        ..B4.15       # Prob 50%                      #33.41
        movq      %rax, -48(%rsp)                               #32.12
        movq      %rdx, -56(%rsp)                               #32.12
        xorl      %eax, %eax                                    #33.7
..B4.13:                        # Preds ..B4.11 ..B4.13
        addsd     -40(%rsp,%rax,8), %xmm0                       #34.9
        incq      %rax                                          #33.7
        cmpq      $4, %rax                                      #33.7
        jb        ..B4.13       # Prob 82%                      #33.7
..B4.15:                        # Preds ..B4.13 ..B4.1
        ret                                                     #35.14

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

double countedDep(double param, Test & d)
{
    for (int i = 0; i < d.size; i++)
        param += d.arr[i];
    return param;
}

Такой шлейф и не развернется.