1

This is one of those tiny optimization questions that doesn't matter, but is fun to think about anyway.

I've got two different lines of Java code I could use:

  1. coord < 0 ? (coord % max + max) % max : coord % max or
  2. (coord % max + max) % max

I assume max is always a positive int and coord could be any valid int. I believe these two lines should always yield the same result, which is to wrap a coordinate that's gone off the edge of my map where there be monsters.

2 is clearly faster in the case that coord is negative. But if coord is positive, I'm not sure which would tend to be faster. The point of 1 would be to do less math operations in the case that coord is positive but I'm not sure if that's actually faster or not. The compiler might even optimize 1 away into being 2. Does anyone know?

By the way, I've seen people online post functions for wrapping coordinates which just add max in the case that coord is negative, and that breaks in the case that coord > max*-1. I want mine to deal with that case.

(later edit) The context is up on Github for anyone who would like to see it. And yes, I know this doesn't actually matter to the performance of my program, but I just thought it was an interesting question.

sepp2k
  • 363,768
  • 54
  • 674
  • 675
Ben McLean
  • 59
  • 4
  • Nobody knows for sure without seeing the context, and most people don't care one way or the other. The only way to find out for sure is to profile the tight loop which includes this code. Of course, if there is no tight loop around this code, I don't see why one would bother with this problem in the first place. – Sergey Kalinichenko Dec 06 '16 at 16:47
  • Like I said, it's just curiosity. The real question is: "Which is faster, several arithmetic ops or one conditional?" – Ben McLean Dec 06 '16 at 16:49
  • 3
    It depends. The cost of a branch is not fixed, and neither is the cost of a remainder. – harold Dec 06 '16 at 16:49
  • 1
    From [ask]: "If your question generally covers... a **practical**, answerable problem that is unique to software development... then you're in the right place". (My emphasis). – RealSkeptic Dec 06 '16 at 16:51
  • 2
    I would argue that this is practical. From the definition of practical: "of or concerned with the __actual doing or use of something__ rather than with theory and ideas." He is actually using this code for a specific purpose and while the optimization may not be terribly important, it is certainly practical. – Taelsin Dec 06 '16 at 16:55
  • @Taelsin the code may be practical, but the problem isn't. At least not as described. – RealSkeptic Dec 06 '16 at 16:56
  • 1
    Looks practical enough to me, it's just that it's asking for a general answer to a question that is highly context sensitive. – harold Dec 06 '16 at 16:56
  • What exactly would be the factors from the context which would make the difference? :) – Ben McLean Dec 06 '16 at 17:09
  • @BenMcLean predictability of the branch, fraction of times it can take the fast path, distribution of values appearing as as LHS of the remainder operation, whether `max` is statically known to be a power of two, maybe some stuff I've missed.. – harold Dec 06 '16 at 17:13

2 Answers2

1

You're using a too complicated expression for the negative case:

coord < 0 ? (coord % max + max) % max : coord % max

is the same as

coord < 0 ? coord % max + max : coord % max

A mispredicted branch can be costly, however on modern i86/amd64, branching can be eliminated using a conditional move. So the condition is most probably faster.

Note that guava uses it, too.

maaartinus
  • 44,714
  • 32
  • 161
  • 320
0

I guess the answer is branch prediction.

If you use branches (if-else) the code that is executed depends on the input data. So depending on the input data branch prediction might not work, because it might be unpredictable which branch will be executed.

Community
  • 1
  • 1
René Link
  • 48,224
  • 13
  • 108
  • 140