Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How could a for loop be related to a stack overflow?

I've met a piece of code that will cause a stack overflow exception only when a for loop repeats over a certain number of times.

Here's the code:

public class Stackoverflow
{
    public static void Test()
    {
        List<int> list = new List<int>() {1, 2};

        Container container = new Container {List = list};
        for (int i = 0; i < 10000; i++)     // This matters
        {
            foreach (var item in container.List)
            {
                Console.WriteLine(item);
            }
        }
    }
}

public class Container
{
    private IEnumerable<int> list;

    public IEnumerable<int> List
    {
        get
        {
            //return list.OrderBy(x => x);  <- This is OK
            list = list.OrderBy(x => x);    // This is not
            return list;
        }
        set { list = value; }
    }

}

When the method Test() is executed, you can see a long series of "1" and "2" being printed on screen before the error actually happens. (which I think means the for loop is advancing properly)

And the stack overflow exception does not occur if the condition becomes "i < 1000" (or less).

The memory dump showed "List.Orderby" is likely the direct cause of the problem

I know it's bad practice to write a "get" like this, but I don't understand what is causing the stack overflow exception here, and why it seems to be accumulative rather than a recursive death trap.

This is probably a trap in the enumeration code, or something by the compiler, or just my oversight? Anyway, looking for an explanation, thanks for your help.

Stacktrace here

In Text:

000000e86215e460 00007ffe28670f7c (MethodDesc 00007ffe28567738 +0x2c System.Linq.OrderedEnumerable`1[[System.Int32, mscorlib]].GetEnumerator())
000000e86215e4a0 00007ffe849ce396 (MethodDesc 00007ffe844a4ce8 +0x66 System.Linq.Buffer`1[[System.Int32, mscorlib]]..ctor(System.Collections.Generic.IEnumerable`1<Int32>))
000000e86215e4c0 00007ffe86bad279 (MethodDesc 00007ffe866d7630 +0x19 System.StubHelpers.StubHelpers.SafeHandleRelease(System.Runtime.InteropServices.SafeHandle))
000000e86215e510 00007ffe28670fe7 (MethodDesc 00007ffe28567e80 +0x47 System.Linq.OrderedEnumerable`1+<GetEnumerator>d__1[[System.Int32, mscorlib]].MoveNext())
000000e86215e520 00007ffe28670f7c (MethodDesc 00007ffe28567738 +0x2c System.Linq.OrderedEnumerable`1[[System.Int32, mscorlib]].GetEnumerator())
000000e86215e560 00007ffe849ce396 (MethodDesc 00007ffe844a4ce8 +0x66 System.Linq.Buffer`1[[System.Int32, mscorlib]]..ctor(System.Collections.Generic.IEnumerable`1<Int32>))
000000e86215e580 00007ffe86c5b552 (MethodDesc 00007ffe867e3f60 +0xf2 DomainNeutralILStubClass.IL_STUB_PInvoke(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr))
000000e86215e5d0 00007ffe28670fe7 (MethodDesc 00007ffe28567e80 +0x47 System.Linq.OrderedEnumerable`1+<GetEnumerator>d__1[[System.Int32, mscorlib]].MoveNext())
000000e86215e5e0 00007ffe28670f7c (MethodDesc 00007ffe28567738 +0x2c System.Linq.OrderedEnumerable`1[[System.Int32, mscorlib]].GetEnumerator())
000000e86215e5e8 00007ffe86c5b526 (MethodDesc 00007ffe867e3f60 +0xc6 DomainNeutralILStubClass.IL_STUB_PInvoke(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr))
000000e86215e620 00007ffe849ce396 (MethodDesc 00007ffe844a4ce8 +0x66 System.Linq.Buffer`1[[System.Int32, mscorlib]]..ctor(System.Collections.Generic.IEnumerable`1<Int32>))
000000e86215e690 00007ffe28670fe7 (MethodDesc 00007ffe28567e80 +0x47 System.Linq.OrderedEnumerable`1+<GetEnumerator>d__1[[System.Int32, mscorlib]].MoveNext())
000000e86215e6a0 00007ffe28670f7c (MethodDesc 00007ffe28567738 +0x2c System.Linq.OrderedEnumerable`1[[System.Int32, mscorlib]].GetEnumerator())
000000e86215e6e0 00007ffe849ce396 (MethodDesc 00007ffe844a4ce8 +0x66 System.Linq.Buffer`1[[System.Int32, mscorlib]]..ctor(System.Collections.Generic.IEnumerable`1<Int32>))
000000e86215e710 00007ffe86b9b46a (MethodDesc 00007ffe86950f90 +0x8a System.IO.StreamWriter.Flush(Boolean, Boolean))
000000e86215e750 00007ffe28670fe7 (MethodDesc 00007ffe28567e80 +0x47 System.Linq.OrderedEnumerable`1+<GetEnumerator>d__1[[System.Int32, mscorlib]].MoveNext())
000000e86215e760 00007ffe28670f7c (MethodDesc 00007ffe28567738 +0x2c System.Linq.OrderedEnumerable`1[[System.Int32, mscorlib]].GetEnumerator())
000000e86215e7a0 00007ffe849ce396 (MethodDesc 00007ffe844a4ce8 +0x66 System.Linq.Buffer`1[[System.Int32, mscorlib]]..ctor(System.Collections.Generic.IEnumerable`1<Int32>))
000000e86215e7d0 00007ffe28670da5 (MethodDesc 00007ffe28565c68 +0xe5 ConsoleTest.Container.get_List())
000000e86215e810 00007ffe28670fe7 (MethodDesc 00007ffe28567e80 +0x47 System.Linq.OrderedEnumerable`1+<GetEnumerator>d__1[[System.Int32, mscorlib]].MoveNext())
000000e86215e820 00007ffe28670f7c (MethodDesc 00007ffe28567738 +0x2c System.Linq.OrderedEnumerable`1[[System.Int32, mscorlib]].GetEnumerator())
000000e86215e860 00007ffe2867065f (MethodDesc 00007ffe28565b98 +0x11f ConsoleTest.Stackoverflow.Test())
000000e86215e900 00007ffe286704ba (MethodDesc 00007ffe28565ac0 +0x3a ConsoleTest.Program.Main(System.String[]))
like image 707
ck1521 Avatar asked Jul 03 '19 11:07

ck1521


1 Answers

The problem is that your get property replaces the list variable each time with a new object defined by list.OrderBy(x => x);.

Note that OrderBy(x => x) does not do any ordering yet, it creates an object that defines how to return items, which only gets executed if/when you iterate it with e.g. foreach.

I will try to show the consequences of this:

  • Before the first run, list equals List<int>() {1, 2}
  • After it ran once, list equals (List<int>() {1, 2}).OrderBy(x => x)
  • After it ran twice, list equals (List<int>() {1, 2}).OrderBy(x => x).OrderBy(x => x)
  • After it ran 10000 times... I wont even attempt to show what list contains.

Enumerating that 10000-fold-nested object is causing 10000 Enumerator objects to be spun up, each performing an ordered retrieval of the previous one, until the original source List<int>is encountered. Apparently it runs out of space before the source list is reached.

The fix is to not re-assign list every time, or (if you feel you must for some reason) then make it "do" the OrderBy by using ToList():

get
{
    list = list.OrderBy(x => x).ToList(); // creates a new list and does not keep to OrderBy() object
    return list;
}

That would still cause redundant re-ordering and re-assignment every time the property is accessed. If you need the ordering always, it will be far more efficient to put that logic in the setter, so it will happen just once:

get { return list; }
set { list = value.OrderBy(x => x).ToList(); }
like image 188
Peter B Avatar answered Sep 29 '22 10:09

Peter B