StackOverflow exception when initializing array

Question

I call the method and get StackOverflowException. It is not recursive call and it just contains array initialization. I need an array of BigIntegers, the code works fine with int array even of much bigger size. I show simplified example and in real code I can't use loop to fill the array as I can't generate numbers I need, so I have to hard code them all.

Setup: x64 mode, .Net Core

From error details we can see that:

1) Stack trace is null

2) Error presumably originated in System.Collections.ListDictionaryInternal

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Before"); // <--- This is displayed

            var a = GetBigIntegers(); // <--- Method is called

            Console.WriteLine("After"); // <--- We will never get there
        }


        static BigInteger[] GetBigIntegers()
        {
            // <--- Crash here
            return new BigInteger[]
            {
                1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                // Many more lines (850-900) and they are 2-3 times longer than here
                1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
            };
        }
    }

I've checked IL code, it looks correct and it takes close to 400 000 lines.

.method private hidebysig static 
    valuetype [System.Runtime.Numerics]System.Numerics.BigInteger[] GetBigIntegers () cil managed 
{
    // Method begins at RVA 0x207c
    // Code size 1130123 (0x113e8b)
    .maxstack 4
    .locals init (
        [0] valuetype [System.Runtime.Numerics]System.Numerics.BigInteger[]
    )

    // (no C# code)
    IL_0000: nop
    IL_0001: ldc.i4 66500
    IL_0006: newarr [System.Runtime.Numerics]System.Numerics.BigInteger
    IL_000b: dup
    IL_000c: ldc.i4.0
    //  return new BigInteger[66500]IL_000d: ldc.i4.1
    IL_000e: call valuetype [System.Runtime.Numerics]System.Numerics.BigInteger [System.Runtime.Numerics]System.Numerics.BigInteger::op_Implicit(int32)
    // (no C# code)
    IL_0013: stelem [System.Runtime.Numerics]System.Numerics.BigInteger
    IL_0018: dup
    IL_0019: ldc.i4.1
    IL_001a: ldc.i4.1
    IL_001b: call valuetype [System.Runtime.Numerics]System.Numerics.BigInteger [System.Runtime.Numerics]System.Numerics.BigInteger::op_Implicit(int32)
    IL_0020: stelem [System.Runtime.Numerics]System.Numerics.BigInteger
.....
    IL_113e75: dup
    IL_113e76: ldc.i4 66499
    IL_113e7b: ldc.i4.1
    IL_113e7c: call valuetype [System.Runtime.Numerics]System.Numerics.BigInteger [System.Runtime.Numerics]System.Numerics.BigInteger::op_Implicit(int32)
    IL_113e81: stelem [System.Runtime.Numerics]System.Numerics.BigInteger
    IL_113e86: stloc.0
    IL_113e87: br.s IL_113e89

    IL_113e89: ldloc.0
    IL_113e8a: ret
} // end of method Program::GetBigIntegers

I expected that array will be initialized and returned, but actually I got StackOverflow error.

I know that I can use different approaches to do the same stuff, but I want to know WHY it doesn't work this way. Hope it is interesting to everyone reading this question too.

https://stackoverflow.com/questions/1391672/what-is-the-maximum-size-that-an-array-can-hold — Markus Appel, Jun 25 '19 at 12:12
What happens when you remove a couple of these lines? remove like 90% of those 900 lines and see if the error still happens. — LoukMouk, Jun 25 '19 at 12:12
To enable arrays of more than 2GB you need to allowVeryLargeObjects in config. https://learn.microsoft.com/en-us/dotnet/framework/configure-apps/file-schema/runtime/gcallowverylargeobjects-element — Nitesh Saxena, Jun 25 '19 at 12:15
This likely is not related to the array itself, but to the initialization code generated for it (which is terrifyingly enormous and I can imagine the jitter to choke on it; `BigInteger` is a custom value type and the initialization can't be optimized like it can for a native type like `int`). Consider using a `new BigInteger[size]` declaration and filling it with a `for` loop (which, as a bonus, will make your code vastly more readable). — Jeroen Mostert, Jun 25 '19 at 12:17
Added StackTrace, it's null. If I remove enough lines, it works fine. I have 66500 elements in the array. I'm running in x64 mode. As I understand, allowVeryLargeObjects is for .net Framework, I'm using .net Core and if it would be the case, would I get StackOverflow or different exception? — Andrii Siriak, Jun 25 '19 at 12:23
@JeroenMostert thanks for recommendation, but it's just a simplified example and the point is that I can't use loop as there are not only 1s, but different numbers that I can't generate. — Andrii Siriak, Jun 25 '19 at 12:25
There's always another way and yes of course you can use a loop, even if that loop consists of reading a file, or converting elements from an `int` or `byte[]` array that you can do with initialization syntax. Just as long as you don't have one enormous method (which is extremely inefficient from a binary perspective to boot). I sincerely doubt you typed all those 66500 numbers by hand, did you? If code generated this, code can generate something else that *is* amenable to compilation. — Jeroen Mostert, Jun 25 '19 at 12:29
@JeroenMostert I agree with you that I can read it from file and I will definitely do so if i don't find an answer, but it won't give me understanding of what's going on in this program :) — Andrii Siriak, Jun 25 '19 at 12:35
My working hypothesis is that the jitter hits some internal limit and chokes when it has to translate your beast of a 400K instruction method to machine code and run it, but I haven't gone so far as to see whether that's actually the case (setting that up is a bit of a hassle). What is clear is that allocating an array of native types this way gets an optimized path where the array contents are simply copied as bytes, and `BigInteger` does not. The "laziest" way of working around is to initialize two smaller arrays this way (break them up in two methods) and copy them in a bigger array. — Jeroen Mostert, Jun 25 '19 at 12:39
`IL code ... takes close to 400 000 lines` - yikes! can you show a small excerpt? — 500 - Internal Server Error, Jun 25 '19 at 12:46
I was able to replicate the problem (`StackOverflowException`) using a `BigInteger[]` array with a 100,000 elements initializer, as well as a `Decimal[]` array with equal size. No exception occurred with a same sized `int[]` array though. These experiments are scary because the Visual Studio struggles to scroll with so much code in a single file, and even typing is painful. — Theodor Zoulias, Jun 25 '19 at 14:33

score 3 · Accepted Answer · answered Jun 26 '19 at 00:59

3

The actual reason is that evaluation stack frame size is not big enough to fit in everything pushed into.

The reason for that is hiding behind JIT-compiler optimizations which are not performed for struct initialization inside big methods (which leads to poor-perfomance machine code being generated).

Source.

answered Jun 26 '19 at 00:59

Artyom Ignatovich

591
1
3
13

I've read your reference and it looks like my issue. But I don't understand where JIT compiler puts this objects onto stack. From IL I see that there is not more than 4 items on the stack at any time. Reference to array (1), reference to array (2), index (3), value to be stored (4). Could you please explain why I don't see allocations that cause overflow? – Andrii Siriak Jun 26 '19 at 04:24
1

Right, this is a limitation on how the jit handles structures returned from calls. Large structures are returned implicity by reference. So internally when the jit sees a method that returns a large structure it allocates an “jit temporary” to handle the return value. If you have a large initializer list like this, then each initializer turns into a call and each call gets it s own jit temporary struct. The jit is not clever about re-using this space so each temporary struct gets its own slot on the stack. And the jit may also make additional copies to other temporaries. – Andy Ayers Jun 26 '19 at 18:21
1

The method needs to allocate space for all these temporaries in the prolog. So at the start of the method there will be a very large adjustment to the stack pointer, and this adjustment triggers a stack overflow. – Andy Ayers Jun 26 '19 at 18:21
Detecting when temporaries can be reused to avoid blowing up the stack like this is not as simple as one would hope. But it is something we should fix. As https://github.com/dotnet/coreclr/issues/14103 says, the workaround is to declare the initializer as an array of int[] say, and then loop over that filling in your array of BigInteger. – Andy Ayers Jun 26 '19 at 18:21

StackOverflow exception when initializing array

1 Answers1