Thread safe collections in .NET: ConcurrentQueue

Concurrent collections in .NET work very much like their single-thread counterparts with the difference that they are thread safe. These collections can be used in scenarios where you need to share a collection between Tasks. They are typed and use a lightweight synchronisation mechanism to ensure that they are safe and fast to use in parallel programming.

Concurrent queues

If you don’t know what Queues are then you can read about them here. The Queue of T generic collection has a thread-safe counterpart called ConcurrentQueue. Important methods:

  • Enqueue(T element): adds an item of type T to the collection
  • TryPeek(out T): tries to retrieve the next element from the collection without removing it. The value is set to the out parameter if the method succeeds. Otherwise it returns false.
  • TryDequeue(out T): tries to get the first element. It removes the item from the collection and sets the out parameter to the retrieved element. Otherwise the method returns false

The ‘try’ bit in the method names implies that your code needs to prepare for the event where the element could not be retrieved. If multiple threads retrieve elements from the same queue you cannot be sure what’s in there when a specific thread tries to read from it.

Example

Declare and fill a concurrent queue:

ConcurrentQueue<int> concurrentQueue = new ConcurrentQueue<int>();

for (int i = 0; i < 5000; i++)
{
	concurrentQueue.Enqueue(i);
}

We’ll want to get the items from this collection and check if all of them have been retrieved using a counter. The counter will also be shared among the threads using the ‘lock’ technique we saw in this post – or actually something that is similar to the ‘lock’ keyword: the Interlocked class. Interlocked has an Increment method which accepts a ref int parameter. It will increment the incoming integer in an atomic operation.

int itemCount = 0;

Task[] queueTasks = new Task[20];
for (int i = 0; i < queueTasks.Length; i++)
{
	queueTasks[i] = Task.Factory.StartNew(() =>
	{
		while (concurrentQueue.Count > 0)
		{
			int currentElement;
			bool success = concurrentQueue.TryDequeue(out currentElement);
			if (success)
			{
				Interlocked.Increment(ref itemCount);
			}
		}
	});
}

The while loop will ensure that we’ll try to dequeue the items as long as there’s something left in the collection.

Wait for the tasks and print the number of items processed – the counter should have the same value as the number of items in the queue:

Task.WaitAll(queueTasks);
Console.WriteLine("Counter: {0}", itemCount);

View the list of posts on the Task Parallel Library here.

Advertisements

Thread safe collections in .NET: ConcurrentBag

Concurrent collections in .NET work very much like their single-thread counterparts with the difference that they are thread safe. These collections can be used in scenarios where you need to share a collection between Tasks. They are typed and use a lightweight synchronisation mechanism to ensure that they are safe and fast to use in parallel programming.

Concurrent bags

Concurrent bags are similar to concurrent stacks and concurrent queues but there’s a key difference. Bags are unordered collections. This means that the order of the items is not the same as how they were inserted. So concurrent bags are ideal if you would like to share a List of T generic collection among several tasks.

Important methods:

  • Add(T element): adds an item of type T to the collection
  • TryPeek(out T): tries to retrieve the next element from the collection without removing it. The value is set to the out parameter if the method succeeds. Otherwise it returns false.
  • TryTake(out T): tries to get the first element. It removes the item from the collection and sets the out parameter to the retrieved element. Otherwise the method returns false

The ‘try’ bit in the method names imply that your code needs to prepare for the event where the element could not be retrieved. If multiple threads retrieve elements from the same list you cannot be sure what’s in there when a specific thread tries to read from it.

Example

The example is almost identical to what we saw for the collections discussed previously in the posts on TPL.

Declare and fill a concurrent bag:

ConcurrentBag<int> concurrentBag = new ConcurrentBag<int>();

for (int i = 0; i < 5000; i++)
{
	concurrentBag.Add(i);
}

Next we’ll try to take every item from the bag. The bag will be accessed by several tasks at the same time. The counter variable – which is also shared and synchronised- will be used to check if all items have been retrieved.

