Question on lazy val

[Nils Kilden-Pedersen]

I was looking at the byte code generated for a lazy val, and had a few questions and comments. It appears to be implemented as basic DCL using a volatile int as flag and synchronizing on the class instance.
* The int flag does & operation for every access to lazy val. Why, and why not a simple boolean?
* Synchronization is on the enclosing instance. Is that deliberate? Worst case, it could cause a hard to find dead-lock. Could a synthetic monitor not be used to eliminate worst case, or am I missing some obvious reason?

Nils

[David MacIver]

On Thu, Jun 5, 2008 at 9:31 PM, Nils Kilden-Pedersen <nilskp@...> wrote:
> I was looking at the byte code generated for a lazy val, and had a few
> questions and comments. It appears to be implemented as basic DCL using a
> volatile int as flag and synchronizing on the class instance.
> * The int flag does & operation for every access to lazy val. Why, and why
> not a simple boolean?
> * Synchronization is on the enclosing instance. Is that deliberate? Worst
> case, it could cause a hard to find dead-lock. Could a synthetic monitor not
> be used to eliminate worst case, or am I missing some obvious reason?

The reason in both cases is memory usage - this way there's a fairly
low overhead for using a lazy val.

I actually have an alternative lazy implementation which would solve
both these problems that I want to try out some time. It just requires
me to first get over my fear of the scala compiler.

[David MacIver]

On Thu, Jun 5, 2008 at 9:32 PM, David MacIver <david.maciver@...> wrote:

> On Thu, Jun 5, 2008 at 9:31 PM, Nils Kilden-Pedersen <nilskp@...> wrote:
>> I was looking at the byte code generated for a lazy val, and had a few
>> questions and comments. It appears to be implemented as basic DCL using a
>> volatile int as flag and synchronizing on the class instance.
>> * The int flag does & operation for every access to lazy val. Why, and why
>> not a simple boolean?
>> * Synchronization is on the enclosing instance. Is that deliberate? Worst
>> case, it could cause a hard to find dead-lock. Could a synthetic monitor not
>> be used to eliminate worst case, or am I missing some obvious reason?
>
> The reason in both cases is memory usage - this way there's a fairly
> low overhead for using a lazy val.
>
> I actually have an alternative lazy implementation which would solve
> both these problems that I want to try out some time. It just requires
> me to first get over my fear of the scala compiler.

I suppose I shouldn't make comments like that without explaining myself.

The idea is that we'd have a class scala.runtime.Lazy which is used as
a marker object storing a thunk that evaluates to the lazy value. Then
the laziness implementation can use isInstanceOf[Lazy] to test if it's
been thunked and do synchronization on the Lazy instance rather than
on this.

The main reason I want to do this is that it would provide a nice
solution to https://lampsvn.epfl.ch/trac/scala/ticket/720 - you could
store the data on the Lazy object rather than in the enclosing object.

It might also make lazy arguments easier to do.

In general the result will be that objects with unthunked lazy values
will use a bit more memory but objects with thunked lazy values should
use no more memory than their strict equivalents.

[Nils Kilden-Pedersen]

On Thu, Jun 5, 2008 at 3:37 PM, David MacIver <david.maciver@...> wrote:

The idea is that we'd have a class scala.runtime.Lazy which is used as
a marker object storing a thunk that evaluates to the lazy value. Then
the laziness implementation can use isInstanceOf[Lazy] to test if it's
been thunked and do synchronization on the Lazy instance rather than
on this.

I think I know what you mean, but I hope this won't result in instanceof check for every access?

The main reason I want to do this is that it would provide a nice
solution to https://lampsvn.epfl.ch/trac/scala/ticket/720 - you could
store the data on the Lazy object rather than in the enclosing object.

That bug seems to address two completely different cases. I assume you mean case 2?
 

In general the result will be that objects with unthunked lazy values
will use a bit more memory but objects with thunked lazy values should
use no more memory than their strict equivalents.

For the sake of correctness (eliminating dead lock potential) that would be a good trade off.

I didn't see an answer to why (int & 1 == 0) was needed instead of a plain boolean.

[Nils Kilden-Pedersen]

On Thu, Jun 5, 2008 at 4:04 PM, Nils Kilden-Pedersen <nilskp@...> wrote:

That bug seems to address two completely different cases. I assume you mean case 2?

