Why is List not thread-safe?

Question

From the following site:

http://crfdesign.net/programming/top-10-differences-between-java-and-c

Unfortunately, List<> is not thread-safe (C#’s ArrayList and Java’s Vector are thread-safe). C# also has a Hashtable; the generic version is:

What makes List<T> not thread-safe? Is it implementation problem on .NET framework engineer's part? Or are generics not thread-safe?

According to MSDN [ArrayList](http://msdn.microsoft.com/en-us/library/system.collections.arraylist.aspx#threadSafetyToggle) and [List(Of T)](http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx#threadSafetyToggle) have the same thread safety. `ArrayList` does provide the [Synchronized](http://msdn.microsoft.com/en-us/library/system.collections.arraylist.synchronized.aspx) wrapper however. — Mark Hurd, May 10 '12 at 04:52

score 69 · Accepted Answer · edited Sep 27 '12 at 04:25

69

You really need to classify Java's Vector's type of thread safety. Javas Vector is safe to be used from multiple threads because it uses synchronization on the methods. State will not be corrupted.

However, Java's vector's usefulness is limited from multiple threads without additional synchronization. For example, consider the simple act of reading an element from a vector

Vector vector = getVector();
if ( vector.size() > 0 ) { 
  object first = vector.get(0);
}

This method will not corrupt the state of the vector, but it also is not correct. There is nothing stopping another thread from mutating the vector in between the if statement an the get() call. This code can and will eventually fail because of a race condition.

This type of synchronization is only useful in a handfull of scenarios and it is certainly not cheap. You pay a noticable price for synchronization even if you don't use multiple threads.

.Net chose not to pay this price by default for a scenario of only limited usefulness. Instead it chose to implement a lock free List. Authors are responsible for adding any synchronization. It's closer to C++'s model of "pay only for what you use"

I recently wrote a couple of articles on the dangers of using collections with only internal synchronization such as Java's vector.

Reference Vector thread safety: http://www.ibm.com/developerworks/java/library/j-jtp09263.html

edited Sep 27 '12 at 04:25

user

5,335
7
47
63

answered Apr 01 '09 at 03:55

JaredPar

733,204
149
1,241
1,454

14

Small note: "lock free" implies "synchronized without any locks", not "no locks". http://en.wikipedia.org/wiki/Lock_free – Craig Gidney Apr 01 '09 at 06:20
I concur with Strilanc: I had to double-take your use of the terminology "lock free". – Daniel Fortunov Apr 18 '09 at 19:39
Methods like "Count" may be perfectly reasonably and legitimately used on a thread-safe collection, for the purpose of deciding not to bother with something. For example, if one needs to perform some operation using two items taken from a queue, a perfectly reasonable pattern might be to use a property to check the count (with a read-barrier rather than a lock) and, if the count is sufficient, acquire the lock and check the count again. If it is still sufficient, perform the operation; otherwise skip it. Release the lock in any case. – supercat May 11 '12 at 19:57
@supercat your solution involves a lock though and hence is correct. My argument is that `Vector` as coded in the java libraries can't be used safely in the manner you describe without a lock. It's just not possible because every result you find is invalid the moment you read it. – JaredPar May 11 '12 at 20:00
@JaredPar: My point was that methods like `Count` can often be useful outside of locks, for purposes of early-exiting common cases. – supercat May 11 '12 at 20:08
@supercat what would you ever use it for? I'd very much contend that without a lock methods like Count are virtually worthless (except for logging / tracing). You can't make any predictions based on the value b/c it can change before your code even processes the value. – JaredPar May 11 '12 at 20:13
@JaredPar: I just gave an example: if before acquiring a lock one checks whether `Count()` contains a value that would be sufficient for what one needs to do, one can avoid a lock acquire/release cycle in the event that there's nothing to do. If the normal state of affairs is for the collection not to contain enough data to be worth processing, such an optimization can sometimes offer significant benefit. Occasionally one will check `Count()`, decide to acquire the lock, check `Count()` again, and find that the data has disappeared so there's no longer anything to do, but ... – supercat May 11 '12 at 20:19
...if that happens the only consequence is the wasted effort acquiring the lock. If one can avoid that wasted effort in 95% of cases where there's nothing to do, that may be a win even if one doesn't avoid it in all of them. – supercat May 11 '12 at 20:20
@supercat this is still a scenario where the totality of your solution requires a lock. This is the point I'm trying to drive home with my post. I agree in certain limited scenarios call like `Count` can be used as a cheap lock avoidance trick. But note this doesn't actually work with `vector` as `size` itself acquires a lock. – JaredPar May 11 '12 at 20:29

score 21 · Answer 2 · answered Apr 01 '09 at 03:54

Why would it be thread-safe? Not every class is. In fact, by default, classes are not thread-safe.

Being thread-safe would mean that any operation modifying the list would need to be interlocked against simultaneous access. This would be necessary even for those lists that will only ever be used by a single thread. That would be very inefficient.

score 9 · Answer 3 · edited Nov 20 '16 at 03:25

9

It is simply a design decision to implement the types not thread safe. The collections provide the property SyncRoot of the interface ICollection and the Synchronized() method on some collections for explicitly synchronizing the data types.

Use SyncRoot to lock an object in multithreaded environments.

lock (collection.SyncRoot)
{
   DoSomething(collection);
}

Use collection.Synchronized() to obtain a thread-safe wrapper for the collection.

edited Nov 20 '16 at 03:25

David Ferenczy Rogožan

23,966
9
79
68

answered Apr 01 '09 at 03:58

Daniel Brückner

59,031
16
99
143

4

See JaredPar's articles for an explanation of why this is almost certainly not what you want to do. – Daniel Earwicker Apr 03 '09 at 18:35

score 2 · Answer 4 · edited Feb 08 '15 at 05:50

2

For true thread safety, List<> and other collection types would need to be immutable. With the parallel extensions to .NET coming out in .NET 4.0 we'll be seeing thread safe versions of the most commonly used collections. Jon Skeet touches on some of this.

edited Feb 08 '15 at 05:50

John Saunders

160,644
26
247
397

answered Apr 01 '09 at 05:58

Abhijeet Patel

6,562
8
50
93

score 2 · Answer 5 · answered Apr 03 '09 at 18:18

The race-condition possibility JaredPar mentions is the scary consequence of relying on Vector's supposed thread-safety. It's the sort of thing that results in the "every ninth Tuesday the app does something weird"-sort of defect report that will drive you insane.

There are a number of truly thread-safe collections coming in .Net 4, with an interesting side-effect that they allow single-threaded modification of the collection while enumerating, but there's a performance hit that comes with thread-safety, sometimes a pretty big one.

So the logical thing for a framework developer to do is keep the class as performant as possible for the 95% of users who probably won't be doing threading and rely on those who do multi-thread to know what they have to do to keep it safe.

score 0 · Answer 6 · answered Jan 29 '10 at 12:39

0

use SynchronizedCollection it also provides a Constructor-Parameter to use a shared sync :)

answered Jan 29 '10 at 12:39

mo.

3,474
1
23
20

Why is List not thread-safe?

6 Answers6

Linked