int counter = 0;

Task[] bagTasks = new Task[20];
for (int i = 0; i < bagTasks.Length; i++)
{
	bagTasks[i] = Task.Factory.StartNew(() =>
	{
		while (concurrentBag.Count > 0)
		{
			int bagElement;
			bool success = concurrentBag.TryTake(out bagElement);
			if (success)
			{
				Interlocked.Increment(ref counter);
			}
		}
	});
}

The while loop will ensure that we’ll try to take the items as long as there’s something left in the collection.

Wait for the tasks and print the number of items processed – the counter should have the same value as the number of items in the bag:

Task.WaitAll(bagTasks);
Console.WriteLine("Counter: {0}", counter);

View the list of posts on the Task Parallel Library here.

Efficient linked lists in .NET

Sometimes you need a collection that’s modified a lot: you insert, update and remove items. A List of T is then inefficient as it needs to constantly rearrange all other items. The LinkedList class might be a better candidate.

A linked list is a doubly-linked list. Each item has a Next and Previous pointer to look at which element comes right before and after a particular object in the list. A linked list is very efficient at inserting and deleting items in particular.

Initialisation:

LinkedList<int> intList = new LinkedList<int>();

There are multiple ways to add a new item: AddAfter, AddBefore, AddFirst, AddLast.

Adding a new item on the top of the list:

intList.AddFirst(2);

Putting 3 ahead of 2:

intList.AddFirst(3);

It’s not possible to directly pull out an item with an indexer, such as [2].

You can, however, iterate through the collection:

foreach (var i in intList)
{
}

You can get a reference of the first item with the First property:

LinkedListNode<int> firstItem = intList.First;

You can then insert an item after that:

intList.AddAfter(first, 5);

This will add 5 in between 3 and 2.

Inserting before the first item is equally easy:

intList.AddBefore(first, 5);

You can get to the last item… can you guess how? Through the Last property.

The First and Last properties do not return an int, or the type that you provided in place of T. It returns a LinkedListNode of type T, which is int in this case. This object has a Previous and Next properties:

LinkedListNode<int> firstItem = intList.First;
firstItem.Previous;
firstItem.Next;

It also has a Value property which returns the actual value of the LinkedListNode object.

Another way of iterating through the list is the following:

LinkedListNode<int> item = intList.First;
while (item != null)
{
    int val = item.Value;
    item = item.Next;
}

Removing items can be done with methods such as RemoveLast(), RemoveFirst(), Remove(item).

Using HashSet in .NET to allow unique values only

Hashsets allow you to add unique values into a collection. So if you have a rule that no two identical objects are added to a collection then a Set is a good choice.

Initialisation:

HashSet<int> integerSet = new HashSet<int>();

Add new items:

integerSet.Add(2);
integerSet.Add(3);

There’s no direct access available with an index parameter, like [2]. There’s no particular order to the items inserted to a Set. You’ll never know where the items end up and which one is the first in the list.

You can simply iterate through the values like this:

foreach (int value in integerSet)
{
}

If you try to add an integer that already exists then it will ignored. The Add method has a boolean return value. It will return false if the item you’re trying to add already exists in the collection and true otherwise.

You can easily build the intersection of two sets:

HashSet<int> integerSet1 = new HashSet<int>(){1, 2, 3};
HashSet<int> integerSet2 = new HashSet<int>(){2, 3, 4};

integerSet1.IntersectWith(integerSet2);

This operation will only keep those items in integerSet1 that were available in both sets, i.e. the intersection of the two sets: 2 and 3.

Building a union is equally easy:

integerSet1.UnionWith(integerSet2);

…resulting in integerSet1 = 1,2,3,4.

SymmetricExceptWith returns those items that are found in set 1 and set 2 but not both:

integerSet1.SymmetricExceptWith(integerSet2);

Result: 1,4.

If you want to store objects, such as Customer, Product, etc. then you need to take some extra care. Sets have no idea when two object are considered equal. By default the following operation will add both objects:

HashSet<Product> productSet = new HashSet<Product>();
productSet.Add(new Product() { Name = "A" });
productSet.Add(new Product() { Name = "A" });

These are two different objects, they point to two different locations in the memory heap.

One way to solve this is that object will implement the IEquatable interface and override the GetHashCode method:

public class Product : IEquatable<Product>
{
	public string Name { get; set; }

	public override int GetHashCode()
	{
		return Name.GetHashCode();
	}

	public bool Equals(Product other)
	{
		return this.Name.Equals(other.Name);
	}
}

This will prevent adding two equal objects to be added to the Set – provided that they should be considered equal of course.

LIFO data collection in .NET: Stack of T

If you need a data collection in .NET where you are forced to handle the objects in a last-in-first-out manner then you can use the Stack of T object: the last object added will be the first to come out. A typical scenario is a deck of cards: you pick the first card from the top, i.e. the one that was added last.

To initialise:

Stack&lt;Card&gt; stackOfCards = new Stack&lt;Card&gt;();

To add items:

stackOfCards.Push(new Card(ace));
stackOfCards.Push(new Card(ten));

To get the most recently added object from the stack:

Card next = stackOfCards.Pop();

The Pop() method will also remove the item from the collection. So the next time you call Pop() you’ll get the item added before the most recently added one.

Just like with a Queue of T you cannot directly reference an object in the stack collection by some index, e.g. [3].

The Peek() method will let you view the next item on the stack but it won’t be removed from the collection:

Card next = stackOfCards.Peek();

You can test for the absence of an item with Contains:

bool contains = stackOfCards.Contains(ace);

If you absolutely need to access the items directly then convert the stack into an array:

Card[] cardArray = stackOfCards.AsArray();

This will copy the items in the stack but leave the stack itself intact.

FIFO data structure in .NET: Queue of T

If you need a generic collection where you are forced to handle the elements on a first come first served basis then Queue will be your friend. There’s no Insert, Add or Delete method and you cannot access just any particular element by some index, like [2]. This data structure is most applicable in First-in-first-out – FIFO – scenarios.

To initialise:

Queue<Client> clientsQueueingInShop = new Queue<Client>();

To add objects:

clientsQueueingInShop.Enqueue(new Client {Name = "Nice person"});
clientsQueueingInShop.Enqueue(new Client {Name = "My friend"});
clientsQueueingInShop.Enqueue(new Client {Name = "My neighbour"});

To retrieve the first object in the queue:

Client nextUp = clientsQueueingInShop.Dequeue();

This will not only get the first client – “Nice person” – in the queue but also remove it from the collection. So that the next time you call Dequeue() it will return “My friend”.

You can look at the next item in the queue by calling the Peek() method. It doesn’t remove the object from the collection, in other words it will return the same object on subsequent calls:

Client nextUp = clientsQueueingInShop.Peek();

You can query the queue to see if it contains a particular element:

bool contains = clientsQueueingInShop.Contains(myFavouriteClient);

You will need to make sure of course that the objects are comparable in the queue.

In case you absolutely must access an object in the queue by some index one option is to convert the queue to an array:

Client[] clientArrays = clientsQueueingInShop.ToArray();

This will create a copy of the queue as an array, the original queue remains intact.

ultimatemindsettoday

A great WordPress.com site

Elliot Balynn's Blog

A directory of wonderful thoughts

Softwarearchitektur in der Praxis

Wissenswertes zu Webentwicklung, Domain-Driven Design und Microservices

Technology Talks

on Microsoft technologies, Web, Android and others

Software Engineering

Web development

Disparate Opinions

Various tidbits

chsakell's Blog

WEB APPLICATION DEVELOPMENT TUTORIALS WITH OPEN-SOURCE PROJECTS

Guru N Guns's

OneSolution To dOTnET.

Johnny Zraiby

Measuring programming progress by lines of code is like measuring aircraft building progress by weight.

%d bloggers like this: