Недавно я столкнулся со странной деоптимизацией (точнее, упущенной возможностью оптимизации).
Рассмотрим эту функцию для эффективной распаковки массивов 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
всегда должен быть перезагружен перед сохранением, даже если такую нагрузку можно просто поднять за пределы цикла. Мне придется переписать большой объем кода, чтобы избавиться от этих дополнительных хранилищ, в основном путем кэширования самого указателя в локальную переменную, которая объявлена над горячим кодом. Но я всегда думал, что возиться с такими деталями, как кеширование указателя в локальной переменной, несомненно, можно было бы использовать для преждевременной оптимизации в наши дни, когда компиляторы стали такими умными. Но, похоже, я здесь не прав . Кэширование указателя на член в горячем цикле кажется необходимым методом ручной оптимизации.
this->
- это просто синтаксический сахар. Проблема связана с природой переменных (локальные и члены) и с тем, что компилятор выводит из этого факта.Ответы:
По иронии судьбы, проблема заключается в сглаживании указателя между
this
иthis->target
. Компилятор принимает во внимание довольно неприличную возможность, которую вы инициализировали:this->target = &this
В этом случае запись в
this->target[0]
изменит содержимоеthis
(и, следовательно,this->target
).Проблема сглаживания памяти не ограничивается описанным выше. В принципе, любое использование
this->target[XX]
данного (не) подходящего значенияXX
может указывать наthis
.Я лучше разбираюсь в C, где это можно исправить, объявив переменные-указатели с
__restrict__
ключевым словом.источник
target
сuint8_t
наuint16_t
(чтобы сработали строгие правила псевдонима) изменило его. Сuint16_t
, нагрузка всегда оптимизирована.this
Вы имеете в виду не изменение содержимого (это не переменная); вы имеете в виду изменение содержимого*this
.Строгие правила
char*
псевдонима позволяют использовать псевдоним любого другого указателя. Таким образом,this->target
можно использовать псевдоним сthis
первой частью кода и в вашем методе кода,на самом деле
которые
this
могут быть изменены при измененииthis->target
содержимого.После
this->target
кэширования в локальную переменную псевдоним становится невозможным с локальной переменной.источник
char*
илиvoid*
в вашей структуре, обязательно кэшируйте ее в локальной переменной перед записью в нее?char*
, не обязательно в качестве члена.Проблема здесь в строгом псевдониме, который говорит о том, что нам разрешено использовать псевдоним через char *, что предотвращает оптимизацию компилятора в вашем случае. Нам не разрешено использовать псевдоним с помощью указателя другого типа, который был бы неопределенным поведением, обычно в SO мы видим эту проблему, которая заключается в том, что пользователи пытаются использовать псевдоним с помощью несовместимых типов указателей .
Было бы разумно реализовать uint8_t как беззнаковый char, и если мы посмотрим на cstdint в Coliru, он включает stdint.h, который typedefs uint8_t следующим образом:
если вы использовали другой тип, отличный от char, компилятор должен иметь возможность оптимизировать.
Это
3.10
описано в проекте стандартного раздела Lvalues и rvalues C ++, в котором говорится:и включает в себя следующий пункт:
Обратите внимание, я опубликовал комментарий о возможных решениях в вопросе, который спрашивает, когда uint8_t ≠ unsigned char? и рекомендация была такой:
Поскольку C ++ не поддерживает ключевое слово restrict, вы должны полагаться на расширение компилятора, например, gcc использует __restrict__, поэтому это не полностью переносимо, но должно быть другое предложение.
источник