Notes on Java, Solaris, PHP, LDAP…

Java Memory Brief

Java Memory Brief
Effectively Final Fields and Objects

The goal
I’d like to point at inconsistencies between some multi-threading guarantees and non-guarantees of Java Memory Model (JMM) and current practice – J2SE sources and examples in Java Language Specification (JLS). I suggest a backwards-compatible win-win solution with possibility for some extra benefits.

For both you and me this text is quite a catch twenty two: What should go first: informal definitions and the proposal, description of status quo and reasons for extending JMM, or examples of bad practice? I’m putting status quo and reasons first. Then go most of the definitions – because those are useless without reasons/advantages. The examples are at the end. Some terms link to their definitions.

Why now? (Introduction)
Java is the first real multi-threaded language and platform available on such a large scale. It focuses on threads from its very conception – in language, VM, standard and enterprise libraries. It got purified in JMM which also raised awareness about multi-threading among general programmer community.

Thanks to Java’s attention to multi-threading, we can scale well-threaded applications from single-core to multi-hardware thread and/or multi-core, multi-processor and multi-board. Still, many current applications are not designed to scale. We’re only at the beginning of multi-threaded era.

JMM nicely and formally defines correct synchronization in Java code. However, you’ll see that the very J2SE sources fail to follow JMM. Now, they are entitled to it – because method bodies or private/package private fields are not a part of J2SE API and they work in tango with JVM. So as far as JVM guarantees that all J2SE sources run thread-safe on all supported HW platforms (i.e. it gives extra guarantees on top of JMM), then all is fine.

As Java is becoming open source it is likely to be ported to other hardware platforms. That may break J2SE sources – they won’t run compliant to JMM anymore. And it may be even worse, ironically thanks to Java’s becoming GPL. The sources may become learning and code basis for many open source projects. I’m not promoting copy-and-paste, but we may just expect – and we should encourage – that people learn and use patterns from J2SE sources. However, then they’ll end up with code that doesn’t follow JMM.

But there’s more than just J2SE sources (which are easy to fix). It’s that Java gives no ability to one-time ‘flush’ an object to main memory in the Producer thread, so that any Consumer threads could access the object up-to-date without any synchronization costs – provided the object won’t be ever modified again. That affects java.util.HashMap, java.util.HashSet, other J2SE collection classes and third party/user classes.

Rather than enforcing current JMM, let’s ask: Why should we go the same way? Yes, JMM came to play after these J2SE classes were written. But JMM didn’t fix them. No memory model will fix our source code. The question is: should we really call all of this non-compliant code ‘incorrect’?

Effectively final field – really informal
It’s a non-static non-final non-volatile field. You set it once or several times in Creator thread – one that created the object which holds the field. You can set it in the constructor of the object or afterwards. Once you’re happy with it, you publish the object to other threads – Consumers, and you never modify the field anymore. See also the more formal definition.

Isolated costs
These costs are a result of a common error when we use effectively final fields without synchronizing. That’s incorrect under current JMM.

The good news is that if the field is private or package private, you don’t need to change API or check its usage. Therefore the costs of fixing it are isolated. We have two ways of doing it:

  • fix existing code in J2SE sources and all around the globe by educating programmers under current JMM. It will be a lot of work for some designs and it will induce same amount of ‘extra work’ in future. But it will be annoying and unproductive job. I.e.: nobody will care to do it – until their application breaks.
  • add support for effectively final fields to JMM so that it guarantees them to be thread-safe. We’ll still have to do some work – to identify and indicate those existing fields and their holder objects as effectively final. But you don’t need to change the initialization code.

Java provides thread-safety for non-final fields by two levels of cross-thread data access: synchronized and volatile. JMM and Java tutorials on multi-threading suggest to use final (immutable) objects. We thought that was enough. Yes, you can safely implement a multi-threaded design this way. However, you’ll see that it often gets really difficult and those options are not sufficient. That’s why programmers didn’t care and we ended up with incorrect implementations. If JLS/JMM were followed then J2SE sources in question and similar designs would

  • be much more complex
  • have higher synchronization cost

Why did that happen? Because we didn’t recognize the need for finer-grain cross-thread access. We assumed that

  • programmers could do with final fields
  • programmers wouldn’t care to determine and advise that an object is effectively final
  • JVM, objects and applications can’t benefit from any such advice

In JMM-compliant examples and designs we treated effectively-final objects as fully mutable. Therefore we accepted their synchronization/volatile cost as something we can’t do anything about. This rationale is similar as with garbage collection (GC). So let’s look at those two.

