CopyOnWriteArrayList vs ReentrantLock

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

CopyOnWriteArrayList vs ReentrantLock

Vladimir Sitnikov
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.

2) Can initial state (new Object[0]) be reused instead of creating new
Object[0] for each COWAL?
Plain old ArrayList does that, so I wonder why COWList misses the optimization.

[1]: https://gist.github.com/vlsi/3afe92a7f6449cc1692d

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

Re: CopyOnWriteArrayList vs ReentrantLock

Martin Buchholz-3
I think COWAL (and other classes in j.u.c.) could/should use builtin synchronization as you suggest, to save 32 bytes (Doug, do you agree?). 

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not provide, like condition objects.

On Sat, Jan 24, 2015 at 9:58 AM, Vladimir Sitnikov <[hidden email]> wrote:
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.



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

Re: CopyOnWriteArrayList vs ReentrantLock

Benedict Elliott Smith-3
For lists smaller than a (low) preconfigured limit, why not use a simple CAS-loop? When above this size a lock (of either variety) could be inflated, at which point the memory cost is much less significant since it is no longer dwarfing the other state. 

It may even yield superior performance to boot.

On 24 January 2015 at 20:56, Martin Buchholz <[hidden email]> wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin synchronization as you suggest, to save 32 bytes (Doug, do you agree?). 

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not provide, like condition objects.

On Sat, Jan 24, 2015 at 9:58 AM, Vladimir Sitnikov <[hidden email]> wrote:
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.



_______________________________________________
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: CopyOnWriteArrayList vs ReentrantLock

Vitaly Davidovich

Why not *always* use a CAS loop? The use case for COWAL is such that mutation is fairly rare and should not have contention.

sent from my phone

On Jan 24, 2015 5:22 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
For lists smaller than a (low) preconfigured limit, why not use a simple CAS-loop? When above this size a lock (of either variety) could be inflated, at which point the memory cost is much less significant since it is no longer dwarfing the other state. 

It may even yield superior performance to boot.

On 24 January 2015 at 20:56, Martin Buchholz <[hidden email]> wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin synchronization as you suggest, to save 32 bytes (Doug, do you agree?). 

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not provide, like condition objects.

On Sat, Jan 24, 2015 at 9:58 AM, Vladimir Sitnikov <[hidden email]> wrote:
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.



_______________________________________________
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


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

Re: CopyOnWriteArrayList vs ReentrantLock

Benedict Elliott Smith-3
Changing this under the feet of existing users could be problematic in some scenarios. As the list grows the cost under contention scales disproportionately, as both the incidence and cost of failed CAS increases. There's not a lot to be gained from CAS-spinning on modification to a list with tens of thousands of elements, and for even larger lists there could be significant costs. There are likely users with such lists. Below that size, there's still the potential for significant garbage allocation, which may be undesirable by comparison to accepting lower modification speed. 


On 25 January 2015 at 00:05, Vitaly Davidovich <[hidden email]> wrote:

Why not *always* use a CAS loop? The use case for COWAL is such that mutation is fairly rare and should not have contention.

sent from my phone

On Jan 24, 2015 5:22 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
For lists smaller than a (low) preconfigured limit, why not use a simple CAS-loop? When above this size a lock (of either variety) could be inflated, at which point the memory cost is much less significant since it is no longer dwarfing the other state. 

It may even yield superior performance to boot.

On 24 January 2015 at 20:56, Martin Buchholz <[hidden email]> wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin synchronization as you suggest, to save 32 bytes (Doug, do you agree?). 

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not provide, like condition objects.

On Sat, Jan 24, 2015 at 9:58 AM, Vladimir Sitnikov <[hidden email]> wrote:
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.



_______________________________________________
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



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

Re: CopyOnWriteArrayList vs ReentrantLock

Vitaly Davidovich

