Может ли каламбур типа, подписанный для целых чисел без знака, ускорить проверку границ, устранив необходимость сравнения ›=?

Скажем, у меня в программе был действительно критичный к производительности цикл, в котором мне нужно проверить, находится ли точка внутри прямоугольника, но во время компиляции я знаю, что нижняя граница всегда будет равна 0, как показано ниже: (x >= 0 && y >= 0 && x < width && y < height)

Могу ли я исключить первые два сравнения, вводя символы x и y в беззнаковые целые числа (например, с чем-то вроде reinterpret_cast<>() или union в C++), поскольку знаковый бит гарантирует, что любое отрицательное число превратится в unsigned int, достаточно большое, чтобы не выполнить проверку. проверка границ? Если да, то как бы вы реализовали это на C++ или другом языке? Могли бы вы добиться улучшения производительности, сделав это?


c++ performance int type-punning integer-arithmetic
person Stuntddude    schedule 19.01.2015    source источник
comment
Возможно дубликат: stackoverflow.com/questions/2711522/   -  person Jeremy Friesner    schedule 19.01.2015
comment
Используйте static_cast для преобразования целочисленных типов. Вы также можете попробовать сравнить сборку, чтобы увидеть, оптимизирует ли компилятор ее автоматически.   -  person Neil Kirk    schedule 19.01.2015
comment
@JeremyFriesner Я бы сказал нет - этот вопрос, кажется, очень хорошо осведомлен об этом ответе.   -  person Drew Dormann    schedule 19.01.2015
comment
Да.   -  person Jerry Coffin    schedule 21.01.2015

Ответы (2)


arrow_upward
12
arrow_downward

Да, это совершенно правильная оптимизация, когда вы тестируете целое число со знаком, а нижняя граница равна нулю. На самом деле это настолько распространенная оптимизация, что ваш компилятор почти наверняка выполнит ее автоматически; запутывание вашего кода, делая это самостоятельно, скорее всего, будет бессмысленной преждевременной оптимизацией.

Я только что проверил это на GCC 4.9 и подтвердил, проверив сгенерированный код сборки, что он выполняет эту оптимизацию автоматически на -O1 и выше. Я ожидаю, что все современные компиляторы будут делать то же самое.

person Ross Smith    schedule 19.01.2015
comment
Насколько я понимаю ваши результаты теста, вы говорите, что делать это вручную не имеет значения... это происходит независимо? - person Drew Dormann; 19.01.2015
comment
Что ж, ему не нужно запутывать код, если он помещен во встроенную функцию с соответствующим названием. - person Ben Voigt; 19.01.2015
comment
Правильно, компилятор достаточно умен, чтобы заметить эту возможность оптимизации и сделать это за вас. - person Ross Smith; 19.01.2015
comment
Таким образом, компилятор обнаруживает, что вы выполняете тест больше нуля для целого числа и выполняете другой тест меньше (против положительного значения!) для того же целого числа, а затем переключает его в режим беззнакового сравнения, чтобы сэкономить менее 1 тактового цикла. ? - person BWG; 19.01.2015
comment
@BWG, что вы подразумеваете под менее чем одним тактовым циклом? Это преобразование двух сравнений в одно при пересмотре знака переменной позволяет это. - person Drew Dormann; 19.01.2015
comment
Думаю, мне следовало ожидать, что у GCC будет для этого дело. Я полагаю, это справедливое предположение, что JVM-компилятор даст аналогичный результат для эквивалента Java? - person Stuntddude; 19.01.2015
comment
@Stuntddude, это совершенно новый вопрос. Для других людей. - person Drew Dormann; 19.01.2015
comment
@Stuntdddude В Java нет целых чисел без знака, но, конечно, это не мешает компилятору использовать коды операций без знака. - person rici; 19.01.2015
comment
Я подтверждаю, что цепочка инструментов Clang/LLVM также оптимизирует это, начиная с O1: она создает %1 = icmp sgt i32 %i, -1 для i >= 0 and i <= 2147483647. - person Matthieu M.; 19.01.2015
comment
Разве эта оптимизация не возможна только автоматически, если компилятор может доказать, что width неотрицательно? - person zch; 19.01.2015

arrow_upward
3
arrow_downward

Может быть...

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

Ваш вопрос зависит от компилятора, процессора, а также от кода до и после проверки, поэтому мой ответ "может быть".

Избегайте приведения x,y к типу, размер которого отличается от того, который они имеют в настоящее время, т. е. приведение от int8_t к uint8_t допустимо, int8_t к uint32_t может повлечь за собой штраф.

Перепишите как хотите:

if ( ( static_cast<uint8_t>(x) < width ) &&
     ( static_cast<uint8_t>(y) < length ) )

Тестировать дельту производительности довольно сложно, вам нужно будет обернуть свой код какой-нибудь сборкой с помощью инструкции RDTSC, чтобы поймать время до и после. Вероятно, вам также потребуется использовать инструкцию CPUID для очистки конвейера.

Короче говоря, мне ваша оптимизация кажется разумной, но, скорее всего, она мало что даст. Однако это сработает.

person stackmate    schedule 19.01.2015