How to write an efficient maximum function?

[Ahmed Moustafa]

Hello,

What would be the most efficient to write a maximum function in Java?

Initially, I had the comparisons that looked for the maximum inside the
main method and then moved it inside its own method (code is below) to
be called from within the main method (to make the code look prettier),
but that cost me almost 3 additional seconds processing time:

<code>
private static float maximum (float a, float b, float c, float d) {
float t1 = a > b ? a : b;
float t2 = c > d ? c : d;
return t1 > t2 ? t1 : t2;
}
</code>

Is there something like C's macros to keep the code clean but to save
the processing time for calling the macro?

Thanks in advance,

Ahmed

 

[Andrew Thompson]

Initially, I had the comparisons that looked for the maximum inside the
main method and then moved it inside its own method (code is below) to
be called from within the main method (to make the code look prettier),
but that cost me almost 3 additional seconds processing time:

Provide an SSCCE that supports this extraordinary claim.
<http://www.physci.org/codes/sscce.jsp>

 

[thirdrock]

Is there something like C's macros to keep the code clean but to save
the processing time for calling the macro?

Er, use *inline* ?

 

[Boudewijn Dijkstra]

Hello,

What would be the most efficient to write a maximum function in Java?

Initially, I had the comparisons that looked for the maximum inside
the main method and then moved it inside its own method (code is
below) to be called from within the main method (to make the code look
prettier), but that cost me almost 3 additional seconds processing
time:

<code>
private static float maximum (float a, float b, float c, float d) {
float t1 = a > b ? a : b;
float t2 = c > d ? c : d;
return t1 > t2 ? t1 : t2;
}
</code>

That method always runs in the same amount of VM ticks. It takes:
- 3 comparisons;
- 3 copies; and
- 3 jumps.

How about:

private static float maximum(float a, float b, float c, float d)
{
float max = a;
if (b > max) max = b;
if (c > max) max = c;
if (d > max) max = d;
return max;
}

which takes:
- 1..4 copies;
- 3 comparisons; and
- 3 jumps.

The average number of copies is calculated as follows:
if a is maximum: 1 copy
if b is maximum: 2 copies
if c is maximum: 3 copies
if d is maximum: 4 copies
average copies = (1 + 2 + 3 + 4) / 4 = 10 / 4 = 2.5

Note that 2.5 < 3

You can even theoretically reduce that 2.5 to 1.5 by removing the first line
and replacing 'max' by 'a', but that should probably be up to the optimizer.

 

[Chris Uppal]

Initially, I had the comparisons that looked for the maximum inside the
main method and then moved it inside its own method (code is below) to
be called from within the main method (to make the code look prettier),
but that cost me almost 3 additional seconds processing time:

This sounds odd. If you assume that the extra overhead of calling a static
method with 4 float arguments and 2 float temps is just a handful of
nanoseconds (I admit I haven't explicitly measured that, but it should be
roughly correct), then you must be calling this function on the order of a
billion times. I'm finding it hard to imagine an application that would need
to do so, but which wouldn't /also/ take so long to run (just creating that
much float data would be slow...) that the additional 3 seconds makes no real
difference. It'd be interesting to know a little more about what you are doing
here.

Is there something like C's macros to keep the code clean but to save
the processing time for calling the macro?

Not really, not in standard Java. You could always just write a little, highly
specialised, pre-processor in your favourite scripting language. If you don't
want to do that, then I think you are stuck with the decision whether those
three seconds are more important than the clarity of your code.

You may find, if you're not using it already, that the extra optimisations
invoked by running the JVM with the -server flag (assuming you're using a Sun
JVM) will get you your 3 seconds back, or -- if you're lucky -- even more).

(I'm assuming, of course, that you are already using the "best" algorithm for
this job -- if not then messing around with inlining is not the place to start.
Still, if might be worthwhile describing what you are doing, someone here may
be able to think of an algorithm that hasn't occurred to you yet.)

-- chris

 

[Greg Smith]

to my knowledge there is no more efficient method. there is no macro
language for java. now, there is nothing to prevent you from using
ant, or cpp to wrap your java code so that you get a macro language,
but it is non-standard.

 

[Ahmed Moustafa]

This sounds odd. If you assume that the extra overhead of calling a static

method with 4 float arguments and 2 float temps is just a handful of
nanoseconds (I admit I haven't explicitly measured that, but it should be
roughly correct), then you must be calling this function on the order of a
billion times. I'm finding it hard to imagine an application that would need
to do so, but which wouldn't /also/ take so long to run (just creating that
much float data would be slow...) that the additional 3 seconds makes no real
difference. It'd be interesting to know a little more about what you are doing
here.

It's an implementation of Smith-Waterman for biological sequence
alignment, the difference between inlining the comparisons and calling a
method is very noticeable when aligning large sequences (order of 10K).

Not really, not in standard Java. You could always just write a little, highly
specialised, pre-processor in your favourite scripting language. If you don't
want to do that, then I think you are stuck with the decision whether those
three seconds are more important than the clarity of your code.

