List, Vector, and the JMM

[Jason Zaugg]

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

[4] 17.5 final Field Semantics

[Aleksandar Prokopec]

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

> <http://www.cs.umd.edu/%7Epugh/java/memoryModel/jsr-133-faq.html>

> [4] 17.5 final Field Semantics
>

> --
> You received this message because you are subscribed to the Google
> Groups "scala-internals" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to scala-interna...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[Jason Zaugg]

On Thu, Sep 12, 2013 at 6:30 PM, Aleksandar Prokopec <aleksanda...@gmail.com> wrote:

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.

Thanks for the background. I've created a ticket to track this. [1]

-jason

[1] https://issues.scala-lang.org/browse/SI-7838 

[Roland Kuhn]

Hi Alex,

making these fields volatile may in practice work on common hardware (i.e. x86), but it is not guaranteed to work in the JMM: if the List is published by a non-volatile write then that write could potentially be visible to other threads before the volatile writes to hd and tl. Since volatile writes only synchronize-with subsequent volatile reads, there needs to be some other means by which it is ensured that the read does not occur too early.

This discussion also occurred on concurrency-interest before, and the outcome always was that unsafe publication invalidates all guarantees the JMM may otherwise provide; in particular there is no way to formulate a memory barrier at the end of a constructor to make construction of non-final fields safe, apart from using synchronized for all accesses (yuck!). I remember discussing exactly this wrt. PartialFunction.orElse and the fallback field: the solution was to remove the var.

Ah, idea: if we make sure that hd is written before tl and mark tl @volatile, then we can check that tl!=null and spin for a while if violated … (yeah, not very nice).

Regards,

Roland

Dr. Roland Kuhn
Akka Tech Lead
Typesafe – Reactive apps on the JVM.
twitter: @rolandkuhn

[Nils Kilden-Pedersen]

On Thu, Sep 12, 2013 at 11:30 AM, Aleksandar Prokopec <aleksanda...@gmail.com> wrote:

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 -

Cheap, not free, if this can be trusted:

http://brooker.co.za/blog/2012/09/10/volatile.html

 

then again, would be useful to try to compile the distribution with and without the @volatile in Lists.

Cheers,
Alex

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

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-internals+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-internals+unsubscribe@googlegroups.com.

[Paul Phillips]

On Thu, Sep 12, 2013 at 9:21 AM, Jason Zaugg <jza...@gmail.com> wrote:

The head and tail of our :: are vars, which allows ListBuffer to directly build a list in start-to-finish order

I don't see ListBuffer ever assigning to hd. The only use to which that is put (that I can find) is deserialization. ListBuffer only writes to tl.

[Paul Phillips]

Speaking of "immutable" Lists, no data races necessary.

scala> val lb = scala.collection.mutable.ListBuffer[Int](5, 10, 15)

lb: scala.collection.mutable.ListBuffer[Int] = ListBuffer(5, 10, 15)

scala> val xs = lb.readOnly

xs: List[Int] = List(5, 10, 15)

scala> lb prependToList List(20, 25)

res0: List[Int] = List(5, 10, 15, 20, 25)

scala> xs

res1: List[Int] = List(5, 10, 15, 20, 25)

scala> 

[√iktor Ҡlang]

*jaw dropped*

--

You received this message because you are subscribed to the Google Groups "scala-internals" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--

Viktor Klang
Director of Engineering

Typesafe

Twitter: @viktorklang

[Nils Kilden-Pedersen]

Not good, not good at all.

At least this works as expected:

scala> val lb = scala.collection.mutable.ListBuffer[Int](5, 10, 15)

lb: scala.collection.mutable.ListBuffer[Int] = ListBuffer(5, 10, 15)

scala> val xs = lb.toList

xs: List[Int] = List(5, 10, 15)

scala> lb prependToList List(20, 25)

res0: List[Int] = List(5, 10, 15, 20, 25)

scala> xs

res1: List[Int] = List(5, 10, 15)

--

[Pavel Pavlov]

This was discussed about a year ago:
https://groups.google.com/d/msg/scala-internals/g_-gIWgB8Os/LbvSVQduzmcJ

[√iktor Ҡlang]

I'm not seeing where it says that it returns something that has a List type in that email.

[Aleksandar Prokopec]

Roland, you're absolutely right - my reply was too hasty.

However, maybe there's something else we could do.

If we introduce a 3rd (non-visible) List subclass (in addition to Nil and ::), then having the (e.g.) ListBuffer return an immutable proxy similar to `::` (in the sense that it has a tail and a head plus an extractor that can match it as if it were a ::) through which we can ensure.

I'm thinking about something like this:

class ColonColonProxy[T](private val hdProxy: T, private val tlProxy: List[T]) {

  @volatile var check: Boolean = false

  def head = {

    check

    hdProxy

  }

  

  def tail = {

    check

    tlProxy

  }

}

And then the ListBuffer that would right now return `lst`, would instead return:

def result = {

  val ccp = new ColonColonProxy(lst.head, lst.tail)

  ccp.check = true

  ccp

}

Seems to me something like this (in addition to having the tail volatile, modulo the possible performance penalties related to that, as others suggest) would ensure that the volatile writes to lst.tail are succeeded by a volatile read on ccp.check.

WDYT?

Cheers,

Alex

[Pavel Pavlov]

Hi all,

I thought about the issue of non-threadsafe ListBuffer some time ago and found one possible (though somewhat hackish) solution.

The core problem is the absence of StoreStore barrier[1] between two actions:
a) constructing the object - in our case is mutation of cons cell's `tl` field.
b) publishing the object - in our case it is returning the constructed List from the `toList` method.
If the reference to newborn List returned by `toList` will escape to another thread, then this thread may see stale values of the cons-cellt's fields.

The is no public API to force StoreStore barrier for now and will unlikely be one in future[2].

However, you can issue StoreStore with volatile write:

package scala.runtime {
  object JMMBarriers {
    @volatile private int hack = 0
    def storeStore() { hack = 42 }
  }
}

This way you can remove all volatile accesses from (possibly frequent) list access path and add extra weight only once for each created list:

  override def toList: List[A] = {
    if (!exported && !start.isEmpty) JMMBarriers.storeStore()
    exported = !start.isEmpty
    start
  }

P.S. Moreover, the same trick can be used to implement lazy vals (and more generally, double checked locking) more efficiently - without any volatile reads on all but first accesses.

P.P.S. In the case of ListBuffer we can avoid all barriers if cons cell will have at least one final field (and I believe that `hd` field must be converted to final in any case) as HotSpot will issue StoreStore barrier at the very end of $colon$colon's constructor. But I think such dependency is very fragile to rely on.

[1] http://gee.cs.oswego.edu/dl/jmm/cookbook.html
[2] There is JEP-171 (http://openjdk.java.net/jeps/171), but it's
 - not yet there
 - not a public API (it's sun.misc.Unsafe)
 - there's virtually no chance something like this will ever be in the public API [3]
[3] personal communication with JMM guys from Oracle

[Pavel Pavlov]

Please read the whole disscussion starting from this point:
https://groups.google.com/d/msg/scala-internals/g_-gIWgB8Os/rCTxrd_npk0J

ListBuffer.readOnly is the implementation of abstract method of BufferLike.
Even if BufferLike.readOnly's return type is collection.Seq, it's stiil wrong to return not-yet-immutable List here.

[martin odersky]

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

[martin odersky]

On Thu, Sep 12, 2013 at 6:21 PM, Jason Zaugg <jza...@gmail.com> 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?

This problem has been known for a while. It does not seem to come up in practice that much. I guess our position is that safe publishing has to be ensured by some other means. If your threads are Akka actors, for instance, safe publishing is assured by a message handshake. 

I am not sure whether giving better guarantees here is worth the run-time cost. A lot of careful experiments would be needed to get a good handle on what the typical and worst-case run-time cost would be, so that we can reach a more informed decision. 

Cheers

 - Martin

 

-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

[4] 17.5 final Field Semantics

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Paul Phillips]

On Thu, Sep 12, 2013 at 1:13 PM, martin odersky <martin....@epfl.ch> wrote:

This problem has been known for a while. It does not seem to come up in practice that much. I guess our position is that safe publishing has to be ensured by some other means. If your threads are Akka actors, for instance, safe publishing is assured by a message handshake. 

I am not sure whether giving better guarantees here is worth the run-time cost. A lot of careful experiments would be needed to get a good handle on what the typical and worst-case run-time cost would be, so that we can reach a more informed decision. 

It's telling that nobody has ever demonstrated it doing the wrong thing. Whatever the reason for that, it supports the case that you should think hard before paying any new performance tax. (I have tried and failed before, but I didn't try that hard and this is not my expertise.)

[Paul Phillips]

On Thu, Sep 12, 2013 at 1:23 PM, Paul Phillips <pa...@improving.org> wrote:

nobody has ever demonstrated

And of  course a universal qualifier like this actually has a bunch of qualifiers. I'd be glad to see such a demonstration.

[Jason Zaugg]

I couldn't break ::, but I could break something awfully similar:

https://gist.github.com/retronym/6543654

-jason

[Paul Phillips]

On Thu, Sep 12, 2013 at 2:00 PM, Jason Zaugg <jza...@gmail.com> wrote:

I couldn't break ::, but I could break something awfully similar:

Do you have any theory why not :: ?

[Jason Zaugg]

When I changed my test to:

- class Cons(var head: String)

+ class Cons(var head: String, var tail: String)

.. I didn't observe an NPE. Same with additional parameters.

This also NPEs:

class Cons(var head: String) {

  var tail: String = null

}

...

    val c = new Cons(toString)

    c.v1 = toString

    Global.global = c

...

assert(get.tail ne null)

Maybe the inlinability of of Cons#<init> affects matter. (Are constructors inlined by HotSpot?)

Other than knowing what variations to try to exploit the data race, though, the particular reason for the difference shouldn't inform our design. We have to assume that List and Vector are unsafe for clients that publish them unsafely. (ie, ones who fail to mark `global` as @volatile.)

-jason

[√iktor Ҡlang]

Unsafe publication is unsafe...
However, there needs to be a decision on what is to be expected of immutable collections.

--

[Paul Phillips]

On Thu, Sep 12, 2013 at 2:31 PM, Jason Zaugg <jza...@gmail.com> wrote:

Other than knowing what variations to try to exploit the data race, though, the particular reason for the difference shouldn't inform our design.

Yes, I don't mean to imply otherwise - but uncouth though it may be, even correctness is a tradeoff which has to be assessed against its costs. I have no horse in the race, but if I did, it would be my position that any change which is sure to negatively impact performance should be accompanied by at least an existence proof demonstrating its purpose. If something can happen in theory, then it should be possible to make it happen in practice. If it can't be made to happen in practice, then maybe the theory is incomplete.

[Jason Zaugg]

I'd defer to the experience of others to figure out whether we fix this or document our way out of it. But if I tend to think that if these guarantees are important for String, we need to justify ourselves well to exclude List and Vector.

Pavel's `JMMBarriers` trick dries up the NPEs in my test, but I believe it is doing so by relying on implementation details, rather than the model. As i understand, writing to an unrelated volatile field doesn't guarantee anything other consistent access to that very field, not to unrelated non-volatile fields.

-jason

[Roland Kuhn]

13 sep 2013 kl. 08:23 skrev Jason Zaugg:

On Thu, Sep 12, 2013 at 11:47 PM, Paul Phillips <pa...@improving.org> wrote:

On Thu, Sep 12, 2013 at 2:31 PM, Jason Zaugg <jza...@gmail.com> wrote:

Other than knowing what variations to try to exploit the data race, though, the particular reason for the difference shouldn't inform our design.

Yes, I don't mean to imply otherwise - but uncouth though it may be, even correctness is a tradeoff which has to be assessed against its costs. I have no horse in the race, but if I did, it would be my position that any change which is sure to negatively impact performance should be accompanied by at least an existence proof demonstrating its purpose. If something can happen in theory, then it should be possible to make it happen in practice. If it can't be made to happen in practice, then maybe the theory is incomplete.

I'd defer to the experience of others to figure out whether we fix this or document our way out of it. But if I tend to think that if these guarantees are important for String, we need to justify ourselves well to exclude List and Vector.

I agree with this sentiment. See this thread for an example of where the “String is safe” assumption is broken by Thread.setName() (tl;dr is uses a Char[] instead of String internally because of native code interop).

Pavel's `JMMBarriers` trick dries up the NPEs in my test, but I believe it is doing so by relying on implementation details, rather than the model. As i understand, writing to an unrelated volatile field doesn't guarantee anything other consistent access to that very field, not to unrelated non-volatile fields.

The JMMBarriers hack works on architectures with TSO and without fine-grained memory barriers: on x86 a write barrier will flush the whole store buffer, thus fixing the problem for all previous writes. There are architectures with weaker memory models, though, and I would not bet my business on this trick to work everywhere a JVM is available. (But as mentioned, betting a business on unsafe publication is not wise in general.)

Regards,

Roland

-jason

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Paolo G. Giarrusso]

Well, maybe it breaks in practice on some strange but perfectly conforming JVM you don't have access to, or which wasn't yet written.

But since Martin wrote:

> I guess our position is that safe publishing has to be ensured by some other means

if we have no better solution, we could keep the status quo and document that "safe publishing has to be ensured by some other means". Something like:

In scala package

> Instances of types which are internally immutable can be published safely to other threads.

For List and Vector:

> This type is not internally immutable, so it cannot be published safely to other threads without extra synchronization.
(Probably this should be a ScalaDoc "macro").

[Johannes Rudolph]

Here's a test that fails with ListBuffer in Scala 2.10.2 (tl mutation). With sleep(1) it fails only a few times in 10 seconds on my 4 core / 8 HTs computer. With sleep(0) it fails with much higher frequency obviously.

https://gist.github.com/jrudolph/6552186 

--
Johannes

-----------------------------------------------
Johannes Rudolph
http://virtual-void.net

[Paul Phillips]

Theory and practice, best friends forever!

--

[Paolo G. Giarrusso]

On Friday, September 13, 2013 11:54:57 AM UTC+2, rkuhn wrote:

13 sep 2013 kl. 08:23 skrev Jason Zaugg:

On Thu, Sep 12, 2013 at 11:47 PM, Paul Phillips <pa...@improving.org> wrote:

On Thu, Sep 12, 2013 at 2:31 PM, Jason Zaugg <jza...@gmail.com> wrote:

Other than knowing what variations to try to exploit the data race, though, the particular reason for the difference shouldn't inform our design.

Yes, I don't mean to imply otherwise - but uncouth though it may be, even correctness is a tradeoff which has to be assessed against its costs. I have no horse in the race, but if I did, it would be my position that any change which is sure to negatively impact performance should be accompanied by at least an existence proof demonstrating its purpose. If something can happen in theory, then it should be possible to make it happen in practice. If it can't be made to happen in practice, then maybe the theory is incomplete.

I'd defer to the experience of others to figure out whether we fix this or document our way out of it. But if I tend to think that if these guarantees are important for String, we need to justify ourselves well to exclude List and Vector.

I agree with this sentiment. See this thread for an example of where the “String is safe” assumption is broken by Thread.setName() (tl;dr is uses a Char[] instead of String internally because of native code interop).

Pavel's `JMMBarriers` trick dries up the NPEs in my test, but I believe it is doing so by relying on implementation details, rather than the model.

It can be fixed to rely on the model, at the cost of adding a volatile read to the other threads.

But the explanation is surely unsound even on x86 - StoreStore barriers are no-op on x86, according to Doug Lea's cookbook [2].

As i understand, writing to an unrelated volatile field doesn't guarantee anything other consistent access to that very field, not to unrelated non-volatile fields. 

*After* you read that very volatile field, you can safely read unrelated non-volatile fields. [1]

However, simply *writing* to a volatile field in the publisher thread is not enough. You need to also read the volatile field on the other thread. The result is then JMM-safe. Thanks to this, when you read a volatile reference you can actually look at its contents safely (different memory cells), or you can use a boolean flag to tell another thread that something was initialized. IOW, volatile *must* affect the rest of memory or it's useless.

The placement of these barriers (and the overhead) would be like in Aleksandar email. However, you don't need a separate volatile field per instance.

class ColonColonProxy[T](private val hdProxy: T, private val tlProxy: List[T]) {

  //You must wrap any method directly looking at the fields, but you don't need to wrap methods using them.

  def head = {

    JMMBarriers.readBarrier()

    hdProxy

  }

  

  def tail = {

    JMMBarriers.readBarrier()

    tlProxy

  }

}

def result = {

  val ccp = new ColonColonProxy(lst.head, lst.tail)

  JMMBarriers.writeBarrier() //This must come *after* the writes to synchronize, unlike in Pavel's example.

  ccp

}

Here's JMMBarriers (also on https://gist.github.com/Blaisorblade/6551895):

object JMMBarriers {

  @volatile private var volatile: Int = 0

  /** Enforce a write barrier.

    *

    * Writes before this will not be reordered after this barrier, and will be

    * visible from any other thread which performs a read barrier.

    */

  def writeBarrier() { volatile = 1 }

  /** Enforce a read barrier.

    *

    * Reads after this will not be reordered before this barrier, and will see

    * the effects of any writes from a thread which performed a write barrier

    * before this one.

    */

  def readBarrier() { volatile }

}

> [Volatile reads are cheap, not free]:

> http://brooker.co.za/blog/2012/09/10/volatile.html

Volatile reads must be more expensive (sometimes), because they can't be served from the cache without safety checks. I think the behavior observed in that article could be explained by the behavior of MESI cache coherence protocols: a volatile store of x informs other processors that their copy of x (in their caches) is out-of-date, so a volatile read will 

[1] The picture here, and the article, should be an unambiguous explanation: http://jeremymanson.blogspot.de/2008/11/what-volatile-means-in-java.html

[2] http://gee.cs.oswego.edu/dl/jmm/cookbook.html

[Roland Kuhn]

Hi Paolo,

your approach introduces a synchronization edge between the volatile read and all preceding volatile writes. The problem is that in this code

  var xs: List[String] = Nil

Thread1:

  xs ::= "hello"

Thread2:

  while (xs == Nil) {}

  println(xs)

there is no synchronization action between the two threads which ensures the proper order of the accesses to your volatile field. The compiler or CPU might schedule the write to xs ahead of its time since the value is known before writing to hd and tl, meaning that the other thread might see that write before the volatile write has occurred. The volatile read then does nothing to ensure synchronization with the write which has yet to be done.

According to the JMM this program is still not properly synchronized.

Regards,

Roland

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Paolo G. Giarrusso]

On Friday, September 13, 2013 6:39:13 PM UTC+2, rkuhn wrote:

Hi Paolo,

your approach introduces a synchronization edge between the volatile read and all preceding volatile writes. The problem is that in this code

  var xs: List[String] = Nil

Thread1:

  xs ::= "hello"

Thread2:

  while (xs == Nil) {}

  println(xs)

there is no synchronization action between the two threads which ensures the proper order of the accesses to your volatile field. The compiler or CPU might schedule the write to xs ahead of its time since the value is known before writing to hd and tl, meaning that the other thread might see that write before the volatile write has occurred. The volatile read then does nothing to ensure synchronization with the write which has yet to be done.

According to the JMM this program is still not properly synchronized.

That's true, I hadn't considered the above example; the above program would "work" if :: was actually immutable (by final field semantics). Does any other proposal fix it? I think not even Aleksander's does.
Actually, there's a race on xs anyway, so Thread 2 might never exit the loop - but at least, with immutable lists Thread 2 would always see some valid list (either before or after Thread1's action).

Another fix (I suspect) would be to make the :: operator create a ColonColonProxy instance.
Of course, this is unsafe because this requires blacklisting all possible races, otherwise there might be other examples; one could consider making :: immutable and having ListBuffer use a different class (with actually mutable fields) and the code I proposed (or Aleksander's code, if it were safer), as long as those nodes produced by ListBuffer are never modified after exporting.

But one would also need to abstract over the two types of cons nodes by creating suitable abstractors. I suspect this could all be done, but maintaining it feels dangerous.

So overall I guess I'm for documenting the limitation.

[Simon Ochsenreither]

As far as I understand, stuff works when we declare the members final?

What about declaring them final then and using reflection to modify them where necessary?

[Paolo G. Giarrusso]

On Thursday, September 19, 2013 10:49:46 AM UTC+2, Simon Ochsenreither wrote:

As far as I understand, stuff works when we declare the members final?

Under some reasonable conditions, yes. One FAQ entry on this is:

http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#finalRight

What about declaring them final then and using reflection to modify them where necessary?

[I wonder about performance. Every change to a ListBuffer would use reflection. Could that be efficient enough?]

I don't think that works in general, but only if the object owning the field was not published to other threads. Note that it's the same conditions as before, but now they become non-obvious.

However, I needed to look up the JLS itself, and I'm not used to that language, so I might be misinterpreting. *

Moreover, that might still allow some scheme fixing the problem; I've not really had time to think about it. In the scenarios we've considered, we assumed the ListBuffer is not accessed concurrently, only the resulting List is after construction; this might work if construction creates a new object. Still, what if ListBuffer was shared under some lock? Does that count as "not published"?

* Quoting the JLS:

In some cases, such as deserialization, the system will need to change the final fields of an object after construction. final fields can be changed via reflection and other implementation-dependent means. The only pattern in which this has reasonable semantics is one in which an object is constructed and then the final fields of the object are updated. The object should not be made visible to other threads, nor should the final fields be read, until all updates to the final fields of the object are complete. Freezes of a final field occur both at the end of the constructor in which the final field is set, and immediately after each modification of a final field via reflection or other special mechanism.

http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.5.3

Note that "freezes" only work if the object on which they act was not published, as far as I can see.
However, I don't understand yet the corner cases in the rest of the section, I didn't really look into it.

[Roland Kuhn]

The reason is that values of final fields can potentially be inlined into compiled code, and once that happens the reflective modification does not have an effect on those code paths anymore.

Regards,

Roland

However, I don't understand yet the corner cases in the rest of the section, I didn't really look into it.

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Rüdiger Klaehn]

What about making head and tail final and using something a temporary ArrayBuffer inside ListBuffer, and then create the list in the call to ListBuilder.result()?

All operations that work with List in the traditional functional way (building lists by prepending new nodes) would not be affected in any way. If anything, they would become faster when head and tail is final. So the performance reduction would be confined to the ListBuilder. And I think it would not be that large. In the worst case some operations of List would have to be changed to not use ListBuffer, but that would be a good idea anyway.

I think that this would be the cleanest way to deal with this.

[Paolo G. Giarrusso]

On Thursday, September 19, 2013 11:41:51 AM UTC+2, rklaehn wrote:

What about making head and tail final and using something a temporary ArrayBuffer inside ListBuffer, and then create the list in the call to ListBuilder.result()?

All operations that work with List in the traditional functional way (building lists by prepending new nodes) would not be affected in any way. If anything, they would become faster when head and tail is final. So the performance reduction would be confined to the ListBuilder. And I think it would not be that large. In the worst case some operations of List would have to be changed to not use ListBuffer, but that would be a good idea anyway.

Note that List.map (and I guess flatMap) does *not* use the traditional approach. That is, every loop in a List-to-List for comprehension relies on efficient append (though they could be converted to using reverse, efficient prepend, and reverse again).

 

I think that this would be the cleanest way to deal with this. 

The idea makes sense, but ListBuffer supports insertion, so one shouldn't use ArrayBuffer. However, one can have separate implementations of ListBuffer (a mutable list) and List (a really immutable list), and create the list in ListBuilder.result(). This solution has the same thread-safety property of what you describe.

Making such code *thread-safe* would be much easier than the options we discussed, as one would expect; so it would be more maintainable than these alternatives.

OTOH, with this code ListBuilder.result would take O(n) (alternatively, adding an element to a builder would take amortized O(1)), and would use additional temporary space.

However, the authors of ListBuffer assumed the performance difference matters - this is even described in Programming in Scala, 22.3!

So we just need somebody to implement and benchmark one of the alternatives, and show that relevant workloads are not affected badly. Scalac uses enough lists that it *might* be part of the workloads (though other people have much more clue than me on this).

[√iktor Ҡlang]

On Thu, Sep 19, 2013 at 3:29 PM, Paolo G. Giarrusso <p.gia...@gmail.com> wrote:

On Thursday, September 19, 2013 11:41:51 AM UTC+2, rklaehn wrote:

What about making head and tail final and using something a temporary ArrayBuffer inside ListBuffer, and then create the list in the call to ListBuilder.result()?

All operations that work with List in the traditional functional way (building lists by prepending new nodes) would not be affected in any way. If anything, they would become faster when head and tail is final. So the performance reduction would be confined to the ListBuilder. And I think it would not be that large. In the worst case some operations of List would have to be changed to not use ListBuffer, but that would be a good idea anyway.

Note that List.map (and I guess flatMap) does *not* use the traditional approach. That is, every loop in a List-to-List for comprehension relies on efficient append (though they could be converted to using reverse, efficient prepend, and reverse again).

 

I think that this would be the cleanest way to deal with this. 

The idea makes sense, but ListBuffer supports insertion, so one shouldn't use ArrayBuffer. However, one can have separate implementations of ListBuffer (a mutable list) and List (a really immutable list), and create the list in ListBuilder.result(). This solution has the same thread-safety property of what you describe.

Making such code *thread-safe* would be much easier than the options we discussed, as one would expect; so it would be more maintainable than these alternatives.

OTOH, with this code ListBuilder.result would take O(n) (alternatively, adding an element to a builder would take amortized O(1)), and would use additional temporary space.

However, the authors of ListBuffer assumed the performance difference matters - this is even described in Programming in Scala, 22.3!

So we just need somebody to implement and benchmark one of the alternatives, and show that relevant workloads are not affected badly. Scalac uses enough lists that it *might* be part of the workloads (though other people have much more clue than me on this).

Yeah, fixing ListBuffer and then making Cons truly immutable sounds like the appropriate way forward.

Cheers,

√

[Johannes Rudolph]

On Thu, Sep 19, 2013 at 3:29 PM, Paolo G. Giarrusso
<p.gia...@gmail.com> wrote:

> On Thursday, September 19, 2013 11:41:51 AM UTC+2, rklaehn wrote:
>>
>> What about making head and tail final and using something a temporary
>> ArrayBuffer inside ListBuffer, and then create the list in the call to
>> ListBuilder.result()?
>>
>> All operations that work with List in the traditional functional way
>> (building lists by prepending new nodes) would not be affected in any way.
>> If anything, they would become faster when head and tail is final.

Also, all the methods from the companion object of the standard
`scala.Seq` (coming from SeqFactory) seem to use ListBuffer
internally. Interesting enough, I didn't manage to break them (like
Seq.fill) in the same way as the manual usage of ListBuffer. Manual
inlining equivalent code will make it break again.

[Rüdiger Klaehn]

On Thu, Sep 19, 2013 at 3:29 PM, Paolo G. Giarrusso <p.gia...@gmail.com> wrote:

On Thursday, September 19, 2013 11:41:51 AM UTC+2, rklaehn wrote:

What about making head and tail final and using something a temporary ArrayBuffer inside ListBuffer, and then create the list in the call to ListBuilder.result()?

All operations that work with List in the traditional functional way (building lists by prepending new nodes) would not be affected in any way. If anything, they would become faster when head and tail is final. So the performance reduction would be confined to the ListBuilder. And I think it would not be that large. In the worst case some operations of List would have to be changed to not use ListBuffer, but that would be a good idea anyway.

Note that List.map (and I guess flatMap) does *not* use the traditional approach. That is, every loop in a List-to-List for comprehension relies on efficient append (though they could be converted to using reverse, efficient prepend, and reverse again).

 

Map and flatMap will create a completely new list. So for a long list you have to allocate many new tiny objects in any case. Having a transient ArrayBuffer or similar will not make things much worse. It might even make things faster. At least that is what my intuition says. We will have to benchmark it. But even if there is a small performance degradation, I think it would be worth it.

 

I think that this would be the cleanest way to deal with this. 

The idea makes sense, but ListBuffer supports insertion, so one shouldn't use ArrayBuffer. However, one can have separate implementations of ListBuffer (a mutable list) and List (a really immutable list), and create the list in ListBuilder.result(). This solution has the same thread-safety property of what you describe.

ListBuffer is currently backed by a single-linked list where you can modify the tails? Then inserting elements will currently be O(N) because you have to find the place to insert, which is O(N). So swapping the internal representation to an array would not make things worse.

And you might gain some performance for all traversal methods when head and tail are final.

Anyway, the only way to find out is to benchmark it.

[martin odersky]

On Thu, Sep 19, 2013 at 3:31 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

On Thu, Sep 19, 2013 at 3:29 PM, Paolo G. Giarrusso <p.gia...@gmail.com> wrote:

On Thursday, September 19, 2013 11:41:51 AM UTC+2, rklaehn wrote:

What about making head and tail final and using something a temporary ArrayBuffer inside ListBuffer, and then create the list in the call to ListBuilder.result()?

All operations that work with List in the traditional functional way (building lists by prepending new nodes) would not be affected in any way. If anything, they would become faster when head and tail is final. So the performance reduction would be confined to the ListBuilder. And I think it would not be that large. In the worst case some operations of List would have to be changed to not use ListBuffer, but that would be a good idea anyway.

Note that List.map (and I guess flatMap) does *not* use the traditional approach. That is, every loop in a List-to-List for comprehension relies on efficient append (though they could be converted to using reverse, efficient prepend, and reverse again).

 

I think that this would be the cleanest way to deal with this. 

The idea makes sense, but ListBuffer supports insertion, so one shouldn't use ArrayBuffer. However, one can have separate implementations of ListBuffer (a mutable list) and List (a really immutable list), and create the list in ListBuilder.result(). This solution has the same thread-safety property of what you describe.

Making such code *thread-safe* would be much easier than the options we discussed, as one would expect; so it would be more maintainable than these alternatives.

OTOH, with this code ListBuilder.result would take O(n) (alternatively, adding an element to a builder would take amortized O(1)), and would use additional temporary space.

However, the authors of ListBuffer assumed the performance difference matters - this is even described in Programming in Scala, 22.3!

So we just need somebody to implement and benchmark one of the alternatives, and show that relevant workloads are not affected badly. Scalac uses enough lists that it *might* be part of the workloads (though other people have much more clue than me on this).

Yeah, fixing ListBuffer and then making Cons truly immutable sounds like the appropriate way forward.

Careful: It would  mean that *every* transformer on list (map, flatMap, filter, the works)  would consume twice the memory and incur the copying overhead. They all use ListBuffer to do their work. This is not peanuts. It would mean we make the sequential case slower to get a guarantee for the parallel case that people so far did not seem to care about.

Cheers

 - Martin

--

[√iktor Ҡlang]

On Thu, Sep 19, 2013 at 5:12 PM, martin odersky <martin....@epfl.ch> wrote:

On Thu, Sep 19, 2013 at 3:31 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

On Thu, Sep 19, 2013 at 3:29 PM, Paolo G. Giarrusso <p.gia...@gmail.com> wrote:

On Thursday, September 19, 2013 11:41:51 AM UTC+2, rklaehn wrote:

What about making head and tail final and using something a temporary ArrayBuffer inside ListBuffer, and then create the list in the call to ListBuilder.result()?

All operations that work with List in the traditional functional way (building lists by prepending new nodes) would not be affected in any way. If anything, they would become faster when head and tail is final. So the performance reduction would be confined to the ListBuilder. And I think it would not be that large. In the worst case some operations of List would have to be changed to not use ListBuffer, but that would be a good idea anyway.

Note that List.map (and I guess flatMap) does *not* use the traditional approach. That is, every loop in a List-to-List for comprehension relies on efficient append (though they could be converted to using reverse, efficient prepend, and reverse again).

 

I think that this would be the cleanest way to deal with this. 

The idea makes sense, but ListBuffer supports insertion, so one shouldn't use ArrayBuffer. However, one can have separate implementations of ListBuffer (a mutable list) and List (a really immutable list), and create the list in ListBuilder.result(). This solution has the same thread-safety property of what you describe.

Making such code *thread-safe* would be much easier than the options we discussed, as one would expect; so it would be more maintainable than these alternatives.

OTOH, with this code ListBuilder.result would take O(n) (alternatively, adding an element to a builder would take amortized O(1)), and would use additional temporary space.

However, the authors of ListBuffer assumed the performance difference matters - this is even described in Programming in Scala, 22.3!

So we just need somebody to implement and benchmark one of the alternatives, and show that relevant workloads are not affected badly. Scalac uses enough lists that it *might* be part of the workloads (though other people have much more clue than me on this).

Yeah, fixing ListBuffer and then making Cons truly immutable sounds like the appropriate way forward.

Careful: It would  mean that *every* transformer on list (map, flatMap, filter, the works)  would consume twice the memory and incur the copying overhead. They all use ListBuffer to do their work. This is not peanuts. It would mean we make the sequential case slower to get a guarantee for the parallel case that people so far did not seem to care about.

Good point, so if one needs a true immutable Seq, what should one use?

Cheers,

√

[Rex Kerr]

On Thu, Sep 19, 2013 at 8:12 AM, martin odersky <martin....@epfl.ch> wrote:

However, the authors of ListBuffer assumed the performance difference matters - this is even described in Programming in Scala, 22.3!

So we just need somebody to implement and benchmark one of the alternatives, and show that relevant workloads are not affected badly. Scalac uses enough lists that it *might* be part of the workloads (though other people have much more clue than me on this).

Yeah, fixing ListBuffer and then making Cons truly immutable sounds like the appropriate way forward.

Careful: It would  mean that *every* transformer on list (map, flatMap, filter, the works)  would consume twice the memory and incur the copying overhead. They all use ListBuffer to do their work. This is not peanuts. It would mean we make the sequential case slower to get a guarantee for the parallel case that people so far did not seem to care about.

Cheers

 - Martin

I just did a quick test and at least for map, it seems 2-3x _faster_ to use Array as an intermediate (restacking List backwards) than to go through ListBuffer, even for small lists.  I'm sure there are cases where this isn't true (e.g. filter, where most elements are rejected), but it's makes the just-plain-immutable solution more encouraging to pursue.

(I don't know what to do about Vector, though.)

  --Rex

[Scott Carey]

For small lists, you can handle it recursively without an intermediate, but after some length, blowing the stack becomes higher risk and intermediate heap space a requirement.   A hybrid strategy may be most effective.
 

[Paolo Giarrusso]

On Thu, Sep 19, 2013 at 4:15 PM, Rüdiger Klaehn <rkl...@gmail.com> wrote:

On Thu, Sep 19, 2013 at 3:29 PM, Paolo G. Giarrusso <p.gia...@gmail.com> wrote:

On Thursday, September 19, 2013 11:41:51 AM UTC+2, rklaehn wrote:

What about making head and tail final and using something a temporary ArrayBuffer inside ListBuffer, and then create the list in the call to ListBuilder.result()?

All operations that work with List in the traditional functional way (building lists by prepending new nodes) would not be affected in any way. If anything, they would become faster when head and tail is final. So the performance reduction would be confined to the ListBuilder. And I think it would not be that large. In the worst case some operations of List would have to be changed to not use ListBuffer, but that would be a good idea anyway.

Note that List.map (and I guess flatMap) does *not* use the traditional approach. That is, every loop in a List-to-List for comprehension relies on efficient append (though they could be converted to using reverse, efficient prepend, and reverse again).

 

Map and flatMap will create a completely new list. So for a long list you have to allocate many new tiny objects in any case. Having a transient ArrayBuffer or similar will not make things much worse. It might even make things faster. At least that is what my intuition says. We will have to benchmark it. But even if there is a small performance degradation, I think it would be worth it.

You have a point: if you use extra temporary space, it probably better be an ArrayBuffer - as long as you don't need insertion (and often you don't).

I think that this would be the cleanest way to deal with this. 

The idea makes sense, but ListBuffer supports insertion, so one shouldn't use ArrayBuffer. However, one can have separate implementations of ListBuffer (a mutable list) and List (a really immutable list), and create the list in ListBuilder.result(). This solution has the same thread-safety property of what you describe.

ListBuffer is currently backed by a single-linked list where you can modify the tails? Then inserting elements will currently be O(N) because you have to find the place to insert, which is O(N). So swapping the internal representation to an array would not make things worse.

You change from O(1) writes to O(N) writes (which often matters given writes are more expensive), but it's true the overall complexity doesn't change.

However, most libraries allow this in O(1) through some concept of Output Iterator (in C++) or ListIterator (in Java), which allows O(1) insertion. It's interesting that Scala gets away without supporting this, probably because of the emphasis on immutability (though it supports O(log N) insertion through Vector).

And you might gain some performance for all traversal methods when head and tail are final.

Anyway, the only way to find out is to benchmark it.

Indeed.

[Scott Carey]

I am interested in attempting to make List purely immutable. 

I would like to start with Rex's idea here and tweak it to handle the filter cases, etc.   Rex, do you have a branch with your experiment on it?  What test did you do to measure the performance improvement?  I'll need suggestions for how best to performance test it -- what tests will convince people that it is a good change or prove it won't work? I could get started sometime in the next couple weeks as a weekend + holiday project.

I am confident it will be fast, _especially_ for small lists.  There is no reason to spill to any sort of buffer until after there are a minimum threshold of unfiltered items accumulated on the stack.

On Thursday, September 19, 2013 3:40:10 PM UTC-7, Rex Kerr wrote:

[Rex Kerr]

I have no branch; I just typed out the relevant code into the REPL.  It was meant as inspiration, not as a starting point.

  --Rex

--

[Scott Carey]

Ok, I've had a deeper look at the problem and re-read this thread.

First, serialization makes final fields impossible without trickery.  It constructs an object without calling the constructor, then expects you to modify the fields.  Scala, like Java, doesn't have a way to say "this field is final ... but i'm gong to modify it only while deserializing, trust me".   
Either hd and tl are vars, Serialization is not supported, or we use reflection or Unsafe to set the fields during deserialization -- both of which mean that List could fail to deserialize in a security manager.  I hate Java Serialization enough to say to those that require it and use a security manager:  you have to trust the scala library code or it won't work.  I've done both reflective and Unsafe field access in the past in Java for similar purposes, does Scala-library already have an internal facility for this?  Does Scala's reflection take advantage of Unsafe when it is available to make reflective field access faster?  Where would I look for examples of using scala reflection for this or something similar?  Would it be acceptable?

If that problem is solved, then we can have a truly immutable List.   I am highly confident that the use of an array backed buffer will in most situations be very fast and in many be faster than using ListBuffer.
  It will use less memory as an intermediate:  An array of 28 elements is 128 bytes, a singly linked list of length 28 is 576 bytes, with much lower locality of reference. 
One example would be foldRight, which currently reverses the list, then does foldLeft in reverse.  Collecting the values into an array  instead of a reversed list will take up 1/4 the space or so.
Using the stack instead of arrays for small lists is also an option, although it may mean less code sharing with some of the super-traits.

The result would be that List and its builder would not use ListBuffer, and ListBuffer would require its own mutable data structure.  Much of the work would probably be in making ListBuffer work when it no longer has the ability to mutate List.

[Rex Kerr]

On Thu, Nov 14, 2013 at 10:26 AM, Scott Carey <scott...@gmail.com> wrote:

I am highly confident that the use of an array backed buffer will in most situations be very fast and in many be faster than using ListBuffer.

Well, you can benchmark both the existing List and/or ListBuffer against ArrayBuffer, can't you?

Also, I'm not sure why you're talking about serialization for an intermediate representation during a computation.  Just don't serialize in the middle!  You have to maintain the list structure afterwards because you can't do proper structural sharing otherwise.  You really only want arrays as intermediates (or as part of some sort of tree or linked list structure--see immutable.Vector and mutable.ArraySeq for comparison).

  --Rex

[Paolo Giarrusso]

On Thu, Nov 14, 2013 at 8:46 PM, Rex Kerr <ich...@gmail.com> wrote:
> On Thu, Nov 14, 2013 at 10:26 AM, Scott Carey <scott...@gmail.com> wrote:

>> I am highly confident that the use of an array backed buffer will in most
>> situations be very fast and in many be faster than using ListBuffer.

> Well, you can benchmark both the existing List and/or ListBuffer against
> ArrayBuffer, can't you?
>
> Also, I'm not sure why you're talking about serialization for an
> intermediate representation during a computation. Just don't serialize in
> the middle!

I am not sure, but I think the question is "Can you deserialize a
List?", not "Can you serialize a ListBuffer" — and a List is not
obviously an "intermediate representation during a computation". I
sense some disconnect here.

Still, you could probably replace a list by an array right before
serialization (via writeReplace/readReplace IIRC). But this would
destroy structural sharing: if you serialize both a.tail and a, and
then deserialize them, you get two distinct lists. This behavior is
acceptable correctness-wise if you pretend that lists don't have
identity (which is debatable*), but can be a problem space-wise.

* As Paul Phillips pointed out on Twitter, even immutable values have
identity in Scala.

> You have to maintain the list structure afterwards because you
> can't do proper structural sharing otherwise. You really only want arrays
> as intermediates (or as part of some sort of tree or linked list
> structure--see immutable.Vector and mutable.ArraySeq for comparison).

> You received this message because you are subscribed to a topic in the
> Google Groups "scala-internals" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/scala-internals/P7WNVkJQdHk/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to

> scala-interna...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.



--

Paolo G. Giarrusso - Ph.D. Student, Philipps-University Marburg
http://www.informatik.uni-marburg.de/~pgiarrusso/

[Scott Carey]

On Thursday, November 14, 2013 1:30:27 PM UTC-8, Paolo G. Giarrusso wrote:

On Thu, Nov 14, 2013 at 8:46 PM, Rex Kerr <ich...@gmail.com> wrote:
> On Thu, Nov 14, 2013 at 10:26 AM, Scott Carey <scott...@gmail.com> wrote:

>> I am highly confident that the use of an array backed buffer will in most
>> situations be very fast and in many be faster than using ListBuffer.

> Well, you can benchmark both the existing List and/or ListBuffer against
> ArrayBuffer, can't you?
>
> Also, I'm not sure why you're talking about serialization for an
> intermediate representation during a computation.  Just don't serialize in
> the middle!

I am not sure, but I think the question is "Can you deserialize a
List?", not "Can you serialize a ListBuffer" — and a List is not
obviously an "intermediate representation during a computation". I
sense some disconnect here.

Yes, just look at List.scala, around line 371
 https://github.com/scala/scala/blob/master/src/library/scala/collection/immutable/List.scala

Java serialization is happening via readObject, mutating the member variables.   The contract expects mutation, readObject returns nothing, and the instance is expected to mutate itself.  readResolve lets the object return a different instance, but it takes no parameters, so it must have read something from the object stream in readObject and saved it somewhere in order to return a different instance. 
There is therefore _almost_ no way to implement deserialization without mutating variables.  One can get sneaky and mutate 'final' Java member variables with Java reflection.  I don't know if Scala's reflection permits modifying vals.  If not, I can use Java reflection.  Ugly, very ugly.
One even uglier hack is to partner with readResolve and pass a buffer via class scoped map that uses reference equality to pass something from readObject to readResolve...... 

Still, you could probably replace a list by an array right before
serialization (via writeReplace/readReplace IIRC). But this would
destroy structural sharing: if you serialize both a.tail and a, and
then deserialize them, you get two distinct lists. This behavior is
acceptable correctness-wise if you pretend that lists don't have
identity (which is debatable*), but can be a problem space-wise.

 

The List serialization/deserialization already materializes it like an array and destroys structural sharing (see code referenced above).  Objects inside the list may be shared, but the :: objects themselves aren't serialized, only the items in the list and an object to mark the end of the list.

Inside of readObject it is easy enough to read each value, stuff it in an ArrayBuffer, then dump that into a List.  One could stuff this in the tail member, then in readResolve, return the value stuffed in the tail to replace 'this'.  The benefit is that only the tail needs to be modified in that case, either because it is a var, or via reflection.
 


At this stage, I've decided to simply ignore / comment out the serialization problem and see what other changes are beneficial. 


This serialization pain has me thinking of a language feature request:

Inside of a readObject method, allow val's to be modified -- using reflection internally if needed so that the field is 'final' in all other respects.  There is no reason for this pain.  This may be a JVM only wart, but on other platforms Serializable's readObject wouldn't exist. 
It is better to bend the contract of val, than to encourage that var to handle Serializable.  readObject is essentially a special type of constructor anyway.

[Scott Carey]

Note to self:   Proof read even the last line.
"It is better to bend the contract of val, than to encourage using vars for no reason other than handling Serializable."
 

[Paolo Giarrusso]

This serialization pain has me thinking of a language feature request: [...]

 

I see your point. But if you ignore performance for a second, you could implement the current code without using any mutation – just read objects, prepend them to an accumulator list, then reverse it:

```scala
def readList(in: ObjectInputStream, acc: List[A]): List[A] = {

  val a = in.readObject()
  if (a == ListSerializeEnd) reverse(acc) else readList(a :: acc)
}
```
If you use an ArrayBuffer instead of a list, you don't need to reverse the result, just to copy it to a list (again, from the end to the beginning). That's probably faster just because ArrayBuffer is more compact than List, so there's less memory to write to.

And that might be faster than reflection, and surely more compatible than requiring a security manager. It's probably slower than writing to vars directly though. But I'd assume this isn't a problem until a well-written (micro?)benchmark shows otherwise with a realistic load, and I'd require such a proof to exist before considering a language feature.

Java serialization is not that fast anyway, so you shouldn't be using it in a performance-critical loop. Serialization tries to be compatible and robust, so we shouldn't use crazy hacks for serializing Lists.

With other serialization frameworks, which are actually optimized for performance the question *might* make more sense. There are many such frameworks for Java; for Scala, there are [picklers](http://lampwww.epfl.ch/~hmiller/pickling/) from Heather Miller et al.

[Scott Carey]

That won't work.   readObject _does not return anything_ , so there is nothing to do with that list you just created.  The instance that readObject is being called on was instantiated by the JVM without calling any constructor, and the contract is that after readObject returns, all of its member variables have been populated.  This can only be done with mutation.

This is what I meant by "

Inside of readObject it is easy enough to read each value, stuff it in an ArrayBuffer, then dump that into a List. "

It is very easy to create a List from what has been serialized.  It is _impossible_ to make the current instance of :: _be_ that list, without mutating its head and tail directly or via reflection.

And that might be faster than reflection, and surely more compatible than requiring a security manager. It's probably slower than writing to vars directly though. But I'd assume this isn't a problem until a well-written (micro?)benchmark shows otherwise with a realistic load, and I'd require such a proof to exist before considering a language feature.

No benchmark necessary.  Your choices are:
1: use var, and mutate, which by the JMM does not guarantee newly constructed objects are safe
2: use val, and reflection to mutate, which is difficult to use and very clumsy; most will choose 1 instead (see List, Vector, et. al)
3: use val and some ugly hack to pass a constructed object through the ether to readResolve (even more ugly, but might not need reflection, only a hidden object)
4: a language feature to deal with this -- then your code snippet above works well, after reading the whole list, set the head and tail of this object to be the same as the head and tail of the one read.
5: ?? other ideas ??

Java serialization is not that fast anyway, so you shouldn't be using it in a performance-critical loop. Serialization tries to be compatible and robust, so we shouldn't use crazy hacks for serializing Lists.

I could care less about the performance of the serialization, Java serialization is extremely slow.  I just want it to _work_ with an object that uses 'val' member variables.
 

With other serialization frameworks, which are actually optimized for performance the question *might* make more sense. There are many such frameworks for Java; for Scala, there are [picklers](http://lampwww.epfl.ch/~hmiller/pickling/) from Heather Miller et al.

I am extremely familiar with JVM serialization frameworks, being a major author of one.  Java's default serialization is almost useless baggage.   I suppose the decision to support it in Scala's collection framework was made long ago due to some folks wanting to use it with some legacy J2EE stuff.   I'd gladly delete it if I thought the PR would be accepted.

 

[Scott Carey]

I got truly-immutable list working (minus serialization, with a modified ListBuffer) in the library, then went to compile all of scala/scala.   
Surprise! Reflection also (ab)uses the fact that it is mutable in https://github.com/scala/scala/blob/master/src/reflect/scala/reflect/internal/Types.scala (lines 1137 and 1159).

I don't think I need Reflection working in order to test the library performance with various scenarios, so I'll simply break the above locally to get it to compile.

I suspect it would be best if the above did not depend on List being mutable.

[Paolo Giarrusso]

On Fri, Dec 6, 2013 at 9:56 AM, Scott Carey <scott...@gmail.com> wrote:
> That won't work. readObject _does not return anything_ , so there is nothing to do with that list you just created. The instance that readObject is being called on was instantiated by the JVM without calling any constructor, and the contract is that after readObject returns, all of its member variables have been populated. This can only be done with mutation.

I was missing that part, or confusing the behavior with the one of
writeReplace/readResolve. I'm not familiar with that API, but it seems
to allow a functional implementation, since it can return a different
object (with some discipline to avoid destroying identity).

I don't have a better usage example than
http://ashish.vashisht.net/2008/02/serialization-in-java-readresolve.html;
there's one clause in the specification
(http://docs.oracle.com/javase/7/docs/platform/serialization/spec/input.html#5903)
that I still don't get from that, only from the example.

On Fri, Dec 6, 2013 at 10:02 AM, Scott Carey <scott...@gmail.com> wrote:
> I got truly-immutable list working (minus serialization, with a modified ListBuffer) in the library, then went to compile all of scala/scala.
> Surprise! Reflection also (ab)uses the fact that it is mutable in https://github.com/scala/scala/blob/master/src/reflect/scala/reflect/internal/Types.scala (lines 1137 and 1159).
> I don't think I need Reflection working in order to test the library performance with various scenarios, so I'll simply break the above locally to get it to compile.

> I suspect it would be best if the above did not depend on List being mutable.

I'm hoping what that's doing could be implemented with some kind of
buffer, even ListBuffer; the code seems to simply append to a list,
just in C-like style.

Best,

[Rüdiger Klaehn]

There are other collections in scala.collection.immutable that use vars and do support serialization. See for example HashMap: https://github.com/scala/scala/blob/v2.10.3/src/library/scala/collection/immutable/HashMap.scala#L1. There is a SerializationProxy class at the bottom. Couldn't the same approach be used for lists?

[Simon Ochsenreither]

2: use val, and reflection to mutate, which is difficult to use and very clumsy; most will choose 1 instead (see List, Vector, et. al)

Just use this. It's ugly, but it works.

[Scott Carey]

SerializationProxy looks like a great approach!     This should be used more often.   Assuming it works the way I think it works.  Thanks!

It would break serialization, meaning it needs to change before 2.11, or wait until 2.12.

With that in mind, I can make a PR that changes the serialization to be compatible with immutability, and is a first step to a truly immutable list, being minimally invasive otherwise. 

[Daniel Sobral]

Just for the reference of interested parties, this pattern is described as Item 78 on Effective Java 2nd Edition, one of the primary goals being serialization of immutable objects.