Numpty "synchronized" question with ArrayList

[Richard Maher]

Hi,

WRT JavaDocs for the ArrayList class: -

Note that this implementation is not synchronized. If multiple threads
access an ArrayList instance concurrently, and at least one of the threads
modifies the list structurally, it must be synchronized externally. (A
structural modification is any operation that adds or deletes one or more
elements, or explicitly resizes the backing array; merely setting the value
of an element is not a structural modification.) This is typically
accomplished by synchronizing on some object that naturally encapsulates the
list. If no such object exists, the list should be "wrapped" using the
Collections.synchronizedList method. This is best done at creation time, to
prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new ArrayList(...));

and so on. . .

Can someone please explain why locking/synchronizing on the ArrayList
instance itself is not sufficent to serialize access?

eg: -

ArrayList<MyObj> myList = new ArrayList<MyObj>();

synchronized (myList) {

myList.add(aMyObj1);
lotsoffatomicisolatedstuff();
}

Are wrapper classes like collections really necessary here?

Cheers Richard Maher

 

[Eric Sosman]

Hi,

WRT JavaDocs for the ArrayList class: -

Note that this implementation is not synchronized. If multiple threads
access an ArrayList instance concurrently, and at least one of the threads
modifies the list structurally, it must be synchronized externally. (A
structural modification is any operation that adds or deletes one or more
elements, or explicitly resizes the backing array; merely setting the value
of an element is not a structural modification.) This is typically
accomplished by synchronizing on some object that naturally encapsulates the
list. If no such object exists, the list should be "wrapped" using the
Collections.synchronizedList method. This is best done at creation time, to
prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new ArrayList(...));

and so on. . .

Can someone please explain why locking/synchronizing on the ArrayList
instance itself is not sufficent to serialize access?

No one can explain, because it *is* sufficient -- provided you
remember to do it every time, and provided any clients that get a
view of your list also remember to do it every time, and ... The
value of synchronizedList() et al. is that you get an object that
takes care of its synchronization internally and automatically, even
if you or your clients get careless.

Note that even with an internally-synchronized list, external
explicit synchronization is sometimes necessary. For example,

List<Thing> slist = Collections.synchronizedList(...);
while (!slist.isEmpty()) {
Number num = slist.remove(0);
...
}

is faulty, because although the isEmpty() and remove() operations are
synchronized individually, the pair as a whole is not synchronized:
The state of slist could change after isEmpty() finishes and before
remove() starts. A sneakier failure:

for (Number num : slist) {
...
}

is faulty, because although the iterator() method (implied by the
loop) is synchronized, nothing protects the list from being changed
while the iteration is in progress. These need to be rewritten as

synchronized (slist) {
while (!slist.isEmpty()) {
Number num = slist.remove(0);
...
}
}

and

synchronized (slist) {
for (Number num : slist) {
...
}
}

even though slist "synchronizes itself."

 

[Knute Johnson]

Hi,

WRT JavaDocs for the ArrayList class: -

Note that this implementation is not synchronized. If multiple threads
access an ArrayList instance concurrently, and at least one of the threads
modifies the list structurally, it must be synchronized externally. (A
structural modification is any operation that adds or deletes one or more
elements, or explicitly resizes the backing array; merely setting the value
of an element is not a structural modification.) This is typically
accomplished by synchronizing on some object that naturally encapsulates the
list. If no such object exists, the list should be "wrapped" using the
Collections.synchronizedList method. This is best done at creation time, to
prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new ArrayList(...));

and so on. . .

Can someone please explain why locking/synchronizing on the ArrayList
instance itself is not sufficent to serialize access?

It is.

eg: -

ArrayList<MyObj> myList = new ArrayList<MyObj>();

synchronized (myList) {

myList.add(aMyObj1);
lotsoffatomicisolatedstuff();
}

Are wrapper classes like collections really necessary here?

Cheers Richard Maher

No but they are a handy item so you don't have to do synchronization on
a list that is only modified in one thread.

 

[Joshua Cranmer]

Can someone please explain why locking/synchronizing on the ArrayList
instance itself is not sufficent to serialize access?

It is sufficient. However, if you don't wrap it in synchronizedList,
that means you must guarantee that every user of the list handles
synchronization properly. If you publish this in a public API, it is
possible that people don't perform the synchronization on it properly,
which could lead to blessed internal inconsistencies.

