Lazy fetching and volatile fields

[Ashwin Jayaprakash-2]

Some parts of this message have been removed. Learn more about Nabble's security policy.

I'm trying to create a "lazy-retriever handle" for some expensive objects and I'm looking for some validation on its design:

1) A handle can be "fetched" lazily by any thread that has a reference to it. So, there are multiple threads that share a handle

2) Once a thread fetches the actual object, it gets stored in the volatile field which will then become visible to all other threads using the handle

3) Based on my understanding of volatiles, I thought I could optimize it. Pls tell me if this is valid:
    a) The handle has 2 fields - one that is volatile and another that is not. Both will eventually point to the same actual "fetched" object

    b) Since the "getActual()" is called frequently, each thread first checks its non-volatile field to avoid a volatile read

    c) If the non-volatile field is null, then it checks the volatile field to see if any other thread fetched it recently

    d) If the volatile field is also null, then acquire a lock or use some other implementation in the "fetch()" method and store it into the volatile field. "fetch()" is abstract for now to avoid any diversions

    e) Now store the actual object into the non-volatile field. For this thread at least we will not need any volatile reads in future because we have read it into the non-volatile field

Questions:
1) Will this work?
2) Are the performance assumptions correct?
3) Is this really necessary? :) I do not have access to a super-multi-core thingy to verify this
4) Should I pad the volatile into a different cache-line to avoid cache ping-ponging?

 1 package temp;

 2 

 3 public abstract class AbstractLazyHandle<T> {

 4     protected T nonVolatileActual;

 5 

 6     protected volatile T actual;

 7 

 8     public AbstractLazyHandle() {

 9     }

10 

11     public T getActual() {

12         if (nonVolatileActual != null) {

13             return nonVolatileActual;

14         }

15 

16         //--------------

17 

18         //Fetch it into the volatile field.

19         fetch();

20 

21         //Then cache it into a regular field.

22         nonVolatileActual = actual;

23 

24         return nonVolatileActual;

25     }

26 

27     protected abstract T fetch();

28 }

29 

Thanks!
Ashwin (http://www.ashwinjayaprakash.com)

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Boehm, Hans]

Some parts of this message have been removed. Learn more about Nabble's security policy.

 

---

From: concurrency-interest-bounces@... [mailto:concurrency-interest-bounces@...] On Behalf Of Ashwin Jayaprakash
Sent: Friday, October 30, 2009 4:26 PM
To: concurrency-interest@...
Subject: [concurrency-interest] Lazy fetching and volatile fields

I'm trying to create a "lazy-retriever handle" for some expensive objects and I'm looking for some validation on its design:

1) A handle can be "fetched" lazily by any thread that has a reference to it. So, there are multiple threads that share a handle

2) Once a thread fetches the actual object, it gets stored in the volatile field which will then become visible to all other threads using the handle

3) Based on my understanding of volatiles, I thought I could optimize it. Pls tell me if this is valid:
    a) The handle has 2 fields - one that is volatile and another that is not. Both will eventually point to the same actual "fetched" object

    b) Since the "getActual()" is called frequently, each thread first checks its non-volatile field to avoid a volatile read

    c) If the non-volatile field is null, then it checks the volatile field to see if any other thread fetched it recently

    d) If the volatile field is also null, then acquire a lock or use some other implementation in the "fetch()" method and store it into the volatile field. "fetch()" is abstract for now to avoid any diversions

    e) Now store the actual object into the non-volatile field. For this thread at least we will not need any volatile reads in future because we have read it into the non-volatile field

Questions:
1) Will this work? 

 

Not really, though it may appear to.  At least if I understand correctly.  If you get the non-volatile copy of a non-null handle, there is no guarantee that the object it refers to has been completely constructed.  The handle may become visible before the object itself.

 
2) Are the performance assumptions correct? 

 

Depends on the archiecture.  On X86, I believe the answer is no.  The cost of a volatile read shouldn't be much different from an ordinary one.  On other architectures that can be substantially different.

 
3) Is this really necessary? :) I do not have access to a super-multi-core thingy to verify this 

 

I would just use a volatile for the frequently accessed version of the handle and be done with it.

 
4) Should I pad the volatile into a different cache-line to avoid cache ping-ponging? 

 

A volatile read shouldn't require exclusive access to the cache line.  Once things are initialized, I don't see why it should matter.

 

