正则表达式、字符串生成器和大对象堆碎片化问题

Question

如何在大字符串中运行多个正则表达式（以查找匹配项）而不会导致LOH碎片化？

使用.NET Framework 4.0，因此我正在使用StringBuilder，因此它不在LOH中，但是一旦我需要对其运行RegEx，我就必须调用StringBuilder.ToString()，这意味着它将位于LOH中。

有没有解决此问题的解决方案？几乎不可能有一个长时间运行的应用程序来处理像这样的大字符串和RegEx。

解决此问题的一个想法：

考虑到这个问题，我认为我找到了一个肮脏的解决方案。

在给定的时间内，我只有5个字符串，这5个字符串（大于85KB）将传递给RegEx.Match。

由于碎片化发生在新对象无法适合LOH中的空白空间时，这应该解决问题。

将所有字符串都填充到最大接受大小，比如1024KB（我可能需要使用StringBuider进行此操作）

通过这样做，所有新字符串都将适合于先前字符串已经超出范围的已清空内存

不会有任何碎片化，因为对象大小始终相同，因此在给定时间内只分配了1024 * 5个空间，并且这些空间在LOH中将被这些字符串共享。

我想这种设计的最大问题是，如果其他大型对象将此位置分配在LOH中，这将导致应用程序分配许多1024 KB字符串，可能会产生更严重的碎片化。fixed语句可能有帮助，但是如何将固定的字符串发送到RegEx而不实际创建不在固定内存地址中的新字符串呢？

对于这个理论有什么想法？（不幸的是，我无法轻松地复制问题，通常尝试使用内存分析器观察变化，也不确定我可以为此编写什么样的隔离测试用例）

- dr. evil

---

你确定大对象堆正在变得碎片化吗？我经常处理大型字符串（几百千字节），但我从未遇到过LOH碎片问题。 - Jim Mischel

是的，我确定。应用程序需要占用大量内存并长时间运行，才能看到其实际影响。如果您实际上进行内存分析，您可能会发现它正在影响您，但不足以使您的应用程序崩溃。 - dr. evil

是的，这很容易。一百美元就可以买到一个64位操作系统。任何编程工作都无法与之匹敌。 - Hans Passant

我猜你是一位服务器端程序员 :) 这是一个被送到电脑上的工具，我无法控制。你希望我告诉我的用户他们必须使用x64吗？因为这仅仅需要100美元吗？或者只限制客户群体为 x64-Win 7 用户？那会更容易，不是吗？ - dr. evil

任何软件供应商都会发布先决条件。需要Windows，不能使用苹果，必须能够运行.NET，需要磁盘空间，需要RAM等等。这没有什么特别之处，x64也不例外。在过去的三年里，Dell的默认选择，不需要额外费用。 - Hans Passant

@HansPassant 我希望满足业务需求是那么容易 :) - dr. evil

Answer 1

好的，这里是我尝试以一种相当通用但有一些明显限制的方式解决这个问题的方法。由于我没有在任何地方看到这个建议，每个人都在抱怨LOH碎片化，我想分享代码以确认我的设计和假设是正确的。

理论：

1. 创建一个共享的大型StringBuilder（用于存储从流中读取的大字符串）- new StringBuilder(ChunkSize * 5);
2. 创建一个大型字符串（必须比最大接受的大小大），应该初始化为空格。- new string(' ', ChunkSize * 10);
3. 将字符串对象固定到内存中，以便GC不会干扰它。 GCHandle.Alloc(pinnedText, GCHandleType.Pinned)。尽管LOH对象通常被固定，但这似乎可以提高性能。可能是因为unsafe代码
4. 将流读入共享StringBuilder，然后使用索引器将其不安全地复制到pinnedText中
5. 将pinnedText传递给RegEx

使用此实现，下面的代码就像没有LOH分配一样工作。如果我切换到使用静态的StringBuilder或使用StringBuilder.ToString()而不是使用new string(' ')分配，则代码可以在崩溃之前分配少300%的内存出现outofmemory exception

我还使用内存分析器确认了结果，这个实现中没有LOH碎片。我仍然不明白为什么RegEx不会引起任何意外的问题。我还测试了不同且昂贵的RegEx模式，并且结果是相同的，没有碎片。

代码：

http://pastebin.com/ZuuBUXk3

using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;

namespace LOH_RegEx
{
    internal class Program
    {
        private static List<string> storage = new List<string>();
        private const int ChunkSize = 100000;
        private static StringBuilder _sb = new StringBuilder(ChunkSize * 5);


        private static void Main(string[] args)
        {
            var pinnedText = new string(' ', ChunkSize * 10);
            var sourceCodePin = GCHandle.Alloc(pinnedText, GCHandleType.Pinned);

            var rgx = new Regex("A", RegexOptions.CultureInvariant | RegexOptions.Compiled);

            try
            {

                for (var i = 0; i < 30000; i++)
                {                   
                    //Simulate that we read data from stream to SB
                    UpdateSB(i);
                    CopyInto(pinnedText);                   
                    var rgxMatch = rgx.Match(pinnedText);

                    if (!rgxMatch.Success)
                    {
                        Console.WriteLine("RegEx failed!");
                        Console.ReadLine();
                    }

                    //Extra buffer to fragment LoH
                    storage.Add(new string('z', 50000));
                    if ((i%100) == 0)
                    {
                        Console.Write(i + ",");
                    }
                }
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.ToString());
                Console.WriteLine("OOM Crash!");
                Console.ReadLine();
            }
        }


        private static unsafe void CopyInto(string text)
        {
            fixed (char* pChar = text)
            {
                int i;
                for (i = 0; i < _sb.Length; i++)
                {
                    pChar[i] = _sb[i];
                }

                pChar[i + 1] = '\0';
            }
        }

        private static void UpdateSB(int extraSize)
        {
            _sb.Remove(0,_sb.Length);

            var rnd = new Random();
            for (var i = 0; i < ChunkSize + extraSize; i++)
            {
                _sb.Append((char)rnd.Next(60, 80));
            }
        }
    }
}

- dr. evil

Answer 2

你可以在某些时间点被卸载的 AppDomain 中完成你的工作吗？

- DaeMoohn

---

问题在于，除非您使用共享存储并直接从内存或文件中读取数据流，否则仍然需要共享结果，否则您仍将面临同样的问题。因为如果您以任何方式使用远程处理，则会再次创建大型数组或字符串，这些数组或字符串将进入LOH，并且现在存在于两个应用程序域中。共享内存、内存映射文件等确实是一种解决方案，但在大型应用程序中它真的非常复杂，并且会带来相当大的性能损失。 - dr. evil

Answer 3

一个替代方案是找到一种在非数组数据结构上执行正则表达式匹配的方法。不幸的是，快速搜索谷歌并没有找到太多基于流的正则表达式库。我猜测正则表达式算法需要做很多回溯，而流不支持这种操作。

你是否绝对需要完整的正则表达式功能？也许你可以实现自己的简单搜索函数，可以在85kb以下的字符串链表上工作？

此外，只有当您长时间保留大对象引用时，LOH碎片才会真正引起问题。如果您不断地创建和销毁它们，则LOH不应该增长。

顺便说一下，我发现RedGate ANTS memory profiler非常擅长跟踪LOH中的对象和碎片级别。

- SimonC

---

LOH分段只有在长时间保留大对象引用时才会导致问题。据我所知，如果大小超过85KB，则不论持续时间多长，都将位于LOH中。我正在使用ANTS Profiler，确实非常好。 - dr. evil

是的，需要正则表达式的全部功能。 - dr. evil

如果可以的话，你能否阻止其他对象进入LOH（大对象堆）？通常情况下，LOH相当大，因此如果只有你的字符串被分配在那里，并且它们以相同的速率被释放，那么我不会期望出现问题。 - SimonC

如果你读过关于LOH碎片问题的内容，那么你就会知道这是一个已知的问题。这正是我的问题所在。 - dr. evil

是的，我明白什么是LOH碎片化，我只是想了解是什么导致了您的问题。如果只有您的5个字符串被分配在LOH上，它们的大小差不多，并且引用的创建速度与超出范围的速度相同，那么您不应该经历碎片化。但是，如果在您的字符串之间还分配了其他对象，则会出现不同的问题。所以，再次强调，您知道是否有其他对象（除了您的5个字符串）被分配在LOH上吗？ - SimonC