signum of long

[Roedy Green]

When you do a comparator you are supposed to return a + - or 0 int,
even if you have been comparing longs.

Lets say you have + - or 0 long and you want some sort of + 0 or 0
int.

What is the fastest way to get it.

You could do

if ( a > 0 ) return 1;
if ( a < 0 ) return -1;
return 0;

I can't come up with one liner using shift and masks that is less
complex.

if ( a == 0 ) return 0;
else return (int) ( a >>> 32);

since booleans are not bit masks, you can use them in the traditional
Forthian ways.

 

[Robert Klemme]

When you do a comparator you are supposed to return a + - or 0 int,
even if you have been comparing longs.

Lets say you have + - or 0 long and you want some sort of + 0 or 0
int.

What is the fastest way to get it.

You could do

if ( a > 0 ) return 1;
if ( a < 0 ) return -1;
return 0;

I can't come up with one liner using shift and masks that is less
complex.

if ( a == 0 ) return 0;
else return (int) ( a >>> 32);

You're almost there.

return a == 0 ? 0 : (int) (a >> 32);

I don't know whether it's really worth the effort as int arithmetic should
be quite fast anyway. This is certainly something I'd only change from
the straight forward impl (your first version) if that proves to be too
slow.

Kind regards

robert

 

[Roedy Green]

I don't know whether it's really worth the effort as int arithmetic should
be quite fast anyway. This is certainly something I'd only change from
the straight forward impl (your first version) if that proves to be too
slow.

This is a pattern that comes up often writing comparators. In those
cases I like to figure out the fastest way to do it, and use that
consistently.

 

[Roedy Green]

You're almost there.

return a == 0 ? 0 : (int) (a >> 32);

I think from the JVM lever they may generate identical instructions. I
spent so much time back in the 80s fine tuning assembler, it bothers
me to use conditional jumps in stereotypical instances like that.
Conditional jumps are just about the slowest operation because they
tend to screw up pipeline lookahead, caching etc. You can afford to
do quite a bit of arithmetic to avoid one. The Power PC took much of
the penalty away. I don't know about the modern Pentiums.

 

[opalpa]

There is got to be very good reason to distance oneself from an idiom.
Code clarity reduces comprehension time by a lot. It's kind of hard to
compare time reduction in code execution with time reduction in code
maintanance.

This snippet may very well be slower to excute (two if statements in
it and a subtract):

((a > 0)?1:0) - ((a<0)?1:0)

is functionaly equivalent to:

if ( a > 0 ) return 1;
if ( a < 0 ) return -1;
return 0;

if a is positive the first part equates to 1 and the second to 0 and
the subtraction yields 1. if a is zero the first and second part are
both zero and the subtraction yields 0. if a is negative the first
part is 0, the second 1, and the subtraction yields -1.

Opalinski
(e-mail address removed)
http://www.geocities.com/opalpaweb/

 

[Robert Klemme]

This is a pattern that comes up often writing comparators. In those
cases I like to figure out the fastest way to do it, and use that
consistently.

That's easy: put the code into a static method. If measurements show it's
too slow, change the implementation. The JVM is going to inline this
anyway if it's a hot spot.

robert

 

[Robert Klemme]

I think from the JVM lever they may generate identical instructions. I
spent so much time back in the 80s fine tuning assembler, it bothers
me to use conditional jumps in stereotypical instances like that.
Conditional jumps are just about the slowest operation because they
tend to screw up pipeline lookahead, caching etc. You can afford to
do quite a bit of arithmetic to avoid one. The Power PC took much of
the penalty away. I don't know about the modern Pentiums.

Don'f forget that there's the JVM between that also. Usually these things
are not worth the effort until they proove to be a source of performance
problems.

robert

 

[Boris Stumm]

When you do a comparator you are supposed to return a + - or 0 int,
even if you have been comparing longs.

Lets say you have + - or 0 long and you want some sort of + 0 or 0
int.

What is the fastest way to get it.

return Long.signum(a);

or, as comparison:
return Long.signum(a-b);

 

[Eric Sosman]

Robert Klemme wrote On 01/30/06 07:28,:

You're almost there.

return a == 0 ? 0 : (int) (a >> 32);

This doesn't look right: It returns zero for `a'
equal to forty-two, for example.

Best I can think of is something like

return (a > 0) ? 1 : (int)(a >> 32);

 

[Roedy Green]

Don'f forget that there's the JVM between that also. Usually these things
are not worth the effort until they proove to be a source of performance
problems.

Agreed. This is more a obsessive thing, just wanting to know the
fastest way. Then I can use the fastest way routinely, mindlessly,
and know there is one thing I don't have to think about that may need
tweaking. This assumes the fastest way is not so ugly it would
confuse maintenance programmers. If it is encapsulated and inlined,
you can explain it.

 

[Roedy Green]

return Long.signum(a);

or, as comparison:
return Long.signum(a-b);

that came in with JDK 1.5.

 

[opalpa]

or, as comparison:

return Long.signum(a-b);

Might be fast, but it is incorrect:

package experiment;
public class signum {
static public void main(String args[]) {
long a = java.lang.Long.MIN_VALUE;
long b = 1;
int cmpsignum = Long.signum(a-b);
int cmpcorrect = basicCmp(a,b);
System.out.println("maybe="+cmpsignum+" really="+cmpcorrect);
}
static private int basicCmp(long a, long b) {
if ( a > b ) return 1;
if ( a < b ) return -1;
return 0;
}
}

Opalinski
(e-mail address removed)
http://www.geocities.com/opalpaweb/

 

[Roedy Green]

that came in with JDK 1.5.

