Offer stronger guarantees under the Java Memory model for List, Vector

[scabug]

https://groups.google.com/forum/#!topic/scala-internals/P7WNVkJQdHk

We had several discussion previously about this during the Scala meeting. 

I believe that we could solve the list issues by adding the @volatile 
annotation to the head and tail vars. 
Since those fields is only read afterwards, it should not drastically 
affect performance, if at all - then again, would be useful to try to 
compile the distribution with and without the @volatile in Lists. 

Cheers, 
Alex 
- hide quoted text -


On 9/12/13 6:21 PM, Jason Zaugg wrote: 
> A few recent threads [1] [2] have led me to learn a bit more about the 
> JMM and consider how this applies to the standard library. 
> 
> Both of our poster-children for immutable data structures harbour some 
> dirty little vars. The head and tail of our :: are vars, which allows 
> ListBuffer to directly build a list in start-to-finish order, and 
> Vector has a flag `dirty` that seems to be mutated during the first 
> moments of its life before the reference is released. 
> 
> But, this means that if someone unsafely publishes `new ::("", Nil)` 
> or `Vector(1)` to another thread, that thread could observe a 
> inconsistent state (a null `::#hd`, or `Vector#dirty` still set to true.) 
> 
> The JMM makes stronger guarantees for final fields [3][4], this 
> potential problem is specific to non-final fields, even ones that are 
> assigned in the constructor. 
> 
> Given that the canonical example for the need for the JMM's special 
> treatment of final fields is avoiding data races in j.l.String (its 
> somewhat lonely poster child for immutability); what is our position 
> on not being protected by the same guarantees for List and Vector? 
> 
> -jason 
> 
> [1] 
> http://scala-programming-language.1934581.n4.nabble.com/Why-use-List-td2217742.html 
> [2] https://groups.google.com/d/msg/scala-user/ORxWFIzRb2c/ZzsQ9fsmq40J 
> [3] http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html 
> <http://www.cs.umd.edu/%7Epugh/java/memoryModel/jsr-133-faq.html> 
> [4] 17.5 final Field Semantics 
> 

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-7838?orig=1
Reporter: @retronym
Affected Versions: 2.10.0

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-7838?orig=1
Reporter: @retronym
Affected Versions: 2.10.0

[scabug]

@retronym said:
Rex, would you care to look into this one?

[scabug]

@retronym said:
Rex, would you care to look into this one?

[scabug]

@Ichoran said:
I can, but I can't promise I'll come up with the best solution. The email thread seems pretty active; I'm happy to test supposed "best" solutions and pick the one that actually works the best.

[scabug]

@Ichoran said:
I can, but I can't promise I'll come up with the best solution. The email thread seems pretty active; I'm happy to test supposed "best" solutions and pick the one that actually works the best.

[scabug]

@retronym said:
Rex: I'll mark this for 2.12. If the ML comes up with some stellar ideas we could consider 2.11, but I suppose we've lived with this for a long time, so this might be lower priority than other performance related work.

[scabug]

@retronym said:
Rex: I'll mark this for 2.12. If the ML comes up with some stellar ideas we could consider 2.11, but I suppose we've lived with this for a long time, so this might be lower priority than other performance related work.

[scabug]

@Ichoran said:
Partial fix for List in new higher-performance map etc. methods in scala/scala#3498 (untested, though)

[scabug]

@Ichoran said:
Partial fix for List in new higher-performance map etc. methods in scala/scala#3498 (untested, though)

[scabug]

@retronym said:
Merging in the report of #8996

import scala.collection.immutable.$colon$colon;
import scala.collection.immutable.List;
import scala.collection.immutable.Nil$;
import scala.collection.immutable.WrappedString;
 
public class Lists {
  public static void main(String[] args) {
    Nil$ nil = Nil$.MODULE$;
    List<Object> list = new WrappedString("123456789").toList();
    System.out.println(list);
    $colon$colon $colon$colon = ($colon$colon) list;
    $colon$colon.tl_$eq(nil);
    System.out.println(list);
  }
}
Output:
List(1, 2, 3, 4, 5, 6, 7, 8, 9)
List(1)

[scabug]

@retronym said:
Merging in the report of #8996

import scala.collection.immutable.$colon$colon;
import scala.collection.immutable.List;
import scala.collection.immutable.Nil$;
import scala.collection.immutable.WrappedString;
 
public class Lists {
  public static void main(String[] args) {
    Nil$ nil = Nil$.MODULE$;
    List<Object> list = new WrappedString("123456789").toList();
    System.out.println(list);
    $colon$colon $colon$colon = ($colon$colon) list;
    $colon$colon.tl_$eq(nil);
    System.out.println(list);
  }
}
Output:
List(1, 2, 3, 4, 5, 6, 7, 8, 9)
List(1)

[scabug]

@adriaanm said:
How about we give this @volatile tl proposal a shot? Could we do some JMH benchmarks?

[scabug]

@adriaanm said:
How about we give this @volatile tl proposal a shot? Could we do some JMH benchmarks?

[scabug]

@szeiger said:
Blocked on #8873

[scabug]

@szeiger said:
Blocked on #8873