GC got much better over time. Today Java manages memory faster than C for well-written applications. It will get even faster when Java uses escape analysis and it will treat local objects as if they were allocated on stack. But still, you can request a specific GC behaviour if you run Real Time JVM.

However, cost and optimization trend of synchronized/volatile access is worse than that of GC. While synchronization became about two times or more cheaper as JVM evolved from 1.2 to 1.5, JMM increased cost of volatile access to approximately half that of synchronized (at that time). If we make J2SE properly synchronized it will increase the cost again. But, the important thing is that we cannot decrease cost of volatile/synchronized access much more, because it involves situations of two or more threads which we can’t really predict. So rather than expecting synchronization/volatile to miraculously get cheap, how about eliminating synchronized/volatile access when not necessary? Then we can happily make our applications fine-grain synchronized where we actually need it.

There’s another big difference between memory management and cross-thread access. It’s their “breakability” and observability of it. If your or a 3rd party code keeps references to unused objects, it doesn’t do any direct/active harm to JVM, other objects and threads – as far as you have enough memory. If your applications keeps those unused references only temporarily then adding memory is a quick fix and it works. If your application cumulates unused references, then you’ll detect it if you run it long enough – no matter what HW/JVM.

If your application is not thread-safe, you have a much more difficult life. The problem is that it may execute well on one system and it fails on different HW/JVM. Even worse: it may fail silently – when your application behaves incorrectly but it goes undetected.

Arrays
The above was bad but there’s more to it. How about effectively-final arrays within effectively-final owner objects? Those arrays have their items set in the constructor of their owner object, or after the constructor returned but before the owner object is accessed by any other thread. The array won’t be ever modified again. Plus usually the array is not passed outside the owner object but it’s accessed via methods, so the clients have no way to modify the array. How can we have those effectively-final objects in a thread-safe way without any synchronization action in producer and consumer threads?

Common structures
These are designs that can’t easily fulfill their
multi-threading guarantees (documented or implied) because of current JMM limitations. The most difficult ones are backed by arrays e.g. standard ArrayList, HashMap/HashSet. Array-less designs are also affected e.g. LinkedList.

E.g. java.util.HashMap/HashSet is mutable. Following is its Javadoc notes about synchronization:

“Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.”

Look at this specific case:

  1. you create a HashMap instance based on another (possibly temporary) Map using constructor HashMap(Map)
  2. you never modify the instance after you instantiated it
  3. you pass the instance to other threads, without any synchronization in good faith, as it sounds OK with the above JavaDocs
  4. all threads now use the instance read-only

You possibly wrap the HashMap instance using java.util.Collections.unmodifiableMap(Map) and you use this read-only wrapper instead. However, it doesn’t change anything about behavior of the underlying HashMap instance – which is only effectively final and therefore not thread-safe under current JMM.

By this interpretation of HashMap’s docs you should be OK if you don’t ever modify the map after you created it. But its Javadocs is weaker than JMM. It doesn’t define all possible ways of modification because HashMap(Map)
constructor *does* modify the new instance.

In a common sense implementation this constructor sets some kind of non-final backing field within HashMap instance and that fields holds a backing array. J2SE implementation uses array table[]. We may want to add more items later on, so we need the ability to replace the array. Therefore the backing field (e.g. table[]) will normally be non-final. Clearly, the above unsynchronized cross-thread usage of ‘immutable’ HashMap instances doesn’t conform to JMM. In order to use it in other threads (that existed before the HashMap was populated) we must synchronize both creator thread and *all* consumer threads.

Relax or not really?
The fact is: the above won’t be a problem for some usage of standard ArrayList, HashMap/HashSet, LinkedList (and possibly more classes), because of how their ‘fail-fast’ validation is currently implemented. It updates a volatile field every time the map/collection is structurally modified. When you obtain an iterator of ArrayList, HashSet or LinkedList, or of a view Collection to a HashMap (i.e. its keySet(), values() or entryset()), then J2SE stores the current value of that volatile field in the iterator object. Then every time you use the iterator, it compares the stored value and the current value of the backing collection/map. If they are different, it throws ConcurrentModificationException.

However, some methods of ArrayList, HashMap/HashSet and LinkedList don’t use their iterators. If you pass such a non-empty object to another thread without any synchronization action, then you’re failing current JMM it may not work as you expected. And as J2SE API says, fail-fast behaviour is not guaranteed anyway.