Hans 

 1 package temp;

 2 

 3 public abstract class AbstractLazyHandle<T> {

 4     protected T nonVolatileActual;

 5 

 6     protected volatile T actual;

 7 

 8     public AbstractLazyHandle() {

 9     }

10 

11     public T getActual() {

12         if (nonVolatileActual != null) {

13             return nonVolatileActual;

14         }

15 

16         //--------------

17 

18         //Fetch it into the volatile field.

19         fetch();

20 

21         //Then cache it into a regular field.

22         nonVolatileActual = actual;

23 

24         return nonVolatileActual;

25     }

26 

27     protected abstract T fetch();

28 }

29 

Thanks!
Ashwin (http://www.ashwinjayaprakash.com)

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Joe Bowbeer]

On Fri, Oct 30, 2009 at 4:26 PM, Ashwin Jayaprakash wrote:

I'm trying to create a "lazy-retriever handle" for some expensive objects and I'm looking for some validation on its design:

In addition to what Hans wrote:

The 'actual' volatile isn't assigned in the code snippet; I'm assuming the code should read:

  actual = fetch();

The code as written will allow multiple fetch() invocations to execute concurrently.  Is this a problem?

Joe

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Ashwin Jayaprakash-2]

Hans, you said:

1) Will this work? 

 

Not really, though it may appear to.  At least if I understand correctly.  If you get the non-volatile copy of a non-null handle, there is no guarantee that the object it refers to has been completely constructed.  The handle may become visible before the object itself.

Since I copy the value from the volatile to the non-volatile field, why would the volatile field have the incomplete object in the first place? If I use locks to write to the volatile field I shouldn't have such problems, right?


Thanks!
Ashwin (http://www.ashwinjayaprakash.com)

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Boehm, Hans]

I'm not sure I have a completely accurate picture of what you're doing.  But on the fast path, it's presumably something like:

 

1. Read non-volatile field containing reference to object x.

2. Access non-final field x.f

 

The memory model does not guarantee that these will happen in order, though it's difficult to construct scenarios in which they won't be, except on obsolete hardware.  A hypothetical clever compiler or hypothetical clever hardware could transform this to:

 

1. Make a good guess for what x will be.  Read x_predicted.f, and then x.

2. Verify that x_predicted == x.

 

This would read x and x.f in the wrong order if it guessed right.

 

Probably more realistically, I'm not at all sure that there's anything preventing the reordering of

 

- object initialization and assignment to the volatile field

- assignment to the non-volatile field

 

But I don't have a clear picture of your code in mind.

 

Hans

---

From: Ashwin Jayaprakash [mailto:ashwin.jayaprakash@...]
Sent: Friday, October 30, 2009 5:30 PM
To: Boehm, Hans
Cc: concurrency-interest@...
Subject: Re: [concurrency-interest] Lazy fetching and volatile fields

Hans, you said:

1) Will this work? 

 

Not really, though it may appear to.  At least if I understand correctly.  If you get the non-volatile copy of a non-null handle, there is no guarantee that the object it refers to has been completely constructed.  The handle may become visible before the object itself.

Since I copy the value from the volatile to the non-volatile field, why would the volatile field have the incomplete object in the first place? If I use locks to write to the volatile field I shouldn't have such problems, right?


Thanks!
Ashwin (http://www.ashwinjayaprakash.com)

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Ashwin Jayaprakash-2]

All I'd do in the fetch() method would be to create the heavy object and set it to the volatile field. So, why would the fields get re-ordered even with the use of volatiles and a sync block? Or am I treading into the dreaded double-checked-lock bug?

protected T fetch(){
   T newActual = null;

   synchronized(this){
     newActual = new T();
   }

   //Set to volatile field
   actual = newActual;

   return newActual;
}

public T getActual() {
   if (nonVolatileActual != null) {
      return nonVolatileActual;
   }

   //Fetch it into the volatile field.
   fetch();

   //Then cache it into a regular field. (Or, just do nonVolatileActual = fetch() directly)
   nonVolatileActual = actual;

   return nonVolatileActual;
}

On Fri, Oct 30, 2009 at 6:16 PM, Boehm, Hans <hans.boehm@...> wrote:

I'm not sure I have a completely accurate picture of what you're doing.  But on the fast path, it's presumably something like:

 

1. Read non-volatile field containing reference to object x.