As the list grows, CAS only becomes a problem if you have lots of mutator threads involved.  Yes, the window during which someone can come in and change the list while you're doing a copy is expanded, but this is a memcpy-like operation behind the scenes.  There may be users out there mutating these things extensively, but they're probably already feeling the GC effects.

The upside of CAS is there's no additional storage cost for any type of lock, and if one were to use builtin monitor and it inflates, I think that has some effect on GC where inflated monitors are reclaimed.

sent from my phone

On Jan 24, 2015 7:16 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
Changing this under the feet of existing users could be problematic in some scenarios. As the list grows the cost under contention scales disproportionately, as both the incidence and cost of failed CAS increases. There's not a lot to be gained from CAS-spinning on modification to a list with tens of thousands of elements, and for even larger lists there could be significant costs. There are likely users with such lists. Below that size, there's still the potential for significant garbage allocation, which may be undesirable by comparison to accepting lower modification speed. 


On 25 January 2015 at 00:05, Vitaly Davidovich <[hidden email]> wrote:

Why not *always* use a CAS loop? The use case for COWAL is such that mutation is fairly rare and should not have contention.

sent from my phone

On Jan 24, 2015 5:22 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
For lists smaller than a (low) preconfigured limit, why not use a simple CAS-loop? When above this size a lock (of either variety) could be inflated, at which point the memory cost is much less significant since it is no longer dwarfing the other state. 

It may even yield superior performance to boot.

On 24 January 2015 at 20:56, Martin Buchholz <[hidden email]> wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin synchronization as you suggest, to save 32 bytes (Doug, do you agree?). 

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not provide, like condition objects.

On Sat, Jan 24, 2015 at 9:58 AM, Vladimir Sitnikov <[hidden email]> wrote:
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.



_______________________________________________
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



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

Re: CopyOnWriteArrayList vs ReentrantLock

Benedict Elliott Smith-3
Right. My point is not everyone uses the API "correctly" (i.e. in situations with mutator counts approaching zero), and these users could be badly affected by such a change. Since once you get above a few tens of thousands of items the costs are on the same order of magnitude as parking/unparking, but without any risk associated with many competing updates, it seems reasonable to leave the current behaviour in place at least in this situation.

On 25 January 2015 at 00:25, Vitaly Davidovich <[hidden email]> wrote:

As the list grows, CAS only becomes a problem if you have lots of mutator threads involved.  Yes, the window during which someone can come in and change the list while you're doing a copy is expanded, but this is a memcpy-like operation behind the scenes.  There may be users out there mutating these things extensively, but they're probably already feeling the GC effects.

The upside of CAS is there's no additional storage cost for any type of lock, and if one were to use builtin monitor and it inflates, I think that has some effect on GC where inflated monitors are reclaimed.

sent from my phone

On Jan 24, 2015 7:16 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
Changing this under the feet of existing users could be problematic in some scenarios. As the list grows the cost under contention scales disproportionately, as both the incidence and cost of failed CAS increases. There's not a lot to be gained from CAS-spinning on modification to a list with tens of thousands of elements, and for even larger lists there could be significant costs. There are likely users with such lists. Below that size, there's still the potential for significant garbage allocation, which may be undesirable by comparison to accepting lower modification speed. 


On 25 January 2015 at 00:05, Vitaly Davidovich <[hidden email]> wrote:

Why not *always* use a CAS loop? The use case for COWAL is such that mutation is fairly rare and should not have contention.

sent from my phone

On Jan 24, 2015 5:22 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
For lists smaller than a (low) preconfigured limit, why not use a simple CAS-loop? When above this size a lock (of either variety) could be inflated, at which point the memory cost is much less significant since it is no longer dwarfing the other state. 

It may even yield superior performance to boot.

On 24 January 2015 at 20:56, Martin Buchholz <[hidden email]> wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin synchronization as you suggest, to save 32 bytes (Doug, do you agree?). 

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not provide, like condition objects.

On Sat, Jan 24, 2015 at 9:58 AM, Vladimir Sitnikov <[hidden email]> wrote:
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.



