multithreading - 必须同步访问scala.collection.immutable.List和Vector吗？

Question

我正在经历Learning Concurrent Programming in Scala，并遇到以下情况:

In current versions of Scala, however, certain collections that are deemed immutable, such as List and Vector, cannot be shared without synchronization. Although their external API does not allow you to modify them, they contain non-final fields.

Tip: Even if an object seems immutable, always use proper synchronization to share any object between the threads.

摘自Aleksandar Prokopec的《在Scala中学习并发程序设计》，第2章结尾(第58页)，Packt出版社，2014年11月。

可以吗？

我的工作假设一直是，在Scala库数据结构中被描述为不可变的任何内部可变性(实现延迟，缓存等)都是幂等的，因此在不必要的比赛中可能发生的最坏情况就是不必要的重复工作。这位作者似乎暗示，同时访问不可变结构可能会损害正确性。真的吗？我们真的需要同步对列表的访问吗？

我过渡到不可变样式的大部分动机是希望避免同步及其带来的潜在争用开销。如果得知无法避免Scala的核心“不可变”数据结构实现同步，那将是一件不愉快的事情。这位作家是否只是过度保守？

Scala的 documentation of collections包括以下内容:

A collection in package scala.collection.immutable is guaranteed to be immutable for everyone. Such a collection will never change after it is created. Therefore, you can rely on the fact that accessing the same collection value repeatedly at different points in time will always yield a collection with the same elements.

但这并不是说它们对于多个线程的并发访问是安全的。有人知道他们是(或不是)权威的说法吗？

Answer 1

这取决于您在何处共享它们:

在scala库中共享它们并不安全

与Java代码共享它们并不安全，反射

简而言之，与仅具有最终字段的对象相比，这些集合受到的保护较少。不管它们在JVM级别上是相同的(没有像 ldc这样的优化)-两者都可能是具有某些可变地址的字段，因此您可以使用 putfield bytecode命令更改它们。无论如何，与Java的 var，scala的 final 和 final val相比， val仍然受编译器的保护较少。

但是，在大多数情况下仍可以使用它们，因为它们的行为在逻辑上是不可变的-所有可变操作都已封装(适用于Scala代码)。让我们看看 Vector 。它需要可变字段来实现追加算法:

private var dirty = false

//from VectorPointer
private[immutable] var depth: Int = _
private[immutable] var display0: Array[AnyRef] = _
private[immutable] var display1: Array[AnyRef] = _
private[immutable] var display2: Array[AnyRef] = _
private[immutable] var display3: Array[AnyRef] = _
private[immutable] var display4: Array[AnyRef] = _
private[immutable] var display5: Array[AnyRef] = _

实现方式如下:

val s = new Vector(startIndex, endIndex + 1, blockIndex)
s.initFrom(this) //uses displayN and depth
s.gotoPos(startIndex, startIndex ^ focus) //uses displayN
s.gotoPosWritable //uses dirty
...
s.dirty = dirty

而且 s仅在方法返回后才出现。因此，甚至不需要担心 happens-before保证-所有可变操作都在同一线程(您在其中调用 :+， +:或 updated的线程)中执行，这只是一种初始化。唯一的问题是 private[somePackage] is accessible directly from Java code和来自scala库本身，因此，如果将其传递给某些Java方法，则可以对其进行修改。

我不认为您应该担心 cons运算符的线程安全性。它还具有可变字段:

final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false
}

但是它们仅在内部库方法(在一个线程内)使用，而没有任何显式的共享或线程创建，并且它们总是返回一个新的集合，让我们以 take为例:

override def take(n: Int): List[A] = if (isEmpty || n <= 0) Nil else {

    val h = new ::(head, Nil)
    var t = h
    var rest = tail
    var i = 1
    while ({if (rest.isEmpty) return this; i < n}) {
      i += 1
      val nx = new ::(rest.head, Nil)
      t.tl = nx //here is mutation of t's filed 
      t = nx
      rest = rest.tail
    }
    h
}

因此，此处 t.tl = nx与 t = nx在线程安全性方面没有太大区别。它们都仅从单个堆栈( take的堆栈)中引用。总的来说，如果我在 someActor ! t循环中添加 someField = t(或任何其他异步操作)， someFunctionWithExternalSideEffect(t)或 while，则可能会违反此契约(Contract)。

关于与JSR-133的关系的一些补充:

1) new ::(head, Nil)在堆中创建新对象，并将其地址(假设为0x100500)放入堆栈中( val h =)

2)只要此地址在堆栈中，它仅对当前线程是已知的

3)只有在共享此地址并将其放入某个字段后，才能涉及其他线程；如果是 take，则必须在调用 areturn( return h)之前刷新所有缓存(以恢复堆栈和寄存器)，因此返回的对象将是一致的。

因此，只要0x100500仅是堆栈的一部分(不是堆，而不是其他堆栈)，则对0x100500的对象进行的所有操作都不在JSR-133的范围内。但是，0x100500的对象的某些字段可能指向某些共享的对象(可能在JSR-133范围内)，但此处不是这种情况(因为这些对象在外部是不可变的)。

我认为(希望)作者对库开发人员而言意味着逻辑同步保证-如果您正在开发scala库，则仍然需要注意这些事项，因为这些 var是 private[scala]， private[immutable]，因此可以向其中编写一些代码从不同的线程对其进行变异。从scala库开发人员的角度来看，它通常意味着单个实例上的所有突变都应应用于单个线程中，并且仅应用于用户当前不可见的集合。或者，简单地说-请勿以任何方式为外部用户打开可变字段。

P.S. Scala在同步方面有几个意外的问题，这导致某些 parts of the library出人意料地不是线程安全的，因此我不怀疑是否有问题(这是一个错误)，但是在99％的情况下，有99％方法不可变集合是线程安全的。在最坏的情况下，您可能会因为使用某些损坏的方法而受阻，或者只是(对于某些情况而言，可能不只是“正当”)克隆每个线程的集合。

无论如何，不​​变性仍然是线程安全的好方法。

P.S.2可能破坏不可变集合的线程安全性的特殊情况是使用反射来访问其非最终字段。

正如@Steve Waldman和@ axel22(作者)在评论中指出的，这是关于另一种异国情调但确实令人恐惧的方式的一些补充。如果您将不可变集合作为线程之间共享的某些对象的成员共享，并且&&如果集合的构造函数在物理上(通过JIT)内联(默认情况下未在逻辑上内联)，并且&&如果您的JIT实现允许使用普通代码重新排列内联代码-进行同步(通常足以拥有 @volatile)。但是，恕我直言，我不认为最后的条件是正确的行为-但就目前而言，既不能证明也不能证明这一点。