headers
David Holmes | 1 Jul 2009 02:18
Picon

Re: adaptive spinning/biased lockingand java.util.concurrent.lock

Can I also clarify something about biased-locking as I recently encountered
some very mis-guided perceptions of what it is. :)

Biased-locking exists to make un-needed synchronization as cheap as
possible. It works on the assumption that objects are not shared, so locks
are not contended and so aren't in fact needed. So when an object acquires a
monitor lock it simply does a fast-lock by CAS'ing in the owning thread's Id
into the object header. But the release of the lock is almost a no-op, it
leaves the object "locked" by that original thread. Subsequent locks by that
thread then don't need the (expensive) CAS. If another thread tries to lock
the object we go through an expensive bias-revocation process and revert to
using normal locking - the fact that contention occurred shows biasedlocking
is not applicable to this object.

As Doug says you don't tend to use j.u.c Locks in circumstances where
biased-locking would be beneficial.

Cheers,
David Holmes

> -----Original Message-----
> From: concurrency-interest-bounces <at> cs.oswego.edu
> [mailto:concurrency-interest-bounces <at> cs.oswego.edu]On Behalf Of Doug Lea
> Sent: Wednesday, 1 July 2009 6:52 AM
> To: Peter Veentjer
> Cc: concurrency-interest <at> cs.oswego.edu
> Subject: Re: [concurrency-interest] adaptive spinning/biased lockingand
> java.util.concurrent.lock
>
>
(Continue reading)

Permalink | Reply | 1 comment |
headers
Peter Veentjer | 1 Jul 2009 06:37
Picon
Gravatar

Re: adaptive spinning/biased lockingand java.util.concurrent.lock

Thanks Doug and David for the clarifications.

On Wed, Jul 1, 2009 at 2:18 AM, David Holmes<davidcholmes <at> aapt.net.au> wrote:
> Can I also clarify something about biased-locking as I recently encountered
> some very mis-guided perceptions of what it is. :)
>
> Biased-locking exists to make un-needed synchronization as cheap as
> possible. It works on the assumption that objects are not shared, so locks
> are not contended and so aren't in fact needed. So when an object acquires a
> monitor lock it simply does a fast-lock by CAS'ing in the owning thread's Id
> into the object header. But the release of the lock is almost a no-op, it
> leaves the object "locked" by that original thread. Subsequent locks by that
> thread then don't need the (expensive) CAS. If another thread tries to lock
> the object we go through an expensive bias-revocation process and revert to
> using normal locking - the fact that contention occurred shows biasedlocking
> is not applicable to this object.
>
> As Doug says you don't tend to use j.u.c Locks in circumstances where
> biased-locking would be beneficial.
>
> Cheers,
> David Holmes
>
>> -----Original Message-----
>> From: concurrency-interest-bounces <at> cs.oswego.edu
>> [mailto:concurrency-interest-bounces <at> cs.oswego.edu]On Behalf Of Doug Lea
>> Sent: Wednesday, 1 July 2009 6:52 AM
>> To: Peter Veentjer
>> Cc: concurrency-interest <at> cs.oswego.edu
>> Subject: Re: [concurrency-interest] adaptive spinning/biased lockingand
(Continue reading)

Permalink | Reply | 0 comments |
headers
Jeremy Manson | 1 Jul 2009 06:37
Picon

Re: Immutable object conundrums

Sigh.  This is true, but they happen to be unnecessary on x86 +
hotspot.  It's an ongoing discussion.

Jeremy

