another lazy initialization, now with method reference

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

another lazy initialization, now with method reference

JSR166 Concurrency mailing list
I bumped into the following lazy initialization code that tries to piggy-back on the assumption that captures of variables in lambda expressions have final fields semantics:

static <T> Supplier<T> memoize1(Supplier<T> original) {
  return new Supplier<>() {
    //notice the absence of the volatile modifier
    Supplier<T> delegate = this::init; //w1(delegate, init)
    boolean initialized;

    public T get() {
        return delegate.get(); //r1(delegate, either init or captured), hb(w1, r1), not hb(w2, r1)
    }

    private synchronized T init() {
        if(!initialized) {
            T val = original.get();
            delegate = () -> val; //w2(delegate, captured), hb(w1, w2)
            initialized = true;
            return val;
        }
        return delegate.get(); //r2(delegate, captured), hb(w2, r2)
    }
  };
}

Apparently, reads r1 are allowed to observe either the value written by w1, or the value written by w2 because there is no hb(w2, r1). Therefore, the get method is allowed to observe the result of w1 infinitely many times, hence acquiring the monitor per each invocation, which is not good. So this is a performance (not correctness) problem in the code above, but it's not the most interesting part.

A more interesting part of the code is the assumption about final fields semantics of captured variables. Is it true that "a capture" of a variable in lambda expression has the semantics of final fields? I was not able to find anything about it in JLS.

If the assumption is it is not true, then reads from fields of the val object are allowed to observe the default writes and thus observing "not completely initialized state" of the val object is allowed (unless this object itself is immutable, but let's assume it is not).

If the assumption about final fields semantics of captured variables is true, then the aforementioned code is equivalent to the following and is technically correct (but still has the aforementioned problem with an unbounded number of monitor acquire actions):

//comments are specified on some of the lines that have a somewhat corresponding analogous line in the first implementation
static <T> Supplier<T> memoize2(Supplier<T> original) {
  return new Supplier<>() {
    //still intentionally no volatile modifier
    FinalWrapper<T> delegate = null;//w1(delegate, null)

    public T get() {
      FinalWrapper<T> delegate = this.delegate; //r1(delegate, either null or captured), hb(w1, r1), not hb(w2, r1)
      if (delegate == null) {
        delegate = init();//yes, here we intentionally have the same problem of potentially always acquiring the monitor
      }
      return delegate.get();
    }

    private synchronized FinalWrapper<T> init() {
      FinalWrapper<T> delegate = this.delegate; //r2(delegate, either null or captured if hb(w2, r2)),
      if (delegate == null) { //if(!initialized)
        T val = original.get();
        this.delegate = //initialized = true;
            delegate = new FinalWrapper<>(val); //delegate = () -> val; w2(delegate, captured), hb(w1, w2)
      }
      return delegate;
    }
  };
}

static class FinalWrapper<T> {
  private final T val;

  FinalWrapper(T val) {
    this.val = val;
  }

  T get() {
    return val;
  }
}

Just repeating the question so that it does not slip through the cracks: Is it true that "a capture" of a variable in lambda expression has the semantics of final fields? If yes, does anyone knows if this is specified in the JLS?

Regards,
Valentin
LinkedIn   GitHub   YouTube

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: another lazy initialization, now with method reference

JSR166 Concurrency mailing list
On 8/22/19 4:35 PM, Valentin Kovalenko via Concurrency-interest wrote:

> Is it true that "a capture" of a variable in lambda expression has
> the semantics of final fields?

I think not.

> If yes, does anyone knows if this is specified in the JLS?

In 15.27.4. Run-Time Evaluation of Lambda Expressions, it's made clear
that

  "At run time, evaluation of a lambda expression is similar to
  evaluation of a class instance creation expression, insofar as
  normal completion produces a reference to an object. Evaluation of a
  lambda expression is distinct from execution of the lambda body.

  "Either a new instance of a class with the properties below is
  allocated and initialized, or an existing instance of a class with
  the properties below is referenced."

So, it is not guaranteed that an instance is generated, and therefore
it is not guaranteed that a final field is initialized.

--
Andrew Haley  (he/him)
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
https://keybase.io/andrewhaley
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: another lazy initialization, now with method reference

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Hi Andrew,

While it's true that https://docs.oracle.com/javase/specs/jls/se12/html/jls-15.html#jls-15.27.4 allows to not create a new instance each time a lambda expression is evaluated, it simply means that JLS allows returning a previously created instance as a result of evaluating a lambda expression. But I don't think this is relevant to the question of whether or not the semantics of final fields is applicable to the activity of capturing a variable and to the resulted field of a (generated) lambda-class (which I called "a capture" in the previous email). I still agree with your opinion that there is no such guarantee, I just don't think the argument you used is applicable.

While discussing this in "JavaSpecialists Slack Team" (https://www.javaspecialists.eu/slack/), the idea popped up to check if OpenJDK generates lambda-classes with final fields. If it does not, then we could definitely say "the semantics of final fields is not guaranteed" (assuming that OpenJDK JDK implementation does not violate the JLS); if it does, then we can only say "OpenJDK JDK does generate final fields to hold captured values", and we can't say anything about guarantees.

I conducted the experiment on openjdk 12.0.1 2019-04-16, and it does generate final fields, so we know that at least for now this implementation gives us the semantics of final fields for captured values. However, unless there is a statement about this in JLS/JVMS (I searched for "lambda" or "ACC_FINAL" in JVMS, but still did not find any information relevant to the question).

Here is the code for the experiment:

package stincmale.sandbox.examples;
import java.lang.reflect.Field;
import java.util.function.Supplier;
class LambdaFields {
  //run with -Djdk.internal.lambda.dumpProxyClasses=<location for dumping the generated classes>
  public static void main(String... args) {
    StringBuilder captureMe = new StringBuilder();
    Supplier<StringBuilder> s = () -> captureMe;
    for (Field field : s.getClass().getDeclaredFields()) {
      System.out.println(field);
    }
  }
}

output:
private final java.lang.StringBuilder stincmale.sandbox.examples.LambdaFields$$Lambda$14/0x000000080115e840.arg$1

We can also disassemble the generated lambda-class file and see the same final modifier on the field:
javap -p -c 'stincmale/sandbox/examples/LambdaFields$$Lambda$14' (your class name may be different)
output:
final class stincmale.sandbox.examples.LambdaFields$$Lambda$14 implements java.util.function.Supplier {
  private final java.lang.StringBuilder arg$1;
...

So we can see that OpenJDK generates final fields for the captured values, but this observation does not mean such behaviour is guaranteed by JLS/JVMS.

Regards,
Valentin
LinkedIn   GitHub   YouTube


On Fri, 23 Aug 2019 at 10:01, <[hidden email]> wrote:
Send Concurrency-interest mailing list submissions to
        [hidden email]

To subscribe or unsubscribe via the World Wide Web, visit
        http://cs.oswego.edu/mailman/listinfo/concurrency-interest
or, via email, send a message with subject or body 'help' to
        [hidden email]

You can reach the person managing the list at
        [hidden email]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Concurrency-interest digest..."


Today's Topics:

   1. Re: another lazy initialization, now with method reference
      (Andrew Haley)


----------------------------------------------------------------------

Message: 1
Date: Fri, 23 Aug 2019 09:50:15 +0100
From: Andrew Haley <[hidden email]>
To: Valentin Kovalenko <[hidden email]>,
        concurrency-interest <[hidden email]>
Subject: Re: [concurrency-interest] another lazy initialization, now
        with method reference
Message-ID: <[hidden email]>
Content-Type: text/plain; charset=utf-8

On 8/22/19 4:35 PM, Valentin Kovalenko via Concurrency-interest wrote:

> Is it true that "a capture" of a variable in lambda expression has
> the semantics of final fields?

I think not.

> If yes, does anyone knows if this is specified in the JLS?

In 15.27.4. Run-Time Evaluation of Lambda Expressions, it's made clear
that

  "At run time, evaluation of a lambda expression is similar to
  evaluation of a class instance creation expression, insofar as
  normal completion produces a reference to an object. Evaluation of a
  lambda expression is distinct from execution of the lambda body.

  "Either a new instance of a class with the properties below is
  allocated and initialized, or an existing instance of a class with
  the properties below is referenced."

So, it is not guaranteed that an instance is generated, and therefore
it is not guaranteed that a final field is initialized.

--
Andrew Haley  (he/him)
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
https://keybase.io/andrewhaley
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671


------------------------------

Subject: Digest Footer

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


------------------------------

End of Concurrency-interest Digest, Vol 174, Issue 6
****************************************************

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: another lazy initialization, now with method reference

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
It is true that whatever the lambda captures in the closure must be final or effectively final. You can easily see this at compile time, so I fully expect there to be a place in the spec devoted to this question.

It is also true that passing the lambda is safe publishing - it may be that it gets executed on a thread different from creation thread.

Now, given that the captured values are behaving as final, it only makes sense to implement them as final fields in the generated class. This, however, may be out of spec, in case lambda is not required to be implemented as a class with certain fields and methods. Still, safe publishing may be part of the spec.

Alex

On Thu, 22 Aug 2019, 16:39 Valentin Kovalenko via Concurrency-interest, <[hidden email]> wrote:
I bumped into the following lazy initialization code that tries to piggy-back on the assumption that captures of variables in lambda expressions have final fields semantics:

static <T> Supplier<T> memoize1(Supplier<T> original) {
  return new Supplier<>() {
    //notice the absence of the volatile modifier
    Supplier<T> delegate = this::init; //w1(delegate, init)
    boolean initialized;

    public T get() {
        return delegate.get(); //r1(delegate, either init or captured), hb(w1, r1), not hb(w2, r1)
    }

    private synchronized T init() {
        if(!initialized) {
            T val = original.get();
            delegate = () -> val; //w2(delegate, captured), hb(w1, w2)
            initialized = true;
            return val;
        }
        return delegate.get(); //r2(delegate, captured), hb(w2, r2)
    }
  };
}

Apparently, reads r1 are allowed to observe either the value written by w1, or the value written by w2 because there is no hb(w2, r1). Therefore, the get method is allowed to observe the result of w1 infinitely many times, hence acquiring the monitor per each invocation, which is not good. So this is a performance (not correctness) problem in the code above, but it's not the most interesting part.

A more interesting part of the code is the assumption about final fields semantics of captured variables. Is it true that "a capture" of a variable in lambda expression has the semantics of final fields? I was not able to find anything about it in JLS.

If the assumption is it is not true, then reads from fields of the val object are allowed to observe the default writes and thus observing "not completely initialized state" of the val object is allowed (unless this object itself is immutable, but let's assume it is not).

If the assumption about final fields semantics of captured variables is true, then the aforementioned code is equivalent to the following and is technically correct (but still has the aforementioned problem with an unbounded number of monitor acquire actions):

//comments are specified on some of the lines that have a somewhat corresponding analogous line in the first implementation
static <T> Supplier<T> memoize2(Supplier<T> original) {
  return new Supplier<>() {
    //still intentionally no volatile modifier
    FinalWrapper<T> delegate = null;//w1(delegate, null)

    public T get() {
      FinalWrapper<T> delegate = this.delegate; //r1(delegate, either null or captured), hb(w1, r1), not hb(w2, r1)
      if (delegate == null) {
        delegate = init();//yes, here we intentionally have the same problem of potentially always acquiring the monitor
      }
      return delegate.get();
    }

    private synchronized FinalWrapper<T> init() {
      FinalWrapper<T> delegate = this.delegate; //r2(delegate, either null or captured if hb(w2, r2)),
      if (delegate == null) { //if(!initialized)
        T val = original.get();
        this.delegate = //initialized = true;
            delegate = new FinalWrapper<>(val); //delegate = () -> val; w2(delegate, captured), hb(w1, w2)
      }
      return delegate;
    }
  };
}

static class FinalWrapper<T> {
  private final T val;

  FinalWrapper(T val) {
    this.val = val;
  }

  T get() {
    return val;
  }
}

Just repeating the question so that it does not slip through the cracks: Is it true that "a capture" of a variable in lambda expression has the semantics of final fields? If yes, does anyone knows if this is specified in the JLS?

Regards,
Valentin
LinkedIn   GitHub   YouTube
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: another lazy initialization, now with method reference

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
What this code does not achieve, is safe visibility of the constructed Supplier. Ie if it becomes visible to another thread through racy publishing, there is nothing to guarantee that the initial assignment of delegate occurred. Not that you have to guarantee that, but this is what it does not achieve, and the lambda does.

Alex

On Thu, 22 Aug 2019, 16:39 Valentin Kovalenko via Concurrency-interest, <[hidden email]> wrote:
I bumped into the following lazy initialization code that tries to piggy-back on the assumption that captures of variables in lambda expressions have final fields semantics:

static <T> Supplier<T> memoize1(Supplier<T> original) {
  return new Supplier<>() {
    //notice the absence of the volatile modifier
    Supplier<T> delegate = this::init; //w1(delegate, init)
    boolean initialized;

    public T get() {
        return delegate.get(); //r1(delegate, either init or captured), hb(w1, r1), not hb(w2, r1)
    }

    private synchronized T init() {
        if(!initialized) {
            T val = original.get();
            delegate = () -> val; //w2(delegate, captured), hb(w1, w2)
            initialized = true;
            return val;
        }
        return delegate.get(); //r2(delegate, captured), hb(w2, r2)
    }
  };
}

Apparently, reads r1 are allowed to observe either the value written by w1, or the value written by w2 because there is no hb(w2, r1). Therefore, the get method is allowed to observe the result of w1 infinitely many times, hence acquiring the monitor per each invocation, which is not good. So this is a performance (not correctness) problem in the code above, but it's not the most interesting part.

A more interesting part of the code is the assumption about final fields semantics of captured variables. Is it true that "a capture" of a variable in lambda expression has the semantics of final fields? I was not able to find anything about it in JLS.

If the assumption is it is not true, then reads from fields of the val object are allowed to observe the default writes and thus observing "not completely initialized state" of the val object is allowed (unless this object itself is immutable, but let's assume it is not).

If the assumption about final fields semantics of captured variables is true, then the aforementioned code is equivalent to the following and is technically correct (but still has the aforementioned problem with an unbounded number of monitor acquire actions):

//comments are specified on some of the lines that have a somewhat corresponding analogous line in the first implementation
static <T> Supplier<T> memoize2(Supplier<T> original) {
  return new Supplier<>() {
    //still intentionally no volatile modifier
    FinalWrapper<T> delegate = null;//w1(delegate, null)

    public T get() {
      FinalWrapper<T> delegate = this.delegate; //r1(delegate, either null or captured), hb(w1, r1), not hb(w2, r1)
      if (delegate == null) {
        delegate = init();//yes, here we intentionally have the same problem of potentially always acquiring the monitor
      }
      return delegate.get();
    }

    private synchronized FinalWrapper<T> init() {
      FinalWrapper<T> delegate = this.delegate; //r2(delegate, either null or captured if hb(w2, r2)),
      if (delegate == null) { //if(!initialized)
        T val = original.get();
        this.delegate = //initialized = true;
            delegate = new FinalWrapper<>(val); //delegate = () -> val; w2(delegate, captured), hb(w1, w2)
      }
      return delegate;
    }
  };
}

static class FinalWrapper<T> {
  private final T val;

  FinalWrapper(T val) {
    this.val = val;
  }

  T get() {
    return val;
  }
}

Just repeating the question so that it does not slip through the cracks: Is it true that "a capture" of a variable in lambda expression has the semantics of final fields? If yes, does anyone knows if this is specified in the JLS?

Regards,
Valentin
LinkedIn   GitHub   YouTube
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: another lazy initialization, now with method reference

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Hi Alex,

> It is true that whatever the lambda captures in the closure must be final
> or effectively final. You can easily see this at compile time, so I fully
> expect there to be a place in the spec devoted to this question.
Absolutely, and https://docs.oracle.com/javase/specs/jls/se12/html/jls-15.html#jls-15.27.2 specifies this. This part is obvious.

> It is also true that passing the lambda is safe publishing - it may be that
> it gets executed on a thread different from creation thread.
I agree that an immediate receiver of the result of a lambda expression must be guaranteed to observe a fully-initialized object. Otherwise, the implementation of lambda expressions is just broken. However, can we expect safe publishing in a situation when the application code then re-publishes this object via a data race (as we would have with the semantics of final fields)? I think we cannot, because an implementation that does not provide such a guarantee would not violate JLS.

> Now, given that the captured values are behaving as final, it only makes
> sense to implement them as final fields in the generated class.
It totally makes sense. But making sense and being guaranteed are different things. The same is applicable to variables captured by anonymous classes: again OpenJDK uses final fields to represent them, and it makes sense. But removing the final modifier would have not violated any requirements of the specification (at least I am failing to find any of requirements that would have been violated if the final modifier were not there).

> This,
> however, may be out of spec, in case lambda is not required to be
> implemented as a class with certain fields and methods. Still, safe
> publishing may be part of the spec.
As I mentioned above, the question is not about safe publishing of the object from "an evaluator of a lambda expression" to "a direct receiver of the result of a lambda expression", but about guarantees we have (or don't have) while re-publishing such a result via a data race. It would be great to have such a guarantee specified in JLS for both the results of lambda expressions and for the captured part of the state of anonymous classes, but it seems like it is not there.

Regards,
Valentin
LinkedIn   GitHub   YouTube

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: another lazy initialization, now with method reference

JSR166 Concurrency mailing list
Hi Alex,

> It is true that whatever the lambda captures in the closure must be final
> or effectively final. You can easily see this at compile time, so I fully
> expect there to be a place in the spec devoted to this question.
Absolutely, and https://docs.oracle.com/javase/specs/jls/se12/html/jls-15.html#jls-15.27.2 specifies this. This part is obvious.

> It is also true that passing the lambda is safe publishing - it may be that
> it gets executed on a thread different from creation thread.
I agree that an immediate receiver of the result of a lambda expression must be guaranteed to observe a fully-initialized object. Otherwise, the implementation of lambda expressions is just broken. However, can we expect safe publishing in a situation when the application code then re-publishes this object via a data race (as we would have with the semantics of final fields)? I think we cannot, because an implementation that does not provide such a guarantee would not violate JLS.

> Now, given that the captured values are behaving as final, it only makes
> sense to implement them as final fields in the generated class.
It totally makes sense. But making sense and being guaranteed are different things. The same is applicable to variables captured by anonymous classes: again OpenJDK uses final fields to represent them, and it makes sense. But removing the final modifier would have not violated any requirements of the specification (at least I am failing to find any of requirements that would have been violated if the final modifier were not there).

> This,
> however, may be out of spec, in case lambda is not required to be
> implemented as a class with certain fields and methods. Still, safe
> publishing may be part of the spec.
As I mentioned above, the question is not about safe publishing of the object from "an evaluator of a lambda expression" to "a direct receiver of the result of a lambda expression", but about guarantees we have (or don't have) while re-publishing such a result via a data race. It would be great to have such a guarantee specified in JLS for both the results of lambda expressions and for the captured part of the state of anonymous classes, but it seems like it is not there.

Regards,
Valentin
LinkedIn   GitHub   YouTube

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest