0

I wonder which operation works faster:

int c = version1.compareTo(version2);

This one

if (c == 1)

or this

if (c > 0)

Does sign comparasion use just a one bit check and equality comparasion use substraction, or it is not true? For certainty, let's say we work on x86.

P.S. Not an optimization issue, just wondering how it works.

Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
AdamSkywalker
  • 11,408
  • 3
  • 38
  • 76
  • 1
    All those operations are O(1), pronounced Big-O of 1. Meaning, it doesn't really matter if one executes 3 lines of code, or one executes 2 lines of code, performance will be based on CPU more than anything else – Dan Ciborowski - MSFT Jun 13 '15 at 14:50
  • @DanCiborowski-MSFT I don't think it's right to talk about the Big-O here, as the execution of an operation may depend on number of memory accesses, cache hits/misses and many other things that influence perfomance while still speaking about a single instruction. – user35443 Jun 13 '15 at 14:58
  • @DanCiborowski-MSFT Influence of this kind may not be even O(1) (e. g. stall when waiting for a cache load). – user35443 Jun 13 '15 at 15:00
  • 2
    @DanCiborowski-MSFT O(1) is an abstract notion, too high level for this question. The only reason for which we consider all "basic" operations as O(1) is to not complicate complexity analysis any further, hoping that these differences even out over the number of executions. For instance, `x + y` and `x / y` might be O(1) for you, but the latter is definitely heavier for a CPU. – Stefano Sanfilippo Jun 13 '15 at 15:07
  • This is why I put it as a comment and not an answer. Focus on the second part of the comment, about CPU is MOST important about the performance difference between these operations. – Dan Ciborowski - MSFT Jun 15 '15 at 11:11

2 Answers2

2

"How it works" really depends on the platform (e.g. the hardware instruction set), the version of Java that you are using, and the context (e.g. what happens before and after in the program.)

For what it is worth, there is a java command-line option that will dump out the JIT compiled native code for a particular method:

However, you should be aware that the two tests are not equivalent. Specifically, a Comparable<T>.compareTo(T) method is not guaranteed to return -1, 0 or +1. The spec says that it can return any integer. Hence testing for c == 1 may not work ... depending on how compareTo is implemented.

Community
  • 1
  • 1
Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • nice catch about compareTo(), but it was just an example, processor instructions are the main objective – AdamSkywalker Jun 13 '15 at 14:48
  • 1
    @AdamSkywalker - I've added a link so that you can satisfy your curiosity about the native code ... without asking other people. – Stephen C Jun 13 '15 at 14:56
2

Assuming those operations are JITted into x86 opcodes without any optimization, there is no difference. A possible x86 pseudo-assembly snippet for the two cases could be: 

cmp i, 1
je destination

and:

cmp i, 0
jg destination

The cmp operation performs a subtraction between the two operands (register i and immediate 0), discards the result and sets some flags: positive, negative, overflow etc.

These flags are then used to trigger a conditional jump (i.e. jump if condition), in one case if the two operands are equal, in the second case if the first is greater than the second.

Again, this without considering any software (JVM-wise) and/or hardware optimization. In fact, x86_64 architectures have a complex pipeline with advanced branch-prediction and out-of-order execution, for which these microbenchmarks are almost meaningless. We are long past counting instructions.

Stefano Sanfilippo
  • 32,265
  • 7
  • 79
  • 80
  • Was looking for this, thanks. Seems that **jg**, **je** and other transition commands are assembly abstraction and they can't be decomposed more. – AdamSkywalker Jun 13 '15 at 14:56
  • @AdamSkywalker what about counting cycles an instruction would, if you want to be exact? :) – user35443 Jun 13 '15 at 15:00
  • @user35443 seems to be the same, found the asnwer here http://stackoverflow.com/questions/12135518/is-faster-than – AdamSkywalker Jun 13 '15 at 15:01
  • @AdamSkywalker they aren't abstractions, but direct commands to the hardware. Those tests are performed by a dedicated hardware unit. You can't go any deeper than that at a software level. – Stefano Sanfilippo Jun 13 '15 at 15:01
  • @StefanoSanfilippo what about electonics and circuit design?) – AdamSkywalker Jun 13 '15 at 15:02
  • @user35443 as I said, the x86 and x86_64 architectures are such that counting instruction cycles is quite meaningless in itself, unfortunately. – Stefano Sanfilippo Jun 13 '15 at 15:03
  • @AdamSkywalker no, they can't, `cmp i, 1` takes an immediate which could need at least one additional cycle to load, while `cmp i, 0` can be optimized into `test i, i` with no immediate at all. – user35443 Jun 13 '15 at 15:03
  • @StefanoSanfilippo sure, just having fun :) – user35443 Jun 13 '15 at 15:04
  • @AdamSkywalker it is certainly possible to build hardware that performs complex and specialized operations as single macro-instructions, e.g. with FPGAs. For instance, video codecs used in DVD players are (or at least, were) implemented in hardware. The development and distribution costs are definitely higher, though. – Stefano Sanfilippo Jun 13 '15 at 15:16
  • Do note that in many cases simply loading the variable into a register will set the condition-code register that reflects the sign bit without any subsequent explicit comparison being necessary. – Alnitak Jun 13 '15 at 15:21