Почему const не ускоряет код на С-C++?

в 10:28, , рубрики: C, c++, Анализ и проектирование систем, Блог компании Mail.Ru Group, высокая производительность, никто не читает теги, оптимизация
Почему const не ускоряет код на С-C++? - 1

Несколько месяцев назад я упомянул в одном посте, что это миф, будто бы const помогает включать оптимизации компилятора в C и C++. Я решил, что нужно объяснить это утверждение, особенно потому, что раньше я сам верил в этот миф. Начну с теории и искусственных примеров, а затем перейду к экспериментам и бенчмаркам на реальной кодовой базе — SQLite.

Простой тест

Начнём с, как мне казалось, самого простого и очевидного примера ускорения кода на С при помощи const. Допустим, у нас есть два объявления функций:

void func(int *x);
void constFunc(const int *x);

И, предположим, есть две версии кода:

void byArg(int *x)
{
  printf("%dn", *x);
  func(x);
  printf("%dn", *x);
}

void constByArg(const int *x)
{
  printf("%dn", *x);
  constFunc(x);
  printf("%dn", *x);
}

Чтобы выполнить printf(), процессор должен через указатель извлечь из памяти значение *x. Очевидно, что выполнение constByArg() может слегка ускориться, поскольку компилятору известно, что *x является константой, поэтому нет нужды загружать её значение снова, после того как это сделала constFunc(). Правильно? Давайте посмотрим ассемблерный код, сгенерированный GCC со включёнными оптимизациями:

$ gcc -S -Wall -O3 test.c
$ view test.s

А вот полный результат на ассемблере для byArg():

byArg:
.LFB23:
    .cfi_startproc
    pushq   %rbx
    .cfi_def_cfa_offset 16
    .cfi_offset 3, -16
    movl    (%rdi), %edx
    movq    %rdi, %rbx
    leaq    .LC0(%rip), %rsi
    movl    $1, %edi
    xorl    %eax, %eax
    call    __printf_chk@PLT
    movq    %rbx, %rdi
    call    func@PLT  # The only instruction that's different in constFoo
    movl    (%rbx), %edx
    leaq    .LC0(%rip), %rsi
    xorl    %eax, %eax
    movl    $1, %edi
    popq    %rbx
    .cfi_def_cfa_offset 8
    jmp __printf_chk@PLT
    .cfi_endproc

Единственное различие между ассемблерным кодом, сгенерированным для byArg() и constByArg(), заключается в том, что у constByArg() есть call constFunc@PLT, как в исходном коде. Сам const не привносит никаких различий.

Ладно, это был GCC. Возможно, нам нужен компилятор поумнее. Скажем, Clang.

$ clang -S -Wall -O3 -emit-llvm test.c
$ view test.ll

Вот промежуточный код. Он компактнее ассемблера, и я отброшу обе функции, чтобы вам было понятнее, что я имею в виду под «никакой разницы, за исключением вызова»:

; Function Attrs: nounwind uwtable
define dso_local void @byArg(i32*) local_unnamed_addr #0 {
  %2 = load i32, i32* %0, align 4, !tbaa !2
  %3 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %2)
  tail call void @func(i32* %0) #4
  %4 = load i32, i32* %0, align 4, !tbaa !2
  %5 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4)
  ret void
}

; Function Attrs: nounwind uwtable
define dso_local void @constByArg(i32*) local_unnamed_addr #0 {
  %2 = load i32, i32* %0, align 4, !tbaa !2
  %3 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %2)
  tail call void @constFunc(i32* %0) #4
  %4 = load i32, i32* %0, align 4, !tbaa !2
  %5 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4)
  ret void
}

Вариант, который (типа) работает

А вот код, в котором наличие const действительно имеет значение:

void localVar()
{
  int x = 42;
  printf("%dn", x);
  constFunc(&x);
  printf("%dn", x);
}

void constLocalVar()
{
  const int x = 42;  // const on the local variable
  printf("%dn", x);
  constFunc(&x);
  printf("%dn", x);
}

Ассемблерный код для localVar(), который содержит две инструкции, оптимизированные за пределами constLocalVar():

localVar: 
.LFB25:
    .cfi_startproc
    subq    $24, %rsp
    .cfi_def_cfa_offset 32
    movl    $42, %edx
    movl    $1, %edi
    movq    %fs:40, %rax
    movq    %rax, 8(%rsp)
    xorl    %eax, %eax
    leaq    .LC0(%rip), %rsi
    movl    $42, 4(%rsp)
    call    __printf_chk@PLT
    leaq    4(%rsp), %rdi
    call    constFunc@PLT
    movl    4(%rsp), %edx  # not in constLocalVar()
    xorl    %eax, %eax
    movl    $1, %edi
    leaq    .LC0(%rip), %rsi  # not in constLocalVar()
    call    __printf_chk@PLT
    movq    8(%rsp), %rax
    xorq    %fs:40, %rax
    jne .L9
    addq    $24, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 8
    ret
.L9:
    .cfi_restore_state
    call    __stack_chk_fail@PLT
    .cfi_endproc

Промежуточный код LLVM немножко чище. load перед вторым вызовом printf() была оптимизирована за пределами constLocalVar():

; Function Attrs: nounwind uwtable
define dso_local void @localVar() local_unnamed_addr #0 {
  %1 = alloca i32, align 4
  %2 = bitcast i32* %1 to i8*
  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %2) #4
  store i32 42, i32* %1, align 4, !tbaa !2
  %3 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 42)
  call void @constFunc(i32* nonnull %1) #4
  %4 = load i32, i32* %1, align 4, !tbaa !2
  %5 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4)
  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %2) #4
  ret void
}

Итак, constLocalVar() успешно проигнорировала перезагрузку *x, но вы могли заметить нечто странное: в телах localVar() и constLocalVar()один и тот же вызов constFunc(). Если компилятор может сообразить, что constFunc() не модифицировала *x в constLocalVar(), то почему он не может понять, что тот же самый вызов функции не модифицировал *x в localVar()?

Объяснение связано с тем, почему const в С непрактично использовать в качестве оптимизации. В C у const есть, по сути, два возможных смысла:

  • она может означать, что переменная — это доступный только для чтения псевдоним каких-то данных, которые могут быть константой, а могут и не быть.
  • либо она может означать, что переменная действительно является константой. Если вы отвяжете const от указателя на константное значение, а потом запишете в неё, то получите неопределённое поведение. С другой стороны, проблем не будет, если const является указателем на значение, не являющееся константой.

Вот поясняющий пример реализации constFunc():

// x is just a read-only pointer to something that may or may not be a constant
void constFunc(const int *x)
{
  // local_var is a true constant
  const int local_var = 42;

  // Definitely undefined behaviour by C rules
  doubleIt((int*)&local_var);
  // Who knows if this is UB?
  doubleIt((int*)x);
}

void doubleIt(int *x)
{
  *x *= 2;
}

localVar() дала constFunc() указатель const на не-const переменную. Поскольку изначально переменная не была const, то constFunc() может оказаться лжецом и принудительно модифицирует переменную без ицициации UB. Поэтому компилятор не может предполагать, что после возвращения constFunc() переменная будет иметь такое же значение. Переменная в constLocalVar() действительно является const, так что компилятор не может предполагать, что она не будет изменена, поскольку на этот раз она будет UB для constFunc(), чтобы компилятор отвязал const и записал в переменную.

Функции byArg() и constByArg() из первого примера безнадёжны, потому что компилятор никак не может узнать, действительно ли *x является const.