see http://mindprod.com/jgloss/signum.html
for my little essay on the subject.

 

[Piotr Kobzda]

see http://mindprod.com/jgloss/signum.html
for my little essay on the subject.

Well, I think there is something wrong with your code:

<cite>
/**
* alternate to signum for use in compare.
* Not a true signum, since it returns ints
* other than +-1. Where there is any possibility of overflow,
* you should compare two longs with < rather than subtraction.
*
* @param diff usually represents the difference of two long.
*
* @return signum of diff, some -ve int, 0 or some -ve int.
*
*/
public static final int signOf ( long diff )
{
return (a != 0) ? (int)(a >>> 32) : 0;
}

</cite>

First of all a trivial refactoring of 'a' to 'diff' is needed.
Next, consider replacement with the following code:

return (int)(a >>> 32);

Both are equivalent, but the latter should be faster in most cases.


Worst thing is, it doesn't work as described in your comment (if I
understand it well).

What is expected result for e.g. signOf(1L)?
My expectation is some positive integer, but your code produce *0* in
this case?!...


Let's check the consequences:

Long[] test = { 1L, 0L, 4L, 2L, 3L };
Arrays.sort(test, new Comparator<Long>() {
public int compare(Long a1, Long a2) {
long a = a1 - a2;
return (a != 0) ? (int)(a >>> 32) : 0;
}
});
System.out.println(Arrays.asList(test));

The code above produce the following output:

[-1, 0, -4, -2, -3]

Not the expected one, I guess...


I think, your intention is the code like this:

return (a <= 0) ? (int)(a >>> 32) : 1;

Which works fine.

But there are some faster solutions available, e.g:

return (int)(a >>> 32) | (int)a >>> 1 | (int)a & 1;

My simple performance tests shows the latter is even a little faster
than Java 5's Long.signum(). But I haven't tested it intensively...


Regards,
piotr

 

[Roedy Green]

public static final int signOf ( long diff )
{
return (a != 0) ? (int)(a >>> 32) : 0;
}

</cite>
oops.

First of all a trivial refactoring of 'a' to 'diff' is needed.
Next, consider replacement with the following code:

return (int)(a >>> 32);

Both are equivalent, but the latter should be faster in most cases.

consider diff = 3. that would turn into 0 with your method.


The following is still not quite right. See if you can see the flaw:
return (int) ( (a >>> 32) | ( a & 0x07fffff ));

that would have been faster on the old 8086, the assembler I spent
most time in.

the essential problem is you must examine/summarise all 64 bits to
detect 0, and == 0 does to return an integer you can do anything with.
All you can do with a boolean are conditional jumps.

 

[Stefan Ram]

First of all a trivial refactoring of 'a' to 'diff' is needed.

Refactoring means making changes that don't add or change
functionality for clarity. Here you are rectifying a mistake.

 

[Piotr Kobzda]

consider diff = 3. that would turn into 0 with your method.

The method is _yours_, mine is optimized version of it only.

The result of your signOf(3) is 0.
For each 'diff' ranged from 0 to 0xFFFFFFFFL result is 0 as well.

The reason is loose of 32 youngest bits of argument.

The following is still not quite right. See if you can see the flaw:
return (int) ( (a >>> 32) | ( a & 0x07fffff ));

that would have been faster on the old 8086, the assembler I spent
most time in.

Right, but you have similar problem here -- lost bit #31 of 'a'.

the essential problem is you must examine/summarise all 64 bits to
detect 0, and == 0 does to return an integer you can do anything with.
All you can do with a boolean are conditional jumps.

I'm not sure I understand you right. My suggestion, I mean:
return (int)(a >>> 32) | (int)a >>> 1 | (int)a & 1;

behaves exactly as you've mentioned. There is bitwise sum of all 64
bits, with special care on "sign" bit, that's all.


The correction on your site looks better, but IMHO is still buggy...


Regards,
piotr

 

[Piotr Kobzda]

Refactoring means making changes that don't add or change
functionality for clarity. Here you are rectifying a mistake.

Refactoring means also modifying source code without changing its
*external behavior*.

The fragment I've modified is a single line of code, without any change
of its (the line) external behavior...

The refactoring scope may vary.


Regards,
piotr

 

[Roedy Green]

The result of your signOf(3) is 0.
For each 'diff' ranged from 0 to 0xFFFFFFFFL result is 0 as well.

The reason is loose of 32 youngest bits of argument.

How about this:

/**
* alternate to signum for use in compare.
* Not a true signum, since it returns ints
* other than +-1. Where there is any possibility of overflow,
* you should compare two longs with < rather than subtraction.
*
* @param diff usually represents the difference of two long.
*
* @return signum of diff, some -ve int, 0 or some -ve int.
*
*/
public static final int signOf ( long diff )
{
return ( diff != 0 ) ? ( (int)( diff >>> 32 ) | 1 ) : 0;
}


If I screw up this time, I write a test harness.

 

[Thomas Hawtin]

When you do a comparator you are supposed to return a + - or 0 int,
even if you have been comparing longs.

Lets say you have + - or 0 long and you want some sort of + 0 or 0
int.

What is the fastest way to get it.

You could do

if ( a > 0 ) return 1;
if ( a < 0 ) return -1;
return 0;

I can't come up with one liner using shift and masks that is less
complex.

if ( a == 0 ) return 0;
else return (int) ( a >>> 32);

since booleans are not bit masks, you can use them in the traditional
Forthian ways.

How about this (not tested or even compiled, just for added excitement)?

public static int sgn(long value) {
return ((int)(value>>63)) | ((int)((~value)>>>63))
}

(that's a tilde not a minus)

Tom Hawtin