Sorry, I now see how it relates to both cases. So you would store f inside the Lazy instance and null it once evaluated, right?

[David MacIver]

On Thu, Jun 5, 2008 at 10:04 PM, Nils Kilden-Pedersen <nilskp@...> wrote:

> On Thu, Jun 5, 2008 at 3:37 PM, David MacIver <david.maciver@...>
> wrote:
>>
>> The idea is that we'd have a class scala.runtime.Lazy which is used as
>> a marker object storing a thunk that evaluates to the lazy value. Then
>> the laziness implementation can use isInstanceOf[Lazy] to test if it's
>> been thunked and do synchronization on the Lazy instance rather than
>> on this.
>
> I think I know what you mean, but I hope this won't result in instanceof
> check for every access?

It will. instanceof is pretty quick these days. This could be replaced
with a null check, a getClass() == classOf[Lazy] and an additional
level of indirection for the Lazy (have Lazy wrap a Function0 rather
than being abstract).

>> The main reason I want to do this is that it would provide a nice
>> solution to https://lampsvn.epfl.ch/trac/scala/ticket/720 - you could
>> store the data on the Lazy object rather than in the enclosing object.
>
> That bug seems to address two completely different cases. I assume you mean
> case 2?

No, both cases are pretty similar. This would handle both - because
the data is stored on the Lazy instance rather than the enclosing
object it doesn't need to do anything to achieve correctness with
respect to garbage collection.

>> In general the result will be that objects with unthunked lazy values
>> will use a bit more memory but objects with thunked lazy values should
>> use no more memory than their strict equivalents.
>
> For the sake of correctness (eliminating dead lock potential) that would be
> a good trade off.
>
> I didn't see an answer to why (int & 1 == 0) was needed instead of a plain
> boolean.

Because if you have multiple lazy values they reuse other parts of the field.

[David MacIver]

On Thu, Jun 5, 2008 at 10:53 PM, Nils Kilden-Pedersen <nilskp@...> wrote:
> On Thu, Jun 5, 2008 at 4:17 PM, David MacIver <david.maciver@...>
> wrote:
>>
>> It will. instanceof is pretty quick these days.
>
> Everything is relative. I work with code where we sometimes do microsecond
> optimizations.

The way to get microsecond optimisations out of anything like this is
"don't use the language feature. Roll your own evaluation strategy
that will be better suited to your needs". If you arrange it right an
instanceof check is about two instructions. That's pretty quick by any
metric which involves writing for the JVM. :-)

> Why exactly would it be needed?

Because you need to distinguish between the case where you have a
value and the case where you have a thunk waiting to be a value...

[Nils Kilden-Pedersen]

On Thu, Jun 5, 2008 at 5:03 PM, David MacIver <david.maciver@...> wrote:

On Thu, Jun 5, 2008 at 10:53 PM, Nils Kilden-Pedersen <nilskp@...> wrote:
> On Thu, Jun 5, 2008 at 4:17 PM, David MacIver <david.maciver@...>
> wrote:
>>
>> It will. instanceof is pretty quick these days.
>
> Everything is relative. I work with code where we sometimes do microsecond
> optimizations.

The way to get microsecond optimisations out of anything like this is
"don't use the language feature. Roll your own evaluation strategy
that will be better suited to your needs". If you arrange it right an
instanceof check is about two instructions. That's pretty quick by any
metric which involves writing for the JVM. :-)

> Why exactly would it be needed?

Because you need to distinguish between the case where you have a
value and the case where you have a thunk waiting to be a value...

A boolean or int won't solve that?

[David MacIver]

On Fri, Jun 6, 2008 at 4:53 AM, Nils Kilden-Pedersen <nilskp@...> wrote:

> On Thu, Jun 5, 2008 at 5:03 PM, David MacIver <david.maciver@...>
> wrote:
>>
>> On Thu, Jun 5, 2008 at 10:53 PM, Nils Kilden-Pedersen <nilskp@...>
>> wrote:
>> > On Thu, Jun 5, 2008 at 4:17 PM, David MacIver <david.maciver@...>
>> > wrote:
>> >>
>> >> It will. instanceof is pretty quick these days.
>> >
>> > Everything is relative. I work with code where we sometimes do
>> > microsecond
>> > optimizations.
>>
>> The way to get microsecond optimisations out of anything like this is
>> "don't use the language feature. Roll your own evaluation strategy
>> that will be better suited to your needs". If you arrange it right an
>> instanceof check is about two instructions. That's pretty quick by any
>> metric which involves writing for the JVM. :-)
>>
>> > Why exactly would it be needed?
>>
>> Because you need to distinguish between the case where you have a
>> value and the case where you have a thunk waiting to be a value...
>
> A boolean or int won't solve that?

