Optimal (Time paradigm) solution to check variable within boundary

Question

Hi All,

Sorry if the question is very naive.
I will have to check the below condition in my code

0 < x < y
i.e code similar to if(x > 0 && x < y)

The basic problem at system level is - currently, for every call (Telecom domain terminology), my existing code is hit (many times). So performance is very very critical, Now, I need to add a check for boundary checking (at many location - but different boundary comparison at each location).

At very normal level of coding, the above comparison would look very naive without any issue. However, when added over my statistics module (which is dipped many times), performance will go down.

So I would like to know the best possible way to handle the above scenario (kind of optimal way for limits checking technique). Like for example, if bit comparison works better than normal comparison or can both the comparison be evaluation in shorter time span?

Other Info

x is unsigned integer (which must be checked to be greater than 0 and less than y). y is unsigned integer.
y is a non-const and varies for every comparison.
Here time is the constraint compared to space.
Language - C++.

Now, later if I need to change the attribute of y to a float/double, would there be another way to optimize the check (i.e will the suggested optimal technique for integer become non-optimal solution when y is changed to float/double).

Thanks in advance for any input.

---

PS : OS used is SUSE 10 64 bit x64_64, AIX 5.3 64 bit, HP UX 11.1 A 64.

Answer 1

As always, profile first, optimize later. But, given that this is actually an issue, these could be things to look into:

• "Unsigned and greater than zero" is the same as "not equal to zero", which is usually about as fast as a comparison gets. So a first optimization would be to do x != 0 && x < y.

• Make sure that you do the comparison that is most likely to fail the first one, to maximize the gain from short circuiting.

• If possible, use compiler directives to tell the compiler about the most likely code path. This will optimize instruction prefetching etc. I.e. for GCC look at something like this, done in the kernel.

I don't think tricks with subtraction and comparison against zero, etc. will be of any gain. If that is the most effective way to do a less-than comparison, you can be sure your compiler already knows about it.

Answer 2

This eliminates a compare and branch at the expense of two adds; it should be faster:

(x-1) < (y-1)

It works as long as y is guaranteed non-zero.

Answer 3

You probably don't need to change y to a float or a double; you should endeavor to stay in integer for as much as you can. Instead of representing y as seconds, try microseconds or milliseconds (depending on the resolution you need).

Anyway- I suspect you can change

if (x > 0 && x < y)
   ;

to

if ((unsigned int)x < (unsigned int)y)
   ;

but that's probably not going to actually speed anything up. Checking against zero is often one or two instructions (depending on ISA) so the read from memory is certainly the bottleneck here.

After you've profiled your code and determined that this is actually where the performance problems are, you could investigate tweaking the branch predictor, since that's somewhere a lot of time can be wasted if it's regularly mispredicting. Different compilers do it differently, but some have an intrinsic like __expect(x < 0);, which will tell the predictor to assume that's usually the case.