IMHO, the clarity of the code worths paying these 3 seconds.

You may find, if you're not using it already, that the extra optimisations
invoked by running the JVM with the -server flag (assuming you're using a Sun
JVM) will get you your 3 seconds back, or -- if you're lucky -- even more).

Of course, I will try that.

 

[Ahmed Moustafa]

Is there something like C's macros to keep the code clean but to save

Er, use *inline* ?

That's how it was originally written, but changed to a method for the
sake of readability.

 

[Thomas G. Marshall]

Boudewijn Dijkstra coughed up:

That method always runs in the same amount of VM ticks. It takes:
- 3 comparisons;
- 3 copies; and
- 3 jumps.

How about:

private static float maximum(float a, float b, float c, float d)
{
float max = a;
if (b > max) max = b;
if (c > max) max = c;
if (d > max) max = d;
return max;
}

which takes:
- 1..4 copies;
- 3 comparisons; and
- 3 jumps.

The average number of copies is calculated as follows:
if a is maximum: 1 copy
if b is maximum: 2 copies
if c is maximum: 3 copies
if d is maximum: 4 copies
average copies = (1 + 2 + 3 + 4) / 4 = 10 / 4 = 2.5

Note that 2.5 < 3

You can even theoretically reduce that 2.5 to 1.5 by removing the
first line and replacing 'max' by 'a', but that should probably be up
to the optimizer.

Interesting!

What about this I wonder:

private static float maximum(float a, float b, float c, float d)
{
if ((a >= b) && (a >=c) && (a >= d)) return a;
if ((b >= a) && (b >=c) && (b >= d)) return b;
if ((c >= a) && (c >=b) && (c >= d)) return c;
if ((d >= a) && (d >=b) && (d >= c)) return d;
assert(false); // clinical paranoia.
}

Note that >= is required and not >, because of the possibility of one or
more of them being equal.

--
Iamamanofconstantsorrow,I'veseentroubleallmydays.Ibidfarewelltoold
Kentucky,TheplacewhereIwasbornandraised.ForsixlongyearsI'vebeenin
trouble,NopleasureshereonearthIfound.ForinthisworldI'mboundtoramble,
Ihavenofriendstohelpmenow....MaybeyourfriendsthinkI'mjustastrangerMyface,
you'llneverseenomore.ButthereisonepromisethatisgivenI'llmeetyouonGod's
goldenshore.

 

[Boudewijn Dijkstra]

Boudewijn Dijkstra coughed up:


Interesting!

What about this I wonder:

private static float maximum(float a, float b, float c, float d)
{
if ((a >= b) && (a >=c) && (a >= d)) return a;
if ((b >= a) && (b >=c) && (b >= d)) return b;
if ((c >= a) && (c >=b) && (c >= d)) return c;
if ((d >= a) && (d >=b) && (d >= c)) return d;
assert(false); // clinical paranoia.
}

Note that >= is required and not >, because of the possibility of one
or more of them being equal.

Interesting. This gives:
- 3..12 comparisons
- 12 jumps
- 1 copy

But it contains a lot of redundant code. E.g. the last if could be skipped
completely, because it can proven to be always true.

private static float maximum(float a, float b, float c, float d)
{
if ((a >= b) && (a >= c) && (a >= d)) return a;
if ((b >= c) && (b >= d)) return b;
if (c >= d) return c;
return d;
}

This gives:
- 3..6 comparisons
- 3..6 jumps
- 1 copy

But it still contains redundant comparisons.

private static float maximum(float a, float b, float c, float d)
{
if (a >= b) {
if (a >= c) {
if (a >= d)
return a;
return d;
}
if (c >= d)
return c;
return d;
}
if (b >= c) {
if (b >= d)
return b;
return d;
}
if (c >= d)
return c;
return d;
}

Notice the regular tree-like structure.
This gives:
- 3 comparisons
- 3 jumps
- 1 copy

The fastest algorithm yet!

 

[Thomas G. Marshall]

Boudewijn Dijkstra coughed up:

"Thomas G. Marshall"


Interesting. This gives:
- 3..12 comparisons
- 12 jumps
- 1 copy

But it contains a lot of redundant code. E.g. the last if could be
skipped completely, because it can proven to be always true.

private static float maximum(float a, float b, float c, float d)
{
if ((a >= b) && (a >= c) && (a >= d)) return a;
if ((b >= c) && (b >= d)) return b;
if (c >= d) return c;
return d;
}

This gives:
- 3..6 comparisons
- 3..6 jumps
- 1 copy

But it still contains redundant comparisons.

private static float maximum(float a, float b, float c, float d)
{
if (a >= b) {
if (a >= c) {
if (a >= d)
return a;
return d;
}
if (c >= d)
return c;
return d;
}
if (b >= c) {
if (b >= d)
return b;
return d;
}
if (c >= d)
return c;
return d;
}

Notice the regular tree-like structure.
This gives:
- 3 comparisons
- 3 jumps
- 1 copy

The fastest algorithm yet!

Not quite. I like your optimization as your first example, but your second
example is essentially the same as the first.

