В С++, должен ли я беспокоиться о кэшировании переменных или дать компилятору оптимизацию? (Сглаживание)

Ответ 1

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

Источник unoptimized.cpp

note: этот код не предназначен для выполнения.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    for (unsigned x = 0 ; x < static_cast<unsigned>(bitmap.width) ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

Источник optimized.cpp

note: этот код не предназначен для выполнения.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    const unsigned width = static_cast<unsigned>(bitmap.width);
    for (unsigned x = 0 ; x < width ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

Компиляция

• $ g++ -s -O3 unoptimized.cpp
• $ g++ -s -O3 optimized.cpp

Сборка (unoptimized.s)

    .file   "unoptimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    mov %eax, %edx
    addl    $1, %eax
    movq    (%rsi,%rdx,8), %rdx
    movb    $0, (%rdx)
    cmpl    bitmap(%rip), %eax
    jb  .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

Сборка (optimized.s)

    .file   "optimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    subl    $1, %eax
    leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    movq    (%rsi,%rax), %rdx
    addq    $8, %rax
    cmpq    %rcx, %rax
    movb    $0, (%rdx)
    jne .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

дифф

$ diff -uN unoptimized.s optimized.s
--- unoptimized.s   2015-11-24 16:11:55.837922223 +0000
+++ optimized.s 2015-11-24 16:12:02.628922941 +0000
@@ -1,4 +1,4 @@
-   .file   "unoptimized.cpp"
+   .file   "optimized.cpp"
    .text
    .p2align 4,,15
 .globl main
@@ -10,16 +10,17 @@
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
+   subl    $1, %eax
+   leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
 .L3:
-   mov %eax, %edx
-   addl    $1, %eax
-   movq    (%rsi,%rdx,8), %rdx
+   movq    (%rsi,%rax), %rdx
+   addq    $8, %rax
+   cmpq    %rcx, %rax
    movb    $0, (%rdx)
-   cmpl    bitmap(%rip), %eax
-   jb  .L3
+   jne .L3
 .L2:
    xorl    %eax, %eax
    ret

Сгенерированная сборка для оптимизированной версии фактически загружает (lea) константу width в отличие от неоптимизированной версии, которая вычисляет смещение width на каждом итерация (movq).

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

Ответ 2

На самом деле из вашего фрагмента кода на самом деле недостаточно информации, чтобы можно было сказать, и одна вещь, о которой я могу думать, - это псевдонимы. С нашей точки зрения, довольно ясно, что вы не хотите, чтобы p и bitmap указывали на одно и то же место в памяти, но компилятор этого не знает и (поскольку p имеет тип char*) компилятор должен заставить этот код работать, даже если p и bitmap перекрываются.

В этом случае это означает, что если цикл изменит bitmap->width на указатель p, то это нужно увидеть при повторном чтении bitmap->width позже, что, в свою очередь, означает, что сохранение его в локальной переменной быть незаконным.

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

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

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

Ответ 3

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

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

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

for (unsigned x = static_cast<unsigned>(bitmap->width);x > 0;  x--)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Обратите внимание, что эта версия цикла дает значения x в диапазоне 1..width, а не в диапазоне 0.. (ширина-1). Это не имеет значения в вашем случае, потому что вы на самом деле не используете x для чего-либо, кроме того, что вам нужно знать. Если вам нужен цикл обратного отсчета с значениями x в диапазоне 0.. (ширина-1), вы можете сделать.

for (unsigned x = static_cast<unsigned>(bitmap->width); x-- > 0;)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Вы также можете избавиться от приведения в приведенных выше примерах, если хотите, не беспокоясь о том, что это влияет на правила сравнения, поскольку все, что вы делаете с bitmap- > width, присваивает его непосредственно переменной.

Ответ 4

Хорошо, ребята, поэтому я измерил с помощью GCC -O3 (используя GCC 4.9 на Linux x64).

Оказывается, вторая версия работает на 54% быстрее!

Итак, я думаю, что сглаживание - это то, о чем я не думал.

[изменить]

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

[Редактировать 2]

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

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

И измерил (должен был использовать "-mcmodel = большой", чтобы связать его). Затем я попробовал:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

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

Затем я попробовал исходные коды (с указателем p), на этот раз, когда p имеет тип std::uint16_t*. Опять же, результаты были одинаковыми - из-за строгого сглаживания. Затем я попытался построить "-fno-strict-aliasing" и снова увидел разницу во времени.

Ответ 5

Первоначально заданный вопрос:

Стоит ли его оптимизировать?

И мой ответ на это (получение хорошего сочетания голосов вверх и вниз).

Пусть компилятор беспокоится об этом.

Компилятор почти наверняка сделает лучшую работу, чем вы. А также нет никакой гарантии, что ваша "оптимизация" лучше, чем "очевидный" код - вы его измерили?

Что еще более важно, у вас есть доказательства того, что код, который вы оптимизируете оказывает какое-либо влияние на производительность вашей программы?

Несмотря на downvotes (и теперь, видя проблему с псевдонимом), я все еще доволен этим как правильный ответ. Если вы не знаете, стоит ли что-то оптимизировать, это, вероятно, не так.

Конечно, вопрос был бы совсем другим:

Как я могу определить, стоит ли оптимизировать фрагмент кода?

Во-первых, нужно ли запускать приложение или библиотеку быстрее, чем в настоящее время? Неужели пользователь слишком долго ждал? Прогнозирует ли ваше программное обеспечение вчера погода вместо завтрашнего дня?

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

Предполагая, что ваше программное обеспечение нуждается в некоторой оптимизации, следующая задача - начать измерение. Профиляторы расскажут вам, где ваш код тратит время. Если ваш фрагмент не отображается как узкое место, его лучше оставить в покое. Профили и другие измерительные инструменты также расскажут вам, изменились ли ваши изменения. Можно потратить часы, чтобы оптимизировать код, только чтобы найти, что вы не заметили различий.

Что вы подразумеваете под оптимизацией?

Если вы не пишете "оптимизированный" код, чем ваш код должен быть таким четким, чистым и лаконичным, как вы можете это сделать. Аргумент "Преждевременная оптимизация - это зло" не является оправданием для неаккуратного или неэффективного кода.

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

Но часто, с "медленным" кодом, эти микро-оптимизации являются последним средством. Первое место - алгоритмы и структуры данных. Есть ли способ избежать работы вообще? Можно ли заменить линейные поиски двоичными? Будет ли связанный список быстрее здесь, чем вектор? Или хеш-стол? Могу ли я кэшировать результаты? Создание хороших "эффективных" решений здесь может часто влиять на производительность на порядок или больше!

Ответ 6

Единственное, что может помешать оптимизации, - это строгое правило сглаживания. Короче:

"Строгое сглаживание - это предположение, сделанное компилятором C (или С++), что указатели на разузнавание объектов разных типов никогда не будут ссылаться на одно и то же место памяти (то есть псевдонимы друг друга.)"

[...]

Исключением является правило char*, которому разрешено указывать любой тип.

Исключение распространяется также на указатели unsigned и signed char.

Это относится к вашему коду: вы изменяете *p через p, который является unsigned char*, поэтому компилятор должен предположить, что он может указывать на bitmap->width. Следовательно, кэширование bitmap->width является недопустимой оптимизацией. Это оптимизирующее оптимизацию поведение показано в YSC answer.

Если и только если p указывает на тип не char и не decltype(bitmap->width), будет ли кэширование возможной оптимизацией.

Ответ 7

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

for (unsigned int x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
{
  *p++ = 0xAA;
  *p++ = 0xBB;
  *p++ = 0xCC;
}

Это будет быстрее с менее умным компилятором, сборкой отладки или определенными флагами компиляции.

Edit1: размещение постоянной операции за пределами цикла является хорошим шаблоном программирования. Он показывает понимание основ работы машины, особенно в C/С++. Я бы сказал, что усилия, чтобы доказать себя, должны быть на людях, которые не следуют этой практике. Если компилятор наказывает за хороший шаблон, это ошибка в компиляторе.

Edit2:. Я оценил свое предложение против исходного кода на vs2013, получил улучшение% 1. Мы можем сделать лучше? Простая ручная оптимизация дает 3-кратное улучшение по сравнению с исходным циклом на машине x64, не прибегая к экзотическим инструкциям. В приведенном ниже коде предполагается минимальная конечная система и правильно выровненное растровое изображение. TEST 0 является оригинальным (9 секунд), TEST 1 работает быстрее (3 секунды). Бьюсь об заклад, кто-то может сделать это еще быстрее, и результат теста будет зависеть от размера растрового изображения. Определенно, скоро в будущем, компилятор сможет производить последовательный быстрый код. Я боюсь, что это будет будущее, когда компилятор будет также программистом AI, поэтому мы не будем работать. Но на данный момент просто напишите код, который показывает, что вы знаете, что дополнительная операция в цикле не нужна.

#include <memory>
#include <time.h>

struct Bitmap_line
{
  int blah;
  unsigned int width;
  Bitmap_line(unsigned int w)
  {
    blah = 0;
    width = w;
  }
};

#define TEST 0 //define 1 for faster test

int main(int argc, char* argv[])
{
  unsigned int size = (4 * 1024 * 1024) / 3 * 3; //makes it divisible by 3
  unsigned char* pointer = (unsigned char*)malloc(size);
  memset(pointer, 0, size);
  std::unique_ptr<Bitmap_line> bitmap(new Bitmap_line(size / 3));
  clock_t told = clock();
#if TEST == 0
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    for (unsigned x = 0; x < static_cast<unsigned>(bitmap->width); ++x)
    //for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#else
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    unsigned x = 0;
    for (const unsigned n = static_cast<unsigned>(bitmap->width) - 4; x < n; x += 4)
    {
      *(int64_t*)p = 0xBBAACCBBAACCBBAALL;
      p += 8;
      *(int32_t*)p = 0xCCBBAACC;
      p += 4;
    }

    for (const unsigned n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#endif
  double ms = 1000.0 * double(clock() - told) / CLOCKS_PER_SEC;
  printf("time %0.3f\n", ms);

  {
    //verify
    unsigned char* p = pointer;
    for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      if ((*p++ != 0xAA) || (*p++ != 0xBB) || (*p++ != 0xCC))
      {
        printf("EEEEEEEEEEEEERRRRORRRR!!!\n");
        abort();
      }
    }
  }

  return 0;
}

Ответ 8

Можно рассмотреть две вещи.

A) Как часто будет выполняться оптимизация?

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

B) Это сделает код более сложным для поддержки/устранения неполадок?

Если вы не видите большой выигрыш в производительности, то сделать ваш код загадочным просто для сохранения нескольких тактов - это не очень хорошая идея. Многие люди скажут вам, что любой хороший программист должен иметь возможность посмотреть на код и выяснить, что происходит. Это правда. Проблема в том, что в деловом мире дополнительное время выясняет, что издержки стоят денег. Итак, если вы можете сделать это красивее, чтобы читать, тогда сделайте это. Ваши друзья будут благодарны вам за это.

Я сказал бы, что лично использовал бы пример B.

Ответ 9

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

Ответ 10

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

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

Кроме того, я могу думать о патологических ситуациях, когда он может фактически замедлить работу кода. Например, рассмотрим случай, когда компилятор не смог доказать, что bitmap->width был постоянным в процессе. Добавляя переменную width, вы вынуждаете компилятор поддерживать локальную переменную в этой области. Если по какой-то определенной причине платформы эта дополнительная переменная предотвратила некоторую оптимизацию пространства стека, ей, возможно, придется реорганизовать, как она испускает байт-коды, и создавать что-то менее эффективное.

В качестве примера, в Windows x64 каждый должен вызвать специальный вызов API __chkstk в преамбуле функции, если функция будет использовать более 1 страницы локальных переменных. Эта функция дает Windows возможность управлять защитными страницами, которые они используют, для расширения стека, когда это необходимо. Если ваша дополнительная переменная подталкивает использование стека от 1 страницы до 1 или выше, ваша функция теперь должна вызывать __chkstk каждый раз, когда она вводится. Если вы хотите оптимизировать этот цикл на медленном пути, вы можете замедлить быстрый путь вниз больше, чем вы сохранили на медленном пути!

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

Ответ 11

Сравнение неверно, поскольку два фрагмента кода

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)

и

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x<width ;  ++x)

не эквивалентны

В первом случае width зависит, а не const, и нельзя предположить, что он не может меняться между последующими итерациями. Таким образом, он не может быть оптимизирован, но должен быть проверен в каждом цикле.

В вашем оптимизированном случае локальной переменной присваивается значение bitmap->width в какой-то момент во время выполнения программы. Компилятор может проверить, что это фактически не изменяется.

Думали ли вы о многопоточности, или, может быть, значение могло бы быть зависимым от внешних факторов, так что его значение является изменчивым. Как можно ожидать, что компилятор сможет понять все это, если вы не скажете?

Компилятор может делать только то, что позволяет ваш код.

Ответ 12

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

Ответ 13

Компилятор не может оптимизировать bitmap->width, потому что значение width может быть изменено между итерациями. Существует несколько наиболее распространенных причин:

• Многопоточность. Компилятор не может предсказать, собирается ли другой поток изменить значение.
• Модификация внутри цикла, иногда не просто определить, будет ли переменная изменяться внутри цикла.
• Это вызов функции, например. iterator::end() или container::size(), поэтому трудно предсказать, будет ли он всегда возвращать тот же результат.

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