How to do unsigned comparison of two longs?

[Chris]

How do I compare two longs in an unsigned way without having to do
backflips?

I suppose I could copy each long to a pair of longs, the upper 32 bits
into one of the pair and the lower into the other, apply appropriate
masks, and compare one at a time. This is ugly, though, and I need to
compare thousands of longs in a really time-critical section of code.

 

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

How do I compare two longs in an unsigned way without having to do
backflips?

I suppose I could copy each long to a pair of longs, the upper 32 bits
into one of the pair and the lower into the other, apply appropriate
masks, and compare one at a time. This is ugly, though, and I need to
compare thousands of longs in a really time-critical section of code.

Quick attempt on Greater Than:

public static boolean GT(long v1, long v2) {
if(v1 > 0) {
if(v2 > 0) {
return (v1 > v2);
} else {
return false;
}
} else {
if(v2 > 0) {
return true;
} else {
return (v1 > v2);
}
}
}

Arne

 

[Eric Sosman]

How do I compare two longs in an unsigned way without having to do
backflips?

I suppose I could copy each long to a pair of longs, the upper 32 bits
into one of the pair and the lower into the other, apply appropriate
masks, and compare one at a time. This is ugly, though, and I need to
compare thousands of longs in a really time-critical section of code.

Be optimistic, and then be prepared to work harder very
occasionally:

static boolean unsignedLessThan(long l1, long l2) {
if ((l1 >>> 1) != (l2 >>> 1))
return (l1 >>> 1) < (l2 >>> 1);
return (l1 & 1) < (l2 & 1);
}

(This could be rearranged in various ways, but the idea is
simple: Get the answer with one "big chunk" comparison most
of the time, and make a supplementary comparison only if
you must.)

 

[Patricia Shanahan]

Be optimistic, and then be prepared to work harder very
occasionally:

static boolean unsignedLessThan(long l1, long l2) {
if ((l1 >>> 1) != (l2 >>> 1))
return (l1 >>> 1) < (l2 >>> 1);
return (l1 & 1) < (l2 & 1);
}

(This could be rearranged in various ways, but the idea is
simple: Get the answer with one "big chunk" comparison most
of the time, and make a supplementary comparison only if
you must.)

I was thinking along the same lines. Getting the most significant 63
bits compared early seems good. However, if equality is a common case,
consider a pretest.

The details of how best to arrange it are going to be highly data and
situation dependent.

Patricia

 

[Patricia Shanahan]

I was thinking along the same lines. Getting the most significant 63
bits compared early seems good. However, if equality is a common case,
consider a pretest.

The details of how best to arrange it are going to be highly data and
situation dependent.

Patricia

Seems too simple to be true:

v1 + Long.MIN_VALUE "op" v2 + Long.MIN_VALUE

where "op" is any of the numeric comparison operators.

The idea is to shift the ranges so that zero maps to Long.MIN_VALUE
etc., and the natural comparison order is the right one.

Patricia

 

[Patricia Shanahan]

Patricia Shanahan wrote:
....

Seems too simple to be true:

v1 + Long.MIN_VALUE "op" v2 + Long.MIN_VALUE

where "op" is any of the numeric comparison operators.

The idea is to shift the ranges so that zero maps to Long.MIN_VALUE
etc., and the natural comparison order is the right one.

Replying to my own article, yet again, the method is correct, and I
don't think there is a simpler one, but I don't think that is a very
clear explanation. I'm using 32 bit int so that I don't have to type as
many digits, but long works the same way.

Unsigned binary arithmetic and two's complement signed binary arithmetic
agree about the bit pattern that results from adding one to any bit pattern.

In both cases, comparisons treat B as being greater than A if, and only
if, you can obtain B from A by repeated addition of one, without going
through a wrap-around point. At the wrap-around, adding one takes you
from the largest to the smallest value.

They disagree about where the wrap-around point should fall. For
unsigned, 0xffffffff is the largest, and its add-one successor, 0, is
the smallest. For 2's complement, 0x7fffffff, Integer.MAX_VALUE, is the
largest, and its add-one successor, 0x80000000, Integer.MIN_VALUE, is
the smallest.

Adding MIN_VALUE maps the unsigned largest to the 2's complement
largest, and its successor, the unsigned smallest, to the 2's complement
smallest. Getting from A+MIN_VALUE to B+MIN_VALUE by repeated addition
of one goes through the 2's complement wrap around point if, and only
if, getting from A to B by repeated addition of one would go through the
unsigned binary wrap-around point.

Thus the result of a 2's complement signed comparison between
v1+Long.MIN_VALUE and v2+Long.MIN_VALUE, is the same as the result of
the same comparison between v1 and v2 in unsigned long arithmetic.

Patricia

 

[Chris Uppal]

Seems too simple to be true:

v1 + Long.MIN_VALUE "op" v2 + Long.MIN_VALUE

Very nice. Elegant /and/ branch free !

In fact, on my machine I can't measure a difference in performance between that
and a "normal" signed comparison. In a little test program, that (wrapped up
in a static method) compares 100 million random pairs of doubles in around 0.6
seconds (including the loop overhead), a signed comparison (also wrapped up as
a static method) takes about the same. Eric's version (with a slight change to
cache the double evaluations of l1 >>> 1 and 2>>>1 in locals) takes 1.2
seconds, and Arne's version 0.8.

-- chris

 

[Eric Sosman]

>
Seems too simple to be true:

v1 + Long.MIN_VALUE "op" v2 + Long.MIN_VALUE

where "op" is any of the numeric comparison operators.

Slick!

 

[Chris]

Seems too simple to be true:

v1 + Long.MIN_VALUE "op" v2 + Long.MIN_VALUE

where "op" is any of the numeric comparison operators.

The idea is to shift the ranges so that zero maps to Long.MIN_VALUE
etc., and the natural comparison order is the right one.

This is excellent.

I should have defined the question a little more precisely, though. I
need to know if v1 is greater than, equal to, or less than v2. Here is
my current code:

private long unsignedCompare(long long0, long long1) {
long cmp = (long0 >>> 1) - (long1 >>> 1);
if (cmp == 0) {
return (long0 & 0x1) - (long1 & 0x1);
}
return cmp;
}

It returns an integer which is positive, negative, or 0.

Can your method make this execute faster? Does this work?

return (v1 + Long.MIN_VALUE) - (v2 + Long.MIN_VALUE);

(I'm hoping that the compiler can inline this function, else the
overhead of the function call would probably overwhelm any benefit from
a faster compare.)

 

[Patricia Shanahan]

This is excellent.

I should have defined the question a little more precisely, though. I
need to know if v1 is greater than, equal to, or less than v2. Here is
my current code:

private long unsignedCompare(long long0, long long1) {
long cmp = (long0 >>> 1) - (long1 >>> 1);
if (cmp == 0) {
return (long0 & 0x1) - (long1 & 0x1);
}
return cmp;
}

It returns an integer which is positive, negative, or 0.

Can your method make this execute faster? Does this work?

return (v1 + Long.MIN_VALUE) - (v2 + Long.MIN_VALUE);

Unfortunately, no. The effects on bit patterns of additions and
subtractions are the same in signed and unsigned arithmetic. That is
equivalent to "return v1-v2;". The right shift in the current version
gets you out of some problems with overflow.

Are you sure you want to put all the compares in one basket? It will
tend to decrease branch predictability. Presumably, you are going to
test the unsignedCompare result by comparing it to zero, so why not test
the numbers directly in line?

i.e. replace:

long result = unsignedCompare(x,y);
if(result > 0){
// do something
}else if(result < 0){
// do something else
}

with

if(x+Long.MIN_VALUE > y+Long.MIN_VALUE){
// do something
}else if(x+Long.MIN_VALUE < y+Long.MIN_VALUE){
// do something else
}

Patricia

 

[Chris]

Are you sure you want to put all the compares in one basket? It will

tend to decrease branch predictability. Presumably, you are going to
test the unsignedCompare result by comparing it to zero, so why not test
the numbers directly in line?

i.e. replace:

long result = unsignedCompare(x,y);
if(result > 0){
// do something
}else if(result < 0){
// do something else
}

with

if(x+Long.MIN_VALUE > y+Long.MIN_VALUE){
// do something
}else if(x+Long.MIN_VALUE < y+Long.MIN_VALUE){
// do something else
}

Explain branch predictability to me? What kind of magic can the compiler
work here?

Also -- would it not be faster to do this?

x += Long.MIN_VALUE;
y += Long.MIN_VALUE;
if (x > y) {
// do this
} else if (x < y) {
// do that
}

Or is the compiler smart enough to do the additions only once on its own?

 

[Guest]

Also -- would it not be faster to do this?

x += Long.MIN_VALUE;
y += Long.MIN_VALUE;
if (x > y) {
// do this
} else if (x < y) {
// do that
}

Or is the compiler smart enough to do the additions only once on its own?

Depends on what JIT compiler it is.

But I would expect good JIT compilers on common
platform to be able to do that optimization.

They are rather smart nowadays.

Arne

 

[Patricia Shanahan]

Explain branch predictability to me? What kind of magic can the compiler
work here?

It's not a compiler issue. A modern processor is a sort of production
line factory. Instructions are fetched in to the "pipeline" and spend
multiple cycles moving through various stages.

The processor has a real problem when it loads a conditional branch into
the pipeline. It does not know what instructions to load after it, and
will not know for sure until the branch gets to a very late stage and
the branch condition has been evaluated.

Rather than being certain of wasting dozens of opportunities to do
instructions, the processor makes a guess, and gets the corresponding
instructions flowing through the pipeline.

If the processor guesses right, the branch is no more expensive than any
other simple operation. If the processor guesses wrong, it has to stop,
throw away any work done on instructions that logically follow the
branch, and begin again working the right list of instructions through
the pipeline. That can be very expensive.

The processor makes its guesses based on the assumption that patterns
that have happened in the past are more likely than completely new
patterns of branch taking and not taking.

If you want to learn more about this, do a search for "branch prediction".

Also -- would it not be faster to do this?

x += Long.MIN_VALUE;
y += Long.MIN_VALUE;
if (x > y) {
// do this
} else if (x < y) {
// do that
}

Or is the compiler smart enough to do the additions only once on its own?

It might be, but it might not matter if the additions are done twice. An
integer addition is trivial compared to a conditional branch. Note that
Chris Uppal reported earlier in the thread that he could not measure the
difference between my version and conventional signed long comparison.

I believe he was comparing random pairs of longs, so about half the
branches would be mispredicted. In your real work, there is hope that
particular branches will have patterns to them, and the predictor will
be able to do better than random. At that point, it might be worth while
looking at optimizing the additions and see if it makes a difference.

Patricia