The boolean comparisons in the statement

if (A && B && C) ....

are evaluated left to right and abort immediately when false is found. So
if A==false, B and C never get evaluated. (for &&).

Similar reverse logic for ||.

 

[Boudewijn Dijkstra]

Boudewijn Dijkstra coughed up:

Not quite. I like your optimization as your first example, but your second
example is essentially the same as the first.

The boolean comparisons in the statement

if (A && B && C) ....

are evaluated left to right and abort immediately when false is
found. So if A==false, B and C never get evaluated. (for &&).

Similar reverse logic for ||.

If d is the maximum, the first optimization performs 6 comparisons & jumps,
but the second one takes only 3 of those.

 

[bugbear]

You're both well on the way to discovering
some comp-sci:

http://www.cs.brandeis.edu/~hugues/sorting_networks.html

(BTW, this also counts as a reply to the guy
who asked about using comp-sci stuff
for real life tasks)

BugBear

 

[Dave Neary]

Hi,

What would be the most efficient to write a maximum function in Java?

That depends on the data set. You can get the maximum in O(1) on
ordered data

Otherwise, maximum requires you too look at all data elements, so
O(n) is the best you can do.

Initially, I had the comparisons that looked for the maximum inside the
main method and then moved it inside its own method (code is below) to
be called from within the main method (to make the code look prettier),
but that cost me almost 3 additional seconds processing time:

How big is the data set?

<code>
private static float maximum (float a, float b, float c, float d) {
float t1 = a > b ? a : b;
float t2 = c > d ? c : d;
return t1 > t2 ? t1 : t2;
}
</code>

private static float maximum (float a, float b, float c, float d)
{
return (a > b
? (a > c
? (a > d
? a
: d
)
: (c > d
? c
: d
)
)
: (b > c
? (b > d
? b
: d
)
: (c > d
? c
: d
)
)
);
}

should gain you a few clock cycles by always doing the same 3
comparisons, but without the temporary variables. Or maybe it
won't...

Is there something like C's macros to keep the code clean but to save
the processing time for calling the macro?

Java profiles and optimises stuff pretty well when it's inline -
I wouldn't be surprised that you're doing yourself out of time
simply by moving things to a function. But Java doesn't have an
inline function modifier, so...

Cheers,
Dave.

 

[Ahmed Moustafa]

private static float maximum(float a, float b, float c, float d)

{
if (a >= b) {
if (a >= c) {
if (a >= d)
return a;
return d;
}
if (c >= d)
return c;
return d;
}
if (b >= c) {
if (b >= d)
return b;
return d;
}
if (c >= d)
return c;
return d;
}

Notice the regular tree-like structure.
This gives:
- 3 comparisons
- 3 jumps
- 1 copy

The fastest algorithm yet!

And experimentally, that has been found true. But it looks like the
overhead of calling the method is very noticeable and dominating when
it's being called so many times.

 

[Thomas G. Marshall]

Ahmed Moustafa coughed up:

And experimentally, that has been found true. But it looks like the
overhead of calling the method is very noticeable and dominating when
it's being called so many times.

.....which is only more noticeable since the innards of the method are so
much faster.

A good compiler should really optimize the bejeezers outta the method
calling overhead if not remove it outright, at least in the much hyped
theory.

 

[Thomas G. Marshall]

Boudewijn Dijkstra coughed up:

"Thomas G. Marshall"


If d is the maximum, the first optimization performs 6 comparisons &
jumps, but the second one takes only 3 of those.

You're right! my apologies. I wasn't following down the tree properly.



--
Iamamanofconstantsorrow,I'veseentroubleallmydays.Ibidfarewelltoold
Kentucky,TheplacewhereIwasbornandraised.ForsixlongyearsI'vebeenin
trouble,NopleasureshereonearthIfound.ForinthisworldI'mboundtoramble,
Ihavenofriendstohelpmenow....MaybeyourfriendsthinkI'mjustastrangerMyface,
you'llneverseenomore.ButthereisonepromisethatisgivenI'llmeetyouonGod's
goldenshore.

 

[Chris Uppal]

It's an implementation of Smith-Waterman for biological sequence
alignment, the difference between inlining the comparisons and calling a
method is very noticeable when aligning large sequences (order of 10K).

Right; "jaligner", I presume. So it's O(M*N) in sequence length... Makes
sense
now, thanks.

-- chris

 

[Ahmed Moustafa]

It's an implementation of Smith-Waterman for biological sequence

Right; "jaligner", I presume. So it's O(M*N) in sequence length... Makes
sense
now, thanks.

Yes, that's right

 

[Jesper Nordenberg]

Hello,

What would be the most efficient to write a maximum function in Java?

I've only found one that is optimal for integers:

private static int maximum(int a, int b, int c, int d) {
for (int i=Integer.MIN_VALUE; i<=Integer.MAX_VALUE; i++) {
if (i > a && i > b && i > c && i > d)
return i - 1;
}

throw new RuntimeException("Something is wrong with your integers!");
}


Sorry, bad joke ;-)

/Jesper Nordenberg