Custom list to avoid out of memory exceptions

Question

The following class is a helper to avoid OutOfMemoryException exceptions being thrown when the list is to large so that it is added onto the large objects heap. To do this it adds the items onto the heap as smaller arrays contained inside of a list.

Some quick notes:

• I prefer not to use var.
• The constant in all caps is a company standard.

using System;
using System.Collections;
using System.Collections.Generic;

namespace Helpers.Collections
{
    public class ChunkedList<T> : IEnumerable<T>, IDisposable
    {
        private const int DEFAULT_CHUNK_SIZE = 4096;

        private readonly int _nChunkSize;
        private IList<T[]> _alInternalCollection;
        private int _nCount;
        private bool _bTIsDisposable;

        public int Count
        {
            get
            {
                return _nCount;
            }
        }

        public ChunkedList() : this(DEFAULT_CHUNK_SIZE) { }

        public ChunkedList(int chunkSize)
        {
            _alInternalCollection = new List<T[]>();

            _nChunkSize = chunkSize;

            _nCount = 0;

            _bTIsDisposable = typeof(IDisposable).IsAssignableFrom(typeof(T));
        }

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

        public T this[int index]
        {
            get
            {
                if (index < 0 || index >= _nCount)
                {
                    throw new IndexOutOfRangeException();
                }

                int nChunk = index / _nChunkSize;
                int nChunkIndex = index % _nChunkSize;

                return _alInternalCollection[nChunk][nChunkIndex];
            }
            set
            {
                if (index < 0 || index >= _nCount)
                {
                    throw new IndexOutOfRangeException();
                }

                int nChunk = index / _nChunkSize;
                int nChunkIndex = index % _nChunkSize;

                T oldItem = _alInternalCollection[nChunk][nChunkIndex];
                _alInternalCollection[nChunk][nChunkIndex] = value;

                if (_bTIsDisposable)
                {
                    (oldItem as IDisposable).Dispose();
                }
            }
        }

        public void Add(T item)
        {
            int nChunk = _nCount / _nChunkSize;

            int nChunkIndex = _nCount % _nChunkSize;
            if (nChunkIndex == 0)
            {
                _alInternalCollection.Add(new T[_nChunkSize]);
            }

            _alInternalCollection[nChunk][nChunkIndex] = item;
            _nCount++;
        }

        public void AddRange(IEnumerable<T> items)
        {
            if (items == null)
            {
                throw new ArgumentNullException("items");
            }

            foreach (T item in items)
            {
                this.Add(item);
            }
        }

        public void Clear()
        {
            if (_bTIsDisposable)
            {
                foreach (T[] array in _alInternalCollection)
                {
                    foreach (T t in array)
                    {
                        (t as IDisposable).Dispose();
                    }
                }
            }

            _alInternalCollection.Clear();
            _nCount = 0;
        }

