Микро оптимизировать указатель + без знака + 1

Жестко, так как может показаться, что конструкция p[u+1] встречается в нескольких местах в самых внутренних циклах кода, которые я поддерживаю, так что при правильной микро-оптимизации это делает часы разницы в операции, которая работает в течение нескольких дней.

Обычно *((p+u)+1) является наиболее эффективным. Иногда *(p+(u+1)) является наиболее эффективным. Редко *((p+1)+u) лучше. (Но обычно оптимизатор может преобразовать *((p+1)+u) в *((p+u)+1), когда последний лучше, и не может преобразовать *(p+(u+1)) с любым из других).

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

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

В этих 64-битных применениях программист знает, что все три имеют одну и ту же семантику, но компилятор не знает. Насколько компилятор знает, решение о том, когда продлить u с 32-битного на 64-битный, может повлиять на результат.

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

В одном 64-битном компиляторе Linux я получил почти там p[u+1L], что заставляет компилятор разумно выбирать между обычно лучшими *((p+u)+1) и иногда лучше *(p+( (long)(u) + 1) ). В редком случае *(p+(u+1)) был еще лучше второго из них, немного потеряно.

Очевидно, что это не очень хорошо в 64-битной Windows. Теперь, когда мы отказались от 32-битной поддержки, возможно, p[u+1LL] достаточно портативен и достаточно хорош. Но могу ли я лучше?

Обратите внимание, что использование std::size_t вместо unsigned для u устранит всю эту проблему, но создаст большую проблему с производительностью. Кастинг u до std::size_t прямо там почти достаточно, и, возможно, лучшее, что я могу сделать. Но это довольно многословие для несовершенного решения.

Простое кодирование (p+1)[u] делает выбор более оптимальным, чем p[u+1]. Если код был менее шаблонным и более стабильным, я мог бы установить их все на (p+1)[u] затем профиль, а затем переключить несколько назад на p[u+1]. Но шаблоны имеют тенденцию разрушать этот подход (отдельная строка источника появляется в многих местах в профиле, добавляя до серьезного времени, но не индивидуально серьезное время).

Компиляторы, которые должны быть эффективными для этого, - это GCC, ICC и MSVC.

Ответ 1

Ответ неизбежно является компилятором и целевым, но даже если 1ULL шире, чем указатель на любую целевую архитектуру, хороший компилятор должен оптимизировать его. Какие 2 целые операции дополнения могут использоваться без обнуления высоких бит во входе, если требуется только низкая часть результата? объясняет, почему более широкое вычисление усекается до ширины указателя даст идентичные результаты, как и вычисление с шириной указателя. Вот почему компиляторы могут оптимизировать его даже на 32-битных машинах (или x86-64 с x32 ABI), когда 1ULL приводит к продвижению операндов + до 64-битного типа. (Или на некоторых 64-битных ABI для некоторой архитектуры, где long long - 128b).

1ULL выглядит оптимально для 64-битного, а для 32-битного с clang. В любом случае, вы все равно не заботитесь о 32bit, но gcc отправляет инструкцию в return p[u + 1ULL];. Все остальные случаи скомпилированы для одной нагрузки с режимом адресации с масштабированным индексом + 4 + p. Таким образом, кроме одного отказа оптимизации компилятора, 1ULL отлично смотрится и для 32-битного. (Я думаю, что маловероятно, что это ошибка clang и эта оптимизация является незаконной).

int v1ULL(std::uint32_t u) { return p[u + 1ULL]; }
//   ...  load u from the stack
//    add     eax, 1
//    mov     eax, DWORD PTR p[0+eax*4]

вместо

    mov     eax, DWORD PTR p[4+eax*4]

Интересно, что gcc 5.3 не делает эту ошибку при ориентации на x32 ABI (длинный режим с 32-битными указателями и регистрационный вызов ABI аналогично SySV AMD64). Он использует 32-битный префикс размера адреса, чтобы избежать использования верхнего 32b edi.

Раздражающе, он по-прежнему использует префикс размера адреса, когда он может сохранить байт машинного кода, используя 64-битный эффективный адрес (когда нет возможности переполнения/переноса в верхний32, генерирующий адрес за пределами низкого 4GiB). Передача указателя по ссылке является хорошим примером:

int x2   (char *&c) { return *c; }
//    mov     eax, DWORD PTR [edi]  ; upper32 of rax is zero
//    movsx   eax, BYTE PTR [eax]   ; could be byte [rax], saving one byte of machine code

Err, на самом деле я забыл. 32-битные адреса могут подписать - до 64b, а не с нулевым расширением. В этом случае он мог бы использовать movsx для первой инструкции, но это стоило бы байта, потому что movsx имеет более длинный код операции, чем mov.

В любом случае, x32 по-прежнему остается интересным выбором для кода с большим указателем, который хочет больше регистров и более приятного ABI, без попадания в кеш 8B-указателей.

В 64-битном asm должен быть равен нулю верхний регистр 32, содержащий параметр (с mov edi,edi), но это исчезает при встраивании. Взгляд на вывод godbolt для крошечных функций - это правильный способ проверить это.

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

int v1ULL(const std::uint32_t &u) { return p[u + 1ULL]; }
//  mov     eax, DWORD PTR [rdi]
//  mov     eax, DWORD PTR p[4+rax*4]