Which is faster?

Discussion in 'Java' started by bobpreston@gmail.com, Oct 6, 2006.

  1. Guest

    Assuming I have the following:

    byte[] bytes = new byte[100];
    int pos = 0;


    which is faster:

    pos++;
    pos %= bytes.length;

    or:

    pos = ++pos % bytes.length;


    Thanks in advance,

    Bob
     
    , Oct 6, 2006
    #1
    1. Advertising

  2. wrote on 06.10.2006 18:35:
    > Assuming I have the following:
    >
    > byte[] bytes = new byte[100];
    > int pos = 0;
    >
    >
    > which is faster:
    >
    > pos++;
    > pos %= bytes.length;
    >
    > or:
    >
    > pos = ++pos % bytes.length;


    Who cares?
     
    Thomas Kellerer, Oct 6, 2006
    #2
    1. Advertising

  3. Guest

    Thanks Thomas :) How's HSQLDB?

    Thomas Kellerer wrote:
    > wrote on 06.10.2006 18:35:
    > > Assuming I have the following:
    > >
    > > byte[] bytes = new byte[100];
    > > int pos = 0;
    > >
    > >
    > > which is faster:
    > >
    > > pos++;
    > > pos %= bytes.length;
    > >
    > > or:
    > >
    > > pos = ++pos % bytes.length;

    >
    > Who cares?
     
    , Oct 6, 2006
    #3
  4. Thomas Weidenfeller, Oct 6, 2006
    #4
  5. Guest

    I don't believe measuring it on one platform is sufficient, since my
    program is deployed on many platforms. The code is in a method at the
    high end of the execution chain, which I would like to optimize as much
    as possible. If it truly doesn't matter, then I'll go with the more
    maintainable solution (since its a 1 liner):

    pos = ++pos % bytes.length;

    Bob


    Thomas Weidenfeller wrote:
    > wrote:
    > > Assuming I have the following:
    > >
    > > byte[] bytes = new byte[100];
    > > int pos = 0;
    > >
    > >
    > > which is faster:

    >
    > It does not matter. And if it would be really an important issue for
    > you, you would measure it.
    >
    > /Thomas
    > --
    > The comp.lang.java.gui FAQ:
    > http://gd.tuwien.ac.at/faqs/faqs-hierarchy/comp/comp.lang.java.gui/
    > ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
     
    , Oct 6, 2006
    #5
  6. Oliver Wong Guest

    [post re-ordered]

    <> wrote in message
    news:...
    > Thomas Weidenfeller wrote:
    >> wrote:
    >> > Assuming I have the following:
    >> >
    >> > byte[] bytes = new byte[100];
    >> > int pos = 0;
    >> >
    >> >
    >> > which is faster:

    >>
    >> It does not matter. And if it would be really an important issue for
    >> you, you would measure it.
    >>

    >
    >I don't believe measuring it on one platform is sufficient, since my
    > program is deployed on many platforms.


    So measure it on enough platforms for it to be sufficient?

    > The code is in a method at the
    > high end of the execution chain, which I would like to optimize as much
    > as possible. If it truly doesn't matter, then I'll go with the more
    > maintainable solution (since its a 1 liner):
    >
    > pos = ++pos % bytes.length;


    FWIW, I think this is less maintainable, as it is an expression which
    assigns to the same variable twice, which many programmers find confusing.

    - Oliver
     
    Oliver Wong, Oct 6, 2006
    #6
  7. Oliver Wong <> wrote:

    > > pos = ++pos % bytes.length;


    > FWIW, I think this is less maintainable, as it is an expression which
    > assigns to the same variable twice, which many programmers find confusing.


    Not to mention that programmers, such as myself, with a C or C++
    background are likely to berate such code's author for invoking
    dreaded Undefined Behavior before realizing that Java at least
    improved the situation by guaranteeing the behavior of that code.

    As a contradictory data point, however, it seems that IntelliJ will
    not generate an inspection warning on that code; I was sure it would
    have complained about the stylistic dubiousness of it, but apparently
    not.

    --
    C. Benson Manica | I *should* know what I'm talking about - if I
    cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
     
    Christopher Benson-Manica, Oct 6, 2006
    #7
  8. wrote:
    > I don't believe measuring it on one platform is sufficient, since my
    > program is deployed on many platforms. The code is in a method at the
    > high end of the execution chain, which I would like to optimize as much
    > as possible. If it truly doesn't matter, then I'll go with the more
    > maintainable solution (since its a 1 liner):
    >
    > pos = ++pos % bytes.length;


    "Code is usually clearer when each expression contains at most one side
    effect, as its outermost operation..."
    http://java.sun.com/docs/books/jls/second_edition/html/expressions.doc.html#4779

    This line is particularly bad, because both side effects modify pos, and
    the one done by ++pos is dead - only the value of the expression is ever
    used.

    What is wrong with this?

    pos = (pos + 1) % bytes.length;


    As far as performance is concerned, I would examine the method in terms
    of two key issues:

    1. Cache hit vs. cache miss.

    2. Conditional branches, and especially conditional branch predictability.

    A single cache miss, or a mispredicted branch, will cost far, far more
    than changes in exactly how you do a little arithmetic, using the same data.

    Patricia
     
    Patricia Shanahan, Oct 6, 2006
    #8
  9. Chris Uppal Guest

    wrote:

    > I don't believe measuring it on one platform is sufficient, since my
    > program is deployed on many platforms.


    Which is sensible, but if you can't measure it on all your target platforms,
    then how do you expect us to know which is faster without even knowing what
    those platforms are, or which are most important to you ?


    > The code is in a method at the
    > high end of the execution chain, which I would like to optimize as much
    > as possible. If it truly doesn't matter, then I'll go with the more
    > maintainable solution (since its a 1 liner):


    It is perfectly possible (though, I'd guess, not too likely) that if this code
    is in the inner loop of your application then its speed is critical for the
    overall app. If you suspect that might be the case then /measure/ it.

    BTW, when you do measure (if you bother), don't forget to test a version
    without the modulus operator:

    if (++pos >= bytes.length)
    pos = 0;

    It involves a branch (but one which, I imagine, would normally be correctly
    predicted by the CPU -- if you are running on a machine with instruction
    pipelining and branch prediction), but saves a mod operation. You (unless you
    know a lot more about your target architectures than you have said) can't guess
    which is quicker, so -- again -- you have to measure it. I might be worth
    putting bytes.length into a local variable too, OTOH that might be a waste of
    time -- it depends on whether the optimiser in the JIT (if any, on your target
    platforms) spots the repeated use of bytes.length by itself.


    But, whatever you do, DON'T use:

    > I'll go with the more
    > maintainable solution (since its a 1 liner):
    >
    > pos = ++pos % bytes.length;


    It pre-increments pos and assigns to it -- which is just daft.

    -- chris
     
    Chris Uppal, Oct 7, 2006
    #9
  10. Lew Guest

    >>> pos = ++pos % bytes.length;

    > Oliver Wong <> wrote:
    >> FWIW, I think this is less maintainable, as it is an expression which
    >> assigns to the same variable twice, which many programmers find confusing.


    Then they aren't very good programmers. In fact, I recommend that one use
    this type of example as an interview question to avoid hiring those who find
    it confusing.

    Christopher Benson-Manica wrote:
    > Not to mention that programmers, such as myself, with a C or C++
    > background are likely to berate such code's author for invoking
    > dreaded Undefined Behavior


    Slightly O-T, but doesn't C[++] guarantee behavior across the assignment,
    i.e., that the right side is fully evaluated before storing to the left?

    As you point out, Java does make this guarantee.

    Just to complicate matters, there's another idiom that replaces the overhead
    of the mod operator and second assignment with the overhead of a test-and-branch:

    if ( ++pos == bytes.length )
    {
    pos = 0;
    }

    - Lew
     
    Lew, Oct 7, 2006
    #10
  11. Lew Guest

    Lew wrote:
    > if ( ++pos == bytes.length )
    > {
    > pos = 0;
    > }


    I should've read Chris Uppal's post before sending mine.

    > BTW, when you do measure (if you bother), don't forget to test a version
    > without the modulus operator:
    >
    > if (++pos >= bytes.length)
    > pos = 0;
    >
    > It involves a branch (but one which, I imagine, would normally be correctly
    > predicted by the CPU -- if you are running on a machine with instruction
    > pipelining and branch prediction), but saves a mod operation. You (unless you
    > know a lot more about your target architectures than you have said) can't guess
    > which is quicker, so -- again -- you have to measure it. I might be worth
    > putting bytes.length into a local variable too, OTOH that might be a waste of
    > time -- it depends on whether the optimiser in the JIT (if any, on your target
    > platforms) spots the repeated use of bytes.length by itself.


    I agree with his use of testing for >= rather than ==.

    - Lew
     
    Lew, Oct 7, 2006
    #11
  12. Eric Sosman Guest

    Lew wrote:
    > Lew wrote:
    >
    >> if ( ++pos == bytes.length )
    >> {
    >> pos = 0;
    >> }

    >
    >
    > I should've read Chris Uppal's post before sending mine.
    >
    >> BTW, when you do measure (if you bother), don't forget to test a version
    >> without the modulus operator:
    >>
    >> if (++pos >= bytes.length)
    >> pos = 0;
    >>
    >> It involves a branch (but one which, I imagine, would normally be
    >> correctly
    >> predicted by the CPU -- if you are running on a machine with instruction
    >> pipelining and branch prediction), but saves a mod operation. You
    >> (unless you
    >> know a lot more about your target architectures than you have said)
    >> can't guess
    >> which is quicker, so -- again -- you have to measure it. I might be
    >> worth
    >> putting bytes.length into a local variable too, OTOH that might be a
    >> waste of
    >> time -- it depends on whether the optimiser in the JIT (if any, on
    >> your target
    >> platforms) spots the repeated use of bytes.length by itself.

    >
    >
    > I agree with his use of testing for >= rather than ==.


    It makes me wonder, queasily, whether the next line ought
    to read `pos -= bytes.length' or even `pos %= bytes.length'.
    Context is king ...

    --
    Eric Sosman
    lid
     
    Eric Sosman, Oct 7, 2006
    #12
  13. Lew wrote:
    >>>> pos = ++pos % bytes.length;


    > Slightly O-T, but doesn't C[++] guarantee behavior across the
    > assignment, i.e., that the right side is fully evaluated before storing
    > to the left?


    No.

    The C++ standard say that you can only modify a variable
    once between sequence points (in this case the entire
    line).

    If one do it anyway, then it is "undefined behaviour".

    Arne
     
    =?ISO-8859-1?Q?Arne_Vajh=F8j?=, Oct 8, 2006
    #13
  14. Lew <> wrote:

    > Slightly O-T, but doesn't C[++] guarantee behavior across the assignment,
    > i.e., that the right side is fully evaluated before storing to the left?


    No. If you're so inclined, you might find the C faqs on this topic to
    be of interest, starting with http://c-faq.com/expr/ieqiplusplus.html.
    As another poster mentioned, the C++ standard makes similar (non)
    guarantees.

    --
    C. Benson Manica | I *should* know what I'm talking about - if I
    cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
     
    Christopher Benson-Manica, Oct 8, 2006
    #14
  15. Chris Uppal Guest

    Eric Sosman wrote:

    > > I agree with his use of testing for >= rather than ==.

    >
    > It makes me wonder, queasily, whether the next line ought
    > to read `pos -= bytes.length' or even `pos %= bytes.length'.


    ??

    I know my code is not always to everybody's taste, but it has been quite a
    while since someone last complained that it caused feelings of incipient
    nausea...

    -- chris

    P.S. In case it isn't obvious: I'm not offended, just curious.
     
    Chris Uppal, Oct 8, 2006
    #15
  16. Daniel Thoma Guest

    > which is faster:
    Both versions are exactly equally fast, since the produced bytecode is
    the same:

    0: bipush 100
    2: newarray byte
    4: astore_1
    5: iconst_0
    6: istore_2
    7: iinc 2, 1
    10: iload_2
    11: aload_1
    12: arraylength
    13: irem
    14: istore_2

    Do you really have a good reason for worrying about such details? I ask
    because there aren't many good reasons out there...

    Daniel
     
    Daniel Thoma, Oct 8, 2006
    #16
  17. Eric Sosman Guest

    Chris Uppal wrote:
    > Eric Sosman wrote:
    >
    >
    >>>I agree with his use of testing for >= rather than ==.

    >>
    >> It makes me wonder, queasily, whether the next line ought
    >>to read `pos -= bytes.length' or even `pos %= bytes.length'.

    >
    >
    > ??
    >
    > I know my code is not always to everybody's taste, but it has been quite a
    > while since someone last complained that it caused feelings of incipient
    > nausea...
    >
    > -- chris
    >
    > P.S. In case it isn't obvious: I'm not offended, just curious.


    We're considering two alternative code snippets:

    Alternative EQ:
    if (++pos == bytes.length)
    pos = 0;

    Alternative GE:
    if (++pos >= bytes.length)
    pos = 0;

    Neither can be deemed "correct" or "incorrect" in isolation, of
    course: it is necessary to look at the rest of the code to see
    how `pos' is computed and used. Nonetheless, the form of EQ
    strongly suggests its purpose: the index `pos' is cycling through
    the positions of the array `bytes'. In the rest of the code it
    would be startling to find `pos' declared as a `float', or set
    to Integer.MAX_VALUE, or set to a negative value (other than,
    possibly, -1 at the very beginning), or advanced more than once
    per iteration of the loop that almost certainly encloses the code.
    We've seen things like EQ before, and we know how the form is used.

    Alternative GE causes me to wonder whether there's a legitimate
    way for `pos' to become large, how large it might become, and what
    the significance of a large value might be. I wonder whether the
    programmer who wrote GE instead of EQ might be guarding against
    some devious pathway that could change `pos' before arriving at
    this piece of code, and I start looking for that pathway. I also
    find myself thinking that if `pos==bytes.length' cycles back to
    zero, perhaps `pos==bytes.length+1' should cycle back to 1 instead
    of zero, or `pos==bytes.length+n' should cycle back to n -- after
    all, this is a form I've seen before, too, in situations like
    searching through open-addressed hash tables.

    So when I see alternative GE instead of EQ I start asking "Why?"
    and this disrupts my reading of the code. Only a very little bit,
    to be sure, since I've had many years' practice at reading code and
    a tiny trivial matter like this one won't bother me very long.

    One tiny final point: Java, unlike many languages I've used,
    checks array indices for validity. Because of this, there might be
    a very small advantage to using alternative EQ instead of GE, the
    idea being that if there is in fact a bug somewhere that makes `pos'
    large before arriving at the code snippet, GE will "throw a blanket"
    over the bug if it executes before the bad `pos' value actually gets
    used. EQ, on the other hand, will let the bad value survive to be
    exposed by an ArrayIndexOutOfBoundsException, possibly leading to
    earlier detection and repair of the programming error. Maybe.

    Tempest in a teapot, really.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Oct 8, 2006
    #17
  18. Stefan Ram Guest

    Eric Sosman <> writes:
    >if (++pos == bytes.length)
    >if (++pos >= bytes.length)
    >the significance of a large value might be. I wonder whether the
    >programmer who wrote GE instead of EQ might be guarding against
    >some devious pathway that could change `pos' before arriving at
    >this piece of code, and I start looking for that pathway. I also


    The ">=" is more defensive, but some avoid it for exactly this
    reason: They /want/ their code to fail when pos>bytes.length
    in order to detect such an illegal state as early as possible.

    >large before arriving at the code snippet, GE will "throw a blanket"
    >over the bug if it executes before the bad `pos' value actually gets


    Yes, this is what I just meant to say.

    Another reason to prefer one of the two are formal program
    proofs: If the postcondition "pos == bytes.length" is needed
    for the proof, then it is helpful to use "if( pos ==
    bytes.length )", because then the postcondition is obviously
    fulfilled.
     
    Stefan Ram, Oct 8, 2006
    #18
  19. Karl Uppiano Guest

    "Daniel Thoma" <> wrote in message
    news:egaup5$3il$...
    >> which is faster:

    > Both versions are exactly equally fast, since the produced bytecode is
    > the same:
    >
    > 0: bipush 100
    > 2: newarray byte
    > 4: astore_1
    > 5: iconst_0
    > 6: istore_2
    > 7: iinc 2, 1
    > 10: iload_2
    > 11: aload_1
    > 12: arraylength
    > 13: irem
    > 14: istore_2
    >
    > Do you really have a good reason for worrying about such details? I ask
    > because there aren't many good reasons out there...
    >
    > Daniel


    Ha! I suspected as much - the bytecodes are the same! Obsessing over the
    fine points at the language level is almost always a waste of time. You may
    have to re-tune your code every time you change compilers, change runtimes,
    or change platforms. Spend that time coming up with a better overall design.
     
    Karl Uppiano, Oct 8, 2006
    #19
  20. Chris Uppal Guest

    Eric Sosman wrote:

    > So when I see alternative GE instead of EQ I start asking "Why?"
    > and this disrupts my reading of the code. Only a very little bit,
    > to be sure, since I've had many years' practice at reading code and
    > a tiny trivial matter like this one won't bother me very long.


    Thanks for the explanation.

    FWIW, I don't agree (although it's an interesting issue in a small way) -- I
    would find an == test distracting, 'cos I'd have to check the rest of the code
    to ensure that pos couldn't be incremented off the end...

    I suppose it's a question of whether you prefer the weakest possible condition
    (within reason) for taking the true branch, or the weakest possible condition
    for taking the false branch.

    -- chris
     
    Chris Uppal, Oct 9, 2006
    #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. Weng Tianxiang
    Replies:
    12
    Views:
    1,636
  2. Andreas Klemt
    Replies:
    1
    Views:
    452
    Steve C. Orr, MCSD
    Jul 23, 2003
  3. S. Justin Gengo
    Replies:
    2
    Views:
    364
    S. Justin Gengo
    Aug 20, 2003
  4. Bob
    Replies:
    1
    Views:
    2,697
  5. luca

    which one is faster?

    luca, Mar 7, 2004, in forum: Java
    Replies:
    1
    Views:
    326
    William Brogden
    Mar 8, 2004
Loading...

Share This Page