Почти постоянное время вращения, что не нарушает стандарты

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

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

Джон Регер в Университете Юты рекомендует версию «c» своих попыток сделать функцию поворота. Я заменил его assert на битовое AND и обнаружил, что он все еще компилируется в один вращающийся 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).

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

я проверил мой с gcc.godbolt.org, с определенным NDEBUG, для переменных и счетчиков поворотов во время компиляции:

• gcc: оптимальный код с gcc> = 4.9.0, не разветвляющийся нег + сдвиги + или с ранее.
  (счетчик констант времени компиляции: gcc 4.4.7 в порядке)
• Clang: оптимальный код с лязг> = 3.5.0, не разветвляющийся нег + сдвиги + или с ранее.
  (во время компиляции const rotate count: clang 3.0 в порядке)
• ICC 13: оптимальный код.
  (счетчик времени компиляции с параметром -march = native: генерирует медленнее shld $7, %edi, %edi, Хорошо без -march=native)

Даже более новые версии компилятора могут обрабатывать общедоступный код из википедии (включенный в пример godbolt) без генерации ветки или cmov. Версия Джона Регера позволяет избежать неопределенного поведения, когда число поворотов равно 0.

Есть некоторые предостережения с вращением 8 и 16 бит, но компиляторы кажутся хорошими с 32 или 64, когда n является uint32_t, Смотрите комментарии в коде на связь с богом для некоторых заметок из моего тестирования различной ширины 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 по-прежнему генерирует вращающийся insn, но gcc и clang этого не делают, поскольку

// generates slow code: cast separately.
uint32_t r = (uint32_t)( (x<<n) | (x>>( -n&(CHAR_BIT*sizeof(x)-1) )) );

Если кто-то может проверить это с помощью MSVC, было бы полезно узнать, что там происходит.