Компиляторы создают лучший код для циклов do-while по сравнению с другими типами циклов?

В библиотеке сжатия zlib (которая среди многих других используется в проекте Chromium) есть комментарий, который подразумевает, что цикл do-while в C генерирует «лучший» код для большинства компиляторов. Вот фрагмент кода, где он появляется.

do {
} while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         scan < strend);
/* The funny "do {}" generates better code on most compilers */

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c&l=1225

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

Обновление: Марк Адлер , один из первоначальных авторов, дал небольшой контекст в комментариях.

Прежде всего:

do-whileПетля не то же самое , как while-loop или for-loop.

• whileи forциклы могут вообще не запускать тело цикла.
• do-whileЦикл всегда выполняется тело цикла по крайней мере один раз - он пропускает первоначальную проверку условия.

Так что в этом логическая разница. При этом не все строго этого придерживаются. Циклы whileили forиспользуются довольно часто, даже если гарантируется, что он всегда будет повторяться хотя бы один раз. (Особенно в языках с циклами foreach .)

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

Итак, я отвечу на вопрос:

Если whileцикл гарантированно повторяется хотя бы один раз, есть ли прирост производительности от использования do-whileцикла.

A do-whileпропускает первую проверку условий. Таким образом, остается на одну ветвь меньше и на одно условие меньше.

Если проверка условия do-whileтребует больших затрат, и вы знаете, что гарантированно выполните цикл хотя бы один раз, цикл может быть быстрее.

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

Другими словами, цикл while:

while (condition){
    body
}

Фактически то же самое:

if (condition){
    do{
        body
    }while (condition);
}

Если вы знаете, что вы всегда будете выполнять цикл хотя бы один раз, этот оператор if не имеет значения.

Точно так же на уровне сборки примерно так компилируются разные циклы:

цикл do-while:

start:
    body
    test
    conditional jump to start

цикл while:

    test
    conditional jump to end
start:
    body
    test
    conditional jump to start
end:

Обратите внимание, что условие было продублировано. Альтернативный подход:

    unconditional jump to end
start:
    body
end:
    test
    conditional jump to start

... который обменивает повторяющийся код на дополнительный прыжок.

В любом случае, это все равно хуже обычного do-whileцикла.

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

Но для конкретного примера в вопросе все немного странно, потому что у него пустое тело цикла. Поскольку тела нет, нет никакой логической разницы между whileи do-while.

FWIW, я тестировал это в Visual Studio 2012:

• С пустым телом он фактически генерирует тот же код для whileи do-while. Так что эта часть, вероятно, является пережитком старых времен, когда компиляторы были не такими хорошими.

• Но с непустым телом VS2012 удается избежать дублирования кода условия, но все же генерирует дополнительный условный переход.

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

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

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

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

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

В двух словах (tl; dr):

Я интерпретирую комментарий в коде OP немного по-другому, я думаю, что «лучший код», который, по их утверждениям, наблюдался, был вызван переносом фактической работы в «условие» цикла. Однако я полностью согласен с тем, что он очень специфичен для компилятора и что проведенное ими сравнение, хотя и позволяет получить немного другой код, в основном бессмысленно и, вероятно, устарело, как я покажу ниже.

Детали:

Трудно сказать , что оригинальный автор имел в виду его комментарий по поводу этого do {} whileпроизводящего лучшего кода, но я хотел бы порассуждать в другом направлении , чем то , что был воспитан здесь , - мы считаем , что разница между do {} whileи while {}петли довольно тонкий (один меньше ветвь , как Мистический сказал), но в этом коде есть что-то еще «смешнее», и это помещает всю работу в это сумасшедшее состояние и сохраняет внутреннюю часть пустой ( do {}).

Я пробовал следующий код на gcc 4.8.1 (-O3), и он дает интересную разницу:

#include "stdio.h" 
int main (){
    char buf[10];
    char *str = "hello";
    char *src = str, *dst = buf;

    char res;
    do {                            // loop 1
        res = (*dst++ = *src++);
    } while (res);
    printf ("%s\n", buf);

    src = str;
    dst = buf;
    do {                            // loop 2
    } while (*dst++ = *src++);
    printf ("%s\n", buf);

    return 0; 
}

После компиляции -

00000000004003f0 <main>:
  ... 
; loop 1  
  400400:       48 89 ce                mov    %rcx,%rsi
  400403:       48 83 c0 01             add    $0x1,%rax
  400407:       0f b6 50 ff             movzbl 0xffffffffffffffff(%rax),%edx
  40040b:       48 8d 4e 01             lea    0x1(%rsi),%rcx
  40040f:       84 d2                   test   %dl,%dl
  400411:       88 16                   mov    %dl,(%rsi)
  400413:       75 eb                   jne    400400 <main+0x10>
  ...
;loop 2
  400430:       48 83 c0 01             add    $0x1,%rax
  400434:       0f b6 48 ff             movzbl 0xffffffffffffffff(%rax),%ecx
  400438:       48 83 c2 01             add    $0x1,%rdx
  40043c:       84 c9                   test   %cl,%cl
  40043e:       88 4a ff                mov    %cl,0xffffffffffffffff(%rdx)
  400441:       75 ed                   jne    400430 <main+0x40>
  ...

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

В clang 3.3 (-O3), с другой стороны, оба цикла генерируют этот код из 5 инструкций:

  400520:       8a 88 a0 06 40 00       mov    0x4006a0(%rax),%cl
  400526:       88 4c 04 10             mov    %cl,0x10(%rsp,%rax,1)
  40052a:       48 ff c0                inc    %rax
  40052d:       48 83 f8 05             cmp    $0x5,%rax
  400531:       75 ed                   jne    400520 <main+0x20>

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

Итог - если вы хотите оптимизировать код до наилучшего из возможных (и знаете, как он должен выглядеть), сделайте это прямо в сборке и вырежьте «посредника» (компилятор) из уравнения, но примите во внимание, что более новый компиляторы и более новое HW могут сделать эту оптимизацию устаревшей. В большинстве случаев гораздо лучше просто позволить компилятору делать этот уровень работы за вас и сосредоточиться на оптимизации больших вещей.

Еще один момент, на который следует обратить внимание - количество команд (при условии, что это то, что было после исходного кода OP), ни в коем случае не является хорошим показателем эффективности кода. Не все инструкции были созданы равными, и некоторые из них (например, простые переходы от reg-to-reg) действительно дешевы, так как они оптимизируются процессором. Другая оптимизация может повредить внутренней оптимизации ЦП, поэтому в конечном итоге учитываются только правильные тесты.

whileЦикл часто скомпилирован как do-whileпетля с начальной ветвью к условию, т.е.

    bra $1    ; unconditional branch to the condition
$2:
    ; loop body
$1:
    tst <condition> ; the condition
    brt $2    ; branch if condition true

тогда как компиляция do-whileцикла такая же без начальной ветви. Вы можете видеть из этого, что while()это по своей сути менее эффективно из-за стоимости начальной ветви, которая, однако, оплачивается только один раз. [Сравните с наивным способом реализации, while,который требует как условного перехода, так и безусловного перехода на итерацию.]

Сказав это, на самом деле это не сопоставимые альтернативы. Превращать whileпетлю в do-whileпетлю и наоборот больно . Они делают разные вещи. И в этом случае несколько вызовов методов будет полностью доминировать все , что компилятор сделал с whileпротивdo-while.

Замечание не о выборе управляющего оператора (do vs. while), а о развертывании цикла !!!

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

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

В любом случае, это будет работать, только если длина строки кратна четырем или содержит контрольный элемент (так что две строки гарантированно будут отличаться за strendграницей). Довольно рискованно!

Обсуждение эффективности while и do в данном случае совершенно бессмысленно, поскольку тела нет.

while (Condition)
{
}

а также

do
{
}
while (Condition);

абсолютно эквивалентны.