_______________________________________________
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




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

Re: CopyOnWriteArrayList vs ReentrantLock

Vitaly Davidovich

Well, I guess I'm less sympathetic to misusers :) I was thinking for the intended (and majority, I'd hope) use cases, you get the best memory wise outcome by not having any lock object.

The issue with CAS below some threshold and lock above is you still need the lock object; if you allocate it lazily (with CAS!), you'd still pay price of reserving (possibly compressed) size of pointer.  And if you shrink the list back down below threshold, do you null out the lock or keep it? You'd also introduce a branch into these methods.

Also, I haven't verified this, but at current memory bandwidths, I doubt memcpy cost of a few tens of thousands of pointers is equal to park and unpark costs.

Anyway, I'm +1 on at least replacing lock with builtin monitor.

sent from my phone

On Jan 24, 2015 7:30 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
Right. My point is not everyone uses the API "correctly" (i.e. in situations with mutator counts approaching zero), and these users could be badly affected by such a change. Since once you get above a few tens of thousands of items the costs are on the same order of magnitude as parking/unparking, but without any risk associated with many competing updates, it seems reasonable to leave the current behaviour in place at least in this situation.

On 25 January 2015 at 00:25, Vitaly Davidovich <[hidden email]> wrote:

As the list grows, CAS only becomes a problem if you have lots of mutator threads involved.  Yes, the window during which someone can come in and change the list while you're doing a copy is expanded, but this is a memcpy-like operation behind the scenes.  There may be users out there mutating these things extensively, but they're probably already feeling the GC effects.

The upside of CAS is there's no additional storage cost for any type of lock, and if one were to use builtin monitor and it inflates, I think that has some effect on GC where inflated monitors are reclaimed.

sent from my phone

On Jan 24, 2015 7:16 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
Changing this under the feet of existing users could be problematic in some scenarios. As the list grows the cost under contention scales disproportionately, as both the incidence and cost of failed CAS increases. There's not a lot to be gained from CAS-spinning on modification to a list with tens of thousands of elements, and for even larger lists there could be significant costs. There are likely users with such lists. Below that size, there's still the potential for significant garbage allocation, which may be undesirable by comparison to accepting lower modification speed. 


On 25 January 2015 at 00:05, Vitaly Davidovich <[hidden email]> wrote:

Why not *always* use a CAS loop? The use case for COWAL is such that mutation is fairly rare and should not have contention.

sent from my phone

On Jan 24, 2015 5:22 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
For lists smaller than a (low) preconfigured limit, why not use a simple CAS-loop? When above this size a lock (of either variety) could be inflated, at which point the memory cost is much less significant since it is no longer dwarfing the other state. 

It may even yield superior performance to boot.

On 24 January 2015 at 20:56, Martin Buchholz <[hidden email]> wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin synchronization as you suggest, to save 32 bytes (Doug, do you agree?). 

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not provide, like condition objects.

On Sat, Jan 24, 2015 at 9:58 AM, Vladimir Sitnikov <[hidden email]> wrote:
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.



_______________________________________________
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




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

Re: CopyOnWriteArrayList vs ReentrantLock

Benedict Elliott Smith-3

For modifications by index, quite likely. But since that's not going to be atomic, the only such operation commonly used is likely to be append, surely? Many of the other common operations likely entail less efficient work.

Due to object padding, the reference for the unallocated lock is free on many VMs, but even if not it's pretty insignificant by comparison to the other fixed costs.

On 25 Jan 2015 00:41, "Vitaly Davidovich" <[hidden email]> wrote:

Well, I guess I'm less sympathetic to misusers :) I was thinking for the intended (and majority, I'd hope) use cases, you get the best memory wise outcome by not having any lock object.

The issue with CAS below some threshold and lock above is you still need the lock object; if you allocate it lazily (with CAS!), you'd still pay price of reserving (possibly compressed) size of pointer.  And if you shrink the list back down below threshold, do you null out the lock or keep it? You'd also introduce a branch into these methods.

