Re: Possible multi-threading bug

[Gregg Wonderly <gr...@wonderly.org>]

In this kind of software design, where we have a reset(), get() and mutate() 
kind of method, the importance of volatile performance vs synchronized control 
is pretty much a part of what mutate() does.  If mutate() is really set(), then, 
you just have and assignment (typically) and thus there is no atomic view 
problem between get() and set().  get() will return the new value of set() at 
some point in the future, so volatile is enough in the class implementation.

However, in our case where mutate() involves, indirectly, a get() operation, 
then synchronized is required on all mutations because the total order of the 
involved operations is important, as Peter said in his post.  It can be that the 
references also need to be synchronized if there is an intermediate value that 
might be set() before the final mutate() action occurs.

Because of all of these considerations, it is usually far better to pick 
synchronized first until volatile can be proven to be more desirable.  That way, 
any future changes to the reference and mutator methods will not expose a new 
bug related to operation ordering or intermediate values.

Sometimes, people write methods like

	public void increment() {
		if( ++count > MAX ) {
			count = 0;
		}
	}

and there is thus two "set" operations and the final result is really all that 
you want to expose.  So synchronized here is a good idea.

A second issue is that if you are designing a "container" class that others 
might use in multiplicity such that it could end up in a container, and perhaps 
as a key data structure, it can be better to create an internal locking object 
to perform synchronization on so that if the user of your class starts using 
your class as a locking object, the internal locking does not impact unrelated 
code paths.

Gregg Wonderly


On 11/29/2010 5:45 AM, Tom Hobbs wrote:
> Yes, you're right.
>
> I knew about the non-atomicity of ++, my concern was a call to reset
> creeping in between the two parts of that operation.
>
> I forgot about the "Get a global lock on the variable" that volatile
> would require as mentioned here;
> http://www.javaperformancetuning.com/news/qotm051.shtml
>
> On Mon, Nov 29, 2010 at 10:50 AM, Peter Firmstone<ji...@zeus.net.au>  wrote:
>> Tom Hobbs wrote:
>>>
>>> Serious comment:
>>>
>>> Shouldn't reset also be synchronized?
>>
>> You've identified that reset is also a mutator method, I guess I gave
>> mutation as my reason and I wasn't being entirely accurate, sorry.
>>
>> To explain a bit more, reset doesn't have to be synchronized when _count is
>> volatile and increment synchronized, the reason, it's a single operation
>> mutator, it just resets the counter, it doesn't check it first.
>>
>> The increment method is at least two operations _count++ first gets _count,
>> then increments it and sets _count to the new value, if it wasn't
>> synchronized, another increment could get _count at the same time... Or a
>> reset operation could occur in between and the reset fail.
>>
>> The ++ operator isn't atomic.
>>
>> If in doubt use synchronization, so by making reset also synchronized you
>> wouldn't be wrong and it probably wouldn't hurt performance either.
>>
>> The secret to concurrency is, all operations must happen atomically.
>>   Synchronization creates atomicity when it wouldn't otherwise exist.
>>   Synchronization also effects visibility, as does volatile.
>>
>> Cheers,
>>
>> Peter.
>>
>>>   Also, +1 for making _count volatile.
>>>
>>> Frivolous comment:
>>>
>>> Can we drop the underscore prefix for member variables?  It's against
>>> the official Sun/Oracle/Whatever conventions.  Also, it drives me up
>>> the wall...
>>>
>>> http://www.oracle.com/technetwork/java/codeconventions-135099.html#367
>>>
>>>
>>> On Sun, Nov 28, 2010 at 11:16 PM, Patricia Shanahan<pa...@acm.org>  wrote:
>>>
>>>>
>>>> In the way in which this is used, I expect most of the calls to be to
>>>> increment. It has to be synchronized, so it seems simplest to synchronize
>>>> all the methods.
>>>>
>>>> I've done some more experiments, and decided this is a real problem. As
>>>> part
>>>> of my debug effort, I increased the number of threads in the stress test,
>>>> so
>>>> that it fails much more often. I also added some debug printouts, one of
>>>> which was showing up in conjunction with some but not all failures, so I
>>>> thought it was irrelevant.
>>>>
>>>> With the additional synchronization, the debug message shows up in all
>>>> failures. I think I actually had two forms of failure, one of which is
>>>> fixed
>>>> by the synchronization.  In the failure case that has been fixed,
>>>> everything
>>>> works, no debug messages, but the test never admits to having finished,
>>>> exactly the symptom I would expect from this issue.
>>>>
>>>> I plan to check in the enhanced test as well as the fixes, because it
>>>> only
>>>> takes a few minutes longer than the current size, and is much better at
>>>> finding bugs.
>>>>
>>>> Patricia
>>>>
>>>>
>>>> On 11/28/2010 2:52 PM, Peter Firmstone wrote:
>>>>
>>>>>
>>>>> Well, at the absolute minimum the variable should be volatile, so any
>>>>> changes are visible among all threads.
>>>>>
>>>>> Since increment is the only mutating method, this must be synchronized.
>>>>>
>>>>> This is a cheap form of multi read, single write threading, although one
>>>>> must be careful, as this only works on primitives and immutable object
>>>>> references, since only the reference itself is being updated.
>>>>>
>>>>> If it was a reference to a mutable object (or long), then all methods
>>>>> would need to be synchronized.
>>>>>
>>>>> Cheers,
>>>>>
>>>>> Peter.
>>>>>
>>>>> Patricia Shanahan wrote:
>>>>>
>>>>>>
>>>>>> I've found something I think is a problem in
>>>>>> com.sun.jini.test.impl.outrigger.matching.StressTest, but it does not
>>>>>> seem to be the problem, or at least not the only problem, causing the
>>>>>> test hang I'm investigating. It's difficult to test, so I'd like a
>>>>>> review of my reasoning. This is a question for those who are familiar
>>>>>> with the Java memory model.
>>>>>>
>>>>>> Incidentally, if we went to 1.5 as the oldest supported release, this
>>>>>> could be replaced by an AtomicInteger.
>>>>>>
>>>>>> In the following inner class, I think the methods reset and getCount
>>>>>> should be synchronized. As the comments note, the operations they
>>>>>> perform are atomic. My concern is the lack of a happens-before
>>>>>> relationship between those two methods and the increment method. As
>>>>>> far as I can tell, there is nothing forcing the change in the counter
>>>>>> due to an increment to become visible to a getCount call in another
>>>>>> thread.
>>>>>>
>>>>>> private class Counter {
>>>>>>
>>>>>> /**
>>>>>> * Internal counter variable.
>>>>>> */
>>>>>> private int _count = 0;
>>>>>>
>>>>>> /**
>>>>>> * Constructor. Declared to enforce protection level.
>>>>>> */
>>>>>> Counter() {
>>>>>>
>>>>>> // Do nothing.
>>>>>> }
>>>>>>
>>>>>> /**
>>>>>> * Resets internal counter to zero.
>>>>>> */
>>>>>> void reset() {
>>>>>>
>>>>>> // Integer assignment is atomic.
>>>>>> _count = 0;
>>>>>> }
>>>>>>
>>>>>> /**
>>>>>> * Increments internal counter by one.
>>>>>> */
>>>>>> synchronized void increment() {
>>>>>> ++_count;
>>>>>> }
>>>>>>
>>>>>> /**
>>>>>> * Returns current value of this<code>Counter</code>  object.
>>>>>> */
>>>>>> int getCount() {
>>>>>>
>>>>>> // Returning an integer is atomic.
>>>>>> return _count;
>>>>>> }
>>>>>> }
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>

