Confusion with Synchronisation, plus primative / object use of ++ operator

[Rob Wilson]

Hi all,

I was doing my 4th Java workshop (recorded here
http://www.ciderbob.com/babyduke/presentations) and during it I was
suprised that using a HashMap (that's not synchronised unlike the
HashTable) with 1,000 threads accessing it at the same time, adding
and removing entries through the usual put and remove methods, that it
did not suffer from a ConcurrentModificationException.

I initially wrote the test on the train as preparation for the
workshop, but then had to go into the workshop with the plan that
perhaps enumerating over the keyset would then cause it to barf -
which it did.

Now at that point I thought that changing from HashMap to HashTable
would solve the ConcurrentModificationException, but it did not...
Whilst looking today at the Collections.synchronizedMap(xxx) the
Javadocs clearly state that the keySet should be synchronized with the
collection.

So, question 1 - why does the HashMap not suffer with
ConcurrentModificationException in the first place - there are plenty
of threads to cause it to trip up

Q2 - If HashMap does not trip up, then whats the advantage of using
the HashTable over HashMap?

Q2b - Am I safe to leave the HashMap unsynchronised as long as I don't
use the keyset / valueset / enumerations etc?

Q3 - Enumerating over the keyset breaks it, but then my test was to
dump the contents and caused a significant timing problem doing this.
I attempted to clone the hashmap contents so I could iterate over the
cloned version instead - in the hope that this might be quicker, but
then I experienced different problems (feel free to look at the
movie), but it appeared that the cloned hashmap had some dependency on
the original. When I say cloned, I mean Map m2 = new HashMap(map1);

Q4 - I ended up synchronising my methods using local synchronisation
blocks around the bits that needed it (I don't like synchronised
methods), What would you guys advocate?

Q5 - How do you efficiently enumerate through the entire hashmap
outputting all the key value pairs?

Problem 2 - This was related to primative v object comparisons...

I'm used to Java 1.4 where things like this were not valid

Integer i2 = 100;
i2++; // <-- fails

So during my talk I expected this to fail, but since I compiled with
Java 1.5 this actually worked. I then thought this must be Java 1.5
box / unboxing... I had learnt that it would do this in scenarios like
myIntArrayList.add(myPrimativeInt); but was suprised to see the ++
operator working on the Object!

I then thought, okay, it must be returning a new object - but why does
it change the reference to point to the new one? Here's a code
example...
Integer i1 = 50;
Integer i2 = new Integer(100);
int i3 = 150;
i3 ++;
System.out.println("i1 hash:"+i1.hashCode()+" value:"+i1+"
SystemId:"+System.identityHashCode(i1));
System.out.println("i2 hash:"+i1.hashCode()+" value:"+i2+"
SystemId:"+System.identityHashCode(i2));
i1 ++;
i2 = i3;
System.out.println("i1 hash:"+i1.hashCode()+" value:"+i1+"
SystemId:"+System.identityHashCode(i1));
System.out.println("i2 hash:"+i1.hashCode()+" value:"+i2+"
SystemId:"+System.identityHashCode(i2));

And here's the output...

i1 hash:50 value:50 SystemId:5488661
i2 hash:50 value:100 SystemId:6794265
i1 hash:51 value:51 SystemId:5487165
i2 hash:51 value:151 SystemId:15207001

As you can clearly see, i1 and i2 are Object type Integers (non
primative), so how come the ++ operator changes the original? I
expected i1 to remain the same and the i1++ to be 'lost' because I had
not assigned it back to a variable. I kind of expected i2 to be
different.

Any advice would be great, because then I can add the feedback to the
next workshop!

Thanks,
Rob,

[Christian Catchpole]

You are confusing the problems of not synchronizing with "concurrent
modification" of a keyset of whatever. The keyset is smart enough to
know as you use it, that the original map has changed (wether it was
done on another thread or not). Using a HashMap unsynchronized can
cause corruption, but the code cant detect when it happens and you
wont get an exception when it does. Once a HashMap is set up (on a
single thread or synchronized) you could use multiple threads to read
from it, but once multiple thread want to modify it, it will have to
be synchronized.

So the differences are: Concurrent Modification detects when the
backing Map is modified while your use a KeySet (or whatever) sourced
from it.
Synchronization errors happen at a lower level, where 2 threads are
updating the guts of the hashing buckets and things get out of whack.

Posse listeners will let me know if I got any of this wrong. :)

[Christian Catchpole]

As for the integer ++ thing. It must be to be inline with the
operation of primative ++ operations. Autoboxing is supposed to make
primitive / Object types interchangeable, so you would expect the ++
behavior to be the same.

int i = 0;
Integer ii = 0;

i++;
ii++

i == 1
ii == 1

Does that sound legitimate?

[Christian Catchpole]

As for how to iterate the collection while other threads access the
collection. You will have to clone it or extract what you need while
its synchronized. There is no magic solution to making a snapshot of
the map while others are changing it.

[Jess Holle]

Or use ConcurrentHashMap or some such if this is too much of a
bottleneck and do not care whether or not the iterator gives you entries
that were added/removed during the time you were iterating.

If you need more atomicity between iteration and add/remove, then you
can't take advantage of ConcurrentHashMap or related classes.

[Peter Becker]

On Wed, Jul 9, 2008 at 6:07 AM, Rob Wilson <net...@gmail.com> wrote:
[...]

i2 should be changed, but you have a copy and paste error and always
print the hashcode of i1 ;-)

If you look at this bit of code:

Integer i1 = 50
i1++;

Then that is equivalent to:

Integer i1 = 50;
i1 = i1 + 1;

which is equivalent to:

Integer i1 = Integer.valueOf(50);
i1 = Integer.valueOf(i1.intValue() + 1);

and in that form it is pretty obvious why you get a new Integer
object. Or more accurately on Sun's JVM: you get the next one from the
cache -- Integer.valueOf uses a cache for the signed byte range. That
cache also explains that the system IDs are so close together.

Note that the cache gives you fun when using the == operator on
Integer objects. On Sun's JVM it actually works as long as you stay in
the signed byte range, which means if you test only in that range but
could get something outside you have a nice little bug. Try this on a
Sun VM:

Integer i1 = 50;
Integer i2 = 500;
Integer i3 = 50;
Integer i4 = 500;
System.out.println(i1 == i3);
System.out.println(i2 == i4);

Note that unboxing is preferred over boxing, so comparing Integers to
ints tends to work. And <=, >= and .equals will always work, too.

Peter

[Reinier Zwitserloot]

Q1: ConcurrentModificationException does not mean what you think it
means.

thread collisions on a non-synchronized collection aren't 'detected'.
You get randomly screwed data in your map/list/set. That's how you'll
eventually 'notice'. Best case scenario you get a random unrelated
exception with probably a useless stacktrace (A real stack trace, just
pointing at code which is innocuous and not the problem).

ConcurrentModificationException occurs anytime that you're using
related things in a way that it wasn't designed for. The most likely
situation is trying to use an Iterator after you change something.
That's one of the reasons why Iterator.remove() exists; it's the only
way you get to remove things while continuing to use the iterator.
Trying to empty a map with: for ( Object x : map.keySet() )
map.remove(x); will ALWAYS generate a ConcurrentMOdificationException
even if you have one thread. In fact, threads have absolutely nothing
to do with this.

Q1 addendum: Don't use HashTable. Consider HashTable @Deprecated, and
consider Sun misguided in not actually adding the @Deprecated tag to
the java runtime libraries. HashTable is effectively the same as
Collections.synchronizedMap(new HashMap()), but 'internally
synchronized' maps, such as Collections.synchronizedMap/HashTable, are
almost never the right answer to a multi-threaded situation. For
example, let's say you want to add something to the map, but only if
the key doesn't exist yet:

if ( !map.containsKey(foo) ) map.put(foo, 0);

FAIL - EVEN if map is synchronized, that'll break in multi threaded
environments. The correct way is to do this:

synchronized ( map ) {
if ( !map.containsKey(foo) ) map.put(foo, 0);
}

and if you have to do your own synchronizing half the time, then why
even bother with the false sense of security that
Collections.synchronizedMap gives you? Threading is hard, and the
pitiful attempt to make things work right offered by HashTable/
Collections.synchronized just doesn't cut the cheese.

Q2b: No, not if you access it from multiple threads. In practice as
long as you just read it from it you have nothing to worry about, but
if you add a key in one thread while another thread is in the middle
of doing a lookup of a completely different key, odds are you'll get a
random element back, or null, eventhough the key is in there. Only
synchronizing writes won't be any help either - you'd have to sync
both the read and the write to the same locker. In general, you're
looking in the wrong place. Look at java.util.concurrent. Much better
than screwing about with 'synchronized'.

Q3: Constructor cloning of collections does not create dependencies of
any kind, it really copies everything. Of course, if your values or
keys are MUTABLE, then modifying the keys/values will also affect the
keys/values in the copied map. Using mutable things in maps is bad, by
the way. Don't - if you need to mutate a key, remove the entry from
the map, mutate the key, and add it back again. maps don't magically
update the location of a key in the hashtree, so mutating a key
without remove/readd is always a bug. Repeat after me: Immutable is
good. Immutable is good! As long as you don't add/remove anything to
the map while enumerating over it, you have no problem. try queueing
up the modifications you plan to make to the map and make them after
you're done iterating, or if you just need to remove stuff, use
Iterator.remove().

Q4: java.util.concurrent.

Q5: Only one way to do it. Lock it down (synchronize on something),
print em all out. To reduce locking time, make sure you're 'printing'
to a memory source, and not to the network or disk.

Q6: In java 1.5.0, using ++ on autoboxed generics stuff broke javac
(javac itself threw an exception, so, a bug in other words), but that
has been addressed.

i++, where i is of type Integer (or Long, Short, Byte, Character,
Long, or Float), is equivalent to:

(i = i+1)

in other words, first the 'i' gets autounboxed into an integer, then 1
is added to this integer, and as ++ is defined to do, the new value is
stored back in 'i'. Because 'i' is an Integer and not an int,
autoboxing is used to make that work. Thus i++ autounboxes and then
autoboxes. As far as I know, it is NOT guaranteed to be atomic, but
then, I don't think i++ is either, if i is an 'int'.

The fact that the SystemId's changed is the obvious tipoff that this
is happening. In fact, if the systemids didn't change, you just
discovered how to mutate Integer, Long, and friends, and that would be
a fundamental security issue, because those are supposed to be
immutable! Fortunately they are, and i++ on Integer will create a new
Integer object and assign it to 'i'.

On Jul 8, 10:07 pm, Rob Wilson <netp...@gmail.com> wrote:
> Hi all,
>

> I was doing my 4th Java workshop (recorded herehttp://www.ciderbob.com/babyduke/presentations) and during it I was

[Viktor Klang]

To summarize Reiniers essay above:  Using mutable datastructures in a concurrent context is a pain in the rectal area.

--
Viktor Klang
Rogue Software Architect

[Rob Wilson]

Thanks all for the excellent repies, especially Reinier for breaking
it down so far - I can add that to the next Java Workshop!

The warning about the cached values is interesting!! - I guess I would
never have seen this, because I wouldn't have done an object
comparison, I would have either used the object .equals on the two
Integer objects, or converted to primatives and done a comparison at
that point..

I'll yell when the next workshop is up (it will be #5).

Cheers,
Rob.

[Rob Wilson]

For those that might be interested, I've put up the feedback from this
post into the 5th workshop...

http://www.ciderbob.com/babyduke/presentations/

Any comments would be appreciated.

[Christian Catchpole]

Cool. Mr 'Catchpol' thanks you. :) I was having the Concurrent
Modification discussion today with some guys at work. I'll point them
back at your presentation. :)

[Rob Wilson]

My pleasure - incidentally I've tried adding credits to the bottom of
each slide, hopefully I included everyone at the right time.

Thanks all for making this subject much clearer.

Rob.