I'm not sure how to answer this question. I get confused by questions
of the form "Why do you do it this way? Couldn't you have done it a
more complicated way instead?"

[Nils Kilden-Pedersen]

On Fri, Jun 6, 2008 at 5:18 AM, David MacIver <david.maciver@...> wrote:

I'm not sure how to answer this question. I get confused by questions
of the form "Why do you do it this way? Couldn't you have done it a
more complicated way instead?"

That's not the question. The question is "Why do you do it this way? Couldn't you have done it a more perfomant way instead?"
I like elegant code as much as the next guy, but when building a language compiler, I just think there are more important concerns than the code looking good or having minimal complexity. It's about providing features that hopefully will help thousands of programmers and do so in a way that will not require them to write custom code because it performs poorly in a given situation.
I think a good analogy to Java is the synchronized keyword. With Java 1.5 we were given ReentrantLock, a class that performed faster than the native monitor mechanism. Granted, the Lock interface provided some possibilities that wasn't available with the keyword, but in many cases it replaced synchronized merely for it's performance advantage, increasing complexity for the average programmer, because a language keyword didn't perform optimally.
As most know, with Java 6 synchronized is now as fast, if not slightly faster, than ReentrantLock, and maybe Scala's lazy keyword will go through the same process. I'd rather just see it perform optimally from the beginning.

[David MacIver]

On Fri, Jun 6, 2008 at 1:49 PM, Nils Kilden-Pedersen <nilskp@...> wrote:
> On Fri, Jun 6, 2008 at 5:18 AM, David MacIver <david.maciver@...>
> wrote:
>>
>> I'm not sure how to answer this question. I get confused by questions
>> of the form "Why do you do it this way? Couldn't you have done it a
>> more complicated way instead?"
>
> That's not the question. The question is "Why do you do it this way?
> Couldn't you have done it a more perfomant way instead?"

You've not made a convincing argument that it would be faster.
instanceof against a statically known type is fast: Hotspot is good at
dynamic type checks, and in particular is good at optimising them away
entirely. Checked type casts are all over the place and don't
noticably slow down the performance. x instanceof FinalClass should be
equivalent to x != null && x.getClass == classOf[FinalClass], which is
not an expensive operation.

I've not tried either approach yet. If the current approach for
testing really proves to be significantly faster then there's a more
convincing argument that it should be used. Even then it's not a clear
cut case - the version with instanceof has the nice property that a
strict object has the same memory footprint as a fully evaluated lazy
one. When you have something like Stream where there are a lot of lazy
nodes a word per node quickly adds up.

[Nils Kilden-Pedersen]

On Fri, Jun 6, 2008 at 8:17 AM, David MacIver <david.maciver@...> wrote:

You've not made a convincing argument that it would be faster.
instanceof against a statically known type is fast: Hotspot is good at
dynamic type checks, and in particular is good at optimising them away
entirely.

Good point.
 

Checked type casts are all over the place and don't
noticably slow down the performance. x instanceof FinalClass should be
equivalent to x != null && x.getClass == classOf[FinalClass], which is
not an expensive operation.

I wasn't advocating != null && == getClass, which I believe may even be slower than instanceof on a final class, but a boolean check.
However I did a few benchmarks and your intuition is correct. I'm unable to get even a simple boolean check to perform faster than an instanceof check on a final class. This is highly surprising to me (not that it's fast, but it's that fast).

Thanks for taking the time to respond to me.

[David MacIver]

On Fri, Jun 6, 2008 at 3:38 PM, Nils Kilden-Pedersen <nilskp@...> wrote:
>> Checked type casts are all over the place and don't
>> noticably slow down the performance. x instanceof FinalClass should be
>> equivalent to x != null && x.getClass == classOf[FinalClass], which is
>> not an expensive operation.
>
> I wasn't advocating != null && == getClass, which I believe may even be
> slower than instanceof on a final class, but a boolean check.

Right, I realise that. But my point was that the two tests should be
of comparable expense (with the getClass one being slightly slower).
I'm not surprised hotspot has a smarter approach for the instanceof.

