.Net Lists and maximum number of elements

Question

So I am developing an append-only 64-bit-ish List and Dictionary, and I've run into a memory error. I figured I would at some point, but not at 64 MBs. I find that somewhat unexpected, and am curious if someone could explain to me why it's running into an issue at 64 MBs.

My test for my new List class is simply an attempt to create and load 8 GBs worth of bools into the List. I figured they'd suck up only ~1 bit each, so I'd get some good metrics / precision for testing my program.

Here is the output from VS:

-       this    {OrganicCodeDesigner.DynamicList64Tail<bool>}   OrganicCodeDesigner.DynamicList64Tail<bool>
        Count   536870912   ulong
-       data    Count = 536870912   System.Collections.Generic.List<bool>
-       base    {"Exception of type 'System.OutOfMemoryException' was thrown."} System.SystemException {System.OutOfMemoryException}
-       base    {"Exception of type 'System.OutOfMemoryException' was thrown."} System.Exception {System.OutOfMemoryException}
+       Data    {System.Collections.ListDictionaryInternal} System.Collections.IDictionary {System.Collections.ListDictionaryInternal}
        HelpLink    null    string
+       InnerException  null    System.Exception
        Message "Exception of type 'System.OutOfMemoryException' was thrown."   string
        Source  "mscorlib"  string
        StackTrace  "   at System.Collections.Generic.Mscorlib_CollectionDebugView`1.get_Items()"   string
+       TargetSite  {T[] get_Items()}   System.Reflection.MethodBase {System.Reflection.RuntimeMethodInfo}
+       Static members      
+       Non-Public members      
-       Raw View        
        Capacity    536870912   int
        Count   536870912   int
-       Static members      
+       Non-Public members      
-       Non-Public members      
+       _items  {bool[536870912]}   bool[]
        _size   536870912   int
        _syncRoot   null    object
        _version    536870912   int
        System.Collections.Generic.ICollection<T>.IsReadOnly    false   bool
        System.Collections.ICollection.IsSynchronized   false   bool
        System.Collections.ICollection.SyncRoot {object}    object
        System.Collections.IList.IsFixedSize    false   bool
        System.Collections.IList.IsReadOnly false   bool
        item    false   bool
-       Type variables      
        T   bool    bool

