Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Could type punning signed to unsigned integers make bounds checking faster by eliminating the need for >= comparison?

Say I had a really performance-critical loop in my program where I need to check if a point was inside a rectangle, but I know at compile time that the lower bounds are always going to be 0, like the following: (x >= 0 && y >= 0 && x < width && y < height)

Could I eliminate the first two comparisons by type-punning x and y to unsigned integers (for instance with something like reinterpret_cast<>() or a union in C++), since the sign bit would guarantee any negative number would turn into an unsigned int large enough to fail the bounds check? If so, how would you go about implementing this in C++ or another language? Could you gain any performance improvement by doing this?

like image 383
Stuntddude Avatar asked Jan 19 '15 01:01

Stuntddude


People also ask

Is unsigned int faster?

unsigned leads to the same or better performance than signed . Some examples: Division by a constant which is a power of 2 (see also the answer from FredOverflow)

What is the basic difference between signed and unsigned type integer?

A signed integer is a 32-bit datum that encodes an integer in the range [-2147483648 to 2147483647]. An unsigned integer is a 32-bit datum that encodes a nonnegative integer in the range [0 to 4294967295]. The signed integer is represented in twos complement notation.

What happens when you cast a signed int to an unsigned int?

If you mix signed and unsigned int, the signed int will be converted to unsigned (which means a large positive number if the signed int has a negative value).

Can signed integers represent more values than unsigned integers?

Both can store 256 different values, but signed integers use half of their range for negative numbers, whereas unsigned integers can store positive numbers that are twice as large. An n-bit unsigned variable has a range of 0 to (2n)-1.


1 Answers

Yes, it's a perfectly valid optimization when you're testing a signed integer and the lower bound is zero. In fact it's such a common optimization that your compiler will almost certainly do it automatically; obfuscating your code by doing it yourself is very likely to be a pointless premature optimization.

I just tested this on GCC 4.9, and confirmed by inspecting the generated assembly code that it performs this optimization automatically at -O1 and above. I would expect all modern compilers to do the same.

like image 199
Ross Smith Avatar answered Sep 28 '22 04:09

Ross Smith