Feedback requested: Enumerating Concurrent Collections

Parallel Programming with NET Feedback requested Enumerating | Insomnia Cure

Parallel Programming with NET Feedback requested Enumerating | Insomnia Cure — Tue, 09 Jun 2009 01:27:35 GMT

PingBack from http://insomniacuresite.info/story.php?id=9257

Parallel Programming with NET Feedback requested Enumerating | Weak Bladder

Parallel Programming with NET Feedback requested Enumerating | Weak Bladder — Mon, 08 Jun 2009 04:44:28 GMT

PingBack from http://weakbladder.info/story.php?id=2525

re: Feedback requested: Enumerating Concurrent Collections

Jerome Paradis — Sun, 12 Apr 2009 02:12:28 GMT

Here's a scenario I'm looking at presently:

An highly scalable distributed in-memory architecture, for millions of users. On a single server, you want all operations done in memory. Instead of using a disk based database with caching, the primary source of data is in memory. However, you want to synchronize changes to some data on disk (in a database) as live backup.

On solution I'm looking at (that I'll have to benchmark) is to use queue(s) to flag updated data objects. Then, background process(es) could navigate the queue to make changes to disk while emptying objects from the queue while going through the queue.

During the queue navigation, objects can be added to the queue from other in-memory updates.

In that scenario, it does not really matter if added objects to the queue are visible while navigating the queue. If we reach the end, we can check if new objects where added to the queue. If not, we can sleep a bit and go back to check the queue.

Of course, the example is simplified, but you get the idea. Such system would need to be benchmarked and probably need some multitheading balance to make sure the queues don't grow faster than they can eventually be emptied.

re: Feedback requested: Enumerating Concurrent Collections

supercat — Tue, 31 Mar 2009 18:50:02 GMT

The ability to support a "delete what doesn't belong" pattern is very useful, and I see no reason an iEnumerable should not be allowed to support such a thing (even though some styles of collection might have trouble with implementing it, I see no reason for the contract to require an exception in cases where an enumeration would otherwise be able to handle things sensibly).

If one is implementing a new design, I would suggest a "set options" method, along with an "available options" property, which would specify the acceptable/available behaviors for an enumerator in case of insertion and deletion (the bitmap passed to the method would offer a choice of acceptable options. If none of the acceptable behaviors were available, an exception would be thrown when attempting to set the option. Even if there were no settable options, the method could do nothing if the calling program's acceptable choices would work, and throw an exception if they would not.

For most scenarios, I would suggest that the preferred handling would be to specify that (1) an object which is inserted during an enumeration may or may not appear in that enumeration, with or without a reset; (2) an object which is deleted during an enumeration may or may not appear even with a reset, but if the object has already been enumerated it will not reappear until a reset; (3) all objects which existed prior to the start of enumeration and which are not deleted will be enumerated once each; (4) if an ordering is specified for the enumerator, items will be output consistent with that order (e.g. if a items are to be enumerated in alphabetical order and "aardvark" is added after "elephant" has been enumerated, "aardvark" should not be included in that enumeration); (5) ordering of items following a reset is arbitrary unless specified otherwise.

If one is designing a new interface for an enumerable type, it may be helpful to add a 64-bit 'ChangeSeed' value which, if sampled before the start of an enumeration and after its completion, will indicate whether anything in the collection may have changed during the enumeration. There are many times when throwing an exception because something changed would be very nasty behavior, but knowing that something changed would nonetheless be very useful.

re: Feedback requested: Enumerating Concurrent Collections

Yurik — Mon, 30 Mar 2009 17:56:19 GMT

I second all the requests for the concurrent priority queue implementation. It is badly needed in the framework, and being concurrent is paramount. Thanks!

re: Feedback requested: Enumerating Concurrent Collections

BK — Wed, 11 Mar 2009 20:04:07 GMT

This (below link) article describes a Concurrent collection in C# - MultiMap (similar to Dictionary)

http://www.codeproject.com/KB/cs/MultiMap_P_2.aspx

Websites tagged "concurrent" on Postsaver

Websites tagged "concurrent" on Postsaver — Sat, 17 Jan 2009 08:32:32 GMT

PingBack from http://www.postsaver.org/tags/concurrent

re: Feedback requested: Enumerating Concurrent Collections

Stephen Toub - MSFT — Fri, 26 Sep 2008 16:30:29 GMT

Frank, thanks for the suggestion.

Thomas, thanks for the feedback. There are a multitude of cases where seeing the latest and greatest version of a collection isn't all that important, and for those cases we've now heard quite a bit of feedback that support for concurrent enumeration is crucial. As Softlion points out, this is very similar in nature to isolation levels in databases, and they have been used successfully for a long time. Still, I definitely understand your concerns, as such capabilities do make it possible for developers to more easily make mistakes, assuming that the data they're looking at is both a snapshot and consistent with the current state of the collection.

Softlion, thanks for the comparison. You're not off subject at all.

re: Feedback requested: Enumerating Concurrent Collections

Softlion — Tue, 23 Sep 2008 22:59:31 GMT

Your problem can be compared to the problem resolved (or not) by database builders. In SQL Server this is called ISOLATION LEVEL.

SQL Select statements (for reading a collection) have hints (options), among them "nolock" (reader may see new entries inserted by another thread) and "readpast" (reader will never see new entries) which can fully work as parallelized.

So it may be a good idea to provide either one enumerator with an isolation level option, or at least two enumerators which behave differently: one for a nolock like reading, the other for a readpast like reading.

I hope I'm not off subject !

re: Feedback requested: Enumerating Concurrent Collections

Thomas van der Ploeg — Sat, 06 Sep 2008 01:06:42 GMT

I have a hard time imagining a scenario where an iterator pattern as such would be truly valuable on a concurrently updated collection. The set of values acquired and processed during the iteration will at best be somewhat similar as the set of values ‘contained’ in the collection. A snapshot variety doesn’t help much. Since the ‘contents’ of the collection will be blurry at the moment the snapshot is taken the snapshot itself will be blurry as well.

Using an iterator you would want to do one of two things. Either calculate a result or modify some state. In the first case I would imagine some transformation methods taking a continuation like the ones defined in LINQ. A concurrent ‘Select’ method, for example, would transform the values of the source and its result would be a concurrently updated collection itself. It would effectively shield the developer of the nastiness of concurrency.

When updating state some form of transaction would be required (STM?). A context wherein value sources can be queried and state updated in a safe manner. Such a context could be a required parameter for a new ‘GetEnumerator’ method.

It could be an option to have collection change notifications sent to a client of a snapshot iterator. The code to handle these will be complex and I don’t think this will lead to any convenient form of programming. Possibly such a mechanism could be used to construct higher level functions like the coined concurrent ‘Select’ method.

I think iterators in a truly concurrent environment without some form of transaction mechanism may have some niche uses but would in fact be a bad idea. They inherently have a very poor compatibility with multithreading and are an open invitation to software disasters.