RegEx, StringBuilder и фрагментация кучи больших объектов

Question

Как я могу запустить много RegExes (чтобы найти совпадения) в больших строках, не вызывая фрагментацию LOH?

Это .NET Framework 4.0, поэтому я использую StringBuilder, поэтому его нет в LOH, однако, как только мне нужно запустить на нем RegEx, я должен вызвать StringBuilder.ToString(), что означает, что он будет в LOH .

Есть ли решение этой проблемы? Практически невозможно иметь долго работающее приложение, которое имеет дело с большими строками и подобными RegEx.

Идея для решения этой проблемы:

Размышляя над этой проблемой, я думаю, что нашел грязное решение.

В данный момент у меня есть только 5 строк, и эти 5 строк (больше 85 КБ) будут переданы в RegEx.Match.

Поскольку фрагментация происходит из-за того, что новые объекты не помещаются в пустые пространства в LOH, это должно решить проблему:

1. PadRight все строки макс. допустимый размер, скажем, 1024 КБ (мне может понадобиться сделать это с StringBuider)
2. При этом все новые строки будут помещаться в уже освобожденную память, поскольку предыдущая строка уже выходит за рамки
3. Фрагментации не будет, потому что размер объекта всегда один и тот же, поэтому я выделю только 1024 * 5 в определенный момент времени, и эти места в LOH будут распределены между этими строками.

Я предполагаю, что самая большая проблема с этим дизайном заключается в том, что случится, если другие большие объекты выделят это местоположение в LOH, что приведет к тому, что приложение выделит много строк по 1024 КБ, возможно, с еще худшей фрагментацией. Оператор fixed может помочь, однако, как я могу отправить фиксированную строку в RegEx без фактического создания новой строки, которая не находится в фиксированном адресе памяти?

Есть идеи по поводу этой теории? (К сожалению, я не могу воспроизвести проблему легко, я обычно пытаюсь использовать профилировщик памяти, чтобы наблюдать за изменениями и не уверен, какой отдельный тестовый пример я могу написать для этого)

Answer 1

Хорошо, вот моя попытка решить эту проблему довольно общим способом, но с некоторыми очевидными ограничениями.Так как я нигде не видел этот совет, и все жалуются на фрагментацию LOH, я хотел бы поделиться кодом, чтобы подтвердить, что мой дизайн и предположения верны.

Теория:

1. Создание общего массивного StringBuilder (для хранения больших строк, которые читаются из того, что мы читаем из потоков) - new StringBuilder(ChunkSize * 5);
2. Создание массивной строки (должно быть больше максимально допустимого размера), должен быть инициализирован с пустым пространством.- новая строка ('', ChunkSize * 10);
3. Закрепить строковый объект в памяти, чтобы GC не связывался с ним.GCHandle.Alloc(pinnedText, GCHandleType.Pinned).Даже если объекты LOH обычно закреплены, это, похоже, улучшает производительность.Возможно из-за unsafe кода
4. Считать поток в общий StringBuilder и затем небезопасно скопировать его в pinnedText с помощью индексаторов
5. Передать pinnedText в RegEx

С этимРеализация кода ниже работает так же, как нет выделения LOH.Если я переключаюсь на new string(' ') выделения вместо использования статического StringBuilder или использую StringBuilder.ToString() код, то можно выделить 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));
            }
        }
    }
}

Answer 2

Одной из альтернатив может быть поиск способа выполнения регулярных сопоставлений для структуры данных, не основанной на массивах. К сожалению, быстрый Google не поднял много с точки зрения основанных на потоке регулярных библиотек. Я бы предположил, что алгоритм reg-ex должен был бы выполнять большое отслеживание назад, что не поддерживается потоками.

Вам абсолютно необходимы все возможности регулярных выражений? Не могли бы вы реализовать свои собственные более простые функции поиска, которые могли бы работать со связанными списками строк размером до 85 КБ?

Кроме того, фрагментация LOH действительно вызывает проблемы, только если вы держите ссылки на большие объекты в течение длительных периодов времени. Если вы постоянно создаете и уничтожаете их, LOH не должен расти.

FWIW, я нашел профилировщик памяти RedGate ANTS , очень хорошо отслеживающий объекты в LOH и уровни фрагментации.

Answer 3

Вы можете выполнять свою работу в домене приложений, который выгружается в определенные моменты времени?