Also, I haven't verified this, but at current memory bandwidths, I doubt memcpy cost of a few tens of thousands of pointers is equal to park and unpark costs.

Anyway, I'm +1 on at least replacing lock with builtin monitor.

sent from my phone

On Jan 24, 2015 7:30 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
Right. My point is not everyone uses the API "correctly" (i.e. in situations with mutator counts approaching zero), and these users could be badly affected by such a change. Since once you get above a few tens of thousands of items the costs are on the same order of magnitude as parking/unparking, but without any risk associated with many competing updates, it seems reasonable to leave the current behaviour in place at least in this situation.

On 25 January 2015 at 00:25, Vitaly Davidovich <[hidden email]> wrote:

As the list grows, CAS only becomes a problem if you have lots of mutator threads involved.  Yes, the window during which someone can come in and change the list while you're doing a copy is expanded, but this is a memcpy-like operation behind the scenes.  There may be users out there mutating these things extensively, but they're probably already feeling the GC effects.

The upside of CAS is there's no additional storage cost for any type of lock, and if one were to use builtin monitor and it inflates, I think that has some effect on GC where inflated monitors are reclaimed.

sent from my phone

On Jan 24, 2015 7:16 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
Changing this under the feet of existing users could be problematic in some scenarios. As the list grows the cost under contention scales disproportionately, as both the incidence and cost of failed CAS increases. There's not a lot to be gained from CAS-spinning on modification to a list with tens of thousands of elements, and for even larger lists there could be significant costs. There are likely users with such lists. Below that size, there's still the potential for significant garbage allocation, which may be undesirable by comparison to accepting lower modification speed. 


On 25 January 2015 at 00:05, Vitaly Davidovich <[hidden email]> wrote:

Why not *always* use a CAS loop? The use case for COWAL is such that mutation is fairly rare and should not have contention.

sent from my phone

On Jan 24, 2015 5:22 PM, "Benedict Elliott Smith" <[hidden email]> wrote:
For lists smaller than a (low) preconfigured limit, why not use a simple CAS-loop? When above this size a lock (of either variety) could be inflated, at which point the memory cost is much less significant since it is no longer dwarfing the other state. 

It may even yield superior performance to boot.

On 24 January 2015 at 20:56, Martin Buchholz <[hidden email]> wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin synchronization as you suggest, to save 32 bytes (Doug, do you agree?). 

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not provide, like condition objects.

On Sat, Jan 24, 2015 at 9:58 AM, Vladimir Sitnikov <[hidden email]> wrote:
Hi,

I am looking into sources of CopyOnWriteArrayList in java 1.8u40 and
it looks strange to see ReentrantLock there.
According to jol (see [1]), COWAL consumes 88 bytes.

It looks like excessive garbage for no apparent reason.

There are two questions:
1) Can ReentrantLock be eliminated in favor of synchronized(something)?
I believe a change of "ReentrantLock lock" to "Object lock=new
Object()" would reduce the footprint without loss of existing
semantics.



_______________________________________________
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




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

Re: CopyOnWriteArrayList vs ReentrantLock

