21

When I was reading System.nanoTime() API in Java. I found this line:

one should use t1 - t0 < 0, not t1 < t0, because of the possibility of numerical overflow.

http://docs.oracle.com/javase/7/docs/api/java/lang/System.html#nanoTime()

To compare two nanoTime values

long t0 = System.nanoTime();
...
long t1 = System.nanoTime();

one should use t1 - t0 < 0, not t1 < t0, because of the possibility of numerical overflow.

I want to know why t1 - t0 < 0 is preferable way to prevent overflow.

Because I read from some other thread that A < B is more preferable than A - B < 0.

Java Integer compareTo() - why use comparison vs. subtraction?

These two things make contradiction.

Hakanai
  • 12,010
  • 10
  • 62
  • 132
user2712734
  • 257
  • 1
  • 6

4 Answers4

13

The Nano time is not a 'real' time, it is just a counter that increments starting from some unspecified number when some unspecified event occurs (maybe the computer is booted up).

It will overflow, and become negative at some point. If your t0 is just before it overflows (i.e. very large positive), and your t1 is just after (very large negative number), then t1 < t0 (i.e. your conditions are wrong because t1 happened after t0).....

But, if you say t1 - t0 < 0, well, the magic is that a for the same overflow (undeflow) reasons (very large negative subtract a very large positive will underflow), the result will be the number of nanoseconds that t1 was after t0..... and will be right.

In this case, two wrongs really do make a right!

rolfl
  • 17,539
  • 7
  • 42
  • 76
  • You put `t1 - t0 > 0` but shouldn't it be `t1 - t0` **<** `0`? – Michael Warner Aug 16 '16 at 13:56
  • @MichaelWarner - Hmm.... yes, you are correct..... `t1 - t0 < 0` is the same logic as `t1 < t0` except that `t1 - t0 < 0` does not "suffer" from nanosecond wraparound problems. Editing now. Not sure why I messed that up. – rolfl Aug 16 '16 at 15:26
  • I assume that `Long.compareUnsigned(long, long)` does the same thing, or possibly even handles some edge case better. – Hakanai May 13 '19 at 05:41
  • @Trejkaz not in this context. It does completely different things, and does not return the difference between two longs at all. – rolfl May 13 '19 at 10:35
  • Is there a good example of a case where it differs? The concept is identical - it moves the negative values to sort above the positive values. Actually, the more I read the docs, the more contradictory they read. The docs on the same method say that you should prepare for the initial value to already be negative. If it can already be negative when you start, and can also become negative when it wraps around, then the entire thing is as good as useless, isn't it? – Hakanai May 13 '19 at 23:15
  • The value increments as time passes. If it it's negative now, then the first wrap (through zero) makes it positive. The next wrap (through the maximum positive value) makes it negative. But negative-to-negative only happens after half the period of the counter, in this case 63 bits worth of nanoseconds, which according to the docs (I did not check) is 292 earth years, –  May 14 '19 at 02:46
  • Hmmm, @Trejkaz - it is certain that `t1 - t0` will always give the correct difference between two `nanoTime()` calls (within the bounds of the minimum granularity of the clock, and 292 years...) ... there are no edge cases on that (especially including wrap-around). So, there are no edge cases on `t1 - t0 < 0` (other than the 292 year one). Assuming the edge cases are covered in the `Long.compareUnsigned()` then it is, at least, more readable. – rolfl May 14 '19 at 02:48
  • Apart from the obscure use/abuse of the `compareUnsigned()` to compare 2 signed values, and on further looking, it's clear that you may be correct it also gives the correct result, but, have you looked at the implementation? It's `return compare(x + MIN_VALUE, y + MIN_VALUE); ` ... which means, while I may have been wrong that it's "completely different", it's clear that `t1 - t0 < 0` is superior to multiple function calls and more complicated logic: http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/561c1038f71a/src/share/classes/java/lang/Long.java#l1267 – rolfl May 14 '19 at 02:53
  • I figure that when more complicated logic is present somewhere, it's often there for a reason. Here, though, I can't tell whether it gives the right result in a less confusing way, or whether it just gives the wrong result, because the docs on nanoTime() are so unclear. They probably should have added some examples to the docs so that we could figure out what the intent of the instructions were. – Hakanai May 16 '19 at 04:52
11

t0 - t1 < 0 is better then t0 < t1 when we are sure that real difference of values (before overflow) is not grater than half or size of set that contains all possible values.
For nanoseconds it will be approximately 292 years (nanoseconds are stored in long and half of long size is 2^64/2 = 2^63 nanoseconds ~= 292 years).

So for time samples separated with less then 292 years we should use t0 - t1 < 0 to get correct results.

To better visualize it lets say that cycle contains 8 possible values which are -4, -3, -2, -1 ,0, 1, 2, 3.

So timeline can look like 

real time values:  .., -6, -5, -4, -3, -2, -1,  0,  1,  2,  3,  4,  5,  6,  7, ..
overflowed values: ..,  2,  3, -4, -3, -2, -1,  0,  1,  2,  3, -4, -3, -2, -1, ..

