c# - 单链表队列在一定大小时抛出SO异常

Question

所以在学习了 .NET 核心 Queue 类型在内部使用数组而不是节点后，我想我可以尝试自己编写它。

MyQueue 的奇怪之处在于，当它有 9200 个节点时，它的 Length 属性返回正确的大小，但是当它有 9300 个节点时，它会抛出一个 StackOverflowException。

我一辈子都弄不明白为什么会这样。

队列节点

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;
        }
    }
}

我的队列

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);
        }
    }
}

测试程序

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

Windows 程序中的默认堆栈大小非常有限:

• 32 位进程 1MB。
• 64 位进程 4MB。

这是多年前决定的，影响所有进程，而不仅仅是 C# 进程。

这就是为什么您的进程如此快地耗尽堆栈空间的原因。

Also see here for more details .

请注意，可以更改用于进程的堆栈大小 - 通过使用 EDITBIN.EXE - 但不建议这样做。

您还可以更改新线程 的堆栈大小，但同样不推荐这样做。 (这并不总是适用于部分受信任的代码 - 如果部分受信任的代码超过默认堆栈大小，堆栈大小参数将被忽略。)

Microsoft 注意到以下内容:

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.

另请注意，您无法轻易更改 Task 的堆栈大小。