[scabug]

@SethTisue said (edited on Aug 12, 2016 2:18:52 AM UTC):
scala/scala#5323 documents the status quo

scala/scala#5316 was Stefan's attempt at a real fix, but was not merged. possibly to be revisited

[scabug]

@SethTisue said (edited on Aug 12, 2016 2:18:52 AM UTC):
scala/scala#5323 documents the status quo

scala/scala#5316 was Stefan's attempt at a real fix, but was not merged. possibly to be revisited

[scabug]

@szeiger said:
From a comment on the PR:

You may want to mention JEP 193 and that the cheapest safe
way to pass a list to another thread is by the pair java.lang.invoke.VarHandle.setRelease
/ VarHandle.getAcquire (available in Unsafe on JDK8).
With standardization of these operations in JDK9 (Jep 193) programmers should have plenty of tools for safe concurrency.

[scabug]

@szeiger said:
From a comment on the PR:

You may want to mention JEP 193 and that the cheapest safe
way to pass a list to another thread is by the pair java.lang.invoke.VarHandle.setRelease
/ VarHandle.getAcquire (available in Unsafe on JDK8).
With standardization of these operations in JDK9 (Jep 193) programmers should have plenty of tools for safe concurrency.

[scabug]

@retronym said:
Here's a good overview of safe initialization: https://shipilev.net/blog/2014/safe-public-construction/

", we emit a trailing barrier ... A final field was written. Notice we do not care about what field was actually written, we unconditionally emit the barrier before exiting the (initializer) method"

This is a HotSpot implementation detail that makes regularly constructed lists (ie, not with tail mutation) safe to share in that VM (the write the the final field head emits the barrier). But we shouldn't rely on such details, so the documentation that "safe publication is up to the client of List" is suitable advice.

Also:

" Fastdebug build is needed to gain access to -XX:+StressLCM -XX:+StressGCM instruction scheduling fuzzers in Hotspot."

These flags have since been made available in release builds of Java 9. They are useful to avoid relying on implementation details of the compliler + processor:

"x86 is Total Store Order hardware, meaning the stores are visible for all processors in some total order. That is, if compiler actually presented the program stores in the same order to hardware, we may be reasonably sure the initializing stores of the instance fields would be visible before seeing the reference to the object itself. Even if your hardware is total-store-ordered, you can not be sure the compiler would not reorder within the allowed memory model spec. If you turn off -XX:+StressGCM -XX:+StressLCM in this experiment, all cases would appear correct since the compiler did not reorder much."

[scabug]

@retronym said:
Here's a good overview of safe initialization: https://shipilev.net/blog/2014/safe-public-construction/

", we emit a trailing barrier ... A final field was written. Notice we do not care about what field was actually written, we unconditionally emit the barrier before exiting the (initializer) method"

This is a HotSpot implementation detail that makes regularly constructed lists (ie, not with tail mutation) safe to share in that VM (the write the the final field head emits the barrier). But we shouldn't rely on such details, so the documentation that "safe publication is up to the client of List" is suitable advice.

Also:

" Fastdebug build is needed to gain access to -XX:+StressLCM -XX:+StressGCM instruction scheduling fuzzers in Hotspot."

These flags have since been made available in release builds of Java 9. They are useful to avoid relying on implementation details of the compliler + processor:

"x86 is Total Store Order hardware, meaning the stores are visible for all processors in some total order. That is, if compiler actually presented the program stores in the same order to hardware, we may be reasonably sure the initializing stores of the instance fields would be visible before seeing the reference to the object itself. Even if your hardware is total-store-ordered, you can not be sure the compiler would not reorder within the allowed memory model spec. If you turn off -XX:+StressGCM -XX:+StressLCM in this experiment, all cases would appear correct since the compiler did not reorder much."

[scabug]

@Blaisorblade said:
Would a PR documenting this be accepted in the ScalaDocs for List be accepted?

[scabug]

@Blaisorblade said:
Would a PR documenting this be accepted in the ScalaDocs for List be accepted?

[scabug]

@Ichoran said:
@Blaisorblade - Seems like a good idea to me, especially if it also covers Vector and any other affected immutable collections.

[scabug]

@Ichoran said:
@Blaisorblade - Seems like a good idea to me, especially if it also covers Vector and any other affected immutable collections.

[scabug]

@Blaisorblade said:
Whoops — the documentation I had in mind is already in scala/scala#5323 for 2.12, and visible at http://www.scala-lang.org/api/current/scala/collection/immutable/List.html. Not sure why I missed that.

[scabug]

@Blaisorblade said:
Whoops — the documentation I had in mind is already in scala/scala#5323 for 2.12, and visible at http://www.scala-lang.org/api/current/scala/collection/immutable/List.html. Not sure why I missed that.

[lrytz]

WIP PR scala/scala#6425, see also scala/collection-strawman#50

[lrytz]

WIP PR scala/scala#6425, see also scala/collection-strawman#50

[xuwei-k]

Should we remove or change Iterable comment ?

[xuwei-k]

Should we remove or change Iterable comment ?

[lrytz]

Yes!

[lrytz]

Yes!