> However I did a few benchmarks and your intuition is correct. I'm unable to
> get even a simple boolean check to perform faster than an instanceof check
> on a final class. This is highly surprising to me (not that it's fast, but
> it's that fast).

Thanks. That's good to know.

> Thanks for taking the time to respond to me.

No problem.

[Christos KK Loverdos]

For what it's worth, I fast-coded a hack that implements lazy vals at the language level, mimicking the compiler's implementation. It turns out 120% slower that built-in lazy vals, if using the client HotSpot (default) and 40% slower if using the server HotSpot (java -server).

It does not leak and the memory footprint is worse than the built-in solution.

final class LazyVal[A](f: => A) {
  private[this] var _f = f _
  private[this] var _value = null.asInstanceOf[A]
 
  def value = {
    if(null != _f) synchronized {
      if(null != _f) {
        _value = _f()
        _f = null
      }
    }
    _value
  }
}

The private[this] things are needed so that field accesses (as compiled by scalac) do not go through methods, although I have noticed that HotSpot is doing a great job even without them.

Christos.

On Fri, Jun 6, 2008 at 5:41 PM, David MacIver <david.maciver@...> wrote:

On Fri, Jun 6, 2008 at 3:38 PM, Nils Kilden-Pedersen <nilskp@...> wrote:
>> Checked type casts are all over the place and don't
>> noticably slow down the performance. x instanceof FinalClass should be
>> equivalent to x != null && x.getClass == classOf[FinalClass], which is
>> not an expensive operation.
>
> I wasn't advocating != null && == getClass, which I believe may even be
> slower than instanceof on a final class, but a boolean check.

Right, I realise that. But my point was that the two tests should be
of comparable expense (with the getClass one being slightly slower).
I'm not surprised hotspot has a smarter approach for the instanceof.

> However I did a few benchmarks and your intuition is correct. I'm unable to
> get even a simple boolean check to perform faster than an instanceof check
> on a final class. This is highly surprising to me (not that it's fast, but
> it's that fast).

Thanks. That's good to know.

> Thanks for taking the time to respond to me.

No problem.

--
__~O
-\ <, Christos KK Loverdos
(*)/ (*) http://ckkloverdos.com

[Christos KK Loverdos]

Clarification: micro-benchmarks were for just one thread.

On Sun, Jun 22, 2008 at 1:42 PM, Christos KK Loverdos <loverdos@...> wrote:

For what it's worth, I fast-coded a hack that implements lazy vals at the language level, mimicking the compiler's implementation. It turns out 120% slower that built-in lazy vals, if using the client HotSpot (default) and 40% slower if using the server HotSpot (java -server).

It does not leak and the memory footprint is worse than the built-in solution.

final class LazyVal[A](f: => A) {
  private[this] var _f = f _
  private[this] var _value = null.asInstanceOf[A]
 
  def value = {
    if(null != _f) synchronized {
      if(null != _f) {
        _value = _f()
        _f = null
      }
    }
    _value
  }
}

The private[this] things are needed so that field accesses (as compiled by scalac) do not go through methods, although I have noticed that HotSpot is doing a great job even without them.

Christos.

On Fri, Jun 6, 2008 at 5:41 PM, David MacIver <david.maciver@...> wrote:

On Fri, Jun 6, 2008 at 3:38 PM, Nils Kilden-Pedersen <nilskp@...> wrote:
>> Checked type casts are all over the place and don't
>> noticably slow down the performance. x instanceof FinalClass should be
>> equivalent to x != null && x.getClass == classOf[FinalClass], which is
>> not an expensive operation.
>
> I wasn't advocating != null && == getClass, which I believe may even be
> slower than instanceof on a final class, but a boolean check.

Right, I realise that. But my point was that the two tests should be
of comparable expense (with the getClass one being slightly slower).
I'm not surprised hotspot has a smarter approach for the instanceof.

> However I did a few benchmarks and your intuition is correct. I'm unable to
> get even a simple boolean check to perform faster than an instanceof check
> on a final class. This is highly surprising to me (not that it's fast, but
> it's that fast).

Thanks. That's good to know.

> Thanks for taking the time to respond to me.

No problem.

--
__~O
-\ <, Christos KK Loverdos
(*)/ (*) http://ckkloverdos.com

--
__~O
-\ <, Christos KK Loverdos
(*)/ (*) http://ckkloverdos.com