Are wrapper classes like collections really necessary here?

Not necessary, just a bit safer.

 

[markspace]

I'm going to agree with the other three posters, but say it in a
slightly different way.

Can someone please explain why locking/synchronizing on the ArrayList
instance itself is not sufficent to serialize access?

Because you have no guarantee that any other user of this list will
synchronize correctly. For example, you write:

ArrayList<MyObj> myList = new ArrayList<MyObj>();

synchronized (myList) {

myList.add(aMyObj1);
lotsoffatomicisolatedstuff();
}

Then I write:

Collection col = myList;

Are wrapper classes like collections really necessary here?

YES! If you replace your line where you assign myList with

ArrayList<MyObj> myList = Collections.syncrhonizedList(
new ArrayList<MyObj>() );

then both code snippets are safe.

This is important to realize in multi-threading: all accesses (read or
write) must use the same lock to synchronize with or the result is not
thread safe. All readers of your list must synchronize on the same
object that you used when you wrote data to the list or there simply is
no thread safety at all. When I read your list by passing it to the
addAll() method (with your first example), that access is not
synchronized and therefore not safe.

Cf. Java Concurrency in Practice by Brain Goetz. Srrsly.

 

[Lew]

YES!  If you replace your line where you assign myList with

   ArrayList<MyObj>  myList = Collections.synchronizedList(
             new ArrayList<MyObj>() );

then both code snippets are safe.

Except for that the declaration will fail. Use

List <MyObj> myList =
Collections.synchronizedList( new ArrayList <MyObj> () );

 

[Richard Maher]

Hi Eric,

No one can explain, because it *is* sufficient -- provided you
remember to do it every time,

Ok, no problem.

and provided any clients that get a
view of your list also remember to do it every time,

Are you using view in the regular english sense of the word here or are
there specific Java constructs that you had in mind?

In my case the ArrayList is used internally, privately, and never return-ed,
but even if the opposite was the case then as long as the consumer(s) also
lock the ArrayList via their reference variables then all is serialized yes?

and ... The
value of synchronizedList() et al. is that you get an object that
takes care of its synchronization internally and automatically, even
if you or your clients get careless.

Ok I can see the usefulness/transparency. Thanks.

Note that even with an internally-synchronized list, external
explicit synchronization is sometimes necessary. For example,

List<Thing> slist = Collections.synchronizedList(...);
while (!slist.isEmpty()) {
Number num = slist.remove(0);
...
}

is faulty, because although the isEmpty() and remove() operations are
synchronized individually, the pair as a whole is not synchronized:
The state of slist could change after isEmpty() finishes and before
remove() starts. A sneakier failure:

for (Number num : slist) {
...
}

is faulty, because although the iterator() method (implied by the
loop) is synchronized, nothing protects the list from being changed
while the iteration is in progress. These need to be rewritten as

synchronized (slist) {
while (!slist.isEmpty()) {
Number num = slist.remove(0);
...
}
}

and

synchronized (slist) {
for (Number num : slist) {
...
}
}

even though slist "synchronizes itself."

Ah thanks for the heads-up.
And thanks for the very useful response.

Cheers Richard Maher

 

[markspace]

In my case the ArrayList is used internally, privately, and never return-ed,
but even if the opposite was the case then as long as the consumer(s) also
lock the ArrayList via their reference variables then all is serialized yes?

And thread safe, yes. As long as you use the same lock for all access
(could be any lock, not just the reference variable, but you have to use
the same one for all access) then you are both thread safe and have
mutex over the List.

 

[Richard Maher]

Hi Mark

And thread safe, yes. As long as you use the same lock for all access
(could be any lock, not just the reference variable, but you have to use
the same one for all access) then you are both thread safe and have mutex
over the List.

Thanks for that. Just to pin something down (in my head and not trying to be
pedantic) that the locks are on object instances and not reference
variables. IOW, synchronized(refVar1) in Thread A is the same as
synchronized(obj1) in Thread B as long as refVar1 had been initialized/set
to obj1.
Cheers Richard Maher

 

[markspace]