        public bool Contains(T item)
        {
            foreach (T[] array in _alInternalCollection)
            {
                foreach (T t in array)
                {
                    if (item.Equals(t))
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        public IEnumerator<T> GetEnumerator()
        {
            foreach (T[] array in _alInternalCollection)
            {
                foreach (T t in array)
                {
                    yield return t;
                }
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public int IndexOf(T item)
        {
            for (int i = 0; i < _alInternalCollection.Count; ++i)
            {
                for (int j = 0; j < _alInternalCollection[i].Length; ++j)
                {
                    if (item.Equals(_alInternalCollection[i][j]))
                    {
                        return ((i * _nChunkSize) + j);
                    }
                }
            }

            return -1;
        }
    }
}

Answer 1

Following the existing conventions is more important than breaking them to follow the established, standard ones - so fine, have SCREAM_CASE constants and redundant type names everywhere.

But then, if you're going to not use var and make every type explicit, it seems to me that there's a worrying amount of care given to what type a variable might be, to the point of keeping Hungarian Notation around:

    private readonly int _nChunkSize;
    private IList<T[]> _alInternalCollection;
    private int _nCount;
    private bool _bTIsDisposable;

These prefixes are useless at best, utterly annoying at worst. I'd much rather read this:

    private readonly int _chunkSize;
    private readonly List<T[]> _items;
    private readonly bool _isDisposable;

Anything that's only ever meant to be assigned in the constructor should be readonly.

_alInternalCollection is a terrible name IMO. First, it's not a collection, second, what's the a prefix for anyway; third, I suppose l stands for "List", and that makes the Collection part redundant, if not confusing. I'd just call it _items and be done with it.

Name things after what they're used for, not after their type.

---

The positioning of members makes the code much harder to follow than it should be: I expect a type's constructor to be the first public member of a class. Your code has a Count property instead.

Hence:

private const int DEFAULT_CHUNK_SIZE = 4096;

private readonly List<T[]> _items;
private readonly int _chunkSize;
private readonly bool _isDisposable;

public ChunkedList()
    : this(DEFAULT_CHUNK_SIZE)
{
}

public ChunkedList(int chunkSize)
{
    _chunkSize = chunkSize;
    _items = new List<T[]>();
    _isDisposable = typeof(IDisposable).IsAssignableFrom(typeof(T));
}

Followed by public properties/indexers, then public methods, then the IEnumerable<T> implementation, and then the IDisposable implementation; you have Dispose near the top, Count above the constructors, and IEnumerable members in the middle of the class. Feels messy.

Another thing that strikes me: you've got Add, AddRange, Clear, Contains, IndexOf, Count ...but you're not implementing IList<T>? Not even ICollection<T>? This means this ChunkedList, when used in code that's written against abstractions, can only ever be exposed as an IEnumerable<T>... and that doesn't feel right. You have a custom generic collection class, make it implement a generic collection interface and let the client code work off an IList<T> and be blissfully unaware of the implementation detail that the "chunking" is.

Answer 2

Really minor things:

1. Why not used unsigned int rather than int? That way you wouldn't have to check for <0.
2. As far as I understand ++j makes no performance improvement in C#, so you could remove them or you could be consistent and fix all the post incremented variables.
3. There are no comments, OK the code is relatively trivial but as a minimum a block explain what the class does would be nice, even if you copied the first paragraph from your post.
4. Would it be better if Index of threw instead of return -1?

Answer 3

I wanted to ask about your use of IDisposable.

You implement IDisposable so that you may call Dispose on elements in your ChunkedList<T>. This feels like a bad idea. As @TrevorAsh mentions, this violates a well accepted principle that it is the owner of the IDisposable that determines its lifecycle, not things that consume it.

This would be lessened if you made it quite clear that only elements that implemented IDisposable could be added to your list. As it stands, you currently make it optional, and that IMO violates SRP (because your list will have two different behaviours depending on what the generic argument is).

I'd therefore suggest making an object having IDisposable mandatory using a generic constraint and not checking it when you create the object, like so:

public class ChunkedList<T> : IEnumerable<T>, IDisposable where T : IDisposable

This enables you to always dispose every object in the collection.

---

Alternatively, you could remove this feature of the List like @TrevorAsh suggested.

I must mention like I said in my comments that the use-case behind this seems very strange and I think you may have an XY problem on your hands. If your issue is dealing with large amounts of objects from a file, why are you not using a Streaming approach instead and dividing the work up among workers?

---

BTW I would also argue this behaviour just isn't safe across threads and you're likely to need them if you want to actually do something with this amount of data.

Answer 4

1. I see duplicated code, especially in the get/set of the indexer. That should be pulled into a private method and shared.
2. Why are you calling Dispose on elements removed from the collection? This breaks a serious expectation. A commonly accepted best practice is to have the object creating the item responsible for dispose. As it stands, it's prone to bugs when the calling code disposes objects it added to the collection.
3. In the Contains method (and perhaps other similar methods) why not call contains for each array in _alInternalCollection? The use of Equals is going to provide inconsistent results. Take a look at some source code for List.Contains to see just how different your implementation is: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

Answer 5

You use the same nested loops four times but you actually could use the one you wrote for the GetEnumerator in the other three places for IndexOf, Contains and Clear with LINQ or a simple foreach.

Another thing is that you shouldn't call it a list without implementing the list interface. A ChunckedCollection would be more appropriate.