Но откуда взялась несогласованность? Если компилятор может предположить, что constFunc() не меняет свой аргумент, будучи вызванной из constLocalVar(), то он может применять те же оптимизации и к вызовам constFunc(), верно? Нет. Компилятор не может предположить, что constLocalVar() вообще когда-либо будет вызвана. И если не будет (например, потому что это просто какой-то дополнительный результат работы генератора кода или макроса), то constFunc() может втихую изменить данные, не инициировав UB.

Возможно, вам потребуется несколько раз прочитать приведённые выше примеры и объяснение. Не переживайте, что это звучит абсурдно — так и есть. К сожалению, запись в переменные const является худшей разновидностью UB: чаще всего компилятор даже не знает, будет ли это UB. Поэтому, когда компилятор видит const, он должен исходить из того, что кто-то где-то может поменять его, а значит компилятор не может использовать const для оптимизации. На практике это справедливо, потому что немало реального кода на С содержит отказ от const в стиле «я знаю, что делаю».

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

int x = 42, y = 0;
printf("%d %dn", x, y);
y += x;
printf("%d %dn", x, y);

Итак, const почти бесполезен для оптимизации, потому что:

  1. За несколькими исключениями, компилятор вынужден игнорировать его, поскольку какой-нибудь код может на законных основаниях отвязать const.
  2. В большинстве вышеупомянутых исключений компилятор всё-равно может понять, что переменная является константой.

C++

Если вы пишете на С++, то const может повлиять на генерирование кода посредством перегрузки функций. У вас могут быть const и не-const-перегрузки одной и той же функции, и при этом не-const могут быть оптимизированы (программистом, а не компилятором), например, чтобы меньше копировать.

void foo(int *p)
{
  // Needs to do more copying of data
}

void foo(const int *p)
{
  // Doesn't need defensive copies
}

int main()
{
  const int x = 42;
  // const-ness affects which overload gets called
  foo(&x);
  return 0;
}

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

Эксперимент с SQLite3

Хватит теории и надуманных примеров. Какое влияние оказывает const на настоящую кодовую базу? Я решил провести эксперимент с БД SQLite (версия 3.30.0), потому что:

  • В ней используется const.
  • Это нетривиальная кодовая база (свыше 200 KLOC).
  • В качестве базы данных она включает в себя ряд механизмов, начиная с обработки строковых значений и заканчивая преобразованием чисел в дату.
  • Её можно протестировать с помощью нагрузки, ограниченной по процессору.

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

Подготовка

Я сделал две копии исходного кода. Одну скомпилировал в обычном режиме, а вторую предварительно обработал с помощью хака, чтобы превратить const в холостую команду:

#define const

(GNU) sed может добавить это поверх каждого файла с помощью команды sed -i '1i#define const' *.c *.h.

SQLite всё немного усложняет, с помощью скриптов генерируя код в ходе сборки. К счастью, компиляторы вносят много помех при смешивании кода с const и без const, так что это можно было сразу заметить и настроить скрипты для добавления моего анти-const кода.

Прямое сравнение скомпилированных кодов не имеет смысла, поскольку мелкое изменение может повлиять на всю схему памяти, что приведёт к изменению указателей и вызовов функций во всём коде. Поэтому я снял дизассемблерный слепок (objdump -d libSQLite3.so.0.8.6) в виде размера бинарника и мнемонического названия каждой инструкции. Например, эта функция:

000000000005d570 <SQLite3_blob_read>:
   5d570:       4c 8d 05 59 a2 ff ff    lea    -0x5da7(%rip),%r8        # 577d0 <SQLite3BtreePayloadChecked>
   5d577:       e9 04 fe ff ff          jmpq   5d380 <blobReadWrite>
   5d57c:       0f 1f 40 00             nopl   0x0(%rax)

Превращается в:

SQLite3_blob_read   7lea 5jmpq 4nopl

При компилировании я не менял сборочные настройки SQLite.

Анализ скомпилированного кода