Thanks for that. Just to pin something down (in my head and not trying to be
pedantic) that the locks are on object instances and not reference
variables. IOW, synchronized(refVar1) in Thread A is the same as
synchronized(obj1) in Thread B as long as refVar1 had been initialized/set
to obj1.

Yes, objects, not references. One consequence of Java's design is that
it's common to use "synchronize( this )" inside an object to synchronize
on itself, no reference variable at all is involved there.

Mainly that technique can allow you to only synchronize on the parts of
a method that you really need synchronized, and not the whole method
(which might be rather long or even involve some IO). The "whole
method" being what you'd get if you just put "synchronized" on the
method declaration.

 

[Arne Vajhøj]

WRT JavaDocs for the ArrayList class: -

Note that this implementation is not synchronized. If multiple threads
access an ArrayList instance concurrently, and at least one of the threads
modifies the list structurally, it must be synchronized externally. (A
structural modification is any operation that adds or deletes one or more
elements, or explicitly resizes the backing array; merely setting the value
of an element is not a structural modification.) This is typically
accomplished by synchronizing on some object that naturally encapsulates the
list. If no such object exists, the list should be "wrapped" using the
Collections.synchronizedList method. This is best done at creation time, to
prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new ArrayList(...));

and so on. . .

Can someone please explain why locking/synchronizing on the ArrayList
instance itself is not sufficent to serialize access?

eg: -

ArrayList<MyObj> myList = new ArrayList<MyObj>();

synchronized (myList) {

myList.add(aMyObj1);
lotsoffatomicisolatedstuff();
}

Are wrapper classes like collections really necessary here?

The old Vector class has methods that are synchronized.

The new ArrayList class does not.

There are 3 relevant cases:
A) single threaded access to the data
B) multi threaded but single operation access to the data
C) multi threaded and multi operation access to the data

Vector ArrayList
A unnecessary synchronized fine
B fine need external synchronized
C need external synchronized need external synchronized
+unnecessary synchronized

So because A+C is more likely than B then ArrayList is
the right way to do it.

Java found out of that in Java 1.2.

And surprisingly .NET started the same way as Java (even though 1.2
was out) and then changed in 2.0.

To make the handling of B a little bit easier then
the Collections.synchronizedList method exist to save
using synchronized everywhere the methods are called.

This both makes the code more readable and prevents
someone forgetting to use synchronized for access.

So definitely good.

But it is only applicable to case B.

Arne

 

[markspace]

Except for that the declaration will fail. Use

List<MyObj> myList =
Collections.synchronizedList( new ArrayList<MyObj> () );

Oops, yeah, none of the code I posted was checked with a compiler, I
just did it all off the top of my head.

 

[Lew]

Hi,

What does "numpty" mean?

 

[Mike Schilling]

What does "numpty" mean?

Just what I choose it to mean -- neither more nor less.

 

[Richard Maher]

The old Vector class has methods that are synchronized.

The new ArrayList class does not.

There are 3 relevant cases:
A) single threaded access to the data
B) multi threaded but single operation access to the data
C) multi threaded and multi operation access to the data

Vector ArrayList
A unnecessary synchronized fine
B fine need external synchronized
C need external synchronized need external synchronized
+unnecessary synchronized

So because A+C is more likely than B then ArrayList is
the right way to do it.

Java found out of that in Java 1.2.

And surprisingly .NET started the same way as Java (even though 1.2
was out) and then changed in 2.0.

To make the handling of B a little bit easier then
the Collections.synchronizedList method exist to save
using synchronized everywhere the methods are called.

This both makes the code more readable and prevents
someone forgetting to use synchronized for access.

So definitely good.

But it is only applicable to case B.

Illuminating. Thanks as always.

Arne

Cheers Richard Maher

 

[Richard Maher]

What does "numpty" mean?

Picked it up when I lived in England but I think it's Scotts. Basic
translation: - "I'm probably going to look like a complete knob-head asking
this, but . . . "
Cheers Richard Maher

 

[Eric Sosman]

Hi Eric,

[...]
Can someone please explain why locking/synchronizing on the ArrayList
instance itself is not sufficent to serialize access?

No one can explain, because it *is* sufficient -- provided you
remember to do it every time,

Ok, no problem.

and provided any clients that get a
view of your list also remember to do it every time,

Are you using view in the regular english sense of the word here or are
there specific Java constructs that you had in mind?

I was making an attempt at English. Some specific Java constructs
that qualify as "views of your list" might be:

- An actual reference to your List

- An Iterator or ListIterator for your List

- An unmodifiableList() or other "wrapper" of your List

- An externally-accessible method that accesses the List

.... and there are probably a few others I haven't thought of.

In my case the ArrayList is used internally, privately, and never return-ed,

Then how can two different threads get access to it? If the List
is used by only one thread, there's no need to synchronize -- one thread
can do only one thing at a time, so there's no way for it to interfere
with itself.

Much hinges, I guess, on exactly what you mean by "internally,
privately, and never return-ed."

but even if the opposite was the case then as long as the consumer(s) also
lock the ArrayList via their reference variables then all is serialized yes?

If more than one thread accesses the List, all must synchronize on
the same object while doing so. Commonly, that object is the List
itself, but in fact any object would do, so long as all threads use
the same one.

Special case: If you create an populate a List in one thread before
you "publish" it to others, and if it is purely read-only thereafter,
synchronization might not be needed. It depends on the implementation
of the List, though: For example, a "self-organizing" List might change
its internal state in response to a query, and the state change would
require synchronization. I don't think any of the Java-provided
collections do such things, but I could be wrong.

 

[Richard Maher]

Hi Eric,

Then how can two different threads get access to it?

Look, unfortunately you'll be seeing a lot more of me in weeks to come as
I'm coming to the end of a project that (barely!) pays the bills and can get
back to my floundering with the 2nd love of my life - Applets.

Not Applets as you/they know them but infrastructure/blind/faceless Applets.
I am delivering (trying to deliver single sign-on,
single-reader/multi-writer, tab-aware, blah-blah-blah wunder-applet that
multiplexes server responses to the appropriate tabs and Applet(s)
instances.

Anyway, cut a loooooong story short, I've got a shit-load of browser
specific :-( threading issues and I'm know trying to knock them down one by
one. First port of call is "Is my internal ArrayList<JSObject> flakey when
it comes to mutexing?" I just need to make sure that I'm synching with me
properly.

FYI, each tab-resident Applet instance accesses/populates a "static"
JSObject database in the form of an ArrayList (there are more such database
(asynch messages and so on) that occur but none accessible from JavaScript
or other Java.
Cheers Richard Maher

 

[Eric Sosman]

Hi Eric,

Then how can two different threads get access to it?

Look, unfortunately you'll be seeing a lot more of me in weeks to come as
[...]

Look, I intended no offense. I was just pointing out that the
mere fact that an ArrayList is used in a multi-threaded program does
not in and of itself imply that synchronization is needed. If the
List (or any mutable object) is used by just one thread and never
touched by others, you can just forget about synchronization since
there are no concurrent accesses to guard against. You only need
synchronization if the object is used by two or more threads -- which
is why I raised the question about what "internally, privately, and
never return-ed" means. You may (*may*) be working harder than you
need to.

 

[Richard Maher]

Hi Eric,

Hi Eric,

In my case the ArrayList is used internally, privately, and never
return-ed,

Then how can two different threads get access to it?

Look, unfortunately you'll be seeing a lot more of me in weeks to come as
[...]

Look, I intended no offense.

None taken! I'm ostensibly one of the most offensive people you'll meet in a
newsgroup and have pretty thick skin.

I was just pointing out that the
mere fact that an ArrayList is used in a multi-threaded program does
not in and of itself imply that synchronization is needed. If the
List (or any mutable object) is used by just one thread and never
touched by others, you can just forget about synchronization since
there are no concurrent accesses to guard against. You only need
synchronization if the object is used by two or more threads -- which
is why I raised the question about what "internally, privately, and
never return-ed" means.

Thanks again for all the info.

You may (*may*) be working harder than you
need to.

Look, if you can show me your Socket implementaion that let's multiple
heterogenous applets on multiple heterogenous web-pages share a single
Socket connection with a server with a single reader thread and multiple
(1:applet instance) writers that multiplexes the responses to the
appropriate JSObject instance then I'm up for the patronising.

Alternatively, someone here can explain why the rest of the world is
"willing" to put up with the complete piece of shit that is HTML5
WebSockets.

Anyway, sorry to flame and digress.
Cheers Richard Maher