How to write an efficient maximum function?

Discussion in 'Java' started by Ahmed Moustafa, Nov 16, 2004.

  1. 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
    Ahmed Moustafa, Nov 16, 2004
    #1
    1. Advertising

  2. On Tue, 16 Nov 2004 02:00:51 GMT, Ahmed Moustafa wrote:

    > 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>

    --
    Andrew Thompson
    http://www.PhySci.org/codes/ Web & IT Help
    http://www.PhySci.org/ Open-source software suite
    http://www.1point1C.org/ Science & Technology
    http://www.LensEscapes.com/ Images that escape the mundane
    Andrew Thompson, Nov 16, 2004
    #2
    1. Advertising

  3. Ahmed Moustafa

    thirdrock Guest

    Ahmed Moustafa wrote:

    >
    > 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* ?
    thirdrock, Nov 16, 2004
    #3
  4. "Ahmed Moustafa" <> schreef in bericht
    news:nbdmd.225$...
    > 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.
    Boudewijn Dijkstra, Nov 16, 2004
    #4
  5. Ahmed Moustafa

    Chris Uppal Guest

    Ahmed Moustafa wrote:

    > 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
    Chris Uppal, Nov 16, 2004
    #5
  6. Ahmed Moustafa

    Greg Smith Guest

    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 <> wrote in message news:<nbdmd.225$>...
    > 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
    Greg Smith, Nov 16, 2004
    #6
  7. > 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).

    >>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.


    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.

    > (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
    Ahmed Moustafa, Nov 16, 2004
    #7
  8. >> 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* ?


    That's how it was originally written, but changed to a method for the
    sake of readability.
    Ahmed Moustafa, Nov 16, 2004
    #8
  9. Boudewijn Dijkstra coughed up:
    > "Ahmed Moustafa" <> schreef in bericht
    > news:nbdmd.225$...
    >> 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.



    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.
    Thomas G. Marshall, Nov 16, 2004
    #9
  10. "Thomas G. Marshall" <>
    schreef in bericht news:CMqmd.11506$tI3.6360@trndny01...
    > Boudewijn Dijkstra coughed up:
    >> "Ahmed Moustafa" <> schreef in bericht
    >> news:nbdmd.225$...
    >>> 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.

    >
    >
    > 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!
    Boudewijn Dijkstra, Nov 16, 2004
    #10
  11. Boudewijn Dijkstra coughed up:
    > "Thomas G. Marshall"
    > <> schreef in
    > bericht news:CMqmd.11506$tI3.6360@trndny01...
    >> Boudewijn Dijkstra coughed up:
    >>> "Ahmed Moustafa" <> schreef in bericht
    >>> news:nbdmd.225$...
    >>>> 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.

    >>
    >>
    >> 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!


    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 ||.



    --
    http://www.allexperts.com is a nifty way to get an answer to just about
    /anything/.
    Thomas G. Marshall, Nov 16, 2004
    #11
  12. "Thomas G. Marshall" <>
    schreef in bericht news:O6tmd.12021$2V4.4422@trndny06...
    > Boudewijn Dijkstra coughed up:
    >> "Thomas G. Marshall"
    >> <> schreef in
    >> bericht news:CMqmd.11506$tI3.6360@trndny01...
    >>> Boudewijn Dijkstra coughed up:
    >>>> "Ahmed Moustafa" <> schreef in bericht
    >>>> news:nbdmd.225$...
    >>>>> 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.
    >>>
    >>>
    >>> 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!

    >
    > 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.
    Boudewijn Dijkstra, Nov 16, 2004
    #12
  13. Ahmed Moustafa

    bugbear Guest

    bugbear, Nov 17, 2004
    #13
  14. Ahmed Moustafa

    Dave Neary Guest

    Hi,

    On Tue, 16 Nov 2004 02:00:51 GMT, Ahmed Moustafa said:
    > 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.

    --
    David Neary,
    E-Mail: bolsh at gimp dot org
    Work e-mail: d dot neary at phenix dot fr
    CV: http://dneary.free.fr/CV/
    Dave Neary, Nov 17, 2004
    #14
  15. > 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.
    Ahmed Moustafa, Nov 18, 2004
    #15
  16. Ahmed Moustafa coughed up:
    >> 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.


    .....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.

    --
    "It's easier to be terrified by an enemy you admire."
    -Thufir Hawat, Mentat and Master of Assassins to House Atreides
    Thomas G. Marshall, Nov 18, 2004
    #16
  17. Boudewijn Dijkstra coughed up:
    > "Thomas G. Marshall"
    > <> schreef in
    > bericht news:O6tmd.12021$2V4.4422@trndny06...
    >> Boudewijn Dijkstra coughed up:
    >>> "Thomas G. Marshall"
    >>> <> schreef in
    >>> bericht news:CMqmd.11506$tI3.6360@trndny01...
    >>>> Boudewijn Dijkstra coughed up:
    >>>>> "Ahmed Moustafa" <> schreef in bericht
    >>>>> news:nbdmd.225$...
    >>>>>> 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.
    >>>>
    >>>>
    >>>> 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!

    >>
    >> 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.



    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.
    Thomas G. Marshall, Nov 20, 2004
    #17
  18. Ahmed Moustafa

    Chris Uppal Guest

    Ahmed Moustafa wrote:

    > 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
    Chris Uppal, Nov 20, 2004
    #18
  19. >>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.


    Yes, that's right :)
    Ahmed Moustafa, Nov 20, 2004
    #19
  20. Ahmed Moustafa <> wrote in message news:<nbdmd.225$>...
    > 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
    Jesper Nordenberg, Nov 22, 2004
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    8
    Views:
    488
  2. Replies:
    10
    Views:
    502
  3. kr
    Replies:
    18
    Views:
    1,234
    Malcolm McLean
    Oct 1, 2007
  4. phanhuyich
    Replies:
    4
    Views:
    258
  5. Tim Chase
    Replies:
    0
    Views:
    86
    Tim Chase
    Dec 16, 2013
Loading...

Share This Page