12

Exploring the code of java.util.LinkedList as it is in OpenJDK 8, I found the following code. The code is straightforward, but I'm confused about saving reference to the first node to a constant in the second line of code. As far as I understand, this code will be inlined to one-liner without reference copying. Am I right? If so, why does one need to copy reference in this and similar situations (such idiom may be found in a half of methods in java.util.LinkedList)?

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

My first thought was that it helps concurrency in some way, but LinkedList does not allow concurrent access (except at your own risk), so I guess it is some hint for optimizer, but can't figure out how it is supposed to work.

Raedwald
  • 46,613
  • 43
  • 151
  • 237
Vladimir Nazarenko
  • 185
  • 14
  • 2
    AFAIK, using a reference that is on the stack is faster than using a reference that is on the heap, or at least used to be. So it was recommended to do this, especially if you used the reference several times in the method. I doubt it makes a significant difference nowadays, because the JIT would probably optimize the one-liner. – JB Nizet Jun 12 '16 at 15:58
  • 2
    Possible duplicate http://stackoverflow.com/questions/4761681/avoiding-getfield-opcode. It's a micro-optimization. – Radiodef Jun 12 '16 at 15:58
  • 1
    Possibly, if `first` might change during the execution of this method, they want to ensure that all tests are done on the same reference. You don't want to test for `first` not null, then have it change out from under you, then try to dereference it when it may have changed to null. – markspace Jun 12 '16 at 15:59
  • They are using final to just tell the compiler once assigned, don't change it. The does basically says 1) put the object first as the first node. 2) to avoid a null pointer if f is null return null else return the 'item' that is within the node f. So really its just a matter of them assigned and returning the item within the first node. And btw if node is null, return null instead so a null pointer won't happen – Dale Jun 12 '16 at 15:59
  • 1
    Also http://stackoverflow.com/questions/2785964/in-arrayblockingqueue-why-copy-final-member-field-into-local-final-variable and http://stackoverflow.com/questions/28975415/why-jdk-code-style-uses-a-variable-assignment-and-read-on-the-same-line-eg-i (**tl;tr**: It's an extreme form of performance optimization, and brings a (very) limited form of ""thread safety"") – Marco13 Jun 13 '16 at 08:30

1 Answers1

12

My first thought was that it helps concurrency in some way...

...so I guess it is some hint for optimizer...

Both. :-) The fact that LinkedList doesn't support concurrency doesn't mean that the authors aren't going to follow good practices anyway, and it tells the compiler and the JIT that they should only look up first once.

Without the f local variable, we'd have:

public E peek() {
    return (this.first == null) ? null : this.first.item;
}

I've added the implied this. to emphasize that first is an instance field.

So if the this.first == null part is evaluated on Thread A, then this.first is changed on Thread B, when this.first.item is evaluated on Thread A, it may throw because this.first has become null in the meantime. That's impossible with f, because f is local; only the thread running the peek call will see it.

The final part is both good in-code documentation (as the author never intends to change the value of f) and a hint to the optimizer that we're never going to change f, which means that when it comes time to optimize, it can optimize it to within an inch of its life, knowing that it only ever has to read this.first once and can then use a register or stack value for both the null check and the return.

Community
  • 1
  • 1
T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
  • 1
    IIRC `final` local variables exists in Java source only and not in the bytecode. So the optimizer won't see it (which is no problem as it can easily determine whether the variable gets ever reassigned). – maaartinus Jun 12 '16 at 20:06
  • @maaartinus: At the bytecode level the local variable exists; if you look at the bytecode for `LinkedList#peek` you'll see `getfield` for `first` and then `astore_1`, and then all the rest of the method is operating on that local variable 1. The JIT presumably takes it further, but initially the variable exists. – T.J. Crowder Jun 13 '16 at 06:03
  • 2
    So,you are saying the OP's suggestion that the JIT would inline f to this.f is wrong. – Raedwald Jun 13 '16 at 07:12
  • I see I was sloppy with my formulation. What I meant: The `final` *modifier* for local variables does not exist. And leaving the modifier out will probably lead to exactly the same bytecode (AFAIK javac is free to do optimizations and their result may differ). – maaartinus Jun 13 '16 at 23:47
  • @maaartinus that's correct. `final` for local variables exists only for `javac`, no barriers are inserted what-so-ever (as opposed to a `final` set via a constructor) – Eugene Feb 08 '18 at 08:18
  • Actually, this would only change the behavior of a very simple JIT. Any sophisticated JIT will ignore the possibility that `this.first` can be changed by a different thread in-between and optimize the code to a single read. That’s the reason why you need `volatile` for a variable when you want to enforce re-reading its value for every read access. – Holger Feb 08 '18 at 11:10