Vladimir Sitnikov
> I was thinking for the intended (and majority, I'd hope) use cases, you get the best memory wise outcome by not having any lock object.

At this point I agree with Vitaly. I can hardly imagine a valid use
case for highly contented COWAL.
Not having any lock object would be nice.

> For modifications by index, quite likely

Even modification by index requires a copy, so it is quite odd if it
is used frequently on a large COWAL.

>Due to object padding, the reference for the unallocated lock is free on many VMs

It is free only on 32bit VM. According to jol, all the other (64,
64coop, 64coop + 16byte alignment) do not have "spare" space if a
class has just a single reference field.

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

Re: CopyOnWriteArrayList vs ReentrantLock

Benedict Elliott Smith-3
Even modification by index requires a copy, so it is quite odd if it is used frequently on a large COWAL.

All modifications to a large COWAL are expensive. My point is that many will be more expensive than a simple copy.

It is free only on 32bit VM.

You are correct; my mistake. This is amounts to 25% of an empty COWAL, and 20% of a list with a single element. The REL is 200% and 160% respectively, so the majority of the cost is saved. By the time there are a handful of elements it's not really that significant.

That said, I don't have a strong opinion either way. It just seems it would be one of those changes that could create headaches for users unexpectedly, given its behaviour under contention would be significantly different. The size of the affected cohort is tough to predict, as APIs are abused universally. Since this is an internal characteristic not explicitly defined by the API, but with wildly different behaviour, it seems especially prone to the problem. The small cost necessary to ensure it never degrades too severely from the existing behaviour might be warranted. 

 

On 25 January 2015 at 07:51, Vladimir Sitnikov <[hidden email]> wrote:
> I was thinking for the intended (and majority, I'd hope) use cases, you get the best memory wise outcome by not having any lock object.

At this point I agree with Vitaly. I can hardly imagine a valid use
case for highly contented COWAL.
Not having any lock object would be nice.

> For modifications by index, quite likely

Even modification by index requires a copy, so it is quite odd if it
is used frequently on a large COWAL.

>Due to object padding, the reference for the unallocated lock is free on many VMs

It is free only on 32bit VM. According to jol, all the other (64,
64coop, 64coop + 16byte alignment) do not have "spare" space if a
class has just a single reference field.

Vladimir


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

Re: CopyOnWriteArrayList vs ReentrantLock

Viktor Klang

Not suggesting it but there's also the option of using its own monitor.

--
Cheers,

On 25 Jan 2015 11:25, "Benedict Elliott Smith" <[hidden email]> wrote:
Even modification by index requires a copy, so it is quite odd if it is used frequently on a large COWAL.

All modifications to a large COWAL are expensive. My point is that many will be more expensive than a simple copy.

It is free only on 32bit VM.

You are correct; my mistake. This is amounts to 25% of an empty COWAL, and 20% of a list with a single element. The REL is 200% and 160% respectively, so the majority of the cost is saved. By the time there are a handful of elements it's not really that significant.

That said, I don't have a strong opinion either way. It just seems it would be one of those changes that could create headaches for users unexpectedly, given its behaviour under contention would be significantly different. The size of the affected cohort is tough to predict, as APIs are abused universally. Since this is an internal characteristic not explicitly defined by the API, but with wildly different behaviour, it seems especially prone to the problem. The small cost necessary to ensure it never degrades too severely from the existing behaviour might be warranted. 

 

On 25 January 2015 at 07:51, Vladimir Sitnikov <[hidden email]> wrote:
> I was thinking for the intended (and majority, I'd hope) use cases, you get the best memory wise outcome by not having any lock object.

At this point I agree with Vitaly. I can hardly imagine a valid use
case for highly contented COWAL.
Not having any lock object would be nice.

> For modifications by index, quite likely

Even modification by index requires a copy, so it is quite odd if it
is used frequently on a large COWAL.

>Due to object padding, the reference for the unallocated lock is free on many VMs

It is free only on 32bit VM. According to jol, all the other (64,
64coop, 64coop + 16byte alignment) do not have "spare" space if a
class has just a single reference field.

Vladimir


_______________________________________________
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: CopyOnWriteArrayList vs ReentrantLock

Doug Lea
In reply to this post by Martin Buchholz-3
On 01/24/2015 03:56 PM, Martin Buchholz wrote:

> I think COWAL (and other classes in j.u.c.) could/should use builtin
> synchronization as you suggest, to save 32 bytes (Doug, do you agree?).
>
> The current situation is historical:
> - j.u.c. classes used their own ReentrantLock as "dogfood" exercise before
> integration into the JDK
> - ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in
> later releases
> - many j.u.c. classes use features of ReentrantLock that builtin monitors do not
> provide, like condition objects.

Right.

One disadvantage of converting to builtin locks is that users
become more dependent on quality of JVM decisions about when to
use biased locking, sometimes encountering surprising delays on
de-biasing. We do live with this risk in some other cases, so
it is probably an OK decision here as well. Using a combination
of locks and CAS seems less defensible. There are some very
wide race windows in some List operations.

-Doug


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

Re: CopyOnWriteArrayList vs ReentrantLock

Martin Buchholz-3
Latest version of COWAL in jsr166 CVS now uses builtin monitor locks.

On Sun, Jan 25, 2015 at 7:40 AM, Doug Lea <[hidden email]> wrote:
On 01/24/2015 03:56 PM, Martin Buchholz wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin
synchronization as you suggest, to save 32 bytes (Doug, do you agree?).

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before
integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in
later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not
provide, like condition objects.

Right.

One disadvantage of converting to builtin locks is that users
become more dependent on quality of JVM decisions about when to
use biased locking, sometimes encountering surprising delays on
de-biasing. We do live with this risk in some other cases, so
it is probably an OK decision here as well. Using a combination
of locks and CAS seems less defensible. There are some very
wide race windows in some List operations.

-Doug



_______________________________________________
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: CopyOnWriteArrayList vs ReentrantLock

Joe Bowbeer
Has anyone encountered a situation where the memory footprint of COWAL matters?

I wouldn't expect it to, and for I'm curious to know if this request is only motivated by code inspection or if there is some existing/anticipated problem.

In defense of the status quo, I'll point out that a consistent implementation throughout j.u.c also has some advantages.

On Mon, Jan 26, 2015 at 10:20 AM, Martin Buchholz <[hidden email]> wrote:
Latest version of COWAL in jsr166 CVS now uses builtin monitor locks.

On Sun, Jan 25, 2015 at 7:40 AM, Doug Lea <[hidden email]> wrote:
On 01/24/2015 03:56 PM, Martin Buchholz wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin
synchronization as you suggest, to save 32 bytes (Doug, do you agree?).

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before
integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in
later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not
provide, like condition objects.

Right.

One disadvantage of converting to builtin locks is that users
become more dependent on quality of JVM decisions about when to
use biased locking, sometimes encountering surprising delays on
de-biasing. We do live with this risk in some other cases, so
it is probably an OK decision here as well. Using a combination
of locks and CAS seems less defensible. There are some very
wide race windows in some List operations.

-Doug



_______________________________________________
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



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

Re: CopyOnWriteArrayList vs ReentrantLock

Vitaly Davidovich
This question is a bit of a slippery slope because, at the end of the day, one could say this about a lot of classes.  Surely it's used less frequently than, say, HashMap or ArrayList, but it's a *library* class and therefore should be as frugal as possible when it doesn't detract from performance, maintainability, and function.

On Mon, Jan 26, 2015 at 2:25 PM, Joe Bowbeer <[hidden email]> wrote:
Has anyone encountered a situation where the memory footprint of COWAL matters?

I wouldn't expect it to, and for I'm curious to know if this request is only motivated by code inspection or if there is some existing/anticipated problem.

In defense of the status quo, I'll point out that a consistent implementation throughout j.u.c also has some advantages.

On Mon, Jan 26, 2015 at 10:20 AM, Martin Buchholz <[hidden email]> wrote:
Latest version of COWAL in jsr166 CVS now uses builtin monitor locks.

On Sun, Jan 25, 2015 at 7:40 AM, Doug Lea <[hidden email]> wrote:
On 01/24/2015 03:56 PM, Martin Buchholz wrote:
I think COWAL (and other classes in j.u.c.) could/should use builtin
synchronization as you suggest, to save 32 bytes (Doug, do you agree?).

The current situation is historical:
- j.u.c. classes used their own ReentrantLock as "dogfood" exercise before
integration into the JDK
- ReentrantLock outperformed builtin locks with hotspot in JDK 5 but not in
later releases
- many j.u.c. classes use features of ReentrantLock that builtin monitors do not
provide, like condition objects.

Right.

One disadvantage of converting to builtin locks is that users
become more dependent on quality of JVM decisions about when to
use biased locking, sometimes encountering surprising delays on
de-biasing. We do live with this risk in some other cases, so
it is probably an OK decision here as well. Using a combination
of locks and CAS seems less defensible. There are some very
wide race windows in some List operations.

-Doug



_______________________________________________
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



_______________________________________________
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: CopyOnWriteArrayList vs ReentrantLock

Vladimir Sitnikov
> Has anyone encountered a situation where the memory footprint of COWAL matters?

Well, the story began when I found heavy traffic on COWALs in our
application (as per JFR).
The "root" cause is the application (ab-)used commons-configuration,
and each commons-configuration "AbstractConfiguration" (as of 1.x)
always created a couple of COWALs (see [1]).

I opened a ticket for commons-configuration to "avoid creating of
empty COWALS" (see [2], jfr screenshot attached).
Then I opened COWAL.java and realized it could be improved (somewhere
near JDK 15:), so I raised a question in c-i.

[1]: http://grepcode.com/file/repo1.maven.org/maven2/commons-configuration/commons-configuration/1.10/org/apache/commons/configuration/event/EventSource.java#EventSource.initListeners%28%29

[2]: https://issues.apache.org/jira/browse/CONFIGURATION-596

Vladimir

2015-01-26 23:03 GMT+03:00 Vitaly Davidovich <[hidden email]>:

> This question is a bit of a slippery slope because, at the end of the day,
> one could say this about a lot of classes.  Surely it's used less frequently
> than, say, HashMap or ArrayList, but it's a *library* class and therefore
> should be as frugal as possible when it doesn't detract from performance,
> maintainability, and function.
>
> On Mon, Jan 26, 2015 at 2:25 PM, Joe Bowbeer <[hidden email]> wrote:
>>
>> Has anyone encountered a situation where the memory footprint of COWAL
>> matters?
>>
>> I wouldn't expect it to, and for I'm curious to know if this request is
>> only motivated by code inspection or if there is some existing/anticipated
>> problem.
>>
>> In defense of the status quo, I'll point out that a consistent
>> implementation throughout j.u.c also has some advantages.
>>
>> On Mon, Jan 26, 2015 at 10:20 AM, Martin Buchholz <[hidden email]>
>> wrote:
>>>
>>> Latest version of COWAL in jsr166 CVS now uses builtin monitor locks.
>>>
>>> On Sun, Jan 25, 2015 at 7:40 AM, Doug Lea <[hidden email]> wrote:
>>>>
>>>> On 01/24/2015 03:56 PM, Martin Buchholz wrote:
>>>>>
>>>>> I think COWAL (and other classes in j.u.c.) could/should use builtin
>>>>> synchronization as you suggest, to save 32 bytes (Doug, do you agree?).
>>>>>
>>>>> The current situation is historical:
>>>>> - j.u.c. classes used their own ReentrantLock as "dogfood" exercise
>>>>> before
>>>>> integration into the JDK
>>>>> - ReentrantLock outperformed builtin locks with hotspot in JDK 5 but
>>>>> not in
>>>>> later releases
>>>>> - many j.u.c. classes use features of ReentrantLock that builtin
>>>>> monitors do not
>>>>> provide, like condition objects.
>>>>
>>>>
>>>> Right.
>>>>
>>>> One disadvantage of converting to builtin locks is that users
>>>> become more dependent on quality of JVM decisions about when to
>>>> use biased locking, sometimes encountering surprising delays on
>>>> de-biasing. We do live with this risk in some other cases, so
>>>> it is probably an OK decision here as well. Using a combination
>>>> of locks and CAS seems less defensible. There are some very
>>>> wide race windows in some List operations.
>>>>
>>>> -Doug
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> 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
>>>
>>
>>
>> _______________________________________________
>> 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
>



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

Re: CopyOnWriteArrayList vs ReentrantLock

Joe Bowbeer
Thanks for adding the back story.

On Mon, Jan 26, 2015 at 12:32 PM, Vladimir Sitnikov <[hidden email]> wrote:
> Has anyone encountered a situation where the memory footprint of COWAL matters?

Well, the story began when I found heavy traffic on COWALs in our
application (as per JFR).
The "root" cause is the application (ab-)used commons-configuration,
and each commons-configuration "AbstractConfiguration" (as of 1.x)
always created a couple of COWALs (see [1]).

I opened a ticket for commons-configuration to "avoid creating of
empty COWALS" (see [2], jfr screenshot attached).
Then I opened COWAL.java and realized it could be improved (somewhere
near JDK 15:), so I raised a question in c-i.

[1]: http://grepcode.com/file/repo1.maven.org/maven2/commons-configuration/commons-configuration/1.10/org/apache/commons/configuration/event/EventSource.java#EventSource.initListeners%28%29

[2]: https://issues.apache.org/jira/browse/CONFIGURATION-596

Vladimir

2015-01-26 23:03 GMT+03:00 Vitaly Davidovich <[hidden email]>:
> This question is a bit of a slippery slope because, at the end of the day,
> one could say this about a lot of classes.  Surely it's used less frequently
> than, say, HashMap or ArrayList, but it's a *library* class and therefore
> should be as frugal as possible when it doesn't detract from performance,
> maintainability, and function.
>
> On Mon, Jan 26, 2015 at 2:25 PM, Joe Bowbeer <[hidden email]> wrote:
>>
>> Has anyone encountered a situation where the memory footprint of COWAL
>> matters?
>>
>> I wouldn't expect it to, and for I'm curious to know if this request is
>> only motivated by code inspection or if there is some existing/anticipated
>> problem.
>>
>> In defense of the status quo, I'll point out that a consistent
>> implementation throughout j.u.c also has some advantages.
>>
>> On Mon, Jan 26, 2015 at 10:20 AM, Martin Buchholz <[hidden email]>
>> wrote:
>>>
>>> Latest version of COWAL in jsr166 CVS now uses builtin monitor locks.
>>>
>>> On Sun, Jan 25, 2015 at 7:40 AM, Doug Lea <[hidden email]> wrote:
>>>>
>>>> On 01/24/2015 03:56 PM, Martin Buchholz wrote:
>>>>>
>>>>> I think COWAL (and other classes in j.u.c.) could/should use builtin
>>>>> synchronization as you suggest, to save 32 bytes (Doug, do you agree?).
>>>>>
>>>>> The current situation is historical:
>>>>> - j.u.c. classes used their own ReentrantLock as "dogfood" exercise
>>>>> before
>>>>> integration into the JDK
>>>>> - ReentrantLock outperformed builtin locks with hotspot in JDK 5 but
>>>>> not in
>>>>> later releases
>>>>> - many j.u.c. classes use features of ReentrantLock that builtin
>>>>> monitors do not
>>>>> provide, like condition objects.
>>>>
>>>>
>>>> Right.
>>>>
>>>> One disadvantage of converting to builtin locks is that users
>>>> become more dependent on quality of JVM decisions about when to
>>>> use biased locking, sometimes encountering surprising delays on
>>>> de-biasing. We do live with this risk in some other cases, so
>>>> it is probably an OK decision here as well. Using a combination
>>>> of locks and CAS seems less defensible. There are some very
>>>> wide race windows in some List operations.
>>>>
>>>> -Doug
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> 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
>>>
>>
>>
>> _______________________________________________
>> 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
>



--
Regards,
Vladimir Sitnikov


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