20

The following code explains my question. I know the list is not thread safe. But what is the underlying "real" reason of this?

 class Program { static void Main(string[] args) { List<string> strCol = new List<string>(); for (int i = 0; i < 10; i++) { int id = i; Task.Factory.StartNew(() => { AddElements(strCol); }).ContinueWith((t) => { WriteCount(strCol, id.ToString()); }); } Console.ReadLine(); } private static void WriteCount(List<string> strCol, string id) { Console.WriteLine(string.Format("Task {0} is done. Count: {1}. Thread ID: {2}", id, strCol.Count, Thread.CurrentThread.ManagedThreadId)); } private static void AddElements(List<string> strCol) { for (int i = 0; i < 20000; i++) { strCol.Add(i.ToString()); } } }
Improve this question
1
  • 3
    looks like some of the threads are writing over each other. Internally list must be using a counter to increment to next position, and since its not thread safe, its overwriting values Commented Mar 26, 2012 at 18:26

2 Answers 2

Reset to default
40

I will skip the obvious answer "List is not thread safe" - this you already know.

List items are kept in an internal array. There are at least two stages (from logical point of view) when adding an item to a List. First, List gets an index indicating where to put new item. It puts new item into array using this index. Then it increments the index and this is stage two. If second (or third, forth, ...) thread happens to add new item at the same time it may be that there will be two (3, 4, ...) new items put into the same array location before the index is incremented by the first thread. Items are overwritten and lost.

The internal operations of adding new item and incrementing index must be always done in one go for the list to be thread safe. That's what is called critical section. This can be achieved by locks.

Hope this explains a bit.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

18

This is because List<T> is not thread safe.

You should use a thread safe collection for this, such as one of the collections in System.Collections.Concurrent. Otherwise, you'll need to synchronize all access to the List<T> (ie: put every Add call within a lock), which will defeat the purpose of calling this using multiple threads entirely, as you're not doing any other work in this situation.

Improve this answer

4 Comments

as stated in the question. I know the list is not thread safe. But what is the underlying "real" reason of this?
@CuiPengFei the "real" reason is likely that there are operations (data copies, array resizes, etc) that are done without locking, under the assumption that the developer is not interacting with the List from multiple threads at once. The additional synchronization required to make the List thread safe would significantly impact performance, and so the BCL designers chose to omit it and document the lack of thread safety so that if you need thread safe access you can built it around the list yourself. Same as in Java's ArrayList and many other List classes.
@CuiPengFei: Because, not being thread-safe, the act of adding to List<T> is not completely atomic. One thread starts to add an element, another thread short-circuits it by adding its own element.
@CuiPengFei When List.Add is called, it just checks to see which element in the underlying array to write to... It's kind of like "Get current size", "Set value of [size] to new value", "Set current size". If another thread starts when the first thread's "Set" occurs, they'll both end up writing to the same element, and setting the overall size the same, and one value will "disappear" from the results.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.