Singly linked list queue throwing SO exception when a certain size

Question

So after learning the .NET core Queue type uses arrays internally and not nodes I thought I'd have a go at writing my own that does.

The strange thing about MyQueue is that when it has a size of 9200 nodes its Length property returns its correct size, but when it has 9300 nodes it throws a StackOverflowException.

I can't for the life of me work out why this is the case.

QueueNode

namespace MyQ.Core
{
    public class MyQueueNode<T> : IMyQueueNode<T>
    {
        private MyQueueNode<T> _nextNode;

        private T _value;

        //..

        public MyQueueNode(T value)
        {
            _value = value;
        }

        public void SetNextNode(ref MyQueueNode<T> nextNode)
        {
            _nextNode = nextNode;
        }

        public MyQueueNode<T> GetNextNode()
        {
            return _nextNode;
        }

        public T GetValue()
        {
            return _value;
        }
    }
}

MyQueue

namespace MyQ.Core
{
    public class MyQueue<T> : IMyQueue<T> where T : class
    {
        private volatile MyQueueNode<T> _headNode, _tailNode;

        //..

        public void Enqueue(T item)
        {
            MyQueueNode<T> newNode = new MyQueueNode<T>(item);

            if (_headNode == null)
            {
                _headNode = newNode;
                _tailNode = _headNode;
            }
            else
            {
                _tailNode.SetNextNode(ref newNode);
                _tailNode = newNode;
            } 
        }

        public T Dequeue()
        {
            if(_headNode == null)
            {
                throw new QueueEmptyException();
            }

            T value = _headNode.GetValue();

            _headNode = _headNode.GetNextNode();

            return value;
        }

        public T Peek()
        {
            if(_headNode == null)
            {
                return null;
            }

            return _headNode.GetValue();
        }

        public long Length => GetLength(_headNode);

        //..

        private long GetLength(MyQueueNode<T> node = null, long level = 0)
        {
            if(node == null)
            {
                return 0;
            }

            level++;

            if (node.GetNextNode() == null)
            {
                return level;
            }

            node = node.GetNextNode();

            return GetLength(node, level);
        }
    }
}

Test program

using System;
using MyQ.Core;
using System.Diagnostics;

namespace MyQ
{
    class Program
    {
        static void Main(string[] args)
        {
            IMyQueue<string> myQ = new MyQueue<string>();

            //..

            myQ.Enqueue("test 1");

            myQ.Enqueue("test 2");

            myQ.Enqueue("test 3");

            //..

            Console.WriteLine($"The length of the queue is: {myQ.Length}");

            //..

            Console.WriteLine("Peek: " + myQ.Peek()); // 1

            //..

            Console.WriteLine("Dequeue: " + myQ.Dequeue()); // 1

            Console.WriteLine("Dequeue: " + myQ.Dequeue()); // 2

            Console.WriteLine($"The length of the queue is: {myQ.Length}");

            Console.WriteLine("Dequeue: " + myQ.Dequeue()); // 3

            //..

            Console.WriteLine("About to test seed a queue. Press a key to start...");

            Console.ReadKey();

            TestSize(9200); // This works fine...

            TestSize(9300); // This one falls over...

            Console.ReadKey();
        }

        static void TestSize(long seedSize)
        {
            Stopwatch sw = new Stopwatch();

            sw.Start();

            IMyQueue<string> queue = new MyQueue<string>();

            for (int i = 0; i < seedSize; i++)
            {
                Console.WriteLine($"Queue {i}");

                queue.Enqueue(i.ToString());
            }

            sw.Stop();

            Console.WriteLine($"Done. Took {sw.Elapsed.TotalSeconds} seconds.");

            Console.WriteLine($"Queue length is: {queue.Length}");
        }
    }
}

Answer 1

The default stack size in Windows programs is extremely limited:

• 1MB for 32-bit processes.
• 4MB for 64-bit processes.

This was decided many years ago, and affects all processes, not just C# ones.

This is why your process runs out of stack space so quickly.

Also see here for more details.

Note that it's possible to change the stack size used for a process - by using EDITBIN.EXE - but this isn't recommended.

You can also change the stack size for a new Thread, but again this is not recommended. (This doesn't always work for partially trusted code - the stack size parameter will be ignored for partially trusted code if it exceeds the default stack size.)

Microsoft notes the following:

Avoid using this constructor overload. The default stack size used by the Thread(ThreadStart) constructor overload is the recommended stack size for threads. If a thread has memory problems, the most likely cause is programming error, such as infinite recursion.

Also note that you can't easily change the stack size of a Task.

Answer 2

Actually you can simplify (and optimize) your GetLength method. Just track items count on Enqueue and Dequeue. Try this:

public int Length { get; private set; }

public void Enqueue(T item)
{
  ++Length;
  // ...
}

public T Dequeue()
{
  --Length;
  // ...
}