HashMap compliant with current JMM
There is at least one way to do it. But it’s a really awkward one – you’ve been warned.:)

HashMap would have two fields for the backing array: final initialArray and non-final non-volatile mutableArray. The accessor methods, backing sets and their iterators would use mutableArray if non-null, otherwise they use initialArray.

HashMap(Map) would set and populate initialArray and it would leave mutableArray to be null initially. Any modifications via HashMap’s methods or via its backing collections and their iterators would set/modify mutableArray and its items. The first change would set mutableArray to a new array and it would populate it with items from initialArray.

Threads would still have to synchronize any instance that was created by HashMap(Map) and which can be modified afterwards, or if the instance was created by another constructor. But if the object was created by HashMap(Map) and the design guarantees that it won’t be ever modified after its creation, then all threads could use it without any synchronization. Thanks to Direct Component Guarantee consumer threads would see initialBacking up-to-date without any synchronization action.

Constructors other than HashMap(Map) would set mutableArray to a new backing array and initialArray to null. Those instances should be always synchronized if used by several threads – even if the Creator thread modifies the instance before it’s passed to the Consumer threads.

But I really don’t want to ‘design’ array-based classes this way. Look at source code of a simplified Map Example.

Flushable fields

We could introduce another level of thread-safety, something between non-volatile mutable fields and effectively final fields, and the same thread-safety for the owner object (or array). Let’s call them ‘flushable’ fields and ‘flushable’ object/array. They all would be mutable and non-volatile. The code could set the fields or items of the array anytime, in any thread, before or after the constructor returned. As far as the object/array is not visible from any other thread, the creator thread can ‘flush’ the object/array (see how to ‘Flush’ effectively final objects). That would ensure all the non-volatile fields and array items would have same values when the object/array is passed to other threads and accessed there. Once flushed and passed to other threads, the instance behaves as standard object/array – it can be modified by any thread as far as those synchronize properly.

But do we probably don’t need this. An object/array is going to be used either as immutable, or not. If it is not guaranteed to be immutable, then you need synchronization actions to use it cross-thread anyway – so you can just as well synchronize the object/array after you fully initialize it and before you use it in any other threads.

Solution
Let’s talk thread-safety :) Really, we need to mark effectively final object/arrays as such. As per mutable ones – the only way is synchronization actions. And for the effectively final ones – we need a way for the client code to indicate an object/array as effectively final.

Deserialization
Situation: you want some final fields to be transient and to have them set/re-calculated/re-created at deserialization. E.g. you want to set the field to be an object from a pool of objects that you don’t serialize. Such transient fields can’t be final. Thinking of using non-transient final fields and setting them via reflection? It won’t work.

The way around it: use readResolve() to create a new instance based on the current instance (this). Something like Serialization Proxy cool pattern (Joshua Bloch: Effective Java Reloaded, JavaOne 2006 – TS-1512) but used to generate full and final instances of same class as the deserialized one. Such a full instance initializes all its final fields – either to persistent fields of the deserialized instance, or to calculated/created values (possibly from an object pool) for any ‘transient’ final fields (i.e. final fields that we don’t want to de/serialize). The deserialized instance is then forgotten and can be garbage-collected.

However, it all adds extra work. And there’s no productive work in replacing deserialized instance by an object of the same type only so that some of its final fields behave like transient. Plus, when serializing the object, those ‘transient’ final fields still get serialized, although their deserialized counterparts are never used. Then you could use writeReplace() to generate a new instance which would have those ‘transient’ final fields set to null.

You also need to think of subclasses – those would have to override readResolve(), to call their own constructor which would then call appropriate parent constructor… So normally developers use effectively-final transient fields and set them in readObject(). Then such instances are not cross-thread safe due to JMM and should be synchronized on. J2SE sources use this approach and don’t perform any synchronization.

The deep problem
The need to synchronize is not the worst thing in all of this. It’s that you don’t know whether you need to synchronize. Java doesn’t know whether your current thread needs to synchronize an object or whether it is already in sync. And it won’t ever know because of nature of multi-threading. Since we can’t advise JVM that our instance is designed to be effectively final, both sides – JVM and the programmer – loose the potential of playing more smoothly.

There is more difference between GC and volatile/synchronized access in Java than just in their cost. It’s about what the application can affect. GC doesn’t ask for much from the programmers. Simplified: you’re OK if you

  • store your local objects locally only
  • break static or ‘global’ links to objects that you don’t need anymore
  • use weak references and weak map when appropriate.

