...

воскресенье, 7 августа 2016 г.

[Перевод] Const и оптимизации в C

Сегодня на /r/C_Programming задали вопрос о влиянии const в C на оптимизацию. Я много раз слышал варианты этого вопроса в течении последних двадцати лет. Лично я обвиняю во всём именование const.


Рассмотрим такую программу:


void foo(const int *);

int
bar(void)
{
    int x = 0;
    int y = 0;
    for (int i = 0; i < 10; i++) {
        foo(&x);
        y += x;  // this load not optimized out
    }
    return y;
}

Функция foo принимает указатель на const, который обещает от имени автора foo что значение x не будет изменено. Может показаться, что компилятор может предположить, что x всегда равен нулю, а значит и y тоже.


Однако, если мы посмотрим на ассемблерный код, генерируемый несколькими разными компиляторами, то увидим, что x загружается при каждой итерации цикла. Вот что выдал gcc 4.9.2 с -O3, с моими комментариями:


bar:
     push   rbp
     push   rbx
     xor    ebp, ebp                ; y = 0
     mov    ebx, 0xa              ; цикл по переменной i
     sub    rsp, 0x18              ; allocate x
     mov    dword [rsp+0xc], 0    ; x = 0

.L0: lea    rdi, [rsp+0xc]        ; вычисляем &x
     call   foo
     add    ebp, dword [rsp+0xc]  ; y += x  (не оптимизировано?)
     sub    ebx, 1
     jne    .L0

     add    rsp, 0x18             ; deallocate x
     mov    eax, ebp              ; возвращаем y
     pop    rbx
     pop    rbp
     ret

clang 3.5 (с -fno-unroll-loops) выдал примерно то же самое, только ebp и ebx поменялись местами, и вычисление &x вынесено из цикла в r14.


Неужели оба компилятора не способны воспользоваться этой полезной информацией? Разве если fooизменит x, это не будет undefined behavior? Как ни странно, ответ — "нет". В этой ситуации, это будет абсолютно верным определением foo.


void
foo(const int *readonly_x)
{
    int *x = (int *)readonly_x;  // cast away const
    (*x)++;
}

Важно помнить, что const — не значит константный. Возьмите себе на заметку, что это неправильное название. Это не инструмент для оптимизации. Он нужен чтобы информировать программиста — а не компилятор — как инструмент, помогающий поймать определенный класс ошибок во время компиляции. Мне нравится, когда его используют в API потому что он сообщает, как функция будет использовать свои аргументы, или как вызывающий должен обращаться с возвращенными указателями. Обычно он недостаточно строгий, чтобы изменить поведение компилятора.


Несмотря на то, что я сказал, иногда компилятор может воспользоваться const для оптимизации. В спецификация C99, в §6.7.3¶5, есть одно предложение об этом:


Если сделана попытка изменить объект объявленный с модификатором const через использование lvalue без модификатора const, поведение неопределенно.


Исходный x был без модификатора const, поэтому это правило не применилось. И нет никакого правила против приведения к не-const типу, чтобы изменить объект который сам по себе не const. Это значит, что вышеприведённое поведение foo это не undefined behavior для этого вызова. Обратите внимание, что неопределенность foo зависит от того, как она была вызвана.


Одним изменением в bar я могу сделать это правило применимым, позволяя оптимизатору поработать.


    const int x = 0;

Компилятор теперь может предположить, что изменение x в foo — это undefined behavior, и потому никогда не происходит. Как бы то ни было, в основном так оптимизатор C рассуждает о ваших программах. Компилятор может предположить, что x никогда не изменяется, позволяя ему оптимизировать и загрузку в каждой итерации, и y.


bar:
     push   rbx
     mov    ebx, 0xa            ; переменная цикла i
     sub    rsp, 0x10           ; allocate x
     mov    dword [rsp+0xc], 0  ; x = 0

.L0: lea    rdi, [rsp+0xc]      ; вычисляем &x
     call   foo
     sub    ebx, 1
     jne    .L0

     add    rsp, 0x10           ; deallocate x
     xor    eax, eax            ; возвращаем 0
     pop    rbx
     ret

Загрузка исчезает, y исчезает, и функция всегда возвращает ноль.


Любопытно, что спецификация позволяет компилятору пойти еще дальше. Он может разместить x где-нибудь вне стека, даже в read-only памяти. Например, он может произвести такую трансформацию:


static int __x = 0;

int
bar(void)
{
    for (int i = 0; i < 10; i++)
        foo(&__x);
    return 0;
}

Или на x86-64 (-fPIC, модель малой памяти), где получается избавиться от еще нескольких инструкций:


section .rodata
x:   dd     0

section .text
bar:
     push   rbx
     mov    ebx, 0xa        ; переменная цикла i

.L0: lea    rdi, [rel x]    ; вычисляем &x
     call   foo
     sub    ebx, 1
     jne    .L0

     xor    eax, eax        ; возвращаем 0
     pop    rbx
     ret

Ни clang, ни gcc не заходят так далеко, видимо потому, что это более опасно для плохо написанного кода.


Даже со специальным правилом о const rule, используйте const для себя и своих товарищей-программистов. Пусть оптимизатор сам для себя решает, что константно, а что нет.

Комментарии (0)

    Let's block ads! (Why?)

    Комментариев нет:

    Отправить комментарий