E
Eric Sosman
Thomas Hawtin wrote On 01/31/06 15:21,:
sgn(0L) -> 1
sgn(0L) -> 1
S
Stefan Ram
Eric Sosman said:
I have not really an idea what this thread is about, but:
public class Main
{ public static int isLessThan( final long left, final long right )
{ return( int )-(( left - right )>> 63 ); }
public static int signum( final long value )
{ return isLessThan( 0, value )-isLessThan( value, 0 ); }
public static void main( final java.lang.String[] args )
{ java.lang.System.out.println( signum( 2L ));
java.lang.System.out.println( signum( 1L ));
java.lang.System.out.println( signum( 0L ));
java.lang.System.out.println( signum( -1L ));
java.lang.System.out.println( signum( -2L )); }}
P
Piotr Kobzda
Roedy said:
You don't have to, it works fine now.
My suggestion (shifts and ors) is a little faster under "client" VM,
under "server" VM your method wins (positions swaps). But we both beat
the competition...
))Nevertheless, it seams to me there is no way to firmly say which method
is fastest for all possible JVMs... But who cares? ... ;-)
Regards,
piotr
R
Roedy Green
I decided to write a test harness to test and time these
contributions:
Here in the output from eclipse:
standard = done with if
Sun = (int) ((i >> 63) | (-i >>> 63)) Long.signum.
signOf = return ( diff != 0 ) ? ( (int) ( diff >>> 32 ) | 1 ) : 0;
sgn = (int) ( diff >> 63 ) ) | ( (int) ( ( ~diff ) >>> 63 );
sgn failed on 0. All the others passed my conformance tests.
On Eclipse the speed the ordering was
standard best, signOf, sgn, sun
Checking conformance on crucial values...
done
Checking conformance on 10 million random longs...
sgn fails at 0 giving 1
done
testing standard signum...
standard: 55984 0
testing Sun's signum...
Sun: 77578 0
testing signOf...
signof: 57469 0
testing sgn...
sgn: 60156 200000000
on Java.exe the speed the ordering was laso
standard best, signOf, sgn, sun
Checking conformance on crucial values...
sgn fails at 0 giving 1
done
Checking conformance on 10 million random longs...
done
testing standard signum...
standard: 49656 0
testing Sun's signum...
Sun: 70438 0
testing signOf...
signof: 53968 0
testing sgn...
sgn: 63235 200000000
finished
with Jet things change drastically:
Now SignOf in a clear winner, twice as fast the runner up and 4 times
as fast as Sun's.
The order is signof, standard, sgn, Sun.
Checking conformance on crucial values...
sgn fails at 0 giving 1
done
Checking conformance on 10 million random longs...
done
testing standard signum...
standard: 31016 0
testing Sun's signum...
Sun: 74390 0
testing signOf...
signof: 16438 0
testing sgn...
sgn: 67953 200000000
finished
The other interesting fact is that is using Jet with signOf is 4.7
times faster than using Sun's Long.signum with Java.exe.
You might wonder why signof is so much faster.
Hint: always use unsigned shifts when you can. Clever optimisers can
use machine instructions for example that will store the high 32 bits
of a long directly to memory or another register. ~ & and | are very
cheap operations, same as + -. conditional jumps are expensive.
Here is the test harness so you can experiment on your own platform.
package com.mindprod.example;
import java.util.Random;
/**
* Compare four different ways of doing a signum.
*
* @author Roedy Green
*/
public class TestSignum {
/**
* crucial values to test for conformance.
*/
private static long testValues[] = {
Long.MIN_VALUE,
Long.MIN_VALUE + 1,
Long.MIN_VALUE + 2,
Integer.MIN_VALUE - 2,
Integer.MIN_VALUE - 1,
Integer.MIN_VALUE,
Integer.MIN_VALUE + 1,
Integer.MIN_VALUE + 2,
-2,
-1,
0,
1,
2,
Integer.MAX_VALUE - 2,
Integer.MAX_VALUE - 1,
Integer.MAX_VALUE,
Integer.MAX_VALUE + 1,
Integer.MAX_VALUE + 2,
Long.MAX_VALUE - 2,
Long.MAX_VALUE - 1,
Long.MAX_VALUE
};
/**
* test all four signum-like algorithms for conformance. To pass
must return
* a + int for a positive long, a -ve int for a negitive long and
0 for a
* zero long.
*
* @param diff
* number to be collapsed to an int preserving sign and
zeroness.
*/
static void checkConforms ( long diff )
{
int standard = signum( diff );
// Sun's Long.signum is implemented as (int) ((i >> 63) | (-iint sun = Long.signum( diff );
int signOf = signOf( diff );
int sgn = sgn( diff );
if ( signum( sun ) != standard )
{
System.err.println( "sun fails at " + diff + " giving " +
sun );
}
if ( signum( signOf ) != standard )
{
System.err
.println( "signOf fails at " + diff + " giving " +
signOf );
}
if ( signum( sgn ) != standard )
{
System.err.println( "sgn fails at " + diff + " giving " +
sgn );
}
}
/**
* Test harness to compare the various signum methods.
*
* @param args
* not used
*/
public static void main ( String[] args )
{
System.out.println( "Checking conformance on crucial
values..." );
for ( long diff : testValues )
{
checkConforms( diff );
}
System.out.println( "done" );
System.out
.println( "Checking conformance on 10 million random
longs..." );
Random wheel = new Random();
for ( int i = 0; i < 10000000; i++ )
{
checkConforms( wheel.nextLong() );
}
System.out.println( "done" );
/** timing test */
/** run timing test 200 million times */
timeStandard();
timeSun();
timeSignOf();
timeSgn();
System.out.println( "finished" );
}
/** how many times to run the timing tests */
final static int timingIterations = 200000000;
/**
* Time the standard signum implementation
*/
private static void timeStandard ()
{
System.out.println( "testing standard signum..." );
int sum = 0;
long start = System.currentTimeMillis();
for ( int i = 0; i < timingIterations; i++ )
{
for ( long diff : testValues )
{
sum += signum( diff );
}
}
// print sum so code to compute it won't be optimised away
System.out.println( "standard: "
+ ( System.currentTimeMillis() - start )
+ " "
+ sum );
}
/**
* Time the signOf signum implementation
*/
private static void timeSignOf ()
{
System.out.println( "testing signOf..." );
int sum = 0;
long start = System.currentTimeMillis();
for ( int i = 0; i < timingIterations; i++ )
{
for ( long diff : testValues )
{
sum += signOf( diff );
}
}
// print sum so code to compute it won't be optimised away
System.out.println( "signof: "
+ ( System.currentTimeMillis() - start )
+ " "
+ sum );
}
/**
* Time the signOf signum implementation
*/
private static void timeSgn ()
{
System.out.println( "testing sgn..." );
int sum = 0;
long start = System.currentTimeMillis();
for ( int i = 0; i < timingIterations; i++ )
{
for ( long diff : testValues )
{
sum += sgn( diff );
}
}
// print sum so code to compute it won't be optimised away
System.out.println( "sgn: "
+ ( System.currentTimeMillis() - start )
+ " "
+ sum );
}
/**
* Time the sun's signum implementation
*/
private static void timeSun ()
{
System.out.println( "testing Sun's signum..." );
int sum = 0;
long start = System.currentTimeMillis();
for ( int i = 0; i < timingIterations; i++ )
{
for ( long diff : testValues )
{
sum += Long.signum( diff );
}
}
// print sum so code to compute it won't be optimised away
System.out.println( "Sun: "
+ ( System.currentTimeMillis() - start )
+ " "
+ sum );
}
/**
* Thomas Hawtin's algorithm 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
* number to be collapsed to an int preserving sign and
zeroness.
* usually represents the difference of two long.
* @return sign of diff, some -ve int, 0 or some -ve int.
*/
public static int sgn ( long diff )
{
return ( (int) ( diff >> 63 ) ) | ( (int) ( ( ~diff ) >>> 63 )
) ;
}
/**
* 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
* number to be collapsed to an int preserving sign and
zeroness.
* usually represents the difference of two long.
* @return sign 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;
}
/**
* Collapse number down to +1 0 or -1 depending on sign. Typically
used in
* compare routines to collapse a difference of two longs to an
int.
*
* @param diff
* number to be collapsed to an int preserving sign and
zeroness.
* usually represents the difference of two long.
* @return true signum of diff, +1, 0 or -1.
*/
public static final int signum ( long diff )
{
if ( diff > 0 )
{
return 1;
}
if ( diff < 0 )
{
return -1;
}
else
{
return 0;
}
} // end signum
}
T
Thomas Hawtin
Eric said:
Er, yeah. The comment is exactly wrong.
Tom Hawtin
R
Roedy Green
your algorithm fails at -9223372036854775808 giving 0
W
Wibble
You can do a little better than signof or sgn:Roedy said:
public static final int wibble ( long diff )
{
return ( ((int)( diff >>> 32 ))
| (((int)diff)>>>1)&0x7fffffff
| (((int)diff)&1));
} // end signum
W
Wibble
Wibble said:
Oops, dont need the &0xfffffff, not much worse than standard on my box....
public static final int mdw ( long diff )
{
return ( ((int)( diff >>> 32 ))
| (((int)diff)>>>1)
| (((int)diff)&1));
}
P
Piotr Kobzda
Roedy said:
Just for comparison, below are listed results for my platform (XP,
1x1,8GHz, 1GB RAM), with additional contribution of the following method:
public static final int signShift ( long diff )
{
return (int)(diff >>> 32) | (int)diff >>> 1 | (int)diff & 1;
}
Sun's 1.5.0_06 "client" VM:
signShift best, standard, sgn, signOf, sun
Checking conformance on crucial values...
done
Checking conformance on 10 million random longs...
done
testing standard signum...
sgn fails at 0 giving 1
standard: 64125 0
testing Sun's signum...
Sun: 78703 0
testing signOf...
signof: 75344 0
testing sgn...
sgn: 73453 200000000
testing signShift...
signShift: 60547 2094967296
finished
Sun's 1.5.0_06 "server" VM:
standard best, signOf, sgn, signShift, sun
Checking conformance on crucial values...
done
Checking conformance on 10 million random longs...
done
testing standard signum...
sgn fails at 0 giving 1
standard: 29609 0
testing Sun's signum...
Sun: 55032 0
testing signOf...
signof: 39140 0
testing sgn...
sgn: 46813 200000000
testing signShift...
signShift: 48672 2094967296
finished
Have no Jet things here to test with.
There are a few differences in your results comparing to my previous
tests. Interesting because the only significant difference in testing
method I've found is shorter timing loop and time measurement using
System.nanoTime() in my tests.
Biggest surprise is very good performance of the "standard" method, not
observed before by me.
The only similarity to my tests I can see under the client VM tests results.
Regards,
piotr
R
Roedy Green
Results of benchmarks to find the fastest Long.signum implementation
stephan fails at -9223372036854775808 giving 0
sgn fails at 0 giving 1
Under Eclipse
millis : candidate
49079 : wibble
53500 : Standard 2 ifs
57469 : signOf
62281 : sgn
69765 : Sun Long.signum
93156 : stephan
under Java.exe -client 1.5
millis : candidate
52000 : Standard 2 ifs
52781 : signOf
53907 : wibble
65094 : sgn
66938 : Sun Long.signum
88468 : stephan
under Java.exe -server 1.6
millis : candidate
29188 : signOf
29985 : wibble
35297 : sgn
37562 : Standard 2 ifs
37625 : Sun Long.signum
42968 : stephan
under Jet 4.0
millis : candidate
13156 : wibble
16562 : signOf
34266 : Standard 2 ifs
69954 : sgn
74906 : Sun Long.signum
113859 : stephan
So what have we discovered:
1. fastest code depends on the JVM. You don't know till you measure
the alternatives.
2. the fastest time was wibble under Jet. This is four times faster
than under Java -client.
3. Though Sun's Long.signum algorithm is terse, it is a pretty much a
pig. Sun's Long.signum is implemented as (int) ((i >> 63) | (-i >>>
63));
I have posted the improved test harness at
http://mindprod.com/jgloss/benchmark.html
R
Roedy Green
Why would you care? Because sorting is often the bottleneck, and the
compare is always the bottleneck of sorting and many compares contain
signum logic.
Knuth says that premature optimisation is the root of all evil.
However, routines that are core and used by everyone are ripe for
optimisation, if you just want to exercise your skills.
You might as well do it right. People often affect the nutty idea
that it is virtuous to write knowingly slow code even when you know of
faster simpler ways. Many folk irrationally believe it is virtuous to
pretend not to have any concerns for speed at ANY time.
What you DON'T do is fiddle with tiny bits of code making them harder
to maintain, until you have demonstrated they are bottlenecks. There
is no reason at all to avoid fast library code or fast algorithms
first time out.
If you know on square 1 that the fastest algorithm to compute
something and the code for it exists, you might as well use it. There
is no more work than using some lame algorithm.
R
Roedy Green
I have changed this is my latest version making sum local rather than
static. It makes quite a difference. My intent was to pare
non-candidate code to the bone in the inner loop.
I accumpulate the sum to a static at the end just in case the
optimiser thinks these calculations are so much hot air.
T
Thomas Hawtin
Roedy said:
I'd like to call foul here. If diff is zero, effectively the result is
ignored.
OTOH, it occurs to me that the typical use of a comparator function is
to 'switch' on the result. (Sorry to bring things back closer to
reality.) Therefore, you actually want the conditional jumps anyway.
'Cleverness' will just clog up the pipeline. In terms of assempler,
actually all you want the processor to do is compare against zero
(possibly available as a side-effect of a load or move).
Intel-style deep pipelines will lose heavily with such bi-twiddling.
Niagra-style single-dispatch, multiple-hardware thread architectures
should do better.
There's also the standard problem with the microbenchmarks: The test
methods have hot inner loops lumped together with large single-use I/O
and timing code. Perhaps a better test would be using some sort.
Tom Hawtin
R
Roedy Green
You might wonder what the heck is going on. the variability is more
than most people would expect.
Consider that longs are faked as a pair of 32 bit registers on 32-bit
machines. This make long operations take more than twice as long as in
ones. The trick is to prune your calculations back to int at the
earliest opportunity. (Wibble2 does this.)
Consider that at the hardware level you have pipelines. This allows
parallel execution of the algorithm if it nicely decomposes into
independent parts.
Consider that on some hardware you have speculative execution of both
a true and false branch in parallel.
Consider that on some hardware jumps are free. The pipeline
preprocessor deals with them.
Consider that on some hardware jumps are very expensive. They clear
caches and pipelines.
Consider that some hardware has special instructions for moving the
upper and lower halves of a long or int.
Consider that >>> is inherently a simpler operation than >>.
Consider that though & | ~ are exotic to most Java programmers, they
are one-cycle ops just like + and -.
Consider that with hotspot, you run interpretively for awhile, then
take time out to compile to native code, and later to optimise. You
are also paying the penalty for this translation time. The behaviour
of interpreted code is vastly different from optimised machine code.
There you have a heavy overhead per JVM instruction so the trick is to
use as few JVM instructions as possible relatively independently of
what they do.
I'd like to see some results from some more exotic hardware,
especially the Power PC whose architecture I find aesthetically
pleasing. Also I'd like to see how the horse-race changes on a 64-bit
machine. I suspect Sun's algorithm will shine there.
R
Roedy Green
you also don't need that forest of (). I have added your revised
algorithm to the harness. Results to come shortly. It takes about
half an hour to run the battery. My last test was interrupted by the
announcement of new Eclipse updates.
..
R
Roedy Green
here's the latest results. As expected, wibble2 is better than
wibble. What I don't understand is why signOf has pulled ahead of
wibble and wibble2. There should be no GC going on to confuse the
issue.
the latest benchmark harness is posted at
http://mindprod.com/jgloss/benchmark.html
* Compare eight different ways of doing a signum.
* Results of benchmarks to find the fastest Long.signum
implementation.
*
* stephan fails at -9223372036854775808 giving 0
* sgn fails at 0 giving 1
*
* Candidates at the top with the lowest elapsed time in
nanoseconds are fastest.
*
* Under Eclipse 3.1
* nanoseconds : candidate
* 45768960301 : wibble2
* 49644018723 : wibble
* 53844393072 : Standard 2 ifs
* 57757400172 : signOf
* 62539824754 : sgn
* 70119185818 : Sun Long.signum
* 93615190478 : stephan
*
* under Java.exe -client 1.5
* nanoseconds : candidate
* 45046931943 : wibble2
* 52720203825 : Standard 2 ifs
* 53114062821 : signOf
* 54456221112 : wibble
* 65598471873 : sgn
* 67578554258 : Sun Long.signum
* 89407076039 : stephan
*
* under Java.exe -server 1.6
* nanoseconds : candidate
* 30604675175 : signOf
* 30795535466 : wibble2
* 30916536599 : wibble
* 37537113795 : sgn
* 38492840011 : Standard 2 ifs
* 40344760018 : Sun Long.signum
* 44422669361 : stephan
*
* under Jet 4.0
* nanoseconds : candidate
* 14847425301 : signOf
* 36774335007 : wibble2
* 39282795997 : wibble
* 48173823210 : Standard 2 ifs
* 73310262058 : sgn
* 74333541274 : Sun Long.signum
* 79269158511 : stephan
signOf with Jet is the fastest combination.
W
Wibble
Roedy said:
I get crazy variablilty between runs and when I reorder
the tests. How many times did you run the benchmarks?
Maybe -Xbatch would give you more control of when the
optimizer runs.
I'm a lisp programmer. I like forests of parens
))))
R
Roedy Green
those are just the results of one run. This is tedious business.
Even that batch took 30 minutes during which time I could not use my
computer least I disturb the results.
Maybe to get the final optimimizations, I should run the tests,
discard the result the run them again in the same JVM, hoping the
world settles to a steady state.
R
Roedy Green
latest benchmark results of nine candidates are posted at
http://mindprod.com/jgloss/benchmark.html
the new overall winner is signOf under Java server 1.5.
P
Piotr Kobzda
Roedy said:
Hmm, 9th candidate is here:
return (int)( diff >>> 32 ) | ( (int)diff | (int)diff << 1 ) >>> 1;
On my box under the Sun server 1.5 JVM the winner is 'Standard 2 ifs'.
Under the JRockit a different animal is the winner too.
Here are my results (the 9th candidate is called "piotr"):
C:\Eclipse\Workspaces\testy\signum\bin>c:\java\jdk1.5.0_06\bin\java
-Xbatch -client com.mindprod.example.TestSignum
Checking conformance on crucial corner values...
stephan fails at -9223372036854775808 giving 0
sgn fails at 0 giving 1
Checking conformance on 10 million random longs...
Running timing tests with 200000000 iterations per candidate.
..........
nanoseconds : candidate
66588911719 : piotr
67003112686 : wibble
71864425228 : kobzda
82698686006 : sgn
84221045692 : signOf
88460140884 : signHalf
93383637865 : Standard 2 ifs
94397889397 : Sun Long.signum
131756354230 : stephan
finished
C:\Eclipse\Workspaces\testy\signum\bin>c:\java\jdk1.5.0_06\bin\java
-Xbatch -server com.mindprod.example.TestSignum
Checking conformance on crucial corner values...
stephan fails at -9223372036854775808 giving 0
sgn fails at 0 giving 1
Checking conformance on 10 million random longs...
Running timing tests with 200000000 iterations per candidate.
..........
nanoseconds : candidate
39823319724 : Standard 2 ifs
41425703546 : signOf
45461844732 : signHalf
58202726883 : kobzda
59459250267 : wibble
62102067441 : sgn
64176119591 : piotr
65859999245 : Sun Long.signum
80201802184 : stephan
finished
C:\Eclipse\Workspaces\testy\signum\bin>c:\java\jrockit-R26.0.0-jdk1.5.0_04\bin\java
com.mindprod.example.TestSignum
Checking conformance on crucial corner values...
stephan fails at -9223372036854775808 giving 0
sgn fails at 0 giving 1
Checking conformance on 10 million random longs...
Running timing tests with 200000000 iterations per candidate.
..........
nanoseconds : candidate
44890325167 : piotr
48472883285 : kobzda
48476054359 : wibble
52179261889 : sgn
54405104001 : Sun Long.signum
66876197953 : signOf
81686631122 : stephan
88293991555 : signHalf
108119541450 : Standard 2 ifs
finished
Regards,
piotr