So you don’t need to do much actively – you only refrain from stepping on GC’s feet. However, with volatile/synchronized access, it’s all your responsibility. You manage it directly through the language synchronized keyword, Object’s notify/wait/interrupt functions and by defining variables volatile, or indirectly via e.g. java.util.concurrent.locks. Either way, JVM doesn’t take synchronization/volatile responsibility from you the same way it does with GC. It can’t optimize it much for you – except in simple cases e.g. escape analysis detects that an object is used only in one thread.

Let’s look at what came after JMM. Java 1.5 brought us much finer tools in its java.utils.concurrent.atomic package. Its Updater classes add a great deal of usability to the volatile fields, as far as you set the fields exclusively via an Updater object. So it looks like eventually we do benefit from different levels of synchronized/volatile access. As we are on this road, we could gain more if Java optimized effectively-final objects.

We should acknowledge some of J2SE sources and API as not compliant to current JMM and we need to do something about it. And while at it, let’s ask: Could we gain from the designer’s knowledge of those objects being effectively-final?

If we introduce reasonably simple support for effectively-final objects then we’ll have easier migration for current J2SE sources and other not JMM-compliant designs. And we could get some extra benefits.

Terminology


Synchronization action
As defined in JLS 17.4.4 page 561 (physical 595).

Synchronized access
It’s when two or more threads use synchronization actions to read and write to a non-volatile non-final field, so that all other threads can read the last written value. The most common synchronization action is a synchronized method/block and write and read of a volatile variable. You need to perform synchronization action on same object or volatile field on both sides – in writer and reader threads.

That doesn’t guarantee the object’s consistency if a change of several fields must appear as an atomic operation (i.e. all changes visible to another thread, or none). Then you need synchronized methods/blocks.

An effectively final field

  • non-static, non-final, non-volatile
  • it gets set to non-default value
    • in some constructors but not all of them and/or
    • in readObject() on deserialization or
  • and therefore the field can’t be final. At least in some cases this field gets sets only after the instance is constructed or deserialized.
  • in any case, the field gets set in the thread that created it and before the instance is seen by any other thread
    • i.e. the instance is not passed to another thread, not stored in any static reference and not accessible from any static reference, before all its effectively-final fields are set

Reasons for effectively final fields

  • in most cases we can just use final fields instead
  • however, we need an effectively final field of an object when we must calculate its value in the same thread
    • after constructing or deserializing the instance
    • via some callback mechanism
      • not a common way to do it but sometimes it’s the easiest one
    • based on other objects which link to/from our object e.g. in matrix/graph structures. Then we may need to calculate effectively final fields of several/all objects within the graph based on other objects (their already initialized fields).

Final object
This is an object with all fields being final. Usually it’s a panacea object. Everybody likes it. Modern garbaged collectors love it. If all its deep components are final objects then it is a real immutable ‘value’ object. However, it can be a pain in the neck to design, if some fields are calculated in complicated way or they are just not available until later after constructing/deserializing the object.

Effectively final type
This is what you get if you aim for a final object, but you just can’t do it because at least one of its fields is an effectively final field. So it can have some final fields and the rest of the fields are effectively final. If the object is an array and all its items are effectively final then the array is effectively final.

You need to declare a class as capable of being effectively final – here I suggest an interface java.lang.EffectivelyFinal. Arrays will be always declared as effectively final and array classes would implement EffectivelyFinal.

There is a difference between class and type in Java, but “effectively final class” sounds confusing. Therefore I call it “effectively final type” although it’s not type as in terms of Java generics. We might use “effectively immutable” rather than/in addition to “effectively final” – then we could use both “effectively immutable class” and “effectively immutable type” as appropriate.

Effectively final instance/object/array
It’s an instance of an array or an effectively final type and it was indicated as effectively final instance. See section below for how we could indicate that.

We need an option to make results of the following methods as effectively-final. We don’t want every result to be effectively-final because it adds the flush overhead. Since some of them are declared in an interface, we can’t just add another set of methods. So we want a way to mark/indicate an array as effectively final on the side of client (consumer), and that would flush it. It could also mark the array as read-only – see Extra benefits.

  • java.util.Arrays.copyOf( *, int )
  • java.util.Arrays.copyOfRange( *, int, int )
  • java.util.Collection.toArray()
  • java.util.Collection.toArray( T[] )

If you don’t indicate your instance as effectively final, then there are no cross-thread guarantees for its mutable fields and you need to synchronize.