On Tue, Jun 30, 2009 at 1:32 PM, Peter Veentjer<alarmnummer <at> gmail.com> wrote:
> On Tue, Jun 30, 2009 at 10:23 PM, Jeremy Manson<jeremy.manson <at> gmail.com> wrote:
>> On Tue, Jun 30, 2009 at 5:25 AM, Peter Veentjer<alarmnummer <at> gmail.com> wrote:
>>>> It seems to me that immutability for the sake of propagating constructor
>>>> changes to main memory
>>>> is something of a misnomer - this is more about using the 'final' keyword as
>>>> a coarse grained hook into the
>>>> java memory model. Maybe if we had more direct access to that memory model
>>>> then we could ensure
>>>> that mutable objects could safely be constructed as well, for example:
>>>>
>>>> public class MyMutableClass {
>>>>   private String myNonFinal;
>>>>
>>>>   public MyClass() {
>>>>      this.myNonFinal = "hello world";
>>>>      MemoryModel.flush(); // flush-commit similar to other cache
>>>> technologies
>>>>   }
>>>> }
>>>
>>> I don't see a happens before relation between the write of the
>>> myNonFinal example and the usage. So I don't think this example is
>>> going to work.
>>
(Continue reading)

Permalink | Reply | 0 comments |
headers
Guy Korland | 1 Jul 2009 06:52
Picon
Gravatar

DeuceSTM 1.0 is ready

Hi all,

I just wanted to inform you that DeuceSTM 1.0 was released.
DeuceSTM is a full non-intrusive Java transactional memory.
The API is as simple as adding <at> Atomic annotation to the targeted method.

For more detail see: http://www.deucestm.org

--
Guy Korland
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest <at> cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Permalink | Reply | 0 comments |
headers
Ashley Williams | 1 Jul 2009 13:00
Picon

Re: Immutable object conundrums

Just looked at the Fences API and this is exactly what I was trying to  
allude to.

In fact I would personally prefer to see the explicit use of  
Fences.preStoreFence()
instead of relying on memory model guarantees through the use of  
final. It would
be all too easy for a developer to come along and mistakenly remove  
the multi-purpose
final keyword without appearing to break the code.

Am I right in thinking most jvms would implement this by writing to  
main memory (writes) and
evicting entries from local memory (reads)? Just wondering about any  
performance costs.

So if one were to use both a final field modifier as well as a fence,  
would the jvm be
clever enough not pay the for the happens-before guarantee twice over?

On 30 Jun 2009, at 21:46, Doug Lea wrote:

> Peter Veentjer wrote:
>
>> PS: Do you have a reference to the other concurrency features that  
>> are
>> going to be added (apart from the fences and the fork/join
>> functionality) to Java 7?
>
> Definitely planned classes are in package jsr166y --
> ForkJoin, Phasers, TransferQueue, ThreadLocalRandom. See
> http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166ydocs/
>
> Plus Fences, which can't be previewed in jsr166y since
> it relies on JVM support. See
> http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/Fences.html
>
> Plus possibly some sort of customized hash map.
> The main reason for delay on that is algorithmic:
> Efficient support for features like eviction and
> memoization across a large enough range of
> policies to be worth supporting in concurrent maps is not a
> fully solved problem. I want to make sure that
> we offer only that range of them for which we are
> very sure we can support well, but without closing
> the door to future algorithmic overhauls.
>
> -Doug
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest <at> cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Permalink | Reply | 6 comments |
headers
Manuel Dominguez Sarmiento | 2 Jul 2009 17:21

PriorityQueue bug with mutable object

Hi Doug,

I recently filed the following bug at Sun's bug database:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6856821

You might want to look into it since this class is used by many 
concurrent classes and you're listed as one of its authors.

I am well aware of the perils of mutable objects, however PriorityQueue 
should account for mutability since priorities might change for a queued 
element at runtime, and it is not always practical to remove and discard 
the previous element and create a new object. This does not only affect 
mutable objects but also those whose priority is somehow based on 
System.currentTimeMillis() or other external data, which is what caused 
us to find this subtle bug.

Best,

Ing. Manuel Dominguez Sarmiento
Director General
Renxo S.A.
e-mail:	mads <at> renxo.com
Phone:	+54 11 4719 6806, ext. 104
Permalink | Reply | 10 comments |
headers
Brian S O'Neill | 2 Jul 2009 17:48
Picon
Gravatar

Re: PriorityQueue bug with mutable object

I'm not Doug, but personally I would fix the bug by documenting the 
behavior of priority queues. It doesn't make sense to support your use 
case, because it would require that every poll from the queue resort the 
entire heap. This defeats the purpose of using such a structure.

If you have tasks with variable priority, you should use a binary search 
tree instead. Then you can quickly remove and re-insert tasks when its 
priority changes. Call pollFirstEntry to remove the task with highest 
priority.

Manuel Dominguez Sarmiento wrote:
> Hi Doug,
>
> I recently filed the following bug at Sun's bug database:
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6856821
>
> You might want to look into it since this class is used by many 
> concurrent classes and you're listed as one of its authors.
>
> I am well aware of the perils of mutable objects, however 
> PriorityQueue should account for mutability since priorities might 
> change for a queued element at runtime, and it is not always practical 
> to remove and discard the previous element and create a new object. 
> This does not only affect mutable objects but also those whose 
> priority is somehow based on System.currentTimeMillis() or other 
> external data, which is what caused us to find this subtle bug.
>
> Best,
>
> Ing. Manuel Dominguez Sarmiento
> Director General
> Renxo S.A.
> e-mail:    mads <at> renxo.com
> Phone:    +54 11 4719 6806, ext. 104
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest <at> cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
Permalink | Reply | 0 comments |
headers
Jim Andreou | 2 Jul 2009 17:50
Picon

Re: PriorityQueue bug with mutable object

How is this different than mutating keys of a HashMap? There is no way a structure could find out just when an arbitrary memory update causes side effects to some of its elements.


Java's PriorityQueue does have some shortcomings (it's very slow to change an element's priority - i.e. through remove and re-add), but this is most certainly not one of them.

Regards,
Dimitris

2009/7/2 Manuel Dominguez Sarmiento <mads <at> renxo.com>
Hi Doug,

I recently filed the following bug at Sun's bug database:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6856821

You might want to look into it since this class is used by many concurrent classes and you're listed as one of its authors.

I am well aware of the perils of mutable objects, however PriorityQueue should account for mutability since priorities might change for a queued element at runtime, and it is not always practical to remove and discard the previous element and create a new object. This does not only affect mutable objects but also those whose priority is somehow based on System.currentTimeMillis() or other external data, which is what caused us to find this subtle bug.

Best,

Ing. Manuel Dominguez Sarmiento
Director General
Renxo S.A.
e-mail: mads <at> renxo.com
Phone:  +54 11 4719 6806, ext. 104


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

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest <at> cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Permalink | Reply | 0 comments |
headers
Mark Thornton | 2 Jul 2009 17:50
Picon
Favicon

Re: PriorityQueue bug with mutable object

Manuel Dominguez Sarmiento wrote:
> Hi Doug,
>
> I recently filed the following bug at Sun's bug database:
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6856821
>
> You might want to look into it since this class is used by many 
> concurrent classes and you're listed as one of its authors. 
That is not a bug --- the behaviour is as expected. TreeSet likewise 
does not work if the ordering of elements changes after insertion. Nor 
do any of the Map's work if the keys are mutable. Priority queues which 
allow the priority to change have an extra method to perform this 
mutation --- i.e. you have to explicitly inform the queue of each 
element whose priority is changing.

Regards,
Mark Thornton
Permalink | Reply | 6 comments |
headers
Holger Hoffstätte | 2 Jul 2009 17:54
Gravatar

Re: PriorityQueue bug with mutable object

Manuel Dominguez Sarmiento wrote:
> I recently filed the following bug at Sun's bug database:
> 
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6856821

The behaviour is neither subtle nor a bug, and IMHO cannot be changed
because the problem you're trying to fix is inherently unsolvable. Taking
your suggestion to its logical conclusion would mean that an arbitrary
number of mutable objects may never be processed because their aggregate
rate of state (priority) change could be so high that the queue would end
up never dequeing anything, only re-sorting.
Apart from this academic showstopper there's the small issue of state
changes during reordering or comparison. Good luck handling that correctly :)

-h
Permalink | Reply | 0 comments |

Gmane