JOL output before this change:

scala.collection.immutable.LazyList@2d2e5f00d footprint:
     COUNT       AVG       SUM   DESCRIPTION
       100        16      1600   java.lang.Object
       101        24      2424   scala.collection.immutable.LazyList
       100        24      2400   scala.collection.immutable.LazyList$State$Cons
         1        16        16   scala.collection.immutable.LazyList$State$Empty$
       302                6440   (total)

After:

scala.collection.immutable.LazyList@2ea6137d footprint:
     COUNT       AVG       SUM   DESCRIPTION
       100        16      1600   java.lang.Object
       101        24      2424   scala.collection.immutable.LazyList
       201                4024   (total)

That looks like a reasonable encoding. However it's going to be tricky to make thread-safe while staying portable for the non-JVM platforms. The straightforward approach would be to use CAS'es on the fields, but that's not supported on JS/Native other than through ju.concurrent.AtomicX classes. Using the latter would of course defeat the purpose of the whole PR.

Does other platform support the AtomicXFieldUpdatper？ that will help save more bytes

No, they don't. These classes are also reflection-based.

Is space or runtime performance more important for LazyList? If space isn't clearly more important, we'd better have a benchmark before/after also. synchronized is an obvious way to fix the thread safety; it's just slower under some scenarios.

I'll try to have a look at this. I've had another idea for a while of boxing all the evaluation into its own class, and then just swapping the val from the box to the result after the evaluation is done, which sidesteps the concurrency issues I believe

👍 I also think this can probably be cleaned up furhter. def state now creates a new State.Cons on each invocation which is unnecessary. I just did the minimal change to see what can be done.

@lrytz I haven't fixed this enough for it to compile, but thoughts on this design? https://github.com/scala/scala/compare/2.13.x...NthPortal:scala:ll-memory/R1?expand=1

@NthPortal I see, the idea is using a lazy val in the Evaluator to implement thread safety, and make sure that multiple threads assigning to _head / _tail is idempotent.

I'm not sure which one is easier, your design or implementing thread safety manually.

Inspired by the desugaring for class C { lazy val x = 42 }:

public class C {
    private int x;
    private volatile boolean bitmap$0;

    private int x$lzycompute() {
        C c = this;
        synchronized (c) {
            if (!this.bitmap$0) {
                this.x = 42;
                this.bitmap$0 = true;
            }
        }
        return this.x;
    }

    public int x() {
        if (!this.bitmap$0) {
            return this.x$lzycompute();
        }
        return this.x;
    }
}

We should be able to do it as:

class LazyList {
  @volatile var _head = Undefined
  var _state = lazyState

  def state =
    if (_head ne Undefined) sCons(_head, _state)
    else {
      synchronized {
        if (_head eq Undefined) {
          // evaluate lazy state
          _state = ...
          _head = ...
        }
      }
      state
    }

I pushed that, wdyt? I would need to brush up my java memory model knowledge to be sure. If a thread observes _head ne Undefined, is it guaranteed to also see the changed _state? It seems so from the lazy val desugaring, but I don't have the knowledge to explain it.

Aren't you creating a new object on every access now? Are we sure this is a win?

@lrytz I'm pretty sure you're correct that setting @volatile var _head second acts as a fence for _state. I think my biggest issue is that it no longer detects self-reference, which means that you get a stack overflow instead, which is bad UX. I do like the idea of less boxing though. on the other hand, this makes it more difficult (maybe impossible?) to share the state when prepending without double-evaluating

Aren't you creating a new object on every access now? Are we sure this is a win?

@Ichoran I changed this now (see commit "remove State"). WDYT?

it no longer detects self-reference, which means that you get a stack overflow instead, which is bad UX

@NthPortal could you explain this in more detail, I don't know what you mean. The selfReferentialFailure JUnit test passes.

I adjusted the tests for toString of cyclic lazy lists. The underlying reason

scala> lazy val ll: LazyList[Int] = 1 #:: 2 #:: ll
lazy val ll: LazyList[Int] // unevaluated

scala> ll.tail.tail eq ll
val res0: Boolean = false

scala> ll.tail.tail.tail eq ll.tail
val res1: Boolean = true

Until here it's the same before and after my change. But ll.toString is now different: before LazyList(1, 2, <cycle>), after LazyList(1, 2, 1, <cycle>)

Before the change, ll.tail.tail.state eq ll.state is true

import scala.util.chaining._
def getMethodAccessible[A: reflect.ClassTag](name: String): java.lang.reflect.Method =
  implicitly[reflect.ClassTag[A]]
    .runtimeClass.getDeclaredMethods
    .find(_.getName == name).get.tap(_.setAccessible(true))

val state = getMethodAccessible[LazyList[_]]("scala$collection$immutable$LazyList$$state")

scala> state.invoke(ll.tail.tail) eq state.invoke(ll)
val res6: Boolean = true

But we no longer have the state objects, so cycles are detected one element later.

Serialization: is actually not compatible, because un-evaluated lazy lists are serialized using plain object serialization. I don't think we can work around this. But we don't guarantee serialization compatibility between releases, so 🤷‍♂️.

@lrytz - I guess is about the best that can be hoped for given the binary compatibility requirements. There is the one extra creation of a LazyList that you destructure and throw away, but reworking everything to use a mutating visitor instead of a regular lambda is probably (1) hard to get right and (2) hard to make binary compatible (because you inherently need visibility into structure that used to not exist).

So I think the performance overhead, if it's an issue, would be the only thing remaining (not counting correctness, of course--I can't eyeball that, but there are a fair number of unit tests, plus some collection-laws).

I'm pretty sure if two different threads are building up erroniously mutually referential lists, you can get a deadlock instead of an error condition here. Maybe we don't care.

If thread 1 is trying to get the next item in xs, and to do so it starts traversing ys; but meanwhile, thread 2 is trying to extend ys and to do that it's looking into xs; you can have thread 1 enter the synchronized block of the next uninitialized xs, then run down ys and wait for ys's synch lock to be free. But thread 2 has it, runs down xs, hits the sync block of xs...and...no more progress can be made.

Now, this is an error condition. If ys(i) depends on xs(j) and xs(j) depends on ys(i), there's no way to perform the initialization. But you won't get the friendly "hey, re-entrancy means you messed up" exception; you won't even get a stack overflow.

I don't know if robustness to this kind of messup is big enough to worry about. To do it, you'd need to drop synchronization while executing the lambda, then try to pick it up again. This would allow one (and eventually both) threads to crash out with exceptions. But under contention, this might increase the cost considerably. Maybe with the volatile var guard, it wouldn't actually matter much. But I wouldn't bet on it without a test, and it's really hard to microbenchmark multi-threaded code.

@Ichoran you're right that a lot of short lived objects are allocated while evaluating lazy lists.

For example

• LazyList.from(1).take(N).toList allocates N*4 LazyList instances during evaluation
• LazyList.from(1).take(N+1).take(N).toList allocates N*6
• (1 #:: 2 ... #:: N #:: LazyList.empty).toList allocates N*3

There's the Function0 allocations on top of that (not one for every LazyList allocation though).

I compared the state of this PR with current LazyList, it's exactly the same (when adding up LazyList and State instances in the current implementation).

Maybe that situation can also be improved..? It doesn't seem to hold up this PR though.

Comparing allocation to Stream:

• Stream.from(1).take(N).toList allocates N*2 Stream instances
• Stream.from(1).take(N+1).take(N).toList allocates N*3
• (1 #:: 2 ... #:: N #:: Stream.empty).toList allocates N

For the deadlock scenarion, I think it's the same with the current LazyList implementation which uses val state: State[A] = { ... lazyState() ... }, no?

@lrytz - I think the deadlock situation is different because lazy val doesn't lock, does it? It uses a CAS-like mechanism, right? (Multiple attempts are cool; whoever finishes first wins and gets to set the cached value.) If that's correct, I think the lambda goes through, tries to initialize the lazy val a second time, and is caught by the re-entrant detection code.

Regarding the temporary object overhead--yeah, I wasn't thinking it was particularly worse. Just that it's a shame, in general. But no reason to fix it with this PR; the memory savings are the key part.

@Ichoran lazy vals are evaluated at most once, i posted the desugaring in a comment above #10937 (comment)

@lrytz - Oh, oops. Then I agree: the deadlock issue is the same.

lazy vals are evaluated at most once

modulo exceptions, that is...

scala> lazy val x = { println("x"); throw new RuntimeException(); 1 }

scala> x
x
java.lang.RuntimeException

scala> x
x
java.lang.RuntimeException

@lrytz - Yes, that was my mistake--I was incorrectly inferring the general behavior from the behavior with exceptions.

could you explain this in more detail, I don't know what you mean. The selfReferentialFailure JUnit test passes.

@lrytz my comment was about your code snippet that didn't have MidEvaluation, so it's moot. I was concerned about the following:

lazy val ll: LazyList[Int] = 1 #:: ll.drop(1)
ll.tail.head // oops

hey Lukas, have you signed the CLA? the bot isn't sure 😜

Thanks a lot for the sharp-eyed (and -brained) review @NthPortal!