No ConcurrentList<T> in .Net 4.0?

Question

I was thrilled to see the new System.Collections.Concurrent namespace in .Net 4.0, quite nice! I've seen ConcurrentDictionary, ConcurrentQueue, ConcurrentStack, ConcurrentBag and BlockingCollection.

One thing that seems to be mysteriously missing is a ConcurrentList<T>. Do I have to write that myself (or get it off the web :) )?

Am I missing something obvious here?

Solution 1

I gave it a try a while back (also: on GitHub). My implementation had some problems, which I won't get into here. Let me tell you, more importantly, what I learned.

Firstly, there's no way you're going to get a full implementation of IList<T> that is lockless and thread-safe. In particular, random insertions and removals are not going to work, unless you also forget about O(1) random access (i.e., unless you "cheat" and just use some sort of linked list and let the indexing suck).

What I thought might be worthwhile was a thread-safe, limited subset of IList<T>: in particular, one that would allow an Add and provide random read-only access by index (but no Insert, RemoveAt, etc., and also no random write access).

This was the goal of my ConcurrentList<T> implementation. But when I tested its performance in multithreaded scenarios, I found that simply synchronizing adds to a List<T> was faster. Basically, adding to a List<T> is lightning fast already; the complexity of the computational steps involved is miniscule (increment an index and assign to an element in an array; that's really it). You would need a ton of concurrent writes to see any sort of lock contention on this; and even then, the average performance of each write would still beat out the more expensive albeit lockless implementation in ConcurrentList<T>.

In the relatively rare event that the list's internal array needs to resize itself, you do pay a small cost. So ultimately I concluded that this was the one niche scenario where an add-only ConcurrentList<T> collection type would make sense: when you want guaranteed low overhead of adding an element on every single call (so, as opposed to an amortized performance goal).

It's simply not nearly as useful a class as you would think.

Solution 2

What would you use a ConcurrentList for?

The concept of a Random Access container in a threaded world isn't as useful as it may appear. The statement

  if (i < MyConcurrentList.Count)  
      x = MyConcurrentList[i]; 

as a whole would still not be thread-safe.

Instead of creating a ConcurrentList, try to build solutions with what's there. The most common classes are the ConcurrentBag and especially the BlockingCollection.

Solution 3

With all due respect to the great answers provided already, there are times that I simply want a thread-safe IList. Nothing advanced or fancy. Performance is important in many cases but at times that just isn't a concern. Yes, there are always going to be challenges without methods like "TryGetValue" etc, but most cases I just want something that I can enumerate without needing to worry about putting locks around everything. And yes, somebody can probably find some "bug" in my implementation that might lead to a deadlock or something (I suppose) but lets be honest: When it comes to multi-threading, if you don't write your code correctly, it is going deadlock anyway. With that in mind I decided to make a simple ConcurrentList implementation that provides these basic needs.

And for what its worth: I did a basic test of adding 10,000,000 items to regular List and ConcurrentList and the results were:

List finished in: 7793 milliseconds. Concurrent finished in: 8064 milliseconds.

public class ConcurrentList<T> : IList<T>, IDisposable
{
    #region Fields
    private readonly List<T> _list;
    private readonly ReaderWriterLockSlim _lock;
    #endregion

    #region Constructors
    public ConcurrentList()
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>();
    }

    public ConcurrentList(int capacity)
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>(capacity);
    }

    public ConcurrentList(IEnumerable<T> items)
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>(items);
    }
    #endregion

    #region Methods
    public void Add(T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Add(item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public void Insert(int index, T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Insert(index, item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public bool Remove(T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            return this._list.Remove(item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public void RemoveAt(int index)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.RemoveAt(index);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public int IndexOf(T item)
    {
        try
        {
            this._lock.EnterReadLock();
            return this._list.IndexOf(item);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public void Clear()
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Clear();
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public bool Contains(T item)
    {
        try
        {
            this._lock.EnterReadLock();
            return this._list.Contains(item);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        try
        {
            this._lock.EnterReadLock();
            this._list.CopyTo(array, arrayIndex);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ConcurrentEnumerator<T>(this._list, this._lock);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return new ConcurrentEnumerator<T>(this._list, this._lock);
    }

    ~ConcurrentList()
    {
        this.Dispose(false);
    }

    public void Dispose()
    {
        this.Dispose(true);
    }

    private void Dispose(bool disposing)
    {
        if (disposing)
            GC.SuppressFinalize(this);

        this._lock.Dispose();
    }
    #endregion

    #region Properties
    public T this[int index]
    {
        get
        {
            try
            {
                this._lock.EnterReadLock();
                return this._list[index];
            }
            finally
            {
                this._lock.ExitReadLock();
            }
        }
        set
        {
            try
            {
                this._lock.EnterWriteLock();
                this._list[index] = value;
            }
            finally
            {
                this._lock.ExitWriteLock();
            }
        }
    }

    public int Count
    {
        get
        {
            try
            {
                this._lock.EnterReadLock();
                return this._list.Count;
            }
            finally
            {
                this._lock.ExitReadLock();
            }
        }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }
    #endregion
}

    public class ConcurrentEnumerator<T> : IEnumerator<T>
{
    #region Fields
    private readonly IEnumerator<T> _inner;
    private readonly ReaderWriterLockSlim _lock;
    #endregion

    #region Constructor
    public ConcurrentEnumerator(IEnumerable<T> inner, ReaderWriterLockSlim @lock)
    {
        this._lock = @lock;
        this._lock.EnterReadLock();
        this._inner = inner.GetEnumerator();
    }
    #endregion

    #region Methods
    public bool MoveNext()
    {
        return _inner.MoveNext();
    }

    public void Reset()
    {
        _inner.Reset();
    }

    public void Dispose()
    {
        this._lock.ExitReadLock();
    }
    #endregion

    #region Properties
    public T Current
    {
        get { return _inner.Current; }
    }

    object IEnumerator.Current
    {
        get { return _inner.Current; }
    }
    #endregion
}

Solution 4

The reason why there is no ConcurrentList is because it fundamentally cannot be written. The reason why is that several important operations in IList rely on indices, and that just plain won't work. For example:

int catIndex = list.IndexOf("cat");
list.Insert(catIndex, "dog");

The effect that the author is going after is to insert "dog" before "cat", but in a multithreaded environment, anything can happen to the list between those two lines of code. For example, another thread might do list.RemoveAt(0), shifting the entire list to the left, but crucially, catIndex will not change. The impact here is that the Insert operation will actually put the "dog" after the cat, not before it.

The several implementations that you see offered as "answers" to this question are well-meaning, but as the above shows, they don't offer reliable results. If you really want list-like semantics in a multithreaded environment, you can't get there by putting locks inside the list implementation methods. You have to ensure that any index you use lives entirely inside the context of the lock. The upshot is that you can use a List in a multithreaded environment with the right locking, but the list itself cannot be made to exist in that world.

If you think you need a concurrent list, there are really just two possibilities:

1. What you really need is a ConcurrentBag
2. You need to create your own collection, perhaps implemented with a List and your own concurrency control.

If you have a ConcurrentBag and are in a position where you need to pass it as an IList, then you have a problem, because the method you're calling has specified that they might try to do something like I did above with the cat & dog. In most worlds, what that means is that the method you're calling is simply not built to work in a multi-threaded environment. That means you either refactor it so that it is or, if you can't, you're going to have to handle it very carefully. You you'll almost certainly be required to create your own collection with its own locks, and call the offending method within a lock.

Solution 5

ConcurrentList (as a resizeable array, not a linked list) is not easy to write with nonblocking operations. Its API doesn't translate well to a "concurrent" version.

View more solutions

Comments

[Rodrigo Reis]

ConcurrentBag<T> (msdn.microsoft.com/pt-br/library/…)

[Adam Calvet Bohl]

@RodrigoReis, ConcurrentBag<T> is an unordered collection, while List<T> is ordered.

[Jeremy Holovacs]

How could you possibly have an ordered collection in a multithreaded environment? You would never have control of the sequence of elements, by design.

[Erik Bergstedt]

Use a Lock instead

[colin lamarre]

there is a file called ThreadSafeList.cs in the dotnet source code which looks alot like some code below. It uses ReaderWriterLockSlim also and was trying to figure out why use that instead of simple lock(obj)?

[colin lamarre]

ok i see it's a performance improvement since reader locks don't really lock unless there's a write going on, useful if you have multiple threads reading the same List.

[Alan]

Good point. Still what I am doing is a little more mundane. I am just trying to assign the ConcurrentBag<T> into an IList<T>. I could switch my property to an IEnumerable<T>, but then I can't .Add stuff to it.

[CodesInChaos]

It's not only difficult to write, it's even difficult to figure out a useful interface.

[dcp]

@Henk - I don't follow your argument. Why wouldn't you have the same type of issue with if (!dict.ContainsKey(somekey)) dict[someKey] = someValue. Would there be thread-safety issues with that code as well (e.g. using ConcurrentDictionary)?

[Admin]

Java has the concept of a ConcurrentList: download.oracle.com/javase/6/docs/api/java/util/concurrent/…

[Billy ONeal]

@Alan: There's no way to implement that without locking the list. Since you can already use Monitor to do that anyway, there's no reason for a concurrent list.

[Henk Holterman]

@dcp: You would use TryGetValue() mostly.

[Billy ONeal]

@0A0D: I don't see one. There's a copy on write version but that's not what most people would expect a "concurrent collection" to do.

[dcp]

@Henk - Ok, but why do they still have the ConcurrentDictionary.ContainsKey method?

[Zarat]

@dcp - yes this inherently non-thread-safe. ConcurrentDictionary has special methods which do this in one atomic operation, like AddOrUpdate, GetOrAdd, TryUpdate, etc. They still have ContainsKey because sometimes you just want to know if the key is there without modifying the dictionary (think HashSet)

[Alan]

@Billy the point of a ConcurrentList would be to aleviate us all from the burden of locking/unlocking it. Same reason all of the other concurrent collections exist.

[dcp]

@Zarat - yes, but that's my point. It seems weird to have non thread-safe methods in a class whose name starts with the word "Concurrent". But I see what you're saying, thanks for the clarifications and explanation.

[Alan]

You cannot see a scenario where I might have 5 threads adding to a list? This way you could see the list accumulate records even before they all terminate.

[Zarat]

@dcp - ContainsKey is threadsafe by itself, your example (not ContainsKey!) just has a race condition because you do a second call depending on the first decision, which may at that point already be out of date.

[Zarat]

@Alan - that would be a ConcurrentQueue, ConcurrentStack or ConcurrentBag. To make sense of a ConcurrentList you should provide a use-case where the available classes are not enough. I don't see why I would want indexed access when the elements at the indices can randomly change through concurrent removes. And for a "locked" read you can already take snapshots of the existing concurrent classes and put them in a list.

[LukeH]

And if you need something similar to List<T> that uses old-skool, monitor-based synchronisation, there's SynchronizedCollection<T> hidden away in the BCL: msdn.microsoft.com/en-us/library/ms668265.aspx

[Henk Holterman]

One small addition: use the Capacity constructor parameter to avoid (as much as possible) the resizing scenario.

[Alan]

You're right -- I don't want indexed access. I generally use IList<T> as a proxy for an IEnumerable to which I can .Add(T) new elements. That's where the question comes from, really.

[Billy ONeal]

@Alan: Then you want a queue, not a list.

[Eric Ouellet]

I think you are wrong. Saying: safe for multiple readers does not mean that you can't write at the same time. Write would also mean delete and you will get an error if you delete while iterating in it.

[Eric Ouellet]

Henk, I'm not agree. I think that there is a simple scenario where it could be very usefull. Worker thread write in it will UI thread read and update interface accordingly. If you want to add item in a sorted fashion, it will require random access write. You could also use a stack and a view to the data but you will have to maintain 2 collections :-(.

[Billy ONeal]

@Eric: I never said you could write at the same time. You can either have one writer. Or you can have multiple readers. Not both.

[Earlz]

One addition I'd like to add. You can avoid the resizing problem by making a linked-list of "chunks". Of course, this adds a lot of complexity, but allows for relatively close to O(1) lookups and additions, and can also make it so you don't have to lock the entire structure upon an Insert or RemoveAt.. But again, it's massively more complex to implement and will never meet the performance of List<T>

[supercat]

The biggest scenario where a ConcurrentList would be a win would be when there isn't a whole lot of activity adding to the list, but there are many concurrent readers. One could reduce the readers' overhead to a single memory-barrier (and eliminate even that if readers weren't concerned about slightly-stale data).

[Kevin Doyon]

@supercat You could synchronize for that scenario using a ReaderWriterLock msdn.microsoft.com/en-us/library/…

[supercat]

@Kevin: It's pretty trivial to construct a ConcurrentList<T> in such a fashion that readers are guaranteed to see consistent state without needing any locking whatsoever, with relatively slight added overhead. When the list expands from e.g. size 32 to 64, keep the size-32 array and create a new size-64 array. When adding each of the next 32 items, put it in slot a 32-63 of the new array and copy an old item from the size-32 array to the new one. Until the 64th item is added, readers will look in the size-32 array for items 0-31 and in the size-64 array for items 32-63.

[supercat]

Once the 64th item is added, the size-32 array will still work for fetching items 0-31, but readers will no longer need to use it. They can use the size-64 array for all items 0-63, and a size-128 array for items 64-127. The overhead of selecting which one of two arrays to use, plus a memory barrier if desired, would be less than the overhead of even the most efficient reader-writer lock imaginable. Writes should probably use locks (lock-free would be possible, especially if one didn't mind creating a new object instance with every insertion, but the lock should be cheap.

[supercat]

One could easily write a ConcurrentOrderedBag<T> which would include a read-only implementation of IList<T>, but would also offer a fully-thread-safe int Add(T value) method. I don't see why any ForEach changes would be needed. Although Microsoft doesn't explicitly say so, their practice suggests that it's perfectly acceptable for IEnumerator<T> to enumerate the collection contents that existed when it was created; the collection-modified exception is only required if the enumerator would be unable to guarantee glitch-free operation.

[Eric Ouellet]

Iterating through a MT collection, the way it is design could lead, as you said, to an exception... Which one I don't know. Would you trap all exceptions? In my own book exception is exception and should not occurs in normal execution of code. Otherwise, to prevent exception, you have to either lock the collection or get a copy (in a safe manner-ie lock) or implement very complex mechanism in the collection to prevent exception to occurs due to concurrency. My though was that it would be nice to add an IEnumeratorMT that would lock the collection while a for each occur and add related code...

[Eric Ouellet]

The other thing that could also occur is that when you get an iterator, you can lock the collection and when your iterator is GC collected you can unlock the collection. According to Microsfot they already check if the IEnumerable is also an IDisposable and call the GC if so at the end of a ForEach. The main problem is that they also use the IEnumerable elsewhere without calling the GC, you then can't rely on that. Having a new clear MT interface for IEnumerable enabling lock would do solve the problem, at least a part of it. (It would not prevent people to not call it).

[supercat]

It is very bad form for a public GetEnumerator method to leave a collection locked after it returns; such designs can easily lead to deadlock. The IEnumerable<T> provides no indication of whether an enumeration can be expected to complete even if a collection is modified; the best one can do is write one's own methods so that they will do so, and have methods which accept IEnumerable<T> document the fact that will only be thread-safe if the IEnumerable<T> supports thread-safe enumeration.

[supercat]

What would have been most helpful would have been if IEnumerable<T> had included a "Snapshot" method with return type IEnumerable<T>. Immutable collections could return themselves; a bounded collection could if nothing else copy itself to a List<T> or T[] and call GetEnumerator on that. Some unbounded collections could implement Snapshot, and those which couldn't would be able to throw an exception without trying to fill up a list with their contents.

[Eric Ouellet]

I mostly agree. Snapshot would be very nice. And locking on "GetEnumerator" could easily lead to what you said because people don't expect that behavior. I don't say I have the perfect solution, but having an iterator without lock is dangerous and implementation should prevent that for sure. The problem with snapshot is performance for big collection. I think that ideally, MT collection should be implemented in more than on way according to its wanted usage (main usage). With snapshot (like you said) and also with mechanics enabling modification while iterating (which slow down insert/delete).

[Eric Ouellet]

Thanks supercat for your comments. I appreciate.

[supercat]

Not all collections could implement Snapshot quickly, and some couldn't implement it at all, but many collections could implement it far more quickly than could outside code whose only exposure to the type was via public interfaces. For example, a snapshot of an AppendOnlyList would could encapsulate a reference to the list and the number of items it presently contains; even though the list wouldn't be completely immutable, a list which reports itself as containing N items could guarantee that the first N items are immutable.

[Eric Ouellet]

Right! I like your idea of AppendOnlyList, it would have solved some of my previous needs.

[supercat]

I think AppendOnlyList and AddOnlyDictionary would have been very nice types, since they can be cheaply implemented in such a way as to allow any number of readers simultaneous with a single writer, allow the construction of immutable snapshots, and (in the case of AddOnlyDictionary), promise to enumerate items in the order they were added (guarantees not made by Dictionary, ConcurrentDictionary, nor ConcurrentBag).

[Eric Ouellet]

Totally agreed. I would have use them few times in the course of my projects. I will consider write one next time I will need it. Thanks.

[James]

What happens if two threads get into the beginning of the try block in Remove or the indexer setter at the same time?

[MsBao]

@James that doesn't seem possible. Read remarks at msdn.microsoft.com/en-us/library/…. Running this code, you'll never enter that lock a 2nd time: gist.github.com/ronnieoverby/59b715c3676127a113c3

[James]

@Ronny Overby: Interesting. Given that, I suspect that this would perform much better if you removed the UpgradableReadLock from all functions where the only operation performed in the time between the upgradable read lock and the write lock--the overhead of taking any kind of lock is so much more than the check to see if the parameter is out of range that just doing that check inside the write lock would likely perform better.

[James]

This class also doesn't seem very useful, as the offset-based functions (most of them) can't really ever be used safely unless there is some external locking scheme anyway because the collection could change between when you decide where to put or get something from and when you actually get it.

[MsBao]

@James So don't use it.

[MsBao]

I wanted to go on record saying that I recognize that the usefulness of IList semantics in concurrent scenarios is limited at best. I wrote this code probably before I came to that realization. My experience is the same as the writer of the accepted answer: I gave it a try with what I knew about synchronization and IList<T> and I learned something by doing that.

[Henk Holterman]

OK, old answer but still: RemoveAt(int index) is never thread-safe, Insert(int index, T item) is only safe for index==0, the return of IndexOf() is immediately outdated etc. Don't even start about the this[int].

[Henk Holterman]

And you don't need and don't want a ~Finalizer().

[Billy ONeal]

@Eugene: I never said that it was a "concurrent list". There is no such thing as "thread safe". Thread safety requires understanding the actual thread safety characteristics of a structure. Not every data structure is safe for multiple readers and no writers because many data structures have global shared state they don't tell you about.

[Evgeniy Berezovsky]

You say you have given up on preventing the possibility of deadlock - and a single ReaderWriterLockSlim can be made to deadlock easily by using EnterUpgradeableReadLock() concurrently. You don't however use it, you don't make the lock accessible to the outside, and you don't e.g. call a method that enters a write lock while holding a read lock, so using your class does not make deadlocks any more likely.

[Evgeniy Berezovsky]

The non-concurrent interface is not appropriate for concurrent access. E.g. the following is not atomic var l = new ConcurrentList<string>(); /* ... */ l[0] += "asdf";. In general, any read-write combo can lead you into deep trouble when done concurrently. That is why concurrent data structures generally provide methods for those, like ConcurrentDictionary's AddOrGet etc. N.B. Your constant (and redundant because the members are already marked as such by the underscore) repetition of this. clutters.

[Billy ONeal]

@Eugene: Which is exactly what my answer says. I understand that the question asked for it; but what the question asks for fundamentally doesn't make any sense.

[Evgeniy Berezovsky]

@supercat Re: ConcurrentList would be a win would be when there isn't a whole lot of activity adding to the list, but there are many concurrent readers and especially if one didn't mind creating a new object instance with every insertion. Exactly for use cases like this, which I've had to deal with increasingly often recently, the CopyOnWriteSwapper in my answer is a generic solution that performs locklessly fast for all reads and iterations, and allows the use of arbitrary data structure, i.e. you can keep your O(1) index lookup.

[supercat]

@EugeneBeresovsky: The CopyOnWriteSwapper implementations I've seen generally have O(N^2) behavior for building. The ConcurrentList I'd have liked to have seen would have retained amortized constant Add time. Building it might not have been as fast as building a synchronized list, but reads would avoid synchronization overhead.

[Evgeniy Berezovsky]

@supercat The one I provide below is generic in that sense. The cost in my example new List(existing) would be O(n). Not as bad as O(n^2), but bad enough if the list is huge, or you modify it often. If you need lockless read access AND something like O(log n) performance for additions, I guess Immutable it has to be.

[supercat]

@EugeneBeresovsky: IMHO, .NET would have benefited greatly from "add-only" list and dictionary types, since such types only need can easily be written to allow lock-free read access and O(1) write access; further, dictionaries of such type can cheaply guarantee that items will be enumerated in the order they were added (if an enumeration is started just as items are added, behavior will be consistent with the items having been added either before or after the enumeration). If there's no need to actually remove items from a collection, types that don't need to support removal could...

[supercat]

...easily provide useful guarantees (always-consistent state for reading, and in-order enumeration) which cannot be readily satisfied in collections that allow deletions.

[Brian Booth]

Thanks Eugene. I am a heavy user of .NET Reflector which puts "this." on all non-static fields. As such, I have grown to prefer the same. Regarding this non-concurrent interface not being appropriate: You are absolutely right that trying to perform multiple actions against my implementation can become unreliable. But the requirement here is simply that single actions (add, or remove, or clear, or enumeration) can be done without corrupting the collection. It basically removes the need to put lock statements around everything.

[Rob The Quant]

instead of locking, it creates a copy of the list, modifies the list and set the reference to the new list. So any other threads that are iterating will not cause any problems.

[Mike Marynowski]

@supercat for what it's worth, ConcurrentDictionary is now lock free for reads, performs essentially the same as a normal dictionary for lookups and allows safe enumeration while being modified.

[supercat]

@MikeMarynowski: I don't think ConcurrentDictionary offers any particular guarantees about enumeration order. Otherwise, though, it seems like a fine class. Add-only lists and dictionaries should each include a member not present in current interfaces; AddAndGetIndex would add an item and return its insertion order, and for dictionaries there should also be a GetItemIndex to yield an insertion order by key. An immutable wrapper on an add-only dictionary with such a function could simply wrap the original dictionary along with a count of how many items were in it when wrapped...

[supercat]

...and treat any items added after that as though they don't exist.

[Mike Marynowski]

@supercat That is correct, though I think what is there is sufficient for most uses of a concurrent dictionary, even in read only scenarios. Just curious, what usage scenario would require you to guarantee an enumeration order on a dictionary? If you want an add-only dictionary with "snapshot" enumeration behavior and 100% dictionary read performance I made an implementation of that here: singulink.com/CodeIndex/post/…

[supercat]

@MikeMarynowski: A typical usage scenario would be a live status report of unique items observed thus far. One could use a concurrent dictionary to establish which items are unique and then add them to a concurrent list, but it should be possible to have one data structure serve both purposes.

[Evgeniy Berezovsky]

My answer has a generic solution, and in N.B #1 I mention that you can (and I think should) return List<T>.AsReadOnly(modifiedList) in non-generic solutions like yours. That makes it really thread-safe. Of course you will need to change your interface from using List<T> to using e.g. IList<T>.

[Theodor Zoulias]

Do you have any benchmarks that compare your AppendOnlyList<T> class with what seems like its closest immutable competitor, the ImmutableQueue<T> class? How much faster is your class, and how much less allocatey it is? We need to see the numbers!

[snowcode]

they solve different problems. In my case I needed an Immutable append only class, and as per my comment, i was easily able to achieve my design goals by writing a few lines of code on top of a linked list and achieve threadsafety, concurrency and immutability. Go check it out, its just a sample to get you inspired to write something yourself. My comment wasn't about "hey my code is the best", it was .. hey, why hasnt anyone mentioned LinkedList in any of the discussions?

[Theodor Zoulias]

Your AppendOnlyList class supports adding (AddItem) and enumerating (Items). These two operations are also supported by the ImmutableQueue<T> class (Enqueue, GetEnumerator), so why do you say that these two classes solve different problems? They don't. So the question becomes: which is faster and less allocatey? Do you want me to do the benchmarks?

[snowcode]

In terms of "allocatey" since it's just a linkedList under the covers, you're really asking "how efficient (less allocatey) is LinkedList". Under the covers I'd wager the ImmutableQueue is also using a LinkedList considering the API. But since my particular use case needs a mutable appendOnly list, I can't use ImmutableQueue and had no reason to spend time comparing them. You're welcome to do it, I'll buy you a coffee if it's faster, or "less allocatey" :D cheers, A

[Theodor Zoulias]

How is it mutable? AFAICS the AppendOnlyList<T> has no API that mutates an instance of the class. The AddItem method returns a new AppendOnlyList<T>, just like the ImmutableQueue<T>.Enqueue returns a new ImmutableQueue<T>.

[snowcode]

@TheodorZoulias I'd love a benchmark, that would be totally awesome :D p.s. make sure you include "Length" counts :D (wink)

[Theodor Zoulias]

Snowcode TBH I am pretty confident that the ImmutableQueue<T> is at least as fast as your class, and not more allocatey. And because of this I have no incentive to write benchmarks. Honestly I think that it's a work that you should do yourself, in order to prove that your idea is worthy.

[snowcode]

I am not trying to prove it, I just shared my code as an example of a custom implementation based on LinkedList that's absolutely trivial and encourage folk to consider many other applications of the very versatile and very under-utilised data structure. Yes, ImmutableQueue is also a good base class also to use as a starting block, I never said it wasn't, look at them both.

[Theodor Zoulias]

Snowcode currently if I have a need for a data structure that support adding items, preserves their insertion order, and is immutable, I am not going to start searching around about whether the LinkedList or the ArrayList or the SortedDictionary or the BitArray is a good starting point for creating a custom class having these features. With that mindset I'll never get anything done. Instead I'll pick the data structure that offers these features out of the box, and I'll go one with my project. I don't know if anyone is persuaded by your arguments, but I'm certainly not.

[snowcode]

I hear you, and you're absolutely right. I think we are talking cross purposes. The OP cannot use an ImmutableQueue as a replacement for ConcurrentList for all the reasons the good folk have mentioned above, e.g. insertAt, removeAt etc, which promoted a lot of interesting discussions around both using existing stuff as well as writing new things, which is why I "mused" over the "interesting to me" wondering, why has not one mentioned LinkedList? If even only to debunk it's use in different situations. Your comments on ImmutableQueue are perfectly valid.

[Theodor Zoulias]

"Why has not one mentioned LinkedList?" This is an impossible to answer question, but if I had to guess I would say because nobody likes to use this class in general, most people have never used it, and so it doesn't popup as a solution in their mind when they have a problem to solve. Another possibility is that anyone who tried to use this class to do anything practical was disappointed by its abysmal performance (compared to array-backed structures like the List<T>), so they decided not to waste their time again with this class. But these are just my wild guesses of course. 😋

[snowcode]

:D @TheodorZoulias drat... now you've got me curious and I'm definitely going to have to do that perf comparison. nice thread, I'll post an update if/when I get around to it.