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

122

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

Рассмотрим эту функцию для эффективной распаковки массивов 3-битных целых чисел в 8-битные целые числа. На каждой итерации цикла он распаковывает 16 int:

void unpack3bit(uint8_t* target, char* source, int size) {
   while(size > 0){
      uint64_t t = *reinterpret_cast<uint64_t*>(source);
      target[0] = t & 0x7;
      target[1] = (t >> 3) & 0x7;
      target[2] = (t >> 6) & 0x7;
      target[3] = (t >> 9) & 0x7;
      target[4] = (t >> 12) & 0x7;
      target[5] = (t >> 15) & 0x7;
      target[6] = (t >> 18) & 0x7;
      target[7] = (t >> 21) & 0x7;
      target[8] = (t >> 24) & 0x7;
      target[9] = (t >> 27) & 0x7;
      target[10] = (t >> 30) & 0x7;
      target[11] = (t >> 33) & 0x7;
      target[12] = (t >> 36) & 0x7;
      target[13] = (t >> 39) & 0x7;
      target[14] = (t >> 42) & 0x7;
      target[15] = (t >> 45) & 0x7;
      source+=6;
      size-=6;
      target+=16;
   }
}

Вот сгенерированная сборка для частей кода:

 ...
 367:   48 89 c1                mov    rcx,rax
 36a:   48 c1 e9 09             shr    rcx,0x9
 36e:   83 e1 07                and    ecx,0x7
 371:   48 89 4f 18             mov    QWORD PTR [rdi+0x18],rcx
 375:   48 89 c1                mov    rcx,rax
 378:   48 c1 e9 0c             shr    rcx,0xc
 37c:   83 e1 07                and    ecx,0x7
 37f:   48 89 4f 20             mov    QWORD PTR [rdi+0x20],rcx
 383:   48 89 c1                mov    rcx,rax
 386:   48 c1 e9 0f             shr    rcx,0xf
 38a:   83 e1 07                and    ecx,0x7
 38d:   48 89 4f 28             mov    QWORD PTR [rdi+0x28],rcx
 391:   48 89 c1                mov    rcx,rax
 394:   48 c1 e9 12             shr    rcx,0x12
 398:   83 e1 07                and    ecx,0x7
 39b:   48 89 4f 30             mov    QWORD PTR [rdi+0x30],rcx
 ...

Выглядит довольно эффективно. Просто a, shift rightза которым следует and, а затем a storeв targetбуфер. Но теперь посмотрите, что происходит, когда я меняю функцию на метод в структуре:

struct T{
   uint8_t* target;
   char* source;
   void unpack3bit( int size);
};

void T::unpack3bit(int size) {
        while(size > 0){
           uint64_t t = *reinterpret_cast<uint64_t*>(source);
           target[0] = t & 0x7;
           target[1] = (t >> 3) & 0x7;
           target[2] = (t >> 6) & 0x7;
           target[3] = (t >> 9) & 0x7;
           target[4] = (t >> 12) & 0x7;
           target[5] = (t >> 15) & 0x7;
           target[6] = (t >> 18) & 0x7;
           target[7] = (t >> 21) & 0x7;
           target[8] = (t >> 24) & 0x7;
           target[9] = (t >> 27) & 0x7;
           target[10] = (t >> 30) & 0x7;
           target[11] = (t >> 33) & 0x7;
           target[12] = (t >> 36) & 0x7;
           target[13] = (t >> 39) & 0x7;
           target[14] = (t >> 42) & 0x7;
           target[15] = (t >> 45) & 0x7;
           source+=6;
           size-=6;
           target+=16;
        }
}

Я думал, что сгенерированная сборка должна быть такой же, но это не так. Вот его часть:

...
 2b3:   48 c1 e9 15             shr    rcx,0x15
 2b7:   83 e1 07                and    ecx,0x7
 2ba:   88 4a 07                mov    BYTE PTR [rdx+0x7],cl
 2bd:   48 89 c1                mov    rcx,rax
 2c0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2c3:   48 c1 e9 18             shr    rcx,0x18
 2c7:   83 e1 07                and    ecx,0x7
 2ca:   88 4a 08                mov    BYTE PTR [rdx+0x8],cl
 2cd:   48 89 c1                mov    rcx,rax
 2d0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2d3:   48 c1 e9 1b             shr    rcx,0x1b
 2d7:   83 e1 07                and    ecx,0x7
 2da:   88 4a 09                mov    BYTE PTR [rdx+0x9],cl
 2dd:   48 89 c1                mov    rcx,rax
 2e0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2e3:   48 c1 e9 1e             shr    rcx,0x1e
 2e7:   83 e1 07                and    ecx,0x7
 2ea:   88 4a 0a                mov    BYTE PTR [rdx+0xa],cl
 2ed:   48 89 c1                mov    rcx,rax
 2f0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 ...

Как видите, мы ввели дополнительную избыточность loadиз памяти перед каждым shift ( mov rdx,QWORD PTR [rdi]). Похоже, что targetуказатель (который теперь является членом, а не локальной переменной) необходимо всегда перезагружать перед сохранением в нем. Это значительно замедляет код (около 15% по моим измерениям).

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

Я сам пробовал кешировать указатель члена в локальную переменную:

void T::unpack3bit(int size) {
    while(size > 0){
       uint64_t t = *reinterpret_cast<uint64_t*>(source);
       uint8_t* target = this->target; // << ptr cached in local variable
       target[0] = t & 0x7;
       target[1] = (t >> 3) & 0x7;
       target[2] = (t >> 6) & 0x7;
       target[3] = (t >> 9) & 0x7;
       target[4] = (t >> 12) & 0x7;
       target[5] = (t >> 15) & 0x7;
       target[6] = (t >> 18) & 0x7;
       target[7] = (t >> 21) & 0x7;
       target[8] = (t >> 24) & 0x7;
       target[9] = (t >> 27) & 0x7;
       target[10] = (t >> 30) & 0x7;
       target[11] = (t >> 33) & 0x7;
       target[12] = (t >> 36) & 0x7;
       target[13] = (t >> 39) & 0x7;
       target[14] = (t >> 42) & 0x7;
       target[15] = (t >> 45) & 0x7;
       source+=6;
       size-=6;
       this->target+=16;
    }
}

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

  • Итак, почему компилятор не может оптимизировать эти нагрузки?
  • Неужели это запрещено моделью памяти C ++? Или это просто недостаток моего компилятора?
  • Верно ли мое предположение или какова точная причина невозможности проведения оптимизации?

Используемый компилятор был g++ 4.8.2-19ubuntu1с -O3оптимизацией. Я также пробовал clang++ 3.4-1ubuntu3с аналогичными результатами: Clang даже может векторизовать метод с помощью локального targetуказателя. Однако использование this->targetуказателя дает тот же результат: дополнительная загрузка указателя перед каждым сохранением.

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

gexicide
источник
5
Не уверен, почему за это проголосовали против - это интересный вопрос. FWIW Я видел похожие проблемы оптимизации с переменными-членами, не являющимися указателями, где решение было аналогичным, то есть кешировать переменную-член в локальной переменной на время существования метода. Я предполагаю, что это как-то связано с правилами псевдонима?
Paul R
1
Похоже, компилятор не оптимизирует, потому что он не может гарантировать, что член не будет доступен через какой-то «внешний» код. Поэтому, если член может быть изменен снаружи, его следует перезагружать при каждом доступе. Кажется, это считается своего рода изменчивым ...
Жан-Батист Юнес
Нет, не использовать this->- это просто синтаксический сахар. Проблема связана с природой переменных (локальные и члены) и с тем, что компилятор выводит из этого факта.
Жан-Батист Юнес
Что-нибудь связано с псевдонимами указателей?
Ив Дауст
3
В более семантическом смысле «преждевременная оптимизация» применяется только к оптимизации, которая является преждевременной, т. Е. До того, как профилирование обнаружит, что это проблема. В этом случае вы тщательно профилировали, декомпилировали и нашли источник проблемы, а также сформулировали и профилировали решение. Совершенно не «преждевременно» применять это решение.
raptortech97

Ответы:

107

По иронии судьбы, проблема заключается в сглаживании указателя между thisи this->target. Компилятор принимает во внимание довольно неприличную возможность, которую вы инициализировали:

this->target = &this

В этом случае запись в this->target[0]изменит содержимое this(и, следовательно, this->target).

Проблема сглаживания памяти не ограничивается описанным выше. В принципе, любое использование this->target[XX]данного (не) подходящего значения XXможет указывать на this.

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

Питер Бонч
источник
18
Я могу это подтвердить! Изменение targetс uint8_tна uint16_t(чтобы сработали строгие правила псевдонима) изменило его. С uint16_t, нагрузка всегда оптимизирована.
гексицид
1
Релевантно: stackoverflow.com/questions/16138237/…
user541686
3
thisВы имеете в виду не изменение содержимого (это не переменная); вы имеете в виду изменение содержимого *this.
Марк ван Леувен,
@gexicide mind уточняет, как строгий псевдоним срабатывает и решает проблему?
HCSF
33

Строгие правила char*псевдонима позволяют использовать псевдоним любого другого указателя. Таким образом, this->targetможно использовать псевдоним с thisпервой частью кода и в вашем методе кода,

target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;

на самом деле

this->target[0] = t & 0x7;
this->target[1] = (t >> 3) & 0x7;
this->target[2] = (t >> 6) & 0x7;

которые thisмогут быть изменены при изменении this->targetсодержимого.

После this->targetкэширования в локальную переменную псевдоним становится невозможным с локальной переменной.

Jarod42
источник
1
Итак, можем ли мы сказать в качестве общего правила: всякий раз, когда у вас есть char*или void*в вашей структуре, обязательно кэшируйте ее в локальной переменной перед записью в нее?
gexicide
5
Фактически, это когда вы используете a char*, не обязательно в качестве члена.
Jarod42
24

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

Было бы разумно реализовать uint8_t как беззнаковый char, и если мы посмотрим на cstdint в Coliru, он включает stdint.h, который typedefs uint8_t следующим образом:

typedef unsigned char       uint8_t;

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

Это 3.10 описано в проекте стандартного раздела Lvalues ​​и rvalues C ++, в котором говорится:

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

и включает в себя следующий пункт:

  • тип char или unsigned char.

Обратите внимание, я опубликовал комментарий о возможных решениях в вопросе, который спрашивает, когда uint8_t ≠ unsigned char? и рекомендация была такой:

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

Поскольку C ++ не поддерживает ключевое слово restrict, вы должны полагаться на расширение компилятора, например, gcc использует __restrict__, поэтому это не полностью переносимо, но должно быть другое предложение.

Шафик Ягмур
источник
Это пример места, где Стандарт хуже для оптимизаторов, чем правило, позволяющее компилятору предположить, что между двумя обращениями к объекту типа T или таким доступом и началом или концом цикла / функции при этом все обращения к хранилищу будут использовать один и тот же объект, если промежуточная операция не использует этот объект (или указатель / ссылку на него) для получения указателя или ссылки на какой-либо другой объект . Такое правило устранит необходимость в «исключении символьного типа», которое может снизить производительность кода, работающего с последовательностями байтов.
supercat