Selector - Multikeyed concurrent dictionary(dictionaries)

01/31/2013 07:54 Super Aids#1

Namespaces Required:

Code:

using System.Collections.Concurrent;

Class:

Code:

	public class Selector<TKey1, TKey2, TValue>
	{
		private ConcurrentDictionary<TKey1, TValue> selectorCollection1;
		private ConcurrentDictionary<TKey2, TValue> selectorCollection2;
		private ConcurrentDictionary<TKey1, TKey2> keymatcher1;
		private ConcurrentDictionary<TKey2, TKey1> keymatcher2;

		public Selector()
		{
			selectorCollection1 = new ConcurrentDictionary<TKey1, TValue>();
			selectorCollection2 = new ConcurrentDictionary<TKey2, TValue>();

			keymatcher1 = new ConcurrentDictionary<TKey1, TKey2>();
			keymatcher2 = new ConcurrentDictionary<TKey2, TKey1>();
		}

		public bool TrySelect(TKey1 key, out TValue value)
		{
			return selectorCollection1.TryGetValue(key, out value);
		}

		public bool TrySelect(TKey2 key, out TValue value)
		{
			return selectorCollection2.TryGetValue(key, out value);
		}

		public bool TryAdd(TKey1 key1, TKey2 key2, TValue value)
		{
			return (selectorCollection1.TryAdd(key1, value) &&
			        selectorCollection2.TryAdd(key2, value) &&
			        keymatcher1.TryAdd(key1, key2) &&
			        keymatcher2.TryAdd(key2, key1));
		}

		public bool TryRemove(TKey1 key1)
		{
			TKey2 key2;
			if (!keymatcher1.TryGetValue(key1, out key2))
				return false;
			TValue rval;
			return (selectorCollection1.TryRemove(key1, out rval) &&
			        selectorCollection2.TryRemove(key2, out rval) &&
			        keymatcher1.TryRemove(key1, out key2) &&
			        keymatcher2.TryRemove(key2, out key1));
		}

		public bool TryRemove(TKey2 key2)
		{
			TKey1 key1;
			if (!keymatcher2.TryGetValue(key2, out key1))
				return false;
			TValue rval;
			return (selectorCollection1.TryRemove(key1, out rval) &&
			        selectorCollection2.TryRemove(key2, out rval) &&
			        keymatcher1.TryRemove(key1, out key2) &&
			        keymatcher2.TryRemove(key2, out key1));
		}

		public bool Contains(TKey1 key1)
		{
			return keymatcher1.ContainsKey(key1);
		}

		public bool Contains(TKey2 key2)
		{
			return keymatcher2.ContainsKey(key2);
		}

		public bool Contains(TValue value)
		{
			return selectorCollection1.Values.Contains(value);
		}
		
		public void Clear()
		{
				selectorCollection1.Clear();
				selectorCollection2.Clear();
				keymatcher1.Clear();
				keymatcher2.Clear();
		}
	}

Example if using the selector to store clients:

Code:

Selector<uint, string, GameClient> Clients; // uint is for the UID, string is for the name and GameClient is the client...

Adding a client:

Code:

			if (!Clients.TryAdd(client.UID, client.Name, client))
				throw new Exception("Could not add the client.");

Getting a client from UID:

Code:

	if (!Clients.TrySelect(1000000, out client)) // get from UID
				throw new Exception("Could not get the client from UID.");

Getting a client from name:

Code:

if (!Clients.TrySelect("Test", out client)) // get from name
				throw new Exception("Could not get the client from name.");

Contains a client from an uid:

Code:

			if (Clients.Contains(1000000))
			{
				// a client with the uid 1000000 is existing
			}

Contains a client from a name:

Code:

		if (Clients.Contains("Test"))
			{
				// a client with the name Test is existing
			}

Contains a client from well... client.

Code:

			if (Clients.Contains(client))
			{
				// the selector already contains the client
			}

Remove a client from UID:

Code:

			int tries = 0;
			while (!Clients.TryRemove(1000000) && (tries++ < 3)) // attempts to remove a client from the uid 1000000
				System.Threading.Thread.Sleep(100); // the while loop is to make sure it will try to remove it again if it failed, most likely never will

Remove a client from name: (Please read the commenting at the UID removing)

Code:

int tries = 0;
			while (!Clients.TryRemove("Test") && (tries++ < 3)) // attempts to remove a client from the name Test
				System.Threading.Thread.Sleep(100);

Clear the collection:

Code:

Clients.Clear();

Never seen anything like this being used a single source, although it would be common to have something like that and I was in need for it in my source, so wrapped it up pretty quickly, but I hope you like it.

And pro4never said he wanted some test on it to see if it was worth it.

Well I just went ahead and did a test, here is the result:
A bit surprised about the concurrent Dictionary, because I didn't though it'd be that slow compared to a regular dictionary o:

If you ask me it's worth it lmao.

Screenshot:
[Only registered and activated users can see links. Click Here To Register...]

Test:

Code:

			#region Regular Dictionary Test
			System.Collections.Generic.Dictionary<uint, GameClient> d_clients = new System.Collections.Generic.Dictionary<uint, Program.GameClient>();
			foreach (GameClient _client in clients)
				d_clients.Add(_client.UID, _client);
			Console.WriteLine("Beginning first test: System.Collections.Generic.Dictionary<TKey, TValue>");
			Console.WriteLine("Started with 1000000 searches (Running 3 tests)...");
			for (int tests = 0; tests < 3; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				int namecounter = 0;
				for (int runs = 0; runs < 1000000; runs++)
				{
					string names = namesearches[namecounter];
					foreach (GameClient client in d_clients.Values)
					{
						if (client.Name == names)
							break;
					}
					
					namecounter++;
					if (namecounter >= 500)
						namecounter = 0;
				}
				Console.WriteLine("Finished test #{0} in {1} milliseconds...", tests, overall.ElapsedMilliseconds);
				overall.Stop();
			}
			#endregion
			#region Concurrent Dictionary Test
			ConcurrentDictionary<uint, GameClient> c_clients = new ConcurrentDictionary<uint, Program.GameClient>();
			foreach (GameClient _client in clients)
				c_clients.TryAdd(_client.UID, _client);
			Console.WriteLine("Beginning first test: System.Collections.Concurrent.Dictionary<TKey, TValue>");
			Console.WriteLine("Started with 1000000 searches (Running 3 tests)...");
			for (int tests = 0; tests < 3; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				int namecounter = 0;
				for (int runs = 0; runs < 1000000; runs++)
				{
					string names = namesearches[namecounter];
					foreach (GameClient client in c_clients.Values)
					{
						if (client.Name == names)
							break;
					}
					
					namecounter++;
					if (namecounter >= 500)
						namecounter = 0;
				}
				Console.WriteLine("Finished test #{0} in {1} milliseconds...", tests, overall.ElapsedMilliseconds);
				overall.Stop();
			}
			#endregion
			#region Selector Dictionary Test
			Selector<uint, string, GameClient> s_clients = new Selector<uint, string, Program.GameClient>();
			foreach (GameClient _client in clients)
				s_clients.TryAdd(_client.UID, _client.Name, _client);
			Console.WriteLine("Beginning first test: Selector<TKey1, TKey2, TValue>");
			Console.WriteLine("Started with 1000000 searches (Running 3 tests)...");
			for (int tests = 0; tests < 3; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				int namecounter = 0;
				int fails = 0;
				for (int runs = 0; runs < 1000000; runs++)
				{
					string names = namesearches[namecounter];
					GameClient client;
					if (!s_clients.TrySelect(names, out client))
						fails++;
					
					namecounter++;
					if (namecounter >= 500)
						namecounter = 0;
				}
				Console.WriteLine("Selector fails: {0}", fails);
				Console.WriteLine("Finished test #{0} in {1} milliseconds...", tests, overall.ElapsedMilliseconds);
				overall.Stop();
			}
			#endregion

01/31/2013 08:01 Lateralus#2

Hey cool. I was wanting to do something like this to implement a thread-safe priority queue a while back.

01/31/2013 12:21 Korvacs#3

Just so your aware, the concurrent dictionary is slower than a standard dictionary because its designed to be used by 10/20+ threads at the same time without blocking, not a single thread.

Also, your tests between Concurrent Dictionary and this Selector should yield the same results, but you test them differently, that's the only reason there is a performance difference. Personally I don't see the point.

01/31/2013 12:45 Korvacs#4

Oh and you don't need to lock to clear the dictionaries, and you should never lock(this) its extremely bad practice and can cause deadlocks.

01/31/2013 13:01 Super Aids#5

Quote:

Originally Posted by Korvacs

Just so your aware, the concurrent dictionary is slower than a standard dictionary because its designed to be used by 10/20+ threads at the same time without blocking, not a single thread.

Also, your tests between Concurrent Dictionary and this Selector should yield the same results, but you test them differently, that's the only reason there is a performance difference. Personally I don't see the point.

The point is usually you store you clients with the UID being the key and when you have to find a player from the name you'd have to search through the whole collection to find that certain player ex. from whispering someone. That's when having a secondary collection with the name as the key comes in hand, because you wouldn't need to search through the whole collection to find the client you want to use.

