8
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Curious: what exactly throws the out of memory exception? Is it the list because you have more then int.Max elements? \$\endgroup\$ – t3chb0t Jul 8 '16 at 15:46
  • 2
    \$\begingroup\$ @t3chb0t The list is being loaded from a file, the object is so large that it gets added onto the Large Object Heap that has different memory managements. By adding the arrays into the list it isn't added onto the LOH and avoids the exception \$\endgroup\$ – TheLethalCoder Jul 8 '16 at 15:48
  • 3
    \$\begingroup\$ Could you explain a bit more about why you're loading that large amount of data in the first place? Is there no way you can load in the data via a stream and split up the work amongst many processes? I'd imagine you might get better bang for your buck than trying to hamfist your way into going past CLR limits. IOW, could you provide a little more context on why you need this (aside from it loading from a file)? \$\endgroup\$ – Dan Jul 9 '16 at 15:57
  • \$\begingroup\$ @DanPantry I'm loading a log file into a viewer and it is just easier to load all the data at once \$\endgroup\$ – TheLethalCoder Jul 9 '16 at 19:22
  • 1
    \$\begingroup\$ Let me introduce you to a wonderful concept called pagination. ;-) en.wikipedia.org/wiki/Pagination \$\endgroup\$ – Dan Jul 9 '16 at 19:24
6
\$\begingroup\$

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.

\$\endgroup\$
0
3
\$\begingroup\$

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?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ The way I understand it, ++j adds then evaluate. j++ evaluates then adds. As in, if int i = 0 then WriteLine(i++) would print 0 while WriteLine(++i) would print 1. For OP's usage ++i and i++ have no difference. Also the standard behavior for .NET collections is that IndexOf returns -1 if no index is found. \$\endgroup\$ – asibahi Jul 8 '16 at 15:55
  • \$\begingroup\$ @AbdulRahmanSibahi Yes that my understanding too, but there is another reason it is normally preferable to write ++j and that is performance. In C++ it makes a difference, but in C# it doesn't. I've just realised that I didn't make it clear I meant it didn't make a performance difference in my post, I'll correct it shortly. \$\endgroup\$ – Code Gorilla Jul 8 '16 at 16:00
  • \$\begingroup\$ It it's just an int (not a custom object with overloaded operators), any decent C++ compiler optimizes j++ if it doesn't have any side effects. \$\endgroup\$ – D. Jurcau Jul 8 '16 at 16:47
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Nice catch! RE thread safety: collections aren't thread-safe by default, a thread-safe implementation could be a ConcurrentChunkedList<T> or similar. \$\endgroup\$ – Mathieu Guindon Jul 9 '16 at 17:35
  • 1
    \$\begingroup\$ @Mat'sMug Sure, I get that standard collections aren't thread-safe, but my main point was that with this volume of data the OP is likely to not be able to circumvent needing threads, so he should probably invest in some thread safety. \$\endgroup\$ – Dan Jul 9 '16 at 17:38
2
\$\begingroup\$
  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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Indeed, that's not a list. But, it's not a Collection either. The only interface it can be exposed as, is IEnumerable<T>... which is definitely a missed opportunity. \$\endgroup\$ – Mathieu Guindon Jul 8 '16 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.