String.Substring() кажется узким местом этого кода

Введение

У меня есть этот любимый алгоритм, который я сделал довольно давно, и я всегда пишу и переписываю на новых языках программирования, платформах и т.д. В качестве своего рода эталона. Хотя мой основной язык программирования - С#, я просто буквально скопировал код и немного изменил синтаксис, построил его на Java и нашел, что он работает на скорости 1000 раз быстрее.

Код

Существует довольно много кода, но я собираюсь представить этот фрагмент, который, по-видимому, является главной проблемой:

for (int i = 0; i <= s1.Length; i++) 
{
    for (int j = i + 1; j <= s1.Length - i; j++)
    {
        string _s1 = s1.Substring(i, j);
        if (tree.hasLeaf(_s1))
         ...

Данные

Важно отметить, что строка s1 в этом конкретном тесте имеет длину 1 миллион символов (1 МБ).

измерения

Я профилировал выполнение моего кода в Visual Studio, потому что думал, что я строю свое дерево или способ, которым я пересекаю его, не является оптимальным. После изучения результатов появляется строка string _s1 = s1.Substring(i, j); вмещает более 90% времени исполнения!

Дополнительные наблюдения

Еще одно отличие, которое я заметил, заключается в том, что хотя мой код является однопоточным Java, ему удается выполнить его с использованием всех 8 ядер (100% загрузка процессора), хотя даже с методами Parallel.For() и многопоточности мой код С# позволяет использовать 35- Максимум 40%. Поскольку алгоритм масштабируется линейно с количеством ядер (и частоты), я компенсировал это, и все же фрагмент в Java выполняет порядок на 100-1000 раз быстрее.

аргументация

Я предполагаю, что причина, по которой это происходит, связана с тем, что строки в С# неизменяемы, поэтому String.Substring() должен создать копию, и поскольку она находится внутри цикла вложенных циклов с множеством итераций, я предполагаю, что много копий и однако сбор мусора продолжается, однако я не знаю, как подстрока реализована на Java.

Вопрос

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

Запрошенная минимальная реализация (из комментариев)

Я отказался от реализации дерева суффикса, которое является O (n) в построении, и O (log (n)) в обход

public static double compute(string s1, string s2)
{
    double score = 0.00;
    suffixTree stree = new suffixTree(s2);
    for (int i = 0; i <= s1.Length; i++) 
    {
        int longest = 0;
        for (int j = i + 1; j <= s1.Length - i; j++)
        {
            string _s1 = s1.Substring(i, j);
            if (stree.has(_s1))
            {
                score += j - i;
                longest = j - i;
            }
            else break;
         };

        i += longest;
    };
    return score;
}

Снимок экрана профайлера

Обратите внимание, что это было проверено со строкой s1 размером 300 000 символов. По какой-то причине 1 миллионный персонаж просто не заканчивается на С#, в то время как в Java он занимает всего 0,75 секунды. Потребляемая память и количество сборок мусора, похоже, не указывают на проблему с памятью. Пик составлял около 400 МБ, но, учитывая огромное дерево суффикса, это кажется нормальным. Никаких странных сборок мусора не обнаружено.

CPU profiler

Memory profiler

Ответы

Ответ 1

Проблема происхождения

После великолепной битвы, которая длилась два дня и три ночи (и удивительные идеи и мысли из комментариев), я, наконец, сумел решить эту проблему!

Я хотел бы опубликовать ответ для всех, кто сталкивается с аналогичными проблемами, где string.Substring(i, j) не является приемлемым решением для получения подстроки строки, потому что строка слишком велика, и вы не можете позволить себе копирование выполняется с помощью string.Substring(i, j) (он должен сделать копию, потому что строки С# неизменяемы, никоим образом не работают) или string.Substring(i, j) вызывается огромное количество раз по сравнению с (например, в моих вложенных циклах), что дало сборщику мусора тяжелое время или, как в моем случае, оба!

попытки

Я пробовал много предложенных вещей, таких как StringBuilder, Streams, неуправляемое выделение памяти с использованием Intptr и Marshal в unsafe{} блоке unsafe{} и даже создание IEnumerable и yield возвращают символы по ссылке в данных позициях. Все эти попытки потерпели неудачу, поскольку какая-то форма соединения данных должна была быть выполнена, так как мне не удалось легко пересечь свой древовидный характер по характеру, не подвергая опасности работу. Если бы существовал способ охватить несколько адресов памяти в массиве сразу, как вы могли бы в C++ с некоторой арифметикой указателя.. кроме того есть.. (кредиты @Ивану Стоеву)

Решение

В решении использовалось System.ReadOnlySpan<T> (не может быть System.Span<T> из-за неизменяемости строк), который, среди прочего, позволяет нам читать вспомогательные массивы адресов памяти в существующем массиве без создания копий.

Этот фрагмент кода размещен:

string _s1 = s1.Substring(i, j);
if (stree.has(_s1))
{
    score += j - i;
    longest = j - i;
}

Был изменен следующий:

if (stree.has(i, j))
{
    score += j - i;
    longest = j - i;
}

Где stree.has() теперь принимает два целых числа (позиция и длина подстроки) и делает:

ReadOnlySpan<char> substr = s1.AsSpan(i, j);

Обратите внимание, что переменная substr буквально является ссылкой на подмножество символов исходного массива s1 а не на копию! (Переменная s1 была доступна из этой функции)

Обратите внимание, что на момент написания этого я использую С# 7.2 и.NET Framework 4.6.1, что означает, что для получения функции Span мне нужно было перейти в Project> Manage NuGet Packages, отметьте флажок "Включить предварительную проверку" и выберите "Система".Memory и установите его.

Повторный запуск начального теста (по строкам длиной 1 миллионный символ, т.е. 1 МБ), скорость увеличилась с 2+ минут (я сдался после двух минут) до ~ 86 миллисекунд!