Re: Possible multi-threading bug

[Patricia Shanahan <pa...@acm.org>]

I've taken a quick look at the source code, and it appears to me to be
somewhere in between.

It is segmented, and the Segment class extends ReentrantLock. However,
the lock is obtained only for methods that modify the segment. The code
uses volatile variables to permit pure read operations to go through
without any locking.

Patricia


Carfield Yim wrote:
> I've read some article which saying that CHM is still locked, it just
> divid the hashmap into few small hashmap internally so that the chance
> of lock-wait is lesser, is that wrong?
> 
> On Fri, Dec 3, 2010 at 10:19 PM, Gregg Wonderly <gr...@wonderly.org> wrote:
>> On 12/2/2010 3:48 PM, Patricia Shanahan wrote:
>>> Gregg Wonderly wrote:
>>> ...
>>>> A second issue is that if you are designing a "container" class that
>>>> others
>>>> might use in multiplicity such that it could end up in a container, and
>>>> perhaps as a key data structure, it can be better to create an internal
>>>> locking object to perform synchronization on so that if the user of your
>>>> class
>>>> starts using your class as a locking object, the internal locking does
>>>> not
>>>> impact unrelated code paths.
>>> ...
>>>
>>> For container objects, I would give the opposite advice, and recommend
>>> making
>>> the container itself the lock object.
>> There are cases for both I believe.  ConcurrentHashMap, for example has no
>> locks performed on the instance.   All locking is internal using mechanisms
>> other than synchronized.
>>
>> The primary issue with using an internal lock, for me, is that I've found
>> that I end up with less opportunity for circular wait if I am in complete
>> control of when a lock is asserted.
>>
>> For things where atomic views need to maintained through multiple operations
>> on the same instance, then a single global view lock will be important.  As
>> the user of the container instance, you are more able to understand that
>> need in your application, so locking is your responsibility.
>>
>> Many people have complained about CHM not being "the lock" itself, but it
>> really comes down to the fact that since it does not use synchronized
>> actions internally, it can not make the object be "the lock".
>>
>> With this in mind, I've started trying to internalize more locking so that
>> for things that I do need to "adjust internal performance" on, I don't have
>> to go everywhere else and change locking use to be in line with the change
>> from synchronized to Lock.
>>
>> Locking with instances via synchronized was convenient, but I'd suggest that
>> not doing that provides a more plastic model that you can more readily
>> adjust.
>>
>> I also find that I will put more application operations into the APIs to
>> help me control and optimize those usage patterns.  This seems to help me
>> create more relevant/useful APIs and fewer "containers".  I.e. more simple
>> algorithms end up in the class implementation instead of strewn about the
>> application.
>>
>> Gregg Wonderly
>>
> 

Re: Possible multi-threading bug

[Carfield Yim <ca...@carfield.com.hk>]

I've read some article which saying that CHM is still locked, it just
divid the hashmap into few small hashmap internally so that the chance
of lock-wait is lesser, is that wrong?

On Fri, Dec 3, 2010 at 10:19 PM, Gregg Wonderly <gr...@wonderly.org> wrote:
> On 12/2/2010 3:48 PM, Patricia Shanahan wrote:
>>
>> Gregg Wonderly wrote:
>> ...
>>>
>>> A second issue is that if you are designing a "container" class that
>>> others
>>> might use in multiplicity such that it could end up in a container, and
>>> perhaps as a key data structure, it can be better to create an internal
>>> locking object to perform synchronization on so that if the user of your
>>> class
>>> starts using your class as a locking object, the internal locking does
>>> not
>>> impact unrelated code paths.
>>
>> ...
>>
>> For container objects, I would give the opposite advice, and recommend
>> making
>> the container itself the lock object.
>
> There are cases for both I believe.  ConcurrentHashMap, for example has no
> locks performed on the instance.   All locking is internal using mechanisms
> other than synchronized.
>
> The primary issue with using an internal lock, for me, is that I've found
> that I end up with less opportunity for circular wait if I am in complete
> control of when a lock is asserted.
>
> For things where atomic views need to maintained through multiple operations
> on the same instance, then a single global view lock will be important.  As
> the user of the container instance, you are more able to understand that
> need in your application, so locking is your responsibility.
>
> Many people have complained about CHM not being "the lock" itself, but it
> really comes down to the fact that since it does not use synchronized
> actions internally, it can not make the object be "the lock".
>
> With this in mind, I've started trying to internalize more locking so that
> for things that I do need to "adjust internal performance" on, I don't have
> to go everywhere else and change locking use to be in line with the change
> from synchronized to Lock.
>
> Locking with instances via synchronized was convenient, but I'd suggest that
> not doing that provides a more plastic model that you can more readily
> adjust.
>
> I also find that I will put more application operations into the APIs to
> help me control and optimize those usage patterns.  This seems to help me
> create more relevant/useful APIs and fewer "containers".  I.e. more simple
> algorithms end up in the class implementation instead of strewn about the
> application.
>
> Gregg Wonderly
>

Re: Possible multi-threading bug

[Gregg Wonderly <gr...@wonderly.org>]

On 12/2/2010 3:48 PM, Patricia Shanahan wrote:
> Gregg Wonderly wrote:
> ...
>> A second issue is that if you are designing a "container" class that others
>> might use in multiplicity such that it could end up in a container, and
>> perhaps as a key data structure, it can be better to create an internal
>> locking object to perform synchronization on so that if the user of your class
>> starts using your class as a locking object, the internal locking does not
>> impact unrelated code paths.
> ...
>
> For container objects, I would give the opposite advice, and recommend making
> the container itself the lock object.

There are cases for both I believe.  ConcurrentHashMap, for example has no locks 
performed on the instance.   All locking is internal using mechanisms other than 
synchronized.

The primary issue with using an internal lock, for me, is that I've found that I 
end up with less opportunity for circular wait if I am in complete control of 
when a lock is asserted.

For things where atomic views need to maintained through multiple operations on 
the same instance, then a single global view lock will be important.  As the 
user of the container instance, you are more able to understand that need in 
your application, so locking is your responsibility.

Many people have complained about CHM not being "the lock" itself, but it really 
comes down to the fact that since it does not use synchronized actions 
internally, it can not make the object be "the lock".

With this in mind, I've started trying to internalize more locking so that for 
things that I do need to "adjust internal performance" on, I don't have to go 
everywhere else and change locking use to be in line with the change from 
synchronized to Lock.

Locking with instances via synchronized was convenient, but I'd suggest that not 
doing that provides a more plastic model that you can more readily adjust.

I also find that I will put more application operations into the APIs to help me 
control and optimize those usage patterns.  This seems to help me create more 
relevant/useful APIs and fewer "containers".  I.e. more simple algorithms end up 
in the class implementation instead of strewn about the application.

Gregg Wonderly

Re: Possible multi-threading bug

[Michał Kłeczek <mi...@xpro.biz>]

I would also suggest taking a look at Google Code Guava project (formelly
Google Collections) - it introduces a concept of a concurrent computing map
which lazily computes a value when asked for non-existent key and a thread
safe memoizer which is a lazily computed value. In many cases it really
makes multithreaded code simpler and less error prone.

Michal

On Fri, Dec 3, 2010 at 10:17 AM, Carfield Yim <ca...@carfield.com.hk>wrote:

> How about using copyonwritearraylist?
> On Dec 3, 2010 5:49 AM, "Patricia Shanahan" <pa...@acm.org> wrote:
> > Gregg Wonderly wrote:
> > ...
> >> A second issue is that if you are designing a "container" class that
> >> others might use in multiplicity such that it could end up in a
> >> container, and perhaps as a key data structure, it can be better to
> >> create an internal locking object to perform synchronization on so that
> >> if the user of your class starts using your class as a locking object,
> >> the internal locking does not impact unrelated code paths.
> > ...
> >
> > For container objects, I would give the opposite advice, and recommend
> > making the container itself the lock object.
> >
> > The reason is code that performs multiple operations on the container to
> > do one related logical operation.
> >
> > For example, I've been looking at some test code that needs to remove a
> > random element from a List. It first uses a random number generator to
> > pick an int n in the range 0 <= n < list.size(), followed by
> list.remove(n).
> >
> > If done using a list that synchronizes on itself, that block of code can
> > be marked synchronized(list), but code that does a single operation on
> > list does not need to be synchronized externally. If the list
> > synchronizes on an internal locking object, *all* access to the list
> > will need to be synchronized in the calling code on some other object.
> >
> > Using the container itself is also consistent with what is done by
> > Collections.synchronizedList etc.
> >
> > Patricia
> >
>

Re: Possible multi-threading bug

[Carfield Yim <ca...@carfield.com.hk>]

How about using copyonwritearraylist?
On Dec 3, 2010 5:49 AM, "Patricia Shanahan" <pa...@acm.org> wrote:
> Gregg Wonderly wrote:
> ...
>> A second issue is that if you are designing a "container" class that
>> others might use in multiplicity such that it could end up in a
>> container, and perhaps as a key data structure, it can be better to
>> create an internal locking object to perform synchronization on so that
>> if the user of your class starts using your class as a locking object,
>> the internal locking does not impact unrelated code paths.
> ...
>
> For container objects, I would give the opposite advice, and recommend
> making the container itself the lock object.
>
> The reason is code that performs multiple operations on the container to
> do one related logical operation.
>
> For example, I've been looking at some test code that needs to remove a
> random element from a List. It first uses a random number generator to
> pick an int n in the range 0 <= n < list.size(), followed by
list.remove(n).
>
> If done using a list that synchronizes on itself, that block of code can
> be marked synchronized(list), but code that does a single operation on
> list does not need to be synchronized externally. If the list
> synchronizes on an internal locking object, *all* access to the list
> will need to be synchronized in the calling code on some other object.
>
> Using the container itself is also consistent with what is done by
> Collections.synchronizedList etc.
>
> Patricia
>

Re: Possible multi-threading bug

[Patricia Shanahan <pa...@acm.org>]

Gregg Wonderly wrote:
...
> A second issue is that if you are designing a "container" class that 
> others might use in multiplicity such that it could end up in a 
> container, and perhaps as a key data structure, it can be better to 
> create an internal locking object to perform synchronization on so that 
> if the user of your class starts using your class as a locking object, 
> the internal locking does not impact unrelated code paths.
...

For container objects, I would give the opposite advice, and recommend 
making the container itself the lock object.

The reason is code that performs multiple operations on the container to 
do one related logical operation.

For example, I've been looking at some test code that needs to remove a 
random element from a List. It first uses a random number generator to 
pick an int n in the range 0 <= n < list.size(), followed by list.remove(n).

If done using a list that synchronizes on itself, that block of code can 
be marked synchronized(list), but code that does a single operation on 
list does not need to be synchronized externally. If the list 
synchronizes on an internal locking object, *all* access to the list 
will need to be synchronized in the calling code on some other object.

Using the container itself is also consistent with what is done by 
Collections.synchronizedList etc.

Patricia