And here are the classes I am currently working on:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace OrganicCodeDesigner
{
    public class DynamicList64Tail<T> : iList64<T>
    {
        private List<T> data;

        public DynamicList64Tail()
        {
            data = new List<T>();
        }


        public void Add(T item)
        {
            data.Add(item);
        }       

        public void Clear()
        {
            data.Clear();
        }

        public bool Contains(T item)
        {
            return data.Contains(item);
        }

        public ulong? IndexOf(T item)
        {
            if(this.data.Contains(item)) {
                return (ulong)data.IndexOf(item);
            }
            return null;
        }

        public T this[ulong index]
        {
            get
            {
                return data[(int)(index)];
            }
            set
            {
                data[(int)(index)] = value;
            }
        }


        public ulong Count
        {
            get { return (ulong)data.Count; }
        }

    }
}


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace OrganicCodeDesigner
{
    // @todo: Create IList64, with 64-bit longs in mind.
    // @todo: Create BigIntegerList, which may supersede this one.
    public class DynamicList64<T> : iList64<T>
    {
        private List<iList64<T>> data;

        private ulong count = 0;
        private ulong depth = 0;

        public DynamicList64()
        {
            data = new List<iList64<T>>() { new DynamicList64Tail<T>()};
            count = 0;
        }

        public DynamicList64(ulong depth)
        {
            this.depth = depth;
            if (depth == 0)
            {
                data = new List<iList64<T>>() { new DynamicList64Tail<T>() };
            }
            else
            {
                depth -= 1;
                data = new List<iList64<T>>() { new DynamicList64<T>(depth) };
            }
        }

        internal DynamicList64(List<iList64<T>> data, ulong depth)
        {

            this.data = data;
            this.depth = depth;
            this.count = Int32.MaxValue;


        }

        public void Add(T item)
        {
            if (data.Count >= Int32.MaxValue)
            {
                //@todo: Do switch operation, whereby this {depth, List l} becomes this {depth + 1, List.Add(List l), count = 1}, and the new object becomes {depth, List l, count = max}  
                DynamicList64<T> newDynamicList64 = new DynamicList64<T>(this.data, this.depth);
                this.data = new List<iList64<T>>() { newDynamicList64 };
                this.count = 0;
                this.depth += 1;
            }

            if(data[data.Count-1].Count >= Int32.MaxValue) {
                if (depth == 0)
                {
                    data.Add(new DynamicList64Tail<T>());
                }
                else
                {
                    data.Add(new DynamicList64<T>(depth - 1));
                }
            }

            data[data.Count - 1].Add(item);
            count++;
        }



        public void Clear()
        {
            data.Clear();
            data = new List<iList64<T>>() { new DynamicList64Tail<T>() };
            count = 0;
            depth = 0;
        }

        public bool Contains(T item)
        {
            foreach(iList64<T> l in data) {
                if(l.Contains(item)) {
                    return true;
                }
            }
            return false;
        }

        public ulong? IndexOf(T item)
        {
            for (int i = 0; i < data.Count; i++ )
            {
                if (data[i].Contains(item))
                {
                    return (ulong)(((ulong)i * (ulong)(Int32.MaxValue)) + data[i].IndexOf(item).Value);
                }
            }

            return null;           
        }

        public T this[ulong index]
        {
            get
            {
                return data[(int)(index / Int32.MaxValue)][index % Int32.MaxValue];
            }
            set
            {
                data[(int)(index / Int32.MaxValue)][index % Int32.MaxValue] = value;
            }
        }


        public ulong Count
        {
            get { return this.count; }
        }

    }
}


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace OrganicCodeDesigner
{
    public interface iList64<T>
    {
        void Add(T item);
        void Clear();
        bool Contains(T item);
        ulong? IndexOf(T item);
        T this[ulong index] { get; set;}
        ulong Count { get; }

    }
}

And the test program's code:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using OrganicCodeDesigner;

namespace OrganicCodeDesignerListDictionaryTest
{
    public partial class MainForm : Form
    {
        public MainForm()
        {
            InitializeComponent();
        }

        private void Button_TestList_Click(object sender, EventArgs e)
        {
            DynamicList64<bool> newList = new DynamicList64<bool>();
            newList.Add(true);
            newList.Add(false);

            bool b = true;
            for (ulong i = 0; i < 68719476736; i++)
            {
                b = !b;
                newList.Add(b);
                //if(i%4096==0) {
                    //TextBox_Output.Text += "List now contains " + i + "\r";
                //}
            }

            TextBox_Output.Text += "Successfully added all the bits.\r";
        }

        private void Button_TestDictionary_Click(object sender, EventArgs e)
        {

        }
    }
}

Perhaps you can spot the error?

Answer 1

Perhaps you can spot the error?

I think the error is here:

I figured they'd suck up only ~1 bit each, so I'd get some good metrics / precision for testing my program.

A bool takes one byte, not one bit - so you've drastically underestimated the size of your list. You're actually running into an error with 512MB of bools. As Reed Copsey is editing a little faster than me - I suspect the list is trying to increase its size by allocating an array 2x it's current size [i.e. a 1GB array] and that this is running into some .net limitations.

This is probably a good time to start implementing your splitting logic.

Answer 2

There are limits to the size of an array in .NET. Even if you are running on 64bit platforms, and set gcAllowVeryLargeObjects (in .NET 4.5), you are still limited to 2,146,435,071 items max in a single dimension of the array.

(In pre-4.5, you are limited by 2gb for a single object, no matter how many entries it contains.)

That being said, a bool is represented by one byte, not one bit, so this will be quite a bit larger than you're expecting. That being said, you still only have 536,870,912 in your list when this fails, so theoretically, on a 64bit system with enough memory, the next allocation for growing the list should still be within the limits. However, this requires the program to succesfully allocate a single, contiguous chunk of memory large enough for the requested data (which will be 2x the size of the last chunk).