How to improve performance of ConcurrentDictionary.Count in C#

Question

Recently, I needed to choose between using SortedDictionary and SortedList, and settled on SortedList.

However, now I discovered that my C# program is slowing to a crawl when performing SortedList.Count, which I check using a function/method called thousands of times.

Usually my program would call the function 10,000 times within 35 ms, but while using SortedList.Count, it slowed to 300-400 ms, basically 10x slower.

I also tried SortedList.Keys.Count, but this reduced my performance another 10 times, to over 3000 ms.

I have only ~5000 keys/objects in SortedList<DateTime, object_name>. I can easily and instantly retrieve data from my sorted list by SortedList[date] (in 35 ms), so I haven't found any problem with the list structure or objects its holding.

Is this performance normal?

What else can I use to obtain the number of records in the list, or just to check that the list is populated? (besides adding a separate tracking flag, which I may do for now)

CORRECTION: Sorry, I'm actually using: ConcurrentDictionary<string, SortedList<DateTime, string>> dict_list = new ConcurrentDictionary<string, SortedList<DateTime, string>>(); And I had various counts in various places, sometimes checking items in the list and other times in ConcurrentDicitonary. So the issue applies to ConcurrentDicitonary and I wrote quick test code to confirm this, which takes 350 ms, without using concurrency. Here is the test with ConcurrentDicitonary, showing 350 ms:

public static void CountTest()
{
    //Create test ConcurrentDictionary
    ConcurrentDictionary<int, string> test_dict = new ConcurrentDictionary<int, string>();
    for (int i = 0; i < 50000; i++)
    {
        test_dict[i] = "ABC";
    }

    //Access .Count property 10,000 times
    int tick_count = Environment.TickCount;
    for (int i = 1; i <= 10000; i++)
    {
        int dict_count = test_dict.Count;
    }

    Console.WriteLine(string.Format("Time: {0} ms", Environment.TickCount - tick_count));
    Console.ReadKey();
}

Answer 1

Well, ConcurrentDictionary<TKey, TValue> must work properly with many threads at once, so it needs some synchronization overhead.

Source code for Count property: https://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentDictionary.cs,40c23c8c36011417

    public int Count
    {
        [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")]
        get
        {
            int count = 0;

            int acquiredLocks = 0;
            try
            {
                // Acquire all locks
                AcquireAllLocks(ref acquiredLocks);

                // Compute the count, we allow overflow
                for (int i = 0; i < m_tables.m_countPerLock.Length; i++)
                {
                    count += m_tables.m_countPerLock[i];
                }

            }
            finally
            {
                // Release locks that have been acquired earlier
                ReleaseLocks(0, acquiredLocks);
            }

            return count;
        }
    }

Looks like you need to refactor your existing code. Since you didn't provide any code, we can't tell you what you could optimize.

Answer 2

For performance sensitive code I would not recommend to use ConcurrentDictionary.Count property as it has a locking implementation. You could use Interlocked.Increment instead to do the count yourself.

Answer 3

this article recommends calling this instead:

dictionary.Skip(0).Count()

The count could be invalid as soon as the call from the method returns. If you want to write the count to a log for tracing purposes, for example, you can use alternative methods, such as the lock-free enumerator