Frequently Asked Questions

  • What are these collections for?
    • These collections allow concurrent readers and writers, with no work on your part
    • Collections are designed to allocated as little as possible in the most commonly used code paths. Making them suitable for use on the .net compact framework
  • What are these collections not for?
    • These collections are not simply for dropping into a program, and adding more threads, some code changes are needed in certain parts. The system, is designed in such a way that these changes are usually rather easy.

Namespaces

  • Concurrent
    • These collections are truly concurrent, no locks are used in their implementation. They will generally be the quickest collections.
    • Such collections are incredibly difficult to design, limiting the range of them included in the project
  • Sharded
    • These collections are not truly concurrent, each collection is broken up into shards, only 1 thread may access a single shard at once. This allows many (but not unlimited) concurrent readers and writers.
    • many collections can be implemented in a sharded manner, ShardedCollection encompasses this by exposing a system for taking anything that implement ICollection and sharding it with minimal work.
  • Spinlocked
    • These collections are not really concurrent at all, instead the entire collection is locked every time a method is called.
  • Blocking
    • These collections are designed to block until a result is available. For example a blocking queue will not return from a dequeue method until there is something to dequeue

Transactions

All concurrent collections suffer from the problem of non determinism. Generally, you cannot assume anything about the state of a collection when you do an operation. For example:

Dictionary<String, int> dictionary = new Dictionary<String, int>();
dictionary.add("key", 42);
if (dictionary.contains("key"))
{
//Vital point here (see below)
foo(dictionary["key"]);
}

This is a perfectly valid operation, if a key is in the dictionary then call a method which uses the value indexed by that key. However, in a concurrent situation imagine if another thread removed "key" at the point marked "vital point here" in the code. The containment query would succeed, but the line to actually fetch the value and use it would fail because it's no longer contained.

In this situation you would need to use a transaction. A transaction accepts a key, and a delegate, it then locks this key and executes the method - nothing else can change that key while the transaction is running. for this example you would need to write it like so:

ShardedDictionary<String, int> dictionary = new ShardedDictionary<String, int>(10);
dictionary.add("key", 42);
dictionary.Transaction<bool>(txn, "key");

private bool txn(KeyValuePair<String, int> a)
{
if (dictionary.Contains(a.Key))
{
foo(dictionary[a.Key]);
}
}

This is slightly, but not much, more complicated. First we create a ShardedDictionary instead of a normal dictionary, then add a value. Next comes the containment query, in the first example the query and subsequent action are not run in a transaction, which leads to race conditions. In this new example, the method txn is run in a Transaction based on the key "key", while the txn method is running nothing else can change anything to do with the "key". The txn method then does what we did in the first example, testing for containment, and doing something if the value is present. The arguments passed to txn are slightly confusing, in the case of the ShardedDictionary the key is a KeyValuePair, the key of this pair is the dictionary key being operated on, the value is meaningless.

Last edited Mar 23, 2010 at 1:48 PM by martindevans, version 8

Comments

No comments yet.