CODEWITHSUNDEEP
javatimecomparisoninteger-overflow
Evgeni
Evgeni

Reputation: 341

How to compare two nano time values? [javadoc confusion]

I have read the javadoc for System.nanoTime() and it all seems clear. Until I reached the final paragraph:

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.

There are two things that are unclear to me:

  1. Why would one check if t1 < t0 if t1 was taken after t0? My understanding is that nano time is always increasing. So, I would rather check t1 > t0.
  2. Let's suppose that's a typo, and they meant the correct check is t1 - t0 > 0. I still don't get it why that is the correct way of checking and not t1 > t0. They mention the numerical overflow and I don't quite get what they mean. Regarding the numerical overflow, here's what is mentioned:

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

OK, so since the nano time is stored as a long value, it will eventually overflow in 292 years. And what happens next? Does it start from the beginning, i.e. the lowest negative value -2^63? Or does it stop measuring and returns (2^63 - 1) always?

Upvotes: 21

Views: 2122

Answers (4)

Milan
Milan

Reputation: 2023

Let me start from the end of your question. Yes in case value is greater than 2^63-1 the value will overflow. Common implementation of an overflow is that the least significant representable bits of the result are stored; value will wrap (you can see at the bottom of my post about overflow for reference)

Sequence is like: 2^63-2, 2^63-1, -2^63, -(2^63-1) ...

Now looking back at Javadoc I agree that the explanation about using comparison is confusing and that naturally we would try to compare t1 > t0 to validate if t1 happened after t0. You are partially right. Though I don't think it is a typo but it is not explained correctly. I think it should say:

For two values t0 and t1 (where t1 is captured after t0), you should not use t1 < t0 (to check for false) but rather t1 - t0 < 0, similarly you should not use t1 > t0 (to check for true) but rather t1 - t0 > 0

Or to formalise it:

For two 'nano' values t0 and t1, where t1 is captured after t0 following stands: (t1 - t0 > 0) == true as long as the period between t1 and t0 is <= 2^63 ns.

Why? Because even when t1 overflows (so it is negative), the result t1 - t0 will also be negative but, it will be less than -2^64 and it will 'overflow back' to positive value! .

This stands as long as the condition about the distance between t0 and t1 is met! In case the distance is larger than 2^64 e.g: for t0 = 1; t1 = -(2^64-2), subtraction result would be: t1 - t0 = -(2^64-1) so the specified condition (t1 - t0 > 0) will give incorrect result.

Right?:)

On overflow

For the sake of explanation lats assume a type that is stored using 8 bits (instead of 64 used by long), so binary to decimal representation is:

0000 0000 => 0
0000 0001 => 1 (2^0)
0000 0010 => 2 (2^1 + 2^0)
...
1111 1111 => 255 (2^7 + 2^6 + ... + 2^1)

now next number is naturally when you would increment by 1. adding 1 to binary 1111 1111 will produce 1 0000 0000

(1) 0000 0000 => -256 !!! typically the overflown bit on a position 8 will represent a (negative-weight) sign bit

first following value is adding 1 to most-right position 
(1) 0000 0001 => -256 + 2^0 = -255
(1) 0000 0010 => -256 + 2^1 = -254
(1) 0000 0011 => -256 + 2^1 + 2^1 = -253
...

you get the picture

The origin of this is in the underlying hardware registry implementation which relies on binary values. You can read more detailed explanation for instance here: http://www.allaboutcircuits.com/textbook/digital/chpt-2/binary-overflow/

Upvotes: 3

Mike Nakis
Mike Nakis

Reputation: 62129

You are right, the parts of the documentation that you quoted seem to be a bit confused.

However, the part of the documentation that counts is this:

This method can only be used to measure elapsed time and is not related to any other notion of system or wall-clock time. The value returned represents nanoseconds since some fixed but arbitrary origin time (perhaps in the future, so values may be negative). The same origin is used by all invocations of this method in an instance of a Java virtual machine; other virtual machine instances are likely to use a different origin.

(emphasis added by me.)

What this means is that you do not have any guarantees that your code will not happen to be running at the time that the yielded long value will happen to flip from positive to negative.

There is nothing that guarantees that this will happen in 300 years from now, it may happen today.

Currently, my JVM returns some number like 3496793269188, but it could, if it wanted to, be returning some number very close to 9223372036854775807, (which is Long.MAX_VALUE,) which would make a flip from positive to negative imminent.

So, you should take all necessary precautions.

Upvotes: 10

Mr_Thorynque
Mr_Thorynque

Reputation: 2012

When t1 is take after t0 (t1 < t0 = false in real word) and there is an owerflow for t1 (not t0). t1 is negative and t0 positive is this case t1 - t0 < 0 give you the good result false because the binary operation '-' don't make mistake of owerflow and t1 < t0 will give you a wrong result : true

More basic a negative number if it read a unsigned number is bigger than a signed positive number : https://en.wikipedia.org/wiki/Signed_number_representations and

Upvotes: 2

Andremoniy
Andremoniy

Reputation: 34920

Well, javadoc says truth. Consider such example:

        long t0 = Long.MAX_VALUE;
        long t1 = Long.MIN_VALUE;

        System.out.println(t1 < t0);
        System.out.println(t1 - t0 < 0);

It will give 

true
false

while mathematically both expressions are true. But in our case we know, that negative value of time means, that it is overflowed, hence it should be really greater then positive number.

Upvotes: 7

Related Questions