У libSQLite3.so версия с const занимала 4 740 704 байтов, примерно на 0,1 % больше версии без const с её 4 736 712 байтами. В обоих случаях было экспортировано 1374 функции (не считая низкоуровневые вспомогательные функции в PLT), и у 13 были какие-нибудь различия в слепках.

Некоторые изменения были связаны с хаком предварительной обработки. К примеру, вот одна из изменившихся функций (я убрал некоторые определения, характерные для SQLite):

#define LARGEST_INT64  (0xffffffff|(((int64_t)0x7fffffff)<<32))
#define SMALLEST_INT64 (((int64_t)-1) - LARGEST_INT64)

static int64_t doubleToInt64(double r){
  /*
  ** Many compilers we encounter do not define constants for the
  ** minimum and maximum 64-bit integers, or they define them
  ** inconsistently.  And many do not understand the "LL" notation.
  ** So we define our own static constants here using nothing
  ** larger than a 32-bit integer constant.
  */
  static const int64_t maxInt = LARGEST_INT64;
  static const int64_t minInt = SMALLEST_INT64;

  if( r<=(double)minInt ){
    return minInt;
  }else if( r>=(double)maxInt ){
    return maxInt; 
  }else{
    return (int64_t)r;
  }
}

Если убрать const, то эти константы превращаются в static-переменные. Не понимаю, зачем кому-то, кого не волнуют const, делать эти переменные static. Если убрать и static, и const, то GCC снова будет считать их константами, и мы получим тот же результат. Из-за таких static const переменных изменения в трёх функциях из тринадцати оказались ложными, но я не стал их исправлять.

SQLite использует много глобальных переменных, и с этим связано большинство настоящих const-оптимизаций: вроде замены сравнения с переменной на сравнение с константой, или частичного отката цикла на один шаг (чтобы понять, какие были сделаны оптимизации, я воспользовался Radare). Несколько изменений не стоят упоминания. SQLite3ParseUri() содержит 487 инструкций, но const внёс лишь одно изменение: взял эти два сравнения:

test %al, %al
je <SQLite3ParseUri+0x717>
cmp $0x23, %al
je <SQLite3ParseUri+0x717>

И поменял местами:

cmp $0x23, %al
je <SQLite3ParseUri+0x717>
test %al, %al
je <SQLite3ParseUri+0x717>

Бенчмарки

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

const Без const
Минимум 10,658 10,803
Медиана 11,571 11,519
Максимум 11,832 11,658
Среднее 11,531 11,492

Лично я не вижу особой разницы. Я убрал const изо всей программы, так что если бы была заметная разница, то её было был легко заметить. Впрочем, если для вас крайне важна производительность, то вас может порадовать даже крошечное ускорение. Давайте проведём статистический анализ.

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

const Без const
N 100 100
Средняя категория (Mean rank) 121,38 79,62
Mann-Whitney U 2912
Z -5,10
2-sided p value <10-6
Средняя разница HL -0,056 с.
95-процентный доверительный интервал -0,077… -0,038 с.

Тест U обнаружил статистически значимую разницу в производительности. Но — сюрприз! — быстрее оказалась версия без const, примерно на 60 мс, то есть на 0,5 %. Похоже, небольшое количество сделанных «оптимизаций» не стоили увеличения количества кода. Вряд ли const активировал какие-нибудь большие оптимизации, вроде автовекторизации. Конечно, ваш пробег может зависеть от различных флагов в компиляторе, или от его версии, или от кодовой базы, или от чего-нибудь ещё. Но мне кажется, будет честным сказать, что если даже const повысили производительность C, то я этого не заметил.

Так для чего нужен const?

При всех его недостатках, const в C/C++ полезен для обеспечения типобезопасности. В частности, если применять const в сочетании с move-семантикой и std::unique_pointer, то можно реализовать явное владение указателем. Неопределённость владения указателем было огромной проблемой в старых кодовых базах на С++ размером свыше 100 KLOC, так что я благодарен const за её решение.

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

Автор: Макс

Источник


* - обязательные к заполнению поля