One question

Recently, I encountered a problem with CocurrentDictionary. I can't understand it for the time being. Multithreading operation, foreach loop error: the keyword is not in the dictionary. All threads did not delete elements, but only did not add or modify keys. What's more strange is that they looked at the keys array collection when they were interrupted, which was obviously annoying and silent. The logic is roughly as follows. Some leaders will help me explain:

//Error reporting: the keyword is not in the dictionary, and there is a current error key in keys
oreach(var key in conDic.keys){
    byte[] byts=conDic[key]
}

II. Understanding concurrent dictionary

For the above problems, I'm going to pick up the source code and summarize it in combination with my predecessors' knowledge.  

As shown in the figure   The data structure of ConcurrentDictionary, in which a tables object is mainly stored, and this tables is an array of many blocks, and each block is a linked list of nodes (a node is a key value pair).

private volatile ConcurrentDictionary<TKey, TValue>.Tables m_tables;
private class Tables
{
    internal readonly ConcurrentDictionary<TKey, TValue>.Node[] m_buckets;
    internal readonly object[] m_locks;
    internal volatile int[] m_countPerLock;
    internal readonly IEqualityComparer<TKey> m_comparer;

    internal Tables(ConcurrentDictionary<TKey, TValue>.Node[] buckets, object[] locks, int[] countPerLock, IEqualityComparer<TKey> comparer)
    {
        this.m_buckets = buckets;
        this.m_locks = locks;
        this.m_countPerLock = countPerLock;
        this.m_comparer = comparer;
    }
}

private class Node
{
    internal TKey m_key;
    internal TValue m_value;
    internal volatile ConcurrentDictionary<TKey, TValue>.Node m_next;
    internal int m_hashcode;

    internal Node(TKey key, TValue value, int hashcode, ConcurrentDictionary<TKey, TValue>.Node next)
    {
        this.m_key = key;
        this.m_value = value;
        this.m_next = next;
        this.m_hashcode = hashcode;
    }
}

Look, the node class is a structure with a next pointer. A node is a linked list  ， In the Tables class   m_ The buckets variable is a list structure that stores n linked lists.

There is a variable named in the Tables class   The countPerLock type is int [], which is the bottom box in the figure. It can be understood as the number of node s corresponding to each lock. This variable is mainly used to count the number of data in the dictionary   Sum of countPerLock array values and M_ The actual number of buckets is consistent. What is the actual number is non null. The length of this array is m_locks have the same length.

The Count() method mainly uses this element for line statistics. The advantage is that you don't have to traverse the node linked list.

The most important thing is m in Tables_ Implementation of locks. This is a list of locks used to control the blocks controlled when multithreading reads and modifies.

When the dictionary is initialized m_ The number of locks is the number of cpu cores * 4 (ps: for example, i7 is 8 * 4 = 32), and m_ The initialization of the number of buckets is 31 (a small condition is that m_locks=m_buckets when m_locks > = m_buckets), so i7   m_ Buckets and   m_ There are 32 locks. Theoretically, a block corresponds to a lock when a new node is not added.

m_locks: lock object, object type. The default value during initialization is the number of cpu cores * 4, and the maximum value is 1024

m_buckets: the default value of initialization is 31, and the maximum value is 2146435071

In other words, if there is a large amount of data in the dictionary, one lock object corresponds to n Node linked lists.

About all read operations in concurrent dictionary

For example, attributes such as Keys Values Count are locked   m_ All lock objects in locks need to be used with caution.

The commonly used indexers [] and   TryGetValue and other methods do not lock any lock objects, and read the corresponding Node linked list atomically through Volatile.Read, and traverse all elements until the corresponding key is found.

About all write operations in concurrent dictionary

When a new data is added, the method calculates the hashcode of the key   Which node is placed in the table, and then the corresponding lock object is locked, which is passed later   The Volatile.Write method replaces the point of the new node. In this case, the node is the new value, and its next point to the original node value.

private void GetBucketAndLockNo(int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount)
{
    bucketNo = (hashcode & int.MaxValue) % bucketCount; //Location of Node
    lockNo = bucketNo % lockCount; // Lock position
}  
Volatile.Write<ConcurrentDictionary<TKey, TValue>.Node>(ref tables.m_buckets[bucketNo], new ConcurrentDictionary<TKey, TValue>.Node(key, value, hashCode, tables.m_buckets[bucketNo]));

Why is it so designed?

For multithreading, multiple linked lists and multiple lock objects can improve the possibility of simultaneous operation of multiple threads, because the data of the operation is written to a large extent   A lock object is not responsible.

At the same time, chained storage is more convenient for adding objects. Let's look at several functions:

public TValue this[TKey key]
{
	[__DynamicallyInvokable]
	get
	{
		TValue result;
		if (!this.TryGetValue(key, out result))
		{
			throw new KeyNotFoundException();
		}
		return result;
		}
		[__DynamicallyInvokable]
	set
	{
		if (key == null)
		{
			throw new ArgumentNullException("key");
		}
		TValue tvalue;
		this.TryAddInternal(key, value, true, true, out tvalue);
	}
}

[__DynamicallyInvokable]
public bool TryGetValue(TKey key, out TValue value)
{
	if (key == null)
	{
		throw new ArgumentNullException("key");
	}
	ConcurrentDictionary<TKey, TValue>.Tables tables = this.m_tables;
	IEqualityComparer<TKey> comparer = tables.m_comparer;
	int num;
	int num2;
	this.GetBucketAndLockNo(comparer.GetHashCode(key), out num, out num2, tables.m_buckets.Length, tables.m_locks.Length);
	for (ConcurrentDictionary<TKey, TValue>.Node node = Volatile.Read<ConcurrentDictionary<TKey, TValue>.Node>(ref tables.m_buckets[num]); node != null; node = node.m_next)
	{
		if (comparer.Equals(node.m_key, key))
		{
			value = node.m_value;
			return true;
		}
	}
	value = default(TValue);
	return false;
}

The above code reports that the keyword is not in the dictionary, which may be caused by the fact that TryGetValue is not locked. If a thread TryRemove(), a thread takes a value, it is easy to cause Volatile.Rea() to read null. This keyword is not explained in the dictionary!