Lets take a look how t0 - t1 < 0 and t0 < t1 will behave for values where difference will be and wont be greater than 4 (half of cycle size, and -4 is minimal value which means it can be minimal result for calculating delta). Notice that only t0 - t1 < 0 will give correct results when t1 overflows

  1. delta = 1 with overflow of bigger value (notice: we don't make lesser value overflow because it would mean that both values are in the same cycle so calculations would be same as if there wouldn't be any overflow)

    • real values: t0 = 3 t1 = 4
    • overflowed: t0 = 3 t1 = -4
    • t0 < t1 ==> 3 < -4 -> false
    • t0 - t1 < 0 ==> 3 - (-4) < 0 ==> -1 < 0 (7 overflows to -1) true

    so only for t0 - t1 < 0 we got correct result despite or maybe thanks to overflow.

  2. delta = 1 but this time no overflow

    a) positive values

    • t0 = 2, t1 = 3
    • 2 < 3 true
    • 2 - 3 < 0 ==> -1 < 0 true

    b) negative values

    • t0 = -4, t1 = -3
    • -4 < -3 true
    • -4 - (-3) < 0 ==> -1 < 0 true

    for rest of cases where real delta = 1 we will also get correct results for both t0 < t1 and t0 - t1 < 0 tests (t0 - t1 will be always -1)

  3. delta = 3 (almost half of cycle)

    a1) with overflow of bigger value

    • real values: t0 = 3 t1 = 6
    • overflowed: t0 = 3 t1 = -2
    • t0 < t1 ==> 3 < -2 -> false
    • t0 - t1 < 0 ==> 3 - (-2) < 0 ==> -3 < 0 (5 overflows to -3) true

    a2) another case with overflow

    • real values: t0 = 2 t1 = 5
    • overflowed: t0 = 2 t1 = -3
    • t0 < t1 ==> 2 < -3 -> false
    • t0 - t1 < 0 ==> 2 - (-3) < 0 ==> -3 < 0 (again 5 overflows to -3) true


    So again only t0 - t1 < 0 gave correct result.

    b) without overflow t0 - t1 will always be equal to -3 (-delta) so this will always be giving correct result. t0 < t1 will also give correct resilt

    • real values: t0 = -1 t1 = 2
    • t0 < t1 ==> -1 < 2 -> true
    • t0 - t1 < 0 ==> -1 - 2 < 0 ==> -3 < 0 true

  4. delta = 4 result of t0 - t1 will always be equal to -4 so it will also be <0.

    examples with overflow
    a1)

    • real values: t0 = 0 t1 = 4
    • overflowed: t0 = 0 t1 = -4
    • t0 < t1 ==> 0 < -4 -> false
    • t0 - t1 < 0 ==> 0 - (-4) < 0 ==> -4 < 0 (4 overflows to -4) true

    a2)

    • real values: t0 = 1 t1 = 5
    • overflowed: t0 = 1 t1 = -3
    • t0 < t1 ==> 1 < -4 -> false
    • t0 - t1 < 0 ==> 1 - (-3) < 0 ==> -4 < 0 (4 overflows to -4) true

    So again only t0 - t1 < 0 give correct results.

    Examples without overflow obviously will be correct for both tests.

  5. delta = 5 (and more)

    a1) with overflow
    (minimal value tor t0 is -1 so lets start with it)

    • real values: t0 = -1 t1 = 4
    • overflowed: t0 = -1 t1 = -4
    • t0 < t1 ==> -1 < -4 -> false
    • t0 - t1 < 0 ==> -1 - (-4) < 0 ==> 3 < 0 false

    a2) with overflow

    • real values: t0 = 1 t1 = 6
    • overflowed: t0 = 1 t1 = -2
    • t0 < t1 ==> 1 < -2 -> false
    • t0 - t1 < 0 ==> 1 - (-2) < 0 ==> 3 < 0 false both tests failed

    b1) without overflow

    • t0 = -4, t1 = 1
    • -4 < 1 true
    • -4 - 1 < 0 ==> 3 < 0 (-5 overflows to 3) false
+-------------+-----------------------------+----------------------------+
|  tests if   | delta <= size of half cycle | delta > size of half cycle |
| t0 is less  |-----------------------------|----------------------------|
|  than t1    |  overflow  |  no overflow   | overflow  |  no overflow   |
|-------------|------------|----------------|-----------|----------------|
|   t0 < t1   |      -     |       +        |     -     |       +        |
|-------------|------------|----------------|-----------|----------------|
| t0 - t1 < 0 |      +     |       +        |     -     |       +        |
|-------------|------------|----------------|-----------|----------------|
| t0 - t1 > 0 |      -     |       -        |     +     |       -        |
+-------------+------------+----------------+-----------+----------------+
Pshemo
  • 122,468
  • 25
  • 185
  • 269
  • In general terms, two's complement subtraction is protective against overflow or underflow of either operand, as long as the distance between them is less than half the number of values that can be represented by their bit width. Under these conditions subtraction yields the same result as if the operand(s) didn't over/under flow. – Daniel Nitzan Jun 27 '23 at 07:13
1

The quote from the API is actually:

Differences in successive calls that span greater than approximately 292 years (2^63 nanoseconds) will not accurately compute elapsed time due to numerical overflow.

If t0 and t1 are measured 292 years apart you will experience numerical overflow. Otherwise either the comparison or the subtraction will work just fine.

zevra0
  • 209
  • 1
  • 5
  • 1
    not true.... they can be just 1ns apart, but if the overflow was between them then `t0 < t1` is different to `t1 - t0 > 0` – rolfl Aug 24 '13 at 02:40
-1

Use any method.
It will be no difference in the nearest 290 years.
Your program (and even Java itself) will not live so long.

Egor Skriptunoff
  • 23,359
  • 2
  • 34
  • 64