read-only acces to static List in massively parallel code without lock

Question

edit : i strongly disagree with the closing, especially now that i found the answer. The question is very precise, the bonus questions are just bonus... The answer simply is :"you can't use List<T> without locking because it is using versioning internally and is enforcing data-consistency". (i posted the answer but i have to wait 1 day before accepting it)

---

Context :

• I'm using NET Core 3.1 and C# in a WPF application.
• I have a lot of threads using either explicitly started Task and Parallel.ForEach, all reading and potentially modifying a static List.
• it is guaranteed that multiple different elements are modified by multiple thread at the same time BUT a single element will be only modified by single thread. (manual task do not modify the list, only Parallel.ForEach does, and i manage them carefully)
• i'm using a very minimalist amount of lock : only when i add/remove an element
• The method where the exception is raised is called by this code : CompositionTarget.Rendering = New EventHandler(CompositionTargetRendering)

The problem :

1. The main UI thread is doing absolutely nothing except reading the static list in a (non-parallel) foreach loop to visualise the list without locking it.
2. I have an exception System.InvalidOperationException : Collection was modified; enumeration operation may not execute; saying that the Collection was modified while the main WPF thread was looping over it to visualise it. (which is true, i am doing it)
3. Even if i lock the list while add/removing element (which make sense and it's ok since it doesn't happen too often), it still crash with an exception.
4. It require to add a lock on the main UI thread, but then my list would be more or less permanently locked by the UI thread and scalability will drop to nil.

Question : How to constantly read(-only) this list without raising an exception and without locking it ?

My temporary workaround : It is ok if the visualization isn't "perfectly accurate", that why i can afford to modify it while visualizing it.

So i'm visualizing a copy using List<T>.ToArray. It works for now, but as the objects stored in the list will grow (a lot) in the future, memory usage will be a problem (many gigabyte). I can't afford to double the memory usage just for this.

---

Bonus question :

• i honestly don't understand why it only raise an exception here. I'm reading and writing the list all over the place without any lock and without problem, except in the WPF thread ?

• And, from the workaround, isn't creating a copy an access to this list anyway ? Why doesn't it raise an exception every single time i read it concurrently ? Is it a WPF thing ?

• If the EventHandler is the problem, and you know another way to manually refresh my XAML <Image>, i'm all ears. It's the only way i know.

Answer 1

So, i checked the Net Core source code : all Lists have a "version".

If the version change while its being enumerated (and it can change very easily) : it throw an exception.

it's an hardcoded behavior in Collection.Generic.List. Using List will never work unless i use extremely unsafe & ugly code.

if (_version != _sortedList.version) 
    throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);

.NET Framwork have a similar code :

if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);

So the only reason it crashed only in the UI thread is because it's read so often. I was just being mislead by this behavior but it's a global problem.

Answer 2

I have an exception System.InvalidOperationException : Collection was modified; enumeration operation may not execute;

You are using a foreach loop. foreach only work on Enumerators, as that is what they were added to support. Every Collection can be turned into a enumerator, but there is one important limitation:

If the collection changes, all Enumerators should become invalid.

The solution is to stop using a foreach. However, Lists are also inherently not useable for concurrent access. None of the indexed Collections is. You should be changing to something like a ConcurrentDictionary. But even that might not be enough.

My biggest confusion is that you are not just locking access to the collection from all endpoints, including the GUI. The Code should at tops run 30 times per second. And if that much updating disrupts operation, it needs to be even less then that.

You may be able to get some better performance out of the GUI, if you avoid doing string-concatenation on the GUI Elements .Text Property. Working directly on the GUI classes has considerable overhead. I wrote a example to demonstrate that:

using System;
using System.Windows.Forms;

namespace UIWriteOverhead
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        int[] getNumbers(int upperLimit)
        {
            int[] ReturnValue = new int[upperLimit];

            for (int i = 0; i < ReturnValue.Length; i++)
                ReturnValue[i] = i;

            return ReturnValue;
        }

        void printWithBuffer(int[] Values)
        {
            textBox1.Text = "";
            string buffer = "";

            foreach (int Number in Values)
                buffer += Number.ToString() + Environment.NewLine;
            textBox1.Text = buffer;
        }

        void printDirectly(int[] Values){
            textBox1.Text = "";

            foreach (int Number in Values)
                textBox1.Text += Number.ToString() + Environment.NewLine;
        }

        private void btnPrintBuffer_Click(object sender, EventArgs e)
        {
            MessageBox.Show("Generating Numbers");
            int[] temp = getNumbers(10000);
            MessageBox.Show("Printing with buffer");
            printWithBuffer(temp);
            MessageBox.Show("Printing done");
        }

        private void btnPrintDirect_Click(object sender, EventArgs e)
        {
            MessageBox.Show("Generating Numbers");
            int[] temp = getNumbers(1000);
            MessageBox.Show("Printing directly");
            printDirectly(temp);
            MessageBox.Show("Printing done");
        }
    }
}

But at the end, you will have to drop the GUI Updates until it stops being an issue for the process.

Answer 3

Use only immutable lists

Do not update the existing list. Instead, create a new list with the revisions you need, then update the reference to point to the new list.

List<Foo> _masterList = new List<Foo>; //This is the list your UI thread will access


Task WorkerThread()
{
    lock (lockObject)
    {
        //This is how you add to the list without mutating it
        _masterList = _masterList.Concat( newItem ).ToList();

        //Here's how you remove an item with Id = x without mutating it
        _masterList = _masterList.Where( item => item.Id != x ).ToList(); 
    }
}

In no case are you mutating a list, so the exception "collection was modified" will never occur.

You still need to lock when adding or remove (otherwise some adds or removes may get lost) but you no longer need to lock anything to access the list for read, since the reference itself is atomic and the thing it points to never changes.