Const и оптимизации в C

Original author: Chris Wellons
  • Translation

Сегодня на /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 для себя и своих товарищей-программистов. Пусть оптимизатор сам для себя решает, что константно, а что нет.

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 28

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


    По-моему тут все хорошо

    Судя по объявлению foo — глобальная нестатическая ф-ция, т.е. мы не знаем что там происходит и не знаем «смоет» она регистры или нет (те, что можно не сохранять).

    А «x» — локальная переменная, выделенная на стеке.

    «x» передается в foo одним из аргументов (через стек или регистр).
    Но при этом foo не обязана по возвращению восстановить это входное значение «x».

    Поэтому, компилятор перестраховывается и делает повторную загрузку.
      +1
      Для того, чтобы узнать, «смоет или нет» — есть calling convention.
        0
        «x» передается в foo одним из аргументов (через стек или регистр).
        В foo передается не x, а указатель на x.
        Поэтому, компилятор перестраховывается и делает повторную загрузку.
        Идея в том, что внутри bar x не меняется, а в foo передается через указатель на константу, поэтому «вроде как» внутри этой функции тоже не может менятся. Из этого компилятор должен бы сделать вывод, что x всегда 0 и нет никакого смысла прибавлять этот 0 к y.
          0
          Да, признаю, про указатель не доглядел.
        0
        В последнее время меня интересует вопрос о влиянии const на время компиляции. Логика заключается в следующем: если компилятору сообщить что переменная определена только для чтения, то это должно отсеять некоторые заведомо некорректные ветки в процессе оптимизации, а следовательно и сократить время работы компилятора.
          0
          Заведомо некорректные ветки приведут к ошибке компиляции.
            0
            Вероятно, я неверно выразился.
            Скажем, компилятор проверяет можно ли «выбросить» переменную (в предположенни что она используется в данной области видимости, но не изменяется). Если переменную определить без «const» то придется просмотреть всю область видимости чтобы убедиться в возможности такого действия, в противном случае просматривать область видимости не придется (хотя это еще вопрос — надо же определить, что переменная не подвергается модификации).
              0
              Всё равно придётся просматривать всю область видимости на наличие const_cast и (). Да даже если и выкидывать, время компиляции обычно итак меньше времени оптимизации и компоновки, особенно если кодогенерация отложена на этап компоновки.
                +3
                Нетушки. Если кто-то скинул const при помощи const_cast и потом попытался записать в полученную сущность, компилятор может с превеликим удовольствием влепить UB:

                $5.2.11/7 — "[Note: Depending on the type of the object, a write operation through the pointer, lvalue or pointer to data member resulting from a const_cast that casts away a const-qualifier68) may produce undefined behavior (7.1.5.1). ]"

                В зависимости от типа объекта, операция записи в указатель, ссылку или указатель на поле данных, полученные путем снятия квалификатора const с помощью const_cast, может привести к неопределенному поведению.
                  +1
                  Т.к. это UB, то точно ничего не скажу, но если говорить о практическом использовании, то если объект изначально не константный, то использовать const_cast относительно безопасно. Т.е. если неконстантный объект передать в функцию по указателю на константу, то от избавление от константности ничего плохого может не сделать.
                  И вообще, мы тут спорим о том, как кошернее говнокодить. Не будем так.)
          +5
          Константы это хорошо.
          Серьезно
          int main(const int argc, const char *const *const argv) {}
          
            +1
            что Вы хотите этим сказать?
              0
              Жуткое наследие ради экономии сотни байт памяти.
              0
              Конечно незначительная мелочь, но можно исправить. В самом начале статьи код вставлен не как С, и поэтому все что после символа ";" в объявлении цикла for воспринимается как комментарий.
              • UFO just landed and posted this here
                  +1
                  Если начнёте писать для Embedded быстро подружитесь.
                    0
                    В embedded быстро начинаешь дружить с volatile, чем с const
                    +5
                    за 10 лет не освоить const? Даже как-то верится с трудом
                    +2
                    Стандарт написан абсолютно правильно, а всю статью можно свести к одному абзацу:
                    Неважно, что написано в объявлении функции, важно, что фактически в неё передаётся здесь и сейчас.
                    Был бы x изначально объявлен как const, то все оптимизации бы сработали, а за трюк с const_cast функция foo получила бы по башке (то самое UB).
                    Т.е. компилятор/оптимизатор смотрит не на декларации о намерениях, а на факты. Что и должно быть.
                      0
                      На мой взгляд, суть статьи в том, что компилятор не имеет права делать предположение (и соответственно, проводить исходя из этого какие-то оптимизации), что если нечто передается внутрь функции по указателю на константу (константной ссылке), то оно внутри этой функции по этому указателю не будет изменено (естественно, в том случае, когда реализацию функции он посмотреть не может). Это довольно контринтуитивно, хотя и логично, если вспомнить о наличии функционала аля const_cast, которым мы должны иметь возможность воспользоваться.
                        0
                        Ладно, на пальцах. В статье слишком упростили и «выкинули вместе с водой ребёнка».
                        Предположим, у нас есть некая железяка — пылесос или марсоход, неважно. И мы пишем под неё под шланг или gcc
                        1. Есть внешняя либа от разработчиков железа, предоставляющая функцию foo(const int*)
                        2. Либа, на самом деле, написана на асме или чём-то таком, где про const не слышали, но сделали extern «C» void foo(...)
                        3. Предположим, аргумент foo — нифига не int*, а указатель на какую-нибудь хитромудрую структуру. Обычно в жизни так и бывает, но в статье упростили.
                        4. Так-то вообще эта структура const, но для целей отладки в неё добавили пару отладочных полей. Ну там счетчиков, не знаю чего. Типа mutable-полей в С++. Есть одна версия *.h файлов, но две версии либы — «релиз» и «дебаг». И в дебаге const_cast неизбежен. Но компилятор видит только хэдеры и решает по факту.
                        5. В дебаг-версии всё работает. Заливаем код в ROM для пылесоса или марсохода, отправляем в релиз… и опа былинный фейл.
                      +4
                      А еще такой модификатор говорит линковщику перенести данные во Flash сектора, если речь идет о встраиваемых системах. В микроконтроллерах процедура изменения flash-секторов несколько сложнее, особенно для более ранних поколений, где вообще ПЗУ прошивалась ультрафиолетом. Но то было раньше, а сейчас это часто используется для указания места хранения больших таблиц данных, например значений тригонометрических функций. Можно конечно и через линковщик выделить, но приписать const гораздо быстрее. Обычно, в МК ram-памяти значительно меньше, чем flash`ки. Так что для embedded систем const очень даже константный, а не просто в помощь программисту.
                        0
                        Да, в нормальных микроконтроллерах достаточно указать Const, и данные лежат во флэше. А вот AVR не поймет — ему надо для этого указывать атрибут PROGMEM (с адресацией там намудрили).
                          0
                          Когда «PROGMEM =» а когда и "=PSTR()", и читать потом через «pgm_read_byte()». А если нужно прочитать int… но в принципе тоже ничего, а вот в MikroC нужно вручную сказать по какому адресу будет лежать массив в flash.
                        +3
                        в с++ в некоторых случаях (например, так реализованы контейнеры в Qt) «лишний» const позволит вызвать правильную, более быструю перегрузку того или иного метода. Поэтому эффект на производительность всё-таки имеется. Ну а в большинстве случаев это просто дополнительный предохранитель от стрельбы себе в ногу. WinAPI, кстати, много где грешит тем, что принимает неконстантные указатели на неизменяемые строки.
                          –5
                          К сожалению, нормальная перегрузка const/не-const функций в плюсах так и не описана. Слишком сложно получается.Ну т.е. где-то оно работает, но в слишком особенных случаях на особенных компиляторах. Вот так взять и написать два метода, один из которых будет конст, а второй — нет, и чотбы оно автоматически выбиралось — нельзя.
                            0
                            в одну сторону то точно везде работает: не может же для const объекта вызваться мутирующий метод…
                          0
                          Еще очень хорошая статья по const: https://habrahabr.ru/post/301332/

                          Only users with full accounts can post comments. Log in, please.