2. Access non-final field x.f

 

The memory model does not guarantee that these will happen in order, though it's difficult to construct scenarios in which they won't be, except on obsolete hardware.  A hypothetical clever compiler or hypothetical clever hardware could transform this to:

 

1. Make a good guess for what x will be.  Read x_predicted.f, and then x.

2. Verify that x_predicted == x.

 

This would read x and x.f in the wrong order if it guessed right.

 

Probably more realistically, I'm not at all sure that there's anything preventing the reordering of

 

- object initialization and assignment to the volatile field

- assignment to the non-volatile field

 

But I don't have a clear picture of your code in mind.

 

Hans

---

From: Ashwin Jayaprakash [mailto:ashwin.jayaprakash@...]
Sent: Friday, October 30, 2009 5:30 PM
To: Boehm, Hans
Cc: concurrency-interest@...
Subject: Re: [concurrency-interest] Lazy fetching and volatile fields

Hans, you said:

1) Will this work? 

 

Not really, though it may appear to.  At least if I understand correctly.  If you get the non-volatile copy of a non-null handle, there is no guarantee that the object it refers to has been completely constructed.  The handle may become visible before the object itself.

Since I copy the value from the volatile to the non-volatile field, why would the volatile field have the incomplete object in the first place? If I use locks to write to the volatile field I shouldn't have such problems, right?


Thanks!
Ashwin (http://www.ashwinjayaprakash.com)

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Ashwin Jayaprakash-2]

I was going to add that for now fetch() will get invoked multiple times. If we can ignore that for the moment, would the volatile field still get read before the sync block? I guess it would, but I missed what Hans was saying. In which case the volatile will still be null and the code would get a null assigned to nonVolatileActual...I guess. So, the only option would be to run it in a loop until the field is not null.

Is all this worth it? :)

On Sat, Oct 31, 2009 at 12:31 AM, Ashwin Jayaprakash <ashwin.jayaprakash@...> wrote:

All I'd do in the fetch() method would be to create the heavy object and set it to the volatile field. So, why would the fields get re-ordered even with the use of volatiles and a sync block? Or am I treading into the dreaded double-checked-lock bug?

protected T fetch(){
   T newActual = null;

   synchronized(this){
     newActual = new T();
   }

   //Set to volatile field
   actual = newActual;

   return newActual;
}

public T getActual() {
   if (nonVolatileActual != null) {
      return nonVolatileActual;
   }

   //Fetch it into the volatile field.
   fetch();

   //Then cache it into a regular field. (Or, just do nonVolatileActual = fetch() directly)
   nonVolatileActual = actual;

   return nonVolatileActual;

}

On Fri, Oct 30, 2009 at 6:16 PM, Boehm, Hans <hans.boehm@...> wrote:

I'm not sure I have a completely accurate picture of what you're doing.  But on the fast path, it's presumably something like:

 

1. Read non-volatile field containing reference to object x.

2. Access non-final field x.f

 

The memory model does not guarantee that these will happen in order, though it's difficult to construct scenarios in which they won't be, except on obsolete hardware.  A hypothetical clever compiler or hypothetical clever hardware could transform this to:

 

1. Make a good guess for what x will be.  Read x_predicted.f, and then x.

2. Verify that x_predicted == x.

 

This would read x and x.f in the wrong order if it guessed right.

 

Probably more realistically, I'm not at all sure that there's anything preventing the reordering of

 

- object initialization and assignment to the volatile field

- assignment to the non-volatile field

 

But I don't have a clear picture of your code in mind.

 

Hans

---

From: Ashwin Jayaprakash [mailto:ashwin.jayaprakash@...]
Sent: Friday, October 30, 2009 5:30 PM
To: Boehm, Hans
Cc: concurrency-interest@...
Subject: Re: [concurrency-interest] Lazy fetching and volatile fields

Hans, you said:

1) Will this work? 

 

Not really, though it may appear to.  At least if I understand correctly.  If you get the non-volatile copy of a non-null handle, there is no guarantee that the object it refers to has been completely constructed.  The handle may become visible before the object itself.

Since I copy the value from the volatile to the non-volatile field, why would the volatile field have the incomplete object in the first place? If I use locks to write to the volatile field I shouldn't have such problems, right?


Thanks!
Ashwin (http://www.ashwinjayaprakash.com)

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Boehm, Hans]