Final field chain
If we access a target object via a final field of another object – or repeatedly via a chain of fields of several intermediate objects, where all those fields are final – then we access the target object by a final field chain from the ‘first’ object. All these links are thread-safe and don’t need to be synchronized – although we may need to synchronize the target object.

Thread’s cache
These are cache(s) that hold changes applied by a thread which were not yet committed to the main memory. It includes caches on all levels of HW thread, CPU core and CPU. If a JVM uses registers to cache some instance fields then they’re also a part of thread’s cache.

Direct Component Guarantee
JMM in JLS 17.5, page 573 (physical 607) as worded in JLS mentions terms version of an object and version of an object’s final fields: “…then when the object is seen by another thread, that thread will always see the correctly constructed version of that object’s final fields. It will also see versions of any object or array referenced by those final fields that are at least as up-to-date as the final fields are.”

So you have an ‘owner’ object which has a final non-primitive field and that points to a mutable target object or array – the direct component. In that target object you have some non-final non-volatile fields (or items, if it’s an array). The above part of JMM guarantees that those fields/items will be up-to-date in threads other than the creator thread, so far as they access the direct component via the final fields of the ‘owner’ object. The guarantee doesn’t apply to any deeper mutable components or multidimensional arrays. Therefore let’s call it ‘Direct Component Guarantee’.

This special treatment of mutable objects/arrays accessed via final fields is not mentioned anywhere else in JLS. There are no details on how it interacts with the rest of JMM, synchronization actions and optimizations allowed by JMM. JLS should define version of an object or its fields. It should also clarify when this guarantee applies. For a long story see Tricky Direct Component Guarantee.

The nice part: it implies that setting a final field and then accessing it in other threads is some kind of hidden one-time flush of (part of) thread’s cache to the main memory. That’s similar to what we need for effectively final fields. So if current JVMs can do this, it shouldn’t be much difficult to make them support effectively final fields.

Unsynchronized cross-thread
Common JMM-compliant code uses synchronization actions when passing an object between threads. If an array or object with non-final instance fields is passed to other threads, there’s a happens-before edge. So we could do without cross-thread guarantees that JMM gives for classic final fields. Because if you have an object and its fields get never modified once you pass from producer thread it to consumer thread(s) with synchronization actions between those threads, then those consumer threads see the object up-to-date – no matter whether the fields are final or not. So the thread-safety of common correct code doesn’t benefit from and it depend on the fields being final. But final fields are important to protect our objects when we pass them to incorrect old/third party code that doesn’t synchronize properly.

There’s at least one way legal with current JMM to do it without any synchronization action: to pass it as a static final field of a class, or accessible from a static final field via a final field chain. It means that Producer initializes the class and assigns the instance reference to a static final field. The Consumer reads the static final field and retrieves the object. Also see a note on Flushing initial static values.

One API part of J2SE indirectly suggests that clients can pass any objects through it to other threads without any synchronization action. It’s the structural modification part of java.util.HashMap docs:

‘Note that this implementation is not synchronized. If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.)’

It means that threads don’t need to synchronize, if they only change values for any existing keys. However, that’s only in regard to thread safety of the HashMap instance itself. It doesn’t say anything about the values. An example: A thread puts a new mutable object as a value for a key that was already present in the map. Then other thread(s) read the new mutable value for the same key. According to the above those threads don’t need to synchronize. But the value object needs to be synchronized because it’s mutable – even if it won’t be ever modified.

The structural modification clause and its implementation are unfortunate. It doesn’t guarantee that the new values (for any existing keys) will be visible to other threads. They may be visible on some HW/JVM and not on other.

Flush
Flushing is when JVM commits all modifications of given object (or any shared data?) by the current thread’s cache to main memory. I.e. it’s a synchronization event by the ‘producer’ thread.

Factory methods
Effectively final instances must be created, populated and indicated as effectively final. Constructor can do all that in some cases but not in all – otherwise all fields would be definitely assigned in the constructor and we could just use standard final fields. So normally we populate the instance and indicate it as effectively final in a method – let’s call it a factory method. It can be static and we pass it the instance as a parameter. A factory method could be non-static invoked on the instance that is being populated. We don’t want the factory method be public and we don’t want to expose the instance publicly before it’s fully populated.

Proposal: Co-operation
Rather than changing design or usage of existing classes, their constructors and deserialization functions, how about relaxing JMM a little so that it supports effectively-final objects.

We need to declare that a class will be used for effectively-final instances. How about a method-less interface e.g. java.lang.EffectivelyFinal?

We also need effectively-final array instances, but users can’t make array class implement an interface. And we don’t want a separate ‘branch’ of effectively final array classes, one per each ‘classic’ array class – because we want to keep things simple. It’s the same reason as to why Java doesn’t have a way to declare an immutable array (although we’ll think about at the end of this section). So because we want effectively-final status for arrays be set on instance basis rather than class basis, we’ll declare all array classes effectively-final. Then all array classes would implement EffectivelyFinal the same way they implement Cloneable and Serializable.

Then we want a way to indicate that an instance of effectively final object/array is already populated – and that it won’t be modified ever after. It’s an action/choice on instance-basis, while making a class implement EffectivelyFinal is only a declaration and it is for the whole class. Instances/arrays that we indicate as effectively final will be flushed while others won’t.

There may be several ways to do it. Some are:

  • just synchronize on them
    • however, this way we downgrade/lose semantics indicating that the effectively-final object/array is ready
    • it should be OK with existing designs – the creator thread shouldn’t be passing the object/array to other threads before the object/array is populated
    • it would be incompatible with quality-assurance proposal at the end of this section: it would break existing designs that correctly synchronize and modify arrays.
  • call a dedicated (static) method with the object/array as an argument. It could be e.g. System.effectivelyFinal(EffectivelyFinal)
    • it’s OK to call it several times – e.g. when invoked from both parent and subclass, or several times within the same class
  • if Java 7 or next allows to have non-abstract non-static methods in interfaces (and also final methods, please), then we could have a non-static final method effectivelyFinal() in EffectivelyFinal
  • we could introduce a new type of block statement, similar to synchronized(Object) {..} – something like effectivelyFinal {…}.
  • or we could just mark the constructor or factory method with a new modifier e.g. effectivelyFinal
    • both effectivelyFinal modifier and effectivelyFinal {…} blocks have to be re-entrant, so that subclasses can call parent constructor/methods that set effectively final fields defined in the parent class, or within same class but factored out to a method on its own

Adding new keywords is not a simple thing in Java, but this would give us extra benefits.

Those actions would be just indications by programmer. It would be up to JVM whether it actually needs to perform any extra cross-thread communication. Probably about all JVM needs to do is to write data changes from current thread’s cache to main memory.

Note that it’s up to the producer code to indicate that an array or an instance of effectively-final type as an effectively-final instance. This allows us to apply the producer’s modifications even after the constructor or deserialization as far as the object/array was not published to any other thread.

First time an effectively-final object is accessed by a thread other than the creator thread, JMM will act as if it were reading any of its volatile fields (even if there are none, or if the object is an array). This would allow consumer threads to safely pick up effectively-final fields and effectively-final objects/arrays. The changes by creator thread would be guaranteed to happen-before first time a consumer thread accesses the effectively final object/array – as far as the effectively object is not published by the creator thread before it’s populated.

Reentrant
Allowing effectively final indication to be reentrant/repeated means that JVM has to flush same instance several times, each time it’s indicated as effectively final in various parent classes. We would benefit if the instance knew the youngest class whose code would indicate the instance as effectively final. Then JVM could ignore the indications in code of any parent classes. We could indicate whether we want the actual subclass of an effectively-final type to benefit of effectively-final guarantee or not. We can do that by declaring that the subclass implements EffectivelyFinal interface again. It’s OK with current Java 6 and it is reflected in both Class.getInterfaces() and Class.getGenericInterfaces() so it would be a good enough hint for JVM.

Extra benefits
Let’s ask whether we can get any quality assurance for effectively final instances. JVM could keep a flag in every effectively-final instance. Let’s call it ‘effectively final flag’. It would be boolean for arrays and true only when the array instance was indicated as fully populated and ‘ready’ to be used cross-thread. For non-arrays the flag would be a Class object. It would be null if the instance was not yet indicated as populated. Once it were indicated as populated in a method or constructor of class C. That would mean the instance shouldn’t be ever modified again within class C and any of its parent classes.

There could be several ways to report that the code attempted to change an item of an effectively final array or a field of an effectively final instance (where that field was declared in a class that indicated as already populated, or any of its parent classes). It would be responsibility of JVM to detect and report that. It could generate an error or assertion. The advantage of assertions is obvious – we can turn them off once we’re confident about our system. This would also give us immutable arrays checked at runtime. Nice, isn’t it?

There’s one more quality assurance we may want. Let’s say we use System.effectivelyFinal(EffectivelyFinal) or non-static EffectivelyFinal.effectivelyFinal() method. Then we need to make sure that if a child class “re-implements” EffectivelyFinal, then all its factory methods also call effectivelyFinal(). Otherwise, if a child factory method calls any factory methods from its parent classes but the child method doesn’t indicate effectivelyFinal() at its end, then we would end up with half-flushed instance. We can have a debugger tool detect that (when such an instance gets passed to a different thread), or the programmers would have to safeguard themselves.

This problem disappears if we used effectivelyFinal {…} blocks to indicate object/array instances as already populated. If we had another boolean flag for user-defined effectively final types, it would indicate whether the instance is being processed within effectivelyFinal {}. When the uppermost effectivelyFinal {} block finishes JVM would set effectively final flag on the instance.

JVM could also use boolean for effectively final flag for user-defined effectively final types rather than using Class<?extends EffectivelyFinal>. This would allow JVM to treat effectively both final arrays and user-defined types in same way.

JVM implementation and costs
On the producer side it’s responsibility of the programmer to assure that the object/array was not passed to any other thread yet. But this synchronized/volatile access is just a semantic hint to JVM. It’s just up to JVM implementation whether the above adds any overhead or not. If JVM detects that the object/array couldn’t be yet accessed by any other thread then it can as well ignore synchronization. It may need just to flush the object/array thread’s cache to main memory.

As per the consumer threads – when the CPU/core/HW thread is accessing the object/array for the first time, it’s getting it either from the cache or main memory. If it’s cached then it got there effective-fields-friendly and we’re OK. If the creator thread was moved to another CPU/Core/HW thread before it sets an effectively final field then JVM may need to invalidate its out-of-date chached fields. As per multi-level caches and non-uniform access memory: there are smart guys who can sort it all.

Tricky Direct Component Guarantee
Let’s have two threads: Producer and Consumer. Let’s have an ‘Old’ object with at least one non-final non-volatile field. Both Producer and Consumer get a reference to Old in a thread-safe way (possibly synchronizing on a shared lock) and they store reference to Old in a local variable. Then Producer modifies a field within Old without any synchronization action. Afterwards Producer creates a new final object ‘Young’. Producer passes reference to Old to the constructor of Young and the constructor sets a final field ‘old’ within Young to be a reference to Old. After Young is fully and properly constructed, Producer passes Young to Consumer without any synchronization action (see Unsynchronized cross-thread). Now Consumer reads and uses Young.old. According to Direct Component Guarantee it should see the same ‘version’ of Old as is seen by Producer – i.e. changes that Producer has done to it since the last synchronization action between the two threads. However, Consumer thread accessed the previous ‘version’ of Old in past and it can still cache it.

So Direct Component Guarantee not only flushes objects stored in final fields of a ‘Holder’ object in the Producer thread, but it also defines some kind of partial/full synchronization or happens-before edge between setting a final field within Holder object in Producer thread and the first access to that final field (of the same Holder object) in other threads. However, it quite goes against the idea that final fields eliminate synchronization costs.

This shows why JLS/JMM should clarify the guarantee and its conditions. Following are examples from JLS that also need some clarification:

  • JLS 8.9 page 255 (physical 289): Direct Component Guarantee applies to static final field prototypeDeck. However, prototypeDeck object gets modified *after* it’s assigned to prototypeDeck field. JLS is not clear whether
    • Direct Component Guarantee applies for such changes, or
    • all the static fields and objects referenced from them get flushed once the class is fully initialized.
  • JLS 15.12.2.12 page 469-470 (physical 503-504): static field COLORS should be marked as final. Then it’s covered by Direct Component Guarantee

Resources
For purpose of this discussion JMM is as described in JLS version 3, PDF. Physical page numbers are as they show up in Acrobat Reader/Preview.app. JVM and J2SE are the ones shipped by Sun Microsystems at java.sun.com (and being open-sourced).

Bad practice
JLS 17.5 page 574 (physical 608)

The FinalFieldExample sets and reads non-final non-volatile field f from several threads without any synchronization action. And its code really looks like Double-Checked Locking anti-pattern – except that the example doesn’t synchronize at all. Yes, the example shows the robustness of final fields and final objects – they themselves don’t need synchronization and they work correctly even when passed to old/third party code which doesn’t synchronize properly. But the example should warn that the incorrect code is there for purpose and it shouldn’t be followed in regard to synchronization.

