Ответ 1
Я связался с этим ответом для получения полной информации из нескольких других вопросов "повернуть", в том числе этот вопрос в вики сообщества, который должен быть обновлен с помощью передовая практика,.
Я нашел сообщение в блоге об этой проблеме, и похоже, что это окончательно решена проблема (с новыми версиями компилятора).
Джон Реджер из Университета штата Юта рекомендует версию "c" своих попыток сделать функцию вращения. Я заменил его assert поразрядным AND и обнаружил, что он все еще компилируется в один rotate insn.
typedef uint32_t rotwidth_t; // parameterize for comparing compiler output with various sizes
rotwidth_t rotl (rotwidth_t x, unsigned int n)
{
const unsigned int mask = (CHAR_BIT*sizeof(x)-1); // e.g. 31
assert ( (n<=mask) &&"rotate by type width or more");
n &= mask; // avoid undef behaviour with NDEBUG. 0 overhead for most types / compilers
return (x<<n) | (x>>( (-n)&mask ));
}
rotwidth_t rot_const(rotwidth_t x)
{
return rotl(x, 7);
}
Это может быть шаблон для типа x, но, вероятно, имеет смысл для реального использования, чтобы иметь ширину в имени функции (например, rotl32). Обычно, когда вы вращаетесь, вы знаете, какую ширину вы хотите, и это важнее, чем какая переменная размера, в которой вы сейчас сохраняете значение.
Также обязательно используйте это только для неподписанных типов. Правый сдвиг подписанных типов выполняет арифметический сдвиг, сдвигая знаковые биты. (Это технически зависит от реализации, но все использует теперь 2 дополнения.)
Пабигот самостоятельно придумал ту же идею, что и я, и разместил ее в gibhub. Его версия имеет проверку С++ static_assert, чтобы сделать ее ошибкой времени компиляции, чтобы использовать счетчик вращения вне диапазона для типа.
I проверил мою версию с gcc.godbolt.org, с определенным NDEBUG, для переменных и компиляции time-const вращает count:
- gcc: оптимальный код с gcc >= 4.9.0, неветвящийся neg + сдвиг + или с более ранним.
(время подсчета compile-time: gcc 4.4.7 в порядке) - clang: оптимальный код с clang >= 3.5.0, не ветвящийся neg + сдвиг + или с более ранним.
(compile-time const rotate count: clang 3.0 отлично) - icc 13: оптимальный код.
(время подсчета compile-time с -march = native: генерирует более медленныйshld $7, %edi, %edi. Тонкий без-march=native)
Даже новые версии компилятора могут обрабатывать обычно заданный код из википедии (включенной в образец godbolt) без создания ветки или cmov. Преимущество Джона Регера состоит в том, чтобы избежать поведения undefined, когда число оборотов равно 0.
Есть некоторые предостережения с 8 и 16 битами, но компиляторы кажутся точными с 32 или 64, когда n - uint32_t. См. Комментарии в коде ссылка godbolt для некоторых заметок из моего тестирования различной ширины uint*_t. Надеемся, что эта идиома будет лучше распознана всеми компиляторами для большего количества комбинаций ширины типов в будущем. Иногда gcc бесполезно выделяет AND insn на счетчик вращения, хотя x86 ISA определяет вращение insns с таким точным AND как первый шаг.
"оптимальный" означает такую же эффективную, как:
# gcc 4.9.2 rotl(unsigned int, unsigned int):
movl %edi, %eax
movl %esi, %ecx
roll %cl, %eax
ret
# rot_const(unsigned int):
movl %edi, %eax
roll $7, %eax
ret
Когда встраивается, компилятор должен иметь возможность упорядочивать значения в правильных регистрах в первую очередь, что приводит к простому вращению.
С более старыми компиляторами вы все равно получите идеальный код, когда счетчик вращения будет константой времени компиляции. Godbolt позволяет вам тестировать с помощью ARM в качестве цели, и он также использовал поворот. С переменными счетчиками на старых компиляторах вы получаете немного раздувания кода, но никаких ветвей или серьезных проблем с производительностью, поэтому эта идиома должна быть безопасной для использования в целом.
Кстати, я модифицировал оригинал Джона Реджера, чтобы использовать CHAR_BIT * sizeof (x), а gcc/clang/icc испускает оптимальный код для uint64_t. Тем не менее, я заметил, что изменение x на uint64_t, в то время как возвращаемый тип функции все еще uint32_t делает gcc скомпилировать его для сдвигов/или. Поэтому будьте осторожны, чтобы привести результат к 32 бит в отдельной точке последовательности, если вы хотите, чтобы низкий 32b 64b вращался. т.е. присвойте результат 64-битной переменной, затем отпустите ее/верните. icc все еще генерирует rotate insn, но gcc и clang этого не делают, для
// generates slow code: cast separately.
uint32_t r = (uint32_t)( (x<<n) | (x>>( -n&(CHAR_BIT*sizeof(x)-1) )) );
Если кто-то может проверить это с помощью MSVC, было бы полезно узнать, что там происходит.