It's not really a performance test, but speed test. The tests is the same for all 3 types of dictionaries and I was aware it was the reason it was slower, just didn't know it was that much. The only difference is that mine does not need to loop through the whole collection to find what it's looking for as it contains two collections one for the UID being the key and another one for being the name as key, so It would just have to call the collection that uses the name as key, rather than looping through the UID collection.

All in all it would be equal to:

Code:

ConcurrentDictionary<uint, GameClient> ClientsWithUIDKey;
ConcurrentDictionary<string, GameClient> ClientsWithNameKey;

So, nothing more than a wrapper for that.

Quote:

Originally Posted by Korvacs

Oh and you don't need to lock to clear the dictionaries, and you should never lock(this) its extremely bad practice and can cause deadlocks.

Thanks :)

01/31/2013 13:07 Korvacs#6

Can you create a test to see how performance is at inserting between the 3? To be honest the performance between the 2 when searching is minimal when you only have 1000 or less entries in the dictionary, so much so that this isn't really worth it, and I suspect inserting into 4 dictionaries instead of 1 is going to have a bigger impact...

01/31/2013 13:10 Super Aids#7

This test was done with 500 entries only.

And I'm aware inserting would be slower, same with removing, but you only do those once. Uhmm will do it now and edit my post.

Alright here is the insert/removal test result:
[Only registered and activated users can see links. Click Here To Register...]

Test:

Code:

			#region Regular Dictionary Test
			System.Collections.Generic.Dictionary<uint, GameClient> d_clients = new System.Collections.Generic.Dictionary<uint, Program.GameClient>();
			Console.WriteLine("Beginning first test: System.Collections.Generic.Dictionary<TKey, TValue>");
			Console.WriteLine("Started with 500 inserts/removals (Running 10 tests)...");
			for (int tests = 0; tests < 10; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				for (int runs = 0; runs < 500; runs++)
				{
					d_clients.Add((uint)runs, new GameClient() { Name = "Test" });
				}
				for (int runs = 0; runs < 500; runs++)
				{
					d_clients.Remove((uint)runs);
				}
				Console.WriteLine("Finished test #{0} in {1} ticks...", tests, overall.ElapsedTicks);
				d_clients.Clear();
				overall.Stop();
			}
			#endregion
			#region Concurrent Dictionary Test
			ConcurrentDictionary<uint, GameClient> c_clients = new ConcurrentDictionary<uint, Program.GameClient>();
			Console.WriteLine("Beginning first test: System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue>");
			Console.WriteLine("Started with 500 inserts/removals (Running 10 tests)...");
			for (int tests = 0; tests < 10; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				for (int runs = 0; runs < 500; runs++)
				{
					c_clients.TryAdd((uint)runs, new GameClient() { Name = "Test" });
				}
				for (int runs = 0; runs < 500; runs++)
				{
					GameClient client;
					c_clients.TryRemove((uint)runs, out client);
				}
				Console.WriteLine("Finished test #{0} in {1} ticks...", tests, overall.ElapsedTicks);
				c_clients.Clear();
				overall.Stop();
			}
			#endregion
			#region Selector Dictionary Test
			Selector<uint, string, GameClient> s_clients = new Selector<uint, string, Program.GameClient>();
			Console.WriteLine("Beginning first test: Selector<TKey1, TKey2, TValue>");
			Console.WriteLine("Started with 500 inserts/removals (Running 10 tests)...");
			for (int tests = 0; tests < 10; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				for (int runs = 0; runs < 500; runs++)
				{
					GameClient client = new Program.GameClient();
					client.Name = "Test";
					s_clients.TryAdd((uint)runs, client.Name, client);
				}
				for (int runs = 0; runs < 500; runs++)
				{
					s_clients.TryRemove((uint)runs);
				}
				Console.WriteLine("Finished test #{0} in {1} ticks...", tests, overall.ElapsedTicks);
				s_clients.Clear();
				overall.Stop();
			}
			#endregion

Also if you know why first test could possibly be so much slower than the rest even though all tests are the same, an explanation would be nice, because it's a bit confusing to me :D

01/31/2013 17:26 Korvacs#8

Its because the first time you run the application after compiling every call needs to be JIT'ed, then after that it'll run as intended.

01/31/2013 18:52 Super Aids#9

Quote:

Originally Posted by Korvacs

Its because the first time you run the application after compiling every call needs to be JIT'ed, then after that it'll run as intended.

But why does it repeat it then? Shouldn't it be doing it for the first one only?

01/31/2013 21:36 Korvacs#10

Its probably to do with the fact that it is being called within a loop, I couldn't tell you exactly why I'm not overly knowledgeable about JIT.

01/31/2013 21:47 Super Aids#11