There’s a tutorial on concurrency in Swing which is not thread-safe because

  • it’s an implementation of SwingWorker<ImageIcon[], Void>
  • its doInBackground() creates a new array ImageIcon[], sets its items and returns the array
  • the returned value (array) is passed to other thread(s) by SwingWorker. However, SwingWorker and the class it uses java.util.concurrent.FutureTask- they don’t synchronize on the result of doInBackground(). As per JMM, they should either synchronize on the result or the implementation of doInBackground() should.

J2SE sources
Here are examples from current J2SE sources which use de-facto effectively final fields without synchronized access. You can browse the sources. I’ve also checked current sources as they were in Mercurial on 26th Dec 2007. See Kelly O’Hair’s blog.

java.util.HashSet – field map

java.util.HashMap – field table

java.awt.SystemColor.java – systemColors should be final, then Direct Composite Guarantee applies. index should be final, or document that instances need to be synchronized if used cross-thread. But also its parent class java.util.Color has non-final field value which is not final and it’s used because for backwards compatibility…

java.security.cert.TrustAnchor – it says ‘TrustAnchor objects must be immutable and thread-safe.’ However, its fields nc and ncBytes should be final (or effectively final). This is a nice example of need for effectively final fields. The authors factored out setting those two fields to function setNameConstraints(byte[]). Then they use the function in all three constructors. There could be ways around it with classic final fields – but that’s not what programmer’s creative work should be.

java.util.UUID – it has plenty fields ‘Computed on demand’. That’s OK but its Javadocs should say that users need to synchronize the instances if cross-thread.

java.util.Date, java.util.SimpleTimeZone – Their instances are mutable but their docs don’t mention that the users need to synchronize properly. Even an instance that doesn’t get ever modified after it’s created is not thread-safe unless there’s happens-before between its constructor and any usage. So if Java supported effectively final fields, then we can make those types optionally effectively final. But then java.util.SimpleTimeZone couldn’t use its magic invalidateCache() and cacheYear, cacheStart the same way anymore.

java.security.cert.CertPath – ‘An immutable sequence of certificates (a certification path)’ – its field type should be final (can be done easily)

Flushing initial static values
I believe that initial values of any static fields should be guaranteed ‘flushed’, so that other threads can see them ‘up-to-date’, even if the fields are not final. Actually, it’s not just ‘flushing’ the fields themselves, but anything accessible from those fields. That means we want a happens-before edge from the end of class initialization and any usage of the class after it was initialization. Maybe that’s how it works in Java but I couldn’t find it mentioned anywhere.

Let’s look at two examples from JLS.

JLS 8.9 page 253 (physical 287) uses effectively-final HashMap instance without synchronization, although it modifies the map after it was constructed:

enum Color {
  RED, GREEN, BLUE;
  static final Map<String,Color> colorMap= new HashMap<String,Color>();
  static {
    for (Color c : Color.values())
      colorMap.put(c.toString(), c);
  }
}

The same for how JLS page 255 (physical 289) uses ArrayList instance prototypeDeck:

private static final List<Card> prototypeDeck = new ArrayList<Card>(52);static {
  for (Suit suit : Suit.values())
    for (Rank rank : Rank.values())
      prototypeDeck.add(new Card(rank, suit));
}

Two minor issues not related to JMM

I think enums should not be able to have non-final static or instance fields. But since we’ve got them already allowed, we should have javac generate a warning about them.

public enum EnumFields {
  FIRST, SECOND;

  private int instanceField;

  private static int staticField;
}

The other issue is: JLS 15.4.2 top of page 486 (physical 520) says:

“A variable that is declared final cannot be incremented (unless it is a definitely unassigned (§16) blank final variable (§4.12.4)), because when an access of such a final variable is used as an expression, the result is a value, not a variable. Thus, it cannot be used as the operand of a postfix increment operator.”

It indirectly suggests that under some conditions we can use postfix/prefix ++/– operator on final fields. However, ++/– can’t be applied to final fields at all. So let’s simplify the above part of JLS.

public class Increment {
  static final int staticField;
  static { staticField++; }
  final int instanceField;

  Increment() {
    instanceField++;
    final int local;
    local++;
  }
}

1 Comment »

  1. I like the idea of ‘effectively’ final fields (and objects/arrays). Certainly I have hit the case where I could not make a field final but wanted it to be.

    Perhaps you should post your ideas onto the java concurrency mailing list?
    It is concurrency-interest@cs.oswego.edu

    I found a blog that looks related…
    http://jeremymanson.blogspot.com/2008/08/top-3-reasons-why-constructors-are.html

    Cheers, Rob.

    Comment by Rob — December 17, 2008 @ 8:44 pm | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: