--
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.
0) Every lazy val field has its own type (value or reference type), initialized with the default value.
It also uses a volatile bitmap as in the current implementation, but each lazy val state is represented with 2 bits instead of 1.
1) To initialize the lazy val, read its corresponding 2 bits in the bitmap (from now on, I refer to this as state). If state is INITIALIZED, just read the lazy val field (fast path).
Otherwise, if it is UNINITIALIZED, go to 2).
Otherwise, if it is INPROGRESS, synchronize(this) { while (readBitmap == INPROGRESS) this.wait() }, the re-read.
2) synchronize(this) { if (readBitmap == UNINITIALIZED) writeBitmap(INPROGRESS) else "go to 1)" }
3) compute the value for the lazy val
4) synchronize(this) { writeBitmap(INITIALIZED); writeField(computed value); this.notifyAll() }
0) Every lazy val field has its own type (value or reference type), initialized with the default value.
It also uses a volatile bitmap as in the current implementation, but each lazy val state is represented with 2 bits instead of 1.
1) To initialize the lazy val, read its corresponding 2 bits in the bitmap (from now on, I refer to this as state). If state is INITIALIZED, just read the lazy val field (fast path).
Otherwise, if it is UNINITIALIZED, go to 2).
Otherwise, if it is INPROGRESS, synchronize(this) { while (readBitmap == INPROGRESS) this.wait() }, the re-read.
2) synchronize(this) { if (readBitmap == UNINITIALIZED) writeBitmap(INPROGRESS) else "go to 1)" }
3) compute the value for the lazy val
4) synchronize(this) { writeBitmap(INITIALIZED); writeField(computed value); this.notifyAll() }
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
Questions in general:
1) Do you see this kind of a change as valuable / should it be implemented?
2) Does this warrant a SIP?
I'd like an 'executable' SIP for this one:
Wow, nice benchmark!
Did you consider a design based on a SwitchPoint?
--
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.
As far as I understand (and I could be totally wrong), you could have a SwitchPoint where the �primary� action is to evaluate the val. As soon as this has happened, the SwitchPoint switches to the �secondary� action which just returns the value and invalidates the old call-sites so that they pick up the new action. This would mean we wouldn't need any bitset at all.
Please take all of this with tons of salt.
--
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.
�
�
SwitchPoints is JDK 8 music therefore not for 2.11
Sounds promising, but not for 2.11.
I just took a brief look, will respond in more detail in the morning.So, is the idea to try to circumvent the notifyAll call if there are no other readers?
In fact, we might do this without a CAS too - we could have the second-arriving thread set the bitmap into the 4th state, that means that a notify is needed. We use 2 bits for the lazy val in the new scheme anyway, and this allows us to encode these 4 states.
On Tuesday, May 21, 2013 12:03:52 AM UTC+2, Aleksandar Prokopec wrote:I just took a brief look, will respond in more detail in the morning.So, is the idea to try to circumvent the notifyAll call if there are no other readers?
Exactly. If there are no concurrent 1st-time readers.
In fact, we might do this without a CAS too - we could have the second-arriving thread set the bitmap into the 4th state, that means that a notify is needed. We use 2 bits for the lazy val in the new scheme anyway, and this allows us to encode these 4 states.
That's exactly the idea I implemented. But I also used CAS instead of synchronization for the case where there's no concurrent 1st-time readers and no notification is necessary. But could do with synchronization too. If it's a situation with no contention then object monitor will not be inflated and it could be fast too. CAS should be of course faster. Why don't you like CAS? Because it's JDK7+ only?
Regards, Peter
-- Aleksandar Prokopec, Doctoral Assistant LAMP, IC, EPFL http://people.epfl.ch/aleksandar.prokopec
On 5/21/13 12:43 AM, Peter Levart wrote:
On Tuesday, May 21, 2013 12:03:52 AM UTC+2, Aleksandar Prokopec wrote:I just took a brief look, will respond in more detail in the morning.So, is the idea to try to circumvent the notifyAll call if there are no other readers?
Exactly. If there are no concurrent 1st-time readers.
In fact, we might do this without a CAS too - we could have the second-arriving thread set the bitmap into the 4th state, that means that a notify is needed. We use 2 bits for the lazy val in the new scheme anyway, and this allows us to encode these 4 states.
That's exactly the idea I implemented. But I also used CAS instead of synchronization for the case where there's no concurrent 1st-time readers and no notification is necessary. But could do with synchronization too. If it's a situation with no contention then object monitor will not be inflated and it could be fast too. CAS should be of course faster. Why don't you like CAS? Because it's JDK7+ only?
Regards, Peter
We could use the CAS in JDK6 as well, either with the atomic field updaters or using Unsafe directly (we already do this in some places).
We actually had a long discussion about this on one of the Scala meetings, and the overall opinion was that we should avoid using a library-level CAS for the basic language feature - different permissions
could disallow the use of Unsafe or Atomic* classes, rendering the code unrunnable.
I believe that the concern was partly about minimizing dependencies to ease the future development of alternate backends, and partly about Unsafe.
I will microbenchmark the solution that uses the updaters.
Regards,
Aleksandar
Unsafe is restricted for use by classes loaded by bootstrap classloader (JDK system classes), but with no SecurityManager installed, it can be used by ordinary classes too, using reflection to obtain access. In environments with SecurityManager (app servers, applets, JavaWebStart apps) this can be prevented, so Unsafe is not appropriate. But Atomic* classes are not restricted. I don't know of any permission that would disallow their use. It's like ConcurrentHashMap for example, or practically any class in java.util.concurrent. Are you strict and don't use standard core Java libraries in language features to minimize dependencies?
Regards, Peter
Here's the updated version of the graphs:
http://lampwww.epfl.ch/~prokopec/lazyvals/report/
(the `lazy-simulation-v3` version is the initialization with 4 states)
The code:
https://github.com/axel22/lazy-val-bench/blob/master/src/test/scala/example/SyncBench.scala#L104
Avoiding the `notifyAll` in the uncontended case seems to work nicely.
Cheers,
Alex
--
Aleksandar Prokopec,
Doctoral Assistant
LAMP, IC, EPFL
http://people.epfl.ch/aleksandar.prokopec
--
Aleksandar Prokopec,
Doctoral Assistant
LAMP, IC, EPFL
http://people.epfl.ch/aleksandar.prokopec
--
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.
I've just merged the CAS-based version PR from Viktor for the 1 lazy val per class case (lazy-simulation-v4).
It seems to be roughly as fast as the current scheme with one synchronization block.
http://lampwww.epfl.ch/~prokopec/lazyvals/report/
Regards,
Aleksandar
--
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.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
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
--
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.
--
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.
After having spent some time thinking about this, I am still convinced that we should take the synchronized path.
Here are some points:
- the overall memory footprint is possibly increased by always using an integer bitmap field - we would spend a minimum of 4 bytes per bitmap on first lazy val, where this was previously 1 byte
- in a setting with multiple bitmaps or an existing base class, we cannot extend `AtomicInteger` (that internally uses `Unsafe` directly), but need to use `AtomicIntegerFieldUpdater`s that are slower due to extra checks
- in a setting with multiple lazy val fields, we can no longer use a `getAndSet` in the initialization (concurrent accesses to other lazy fields may modify the bitmap - we have to read and recompute the expected bitmap state) - we need a `compareAndSet` and have some retry-logic (see the `complete` method above), which is slower
- due to the restrictions on the `AtomicIntegerFieldUpdater`s, we would need to make the bitmap_0 field publicly visible on the bytecode level, which might be an issue for Java code interfacing Scala code
- the 2 synchronized blocks implementation is much simpler overall
IIRC a single "byte" on the JVM eats 32-bit of storage and only byte arrays are 1-byte per cell.
--Rex
--
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.
http://lampwww.epfl.ch/~prokopec/lazyvals/report/
Note that I added a test with contention, and note that this is a borderline synthetic microbenchmark, not a typical use case.Well, except for multithreaded/highly concurrent applications. (Akka comes to mind :-) )
After having spent some time thinking about this, I am still convinced that we should take the synchronized path.I disagree, I think there's a non-blocking solution waiting to be discovered :-)
- in a setting with multiple bitmaps or an existing base class, we cannot extend `AtomicInteger` (that internally uses `Unsafe` directly), but need to use `AtomicIntegerFieldUpdater`s that are slower due to extra checksI'd opt for Unsafe as scala.concurrent is already based on it. FieldUpdaters are bad.
http://lampwww.epfl.ch/~prokopec/lazyvals/report/
Note that I added a test with contention, and note that this is a borderline synthetic microbenchmark, not a typical use case.Well, except for multithreaded/highly concurrent applications. (Akka comes to mind :-) )I think that multithreaded/highly concurrent applications might not be using lazy vals in that particular scenario. :)
After having spent some time thinking about this, I am still convinced that we should take the synchronized path.I disagree, I think there's a non-blocking solution waiting to be discovered :-)Well, in the general case that might be hard, because what the initializer block does might have side-effects.Can't think of anything there besides using a sandboxing non-blocking STM for the lazy val initialization ;)
- in a setting with multiple bitmaps or an existing base class, we cannot extend `AtomicInteger` (that internally uses `Unsafe` directly), but need to use `AtomicIntegerFieldUpdater`s that are slower due to extra checksI'd opt for Unsafe as scala.concurrent is already based on it. FieldUpdaters are bad.
Agree with you completely there - Unsafe is faster.We had previously held a long discussion on the Scala meeting (where I had originally argued for the CAS approach) and the general concern that the people had was the interaction with SecurityManagers.
Cheers,Alex
--
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.
I'd be cheering you on if I was present! Regarding SecurityManagers, we'd have the same problem with scala.concurrent right, so it's more of a question of "sandboxing" from a scala-library perspective, right?
On May 22, 2013 9:33 PM, "Rex Kerr" <ich...@gmail.com> wrote:
>
> Er, sorry, I mean without using unsafe or anything bulky like AtomicWhatever.
See Alex's original proposal.
Isn't having unsafe in something as central as lazy vals just raising headaches for any non-Oracle-JVM target? Or is unsafe completely standardized across JVMs these days
Yes, according to Mr Lea.
(and portable to CLR)?
How lazy vals are encoded must be platform specific.
On May 22, 2013 9:33 PM, "Rex Kerr" <ich...@gmail.com> wrote:
>
> Er, sorry, I mean without using unsafe or anything bulky like AtomicWhatever.See Alex's original proposal.
Isn't having unsafe in something as central as lazy vals just raising headaches for any non-Oracle-JVM target? Or is unsafe completely standardized across JVMs these days
Yes, according to Mr Lea.
--Rex
--
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.
It's a shame that there is no low-level officially supported API. Having to implement "languages"/standard libraries using the same tools that are available to application developers isn't really the right way forward, as witnessed by the use of intrinsics in the JDK.</rant>
--
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.