I know. I was thinking something like that. I just find it strange that it is like that, but it's not anything that its noticable though.

01/31/2013 22:20 _tao4229_#12

Quote:

Originally Posted by Super Aids

. . .

Test:

Code:

			#region Regular Dictionary Test
			System.Collections.Generic.Dictionary<uint, GameClient> d_clients = new System.Collections.Generic.Dictionary<uint, Program.GameClient>();
			Console.WriteLine("Beginning first test: System.Collections.Generic.Dictionary<TKey, TValue>");
			Console.WriteLine("Started with 500 inserts/removals (Running 10 tests)...");
			for (int tests = 0; tests < 10; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				for (int runs = 0; runs < 500; runs++)
				{
					d_clients.Add((uint)runs, new GameClient() { Name = "Test" });
				}
				for (int runs = 0; runs < 500; runs++)
				{
					d_clients.Remove((uint)runs);
				}
				Console.WriteLine("Finished test #{0} in {1} ticks...", tests, overall.ElapsedTicks);
				d_clients.Clear();
				overall.Stop();
			}
			#endregion
			#region Concurrent Dictionary Test
			ConcurrentDictionary<uint, GameClient> c_clients = new ConcurrentDictionary<uint, Program.GameClient>();
			Console.WriteLine("Beginning first test: System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue>");
			Console.WriteLine("Started with 500 inserts/removals (Running 10 tests)...");
			for (int tests = 0; tests < 10; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				for (int runs = 0; runs < 500; runs++)
				{
					c_clients.TryAdd((uint)runs, new GameClient() { Name = "Test" });
				}
				for (int runs = 0; runs < 500; runs++)
				{
					GameClient client;
					c_clients.TryRemove((uint)runs, out client);
				}
				Console.WriteLine("Finished test #{0} in {1} ticks...", tests, overall.ElapsedTicks);
				c_clients.Clear();
				overall.Stop();
			}
			#endregion
			#region Selector Dictionary Test
			Selector<uint, string, GameClient> s_clients = new Selector<uint, string, Program.GameClient>();
			Console.WriteLine("Beginning first test: Selector<TKey1, TKey2, TValue>");
			Console.WriteLine("Started with 500 inserts/removals (Running 10 tests)...");
			for (int tests = 0; tests < 10; tests++)
			{
				Stopwatch overall = new Stopwatch();
				overall.Start();
				for (int runs = 0; runs < 500; runs++)
				{
					GameClient client = new Program.GameClient();
					client.Name = "Test";
					s_clients.TryAdd((uint)runs, client.Name, client);
				}
				for (int runs = 0; runs < 500; runs++)
				{
					s_clients.TryRemove((uint)runs);
				}
				Console.WriteLine("Finished test #{0} in {1} ticks...", tests, overall.ElapsedTicks);
				s_clients.Clear();
				overall.Stop();
			}
			#endregion

Also if you know why first test could possibly be so much slower than the rest even though all tests are the same, an explanation would be nice, because it's a bit confusing to me :D

JIT considerations aside, you are using the same dictionary for every iteration of the test. Dictionaries are backed by an array, so when you add enough elements the collection has to expand and thus create more memory. Creating memory and copying the old elements to the new array takes linear time, and thus slows down a (generally) constant time process. Although you remove all the entries and clear the dictionary, the expanded array is still there (see ms reference for clear, it's an O(n) operation meaning they don't simply create a new array of initial size - [Only registered and activated users can see links. Click Here To Register...]). The subsequent tests thus never need to expand the array and run without that bottleneck.

You should rerun the tests with new dictionary instances for each iteration.

01/31/2013 23:11 pro4never#13

Quote:

Originally Posted by _tao4229_

JIT considerations aside, you are using the same dictionary for every iteration of the test. Dictionaries are backed by an array, so when you add enough elements the collection has to expand and thus create more memory. Creating memory and copying the old elements to the new array takes linear time, and thus slows down a (generally) constant time process. Although you remove all the entries and clear the dictionary, the expanded array is still there (see ms reference for clear, it's an O(n) operation meaning they don't simply create a new array of initial size - [Only registered and activated users can see links. Click Here To Register...]). The subsequent tests thus never need to expand the array and run without that bottleneck.

You should rerun the tests with new dictionary instances for each iteration.

Yay thanks for the clarification. Now I feel kinda smart for remembering how the array still exists behind the scenes but couldn't think of how to explain it or even if I was correct.

01/31/2013 23:12 Spirited#14

Why not just use a KeyValuePair<T1, T2>? .-.

02/01/2013 00:07 Super Aids#15

Fang the point is to not needing 2 keys to be correct to get the value, but just one or the other.

@tao thanks a lot for the explanation.