I suspect that if you assign to the volatile first, then reread it, and assign to the non-volatile, you're probably at the point at which conventional implementations won't break your code on conventional hardware.  However, the memory model still gives you no guarantees:  The problem is that a thread setting actual does not synchronize with a thread just accessing nonVolatileActual.  Thus there is no guarantee that the second thread will see a properly initialized T eventhough nonVolatileActual is nonzero.  Thus a clever implementation, or one on strange hardware, may still break your code.  And it's quite possible I'm overlooking a reason even a conventional implementation will break something.

 

In fact Java non-volatile semantics are so weak that you have yet another problem:

 

The code

 

if (nonVolatileActual != null) {
      return nonVolatileActual;

}

may return null, since the second load of nonVolatileActual may yield an "earlier" value.  This is fixable by loading it only once into a temporary.

 

Just say "no" to data races.   I definitely wouldn't consider anything along these lines unless you have a demonstrable performance problem.  Even then, I'd be inclined to first try caching in a thread-local, rather than a shared non-volatile variable.  Again, I think this makes no sense at all on something like X86 where volatile loads should be cheap.

 

Hans

---

From: concurrency-interest-bounces@... [mailto:concurrency-interest-bounces@...] On Behalf Of Ashwin Jayaprakash
Sent: Saturday, October 31, 2009 12:42 AM
To: concurrency-interest@...
Subject: Re: [concurrency-interest] Lazy fetching and volatile fields

I was going to add that for now fetch() will get invoked multiple times. If we can ignore that for the moment, would the volatile field still get read before the sync block? I guess it would, but I missed what Hans was saying. In which case the volatile will still be null and the code would get a null assigned to nonVolatileActual...I guess. So, the only option would be to run it in a loop until the field is not null.

Is all this worth it? :)

On Sat, Oct 31, 2009 at 12:31 AM, Ashwin Jayaprakash <ashwin.jayaprakash@...> wrote:

All I'd do in the fetch() method would be to create the heavy object and set it to the volatile field. So, why would the fields get re-ordered even with the use of volatiles and a sync block? Or am I treading into the dreaded double-checked-lock bug?

protected T fetch(){
   T newActual = null;

   synchronized(this){
     newActual = new T();
   }

   //Set to volatile field
   actual = newActual;

   return newActual;
}

public T getActual() {
   if (nonVolatileActual != null) {
      return nonVolatileActual;
   }

   //Fetch it into the volatile field.
   fetch();

   //Then cache it into a regular field. (Or, just do nonVolatileActual = fetch() directly)
   nonVolatileActual = actual;

   return nonVolatileActual;

}

On Fri, Oct 30, 2009 at 6:16 PM, Boehm, Hans <hans.boehm@...> wrote:

I'm not sure I have a completely accurate picture of what you're doing.  But on the fast path, it's presumably something like:

 

1. Read non-volatile field containing reference to object x.

2. Access non-final field x.f

 

The memory model does not guarantee that these will happen in order, though it's difficult to construct scenarios in which they won't be, except on obsolete hardware.  A hypothetical clever compiler or hypothetical clever hardware could transform this to:

 

1. Make a good guess for what x will be.  Read x_predicted.f, and then x.

2. Verify that x_predicted == x.

 

This would read x and x.f in the wrong order if it guessed right.

 

Probably more realistically, I'm not at all sure that there's anything preventing the reordering of

 

- object initialization and assignment to the volatile field

- assignment to the non-volatile field

 

But I don't have a clear picture of your code in mind.

 

Hans

---

From: Ashwin Jayaprakash [mailto:ashwin.jayaprakash@...]
Sent: Friday, October 30, 2009 5:30 PM
To: Boehm, Hans
Cc: concurrency-interest@...
Subject: Re: [concurrency-interest] Lazy fetching and volatile fields

Hans, you said:

1) Will this work? 

 

Not really, though it may appear to.  At least if I understand correctly.  If you get the non-volatile copy of a non-null handle, there is no guarantee that the object it refers to has been completely constructed.  The handle may become visible before the object itself.

Since I copy the value from the volatile to the non-volatile field, why would the volatile field have the incomplete object in the first place? If I use locks to write to the volatile field I shouldn't have such problems, right?


Thanks!
Ashwin (http://www.ashwinjayaprakash.com)

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest