List size limitation in C#

Question

This could possibly appear to be a nasty thing to ask but why do we have so short limit of number of objects in a list.

i wrote following code to test list size in C#

    List<int> test = new List<int>();            
    long test1 = 0;
    try
    {
        while (true)
        {
            test.Add(1);
            test1++;
        }
    }
    catch (Exception ex)
    {
        MessageBox.Show(test1 + "   |   " + ex.Message);
    }

and the size of list could only be 134217728

isn't that unfair :( ??? what is alternate way if i want to add objects even beyond 'integer' limits (i mean number of objects > 2^32) ???

Answer 1

A List<int> is backed by an int[]. You will fail as soon as a larger backing array cannot be allocated - and bear in mind that:

• There's a 2GB per-object limit in the CLR even in 64 bits (EDIT: as of .NET 4.5, this can be avoided for the 64-bit CLR - see <gcAllowVeryLargeObjects>)
• The list will try to allocate a backing array which is larger than what it immediately requires, in order to accommodate later Add requests without reallocation.
• During the reallocation, there has to be enough total memory for both the old and the new arrays.

Setting the Capacity to a value which will put the backing array near the theoretical limit may get you a higher cutoff point than the natural growth, but that limit will certainly come.

I would expect a limit of around 2²⁹ elements (536,870,912) - I'm slightly surprised you haven't managed to get beyond 134,217,728. How much memory do you actually have? What version of .NET are you using, and on what architecture? (It's possible that the per-object limit is 1GB for a 32-bit CLR, I can't remember for sure.)

Note that even if the per-object limit wasn't a problem, as soon as you got above 2³¹ elements you'd have problems addressing those elements directly with List<T>, as the indexer takes an int value.

Basically, if you want a collection with more than int.MaxValue elements, you'll need to write your own, probably using multiple backing arrays. You might want to explicitly prohibit removals and arbitrary insertions :)

Answer 2

Here is an incredibly naive (and untested) implementation of a BigList backed by a Long instead of an integer. I wrote it in about 5 minutes, it doesn't implement ienumerable or ilist, but it shows the Partitioning that was mentioned in other answers. yeah, it's in VB, deal with it :)

This will need some pretty serious work and tuning up before it's actually useable, but it illustrates the idea.

Public Class BigList(Of T)
    Private mInternalLists As List(Of List(Of T))
    Private mPartitionSize As Integer = 1000000

    Private mSize As Long = 0

    Public Sub New()
        mInternalLists = New List(Of List(Of T))
    End Sub

    Public Sub Add(Item As T)
        mSize += 1

        Dim PartitionIndex As Integer = CInt(mSize \ mPartitionSize)

        Dim Partition As List(Of T)
        If mInternalLists.Count < PartitionIndex Then
            Partition = New List(Of T)
            mInternalLists.Add(Partition)
        Else
            Partition = mInternalLists(PartitionIndex)
        End If
        Partition.Add(Item)
    End Sub

    Default Public ReadOnly Property Item(Index As Long) As T
        Get
            Dim PartitionIndex As Integer = CInt(mSize \ mPartitionSize)
            Dim Partition As List(Of T)
            If mInternalLists.Count < PartitionIndex Then
                Throw New IndexOutOfRangeException
            Else
                Partition = mInternalLists(PartitionIndex)
            End If

            Return Partition(CInt(mSize Mod mPartitionSize))
        End Get
    End Property
End Class

Answer 3

List limit is ~536,870,912 bytes (1/2 MB on my machine (32 bit Win7, .NET 4.0))

Your adding integers (4 bytes each), so limit is byte limit / 4 (~134,217,727)

Answer 4

I didn't test it but due to its kind of implementation the LinkedList<T> should give you the possibility to add more elements than to a List<T>. But be aware of it's drawbacks (e.g. calling Count).