Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsFree MagazinesWhite PapersSubmit Content
Discussion GroupsASP.NETWindows FormsLanguages.NET FrameworkVisual Studio.NET
Articles.NET FrameworkASP.NETToolsWindows Forms
.NET DirectoryOpen Source ProjectsUser GroupsWeb Resources
Related Topics
Visual Basic 6SQL ServerMS AccessOther DB ProductsMS Server ProductsMore Topics ...

.NET Forum / .NET Framework / CLR / May 2007

Tip: Looking for answers? Try searching our database.

List<T> thread safety

Thread view: 
Enable EMail Alerts  Start New Thread
Thread rating: 
Torsten Seemann - 02 May 2007 08:08 GMT
Hi there

According to the framework documentation, a generic List is thread-safe for
multiple readers, as long as it is not being modified:

"A List can support multiple readers concurrently, as long as the collection
is not modified. Enumerating through a collection is intrinsically not a
thread-safe procedure. In the rare case where an enumeration contends with
one or more write accesses, the only way to ensure thread safety is to lock
the collection during the entire enumeration."

What I need is a generic list that supports thread-safety amongst multiple
readers and only one writer. Locking the list during both read and write
operations would result in all readers blocking eachother, violating the
current support for multiple concurrent readers.

Specifically, I need to be able to periodically add and remove list items
via one thread while multiple other threads are periodically enumerating the
list. While updating the list, the readers should wait for the update
operation to complete, but if no update is occurring, all readers should be
able to read simultaneously.

Is there a way to accomplish synchronization between only the writer and any
number of concurrents readers of a list, without the penalty of readers
blocking eachother?

Regards,
Torsten Seemann
Barry Kelly - 02 May 2007 08:41 GMT
> What I need is a generic list that supports thread-safety amongst multiple
> readers and only one writer. Locking the list during both read and write
[quoted text clipped - 10 lines]
> number of concurrents readers of a list, without the penalty of readers
> blocking eachother?

You can try using ReaderWriterLock, but be aware that it's not terribly
fast. Make sure you measure and see that you are indeed getting better
throughput than you'd get with simple

Another idea is to copy, modify and atomically swap in a new list. That
way, there's no blocking at all, and works quite well if writes are rare
and the list isn't excessively long. Very rough code:

---8<---
for (;;)
{
 myList = theList; // theList => the main list reference
 copy = CopyList(myList);
 copy.ModifyEtc();
 Thread.MemoryBarrier(); // Be extra safe to ensure all writes retired,
   // even though Interlocked.* already retires writes on x86 AFAIK,
   // before the reference is published.
 if (Interlocked.CompareExchange(ref theList, copy, myList) == myList)
   break;
}
--->8---

It doesn't block readers so they'll still see the old list even though
an update is in progress, but that's still the case even if you
serialized all access - there could be an arbitrary number of readers
ahead of the writer in the queue for the lock.

-- Barry

Signature

http://barrkel.blogspot.com/

Torsten Seemann - 02 May 2007 10:12 GMT
Hi Barry

I get your point with the atomic update, but unfortunately the list in
question could potentially contain a rather large number of items. I'm
worried that copying the list would be too slow.

The ReaderWriterLock on the other hand seems to be designed for exactly this
kind of problem. I will try experimenting a little with both approaches and
let some benchmarking be the judge :)

Thanks very much for your input.

Torsten

> > What I need is a generic list that supports thread-safety amongst multiple
> > readers and only one writer. Locking the list during both read and write
[quoted text clipped - 39 lines]
>
> -- Barry
Barry Kelly - 02 May 2007 12:43 GMT
> I get your point with the atomic update, but unfortunately the list in
> question could potentially contain a rather large number of items. I'm
> worried that copying the list would be too slow.

Don't forget that inserting into or deleting from a random location in
the list will average half the cost of copying the whole list, and will
still have the same complexity - O(n) - as copying. You may want to use
a dictionary instead.

-- Barry

Signature

http://barrkel.blogspot.com/

William Stacey [C# MVP] - 03 May 2007 19:13 GMT
IIRC, the readerwriter was updated with much improved speed in 3.0.
The other thing you could do is use an Interleave in the CCR, which is
effectively a non-blocking RW if you can handle switching to a port/handler
metaphore.
Signature

William Stacey [C# MVP]

| > What I need is a generic list that supports thread-safety amongst multiple
| > readers and only one writer. Locking the list during both read and write
[quoted text clipped - 39 lines]
|
| -- Barry
Jon Skeet [C# MVP] - 03 May 2007 19:52 GMT
> IIRC, the readerwriter was updated with much improved speed in 3.0.
> The other thing you could do is use an Interleave in the CCR, which is
> effectively a non-blocking RW if you can handle switching to a port/handler
> metaphore.

Hmm... ReaderWriterLock on my Vista box is still at version 2.0.0.0. I
wouldn't have expected it to change significantly in .NET 3.0, which
was really just bugfixes + the new libraries.

What I think you *may* be thinking of ReaderWriterLockSlim, which will
be in .NET 3.5. Joe Duffy talks about it here (watch for line breaks):

http://www.bluebytesoftware.com/blog/PermaLink,guid,c4ea3d6d-190a-48f8-
a677-44a438d8386b.aspx

Signature

Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet   Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

William Stacey [C# MVP] - 04 May 2007 02:00 GMT
That must be it  Jon.  It was Duffy that I remember reading.

Signature

William Stacey [C# MVP]
PCR concurrency library: www.codeplex.com/pcr
PSH Scripts Project www.codeplex.com/psobject

| > IIRC, the readerwriter was updated with much improved speed in 3.0.
| > The other thing you could do is use an Interleave in the CCR, which is
[quoted text clipped - 10 lines]
| http://www.bluebytesoftware.com/blog/PermaLink,guid,c4ea3d6d-190a-48f8-
| a677-44a438d8386b.aspx

Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.