Ботлнек String/StringBuilder

string source = File.ReadAllText(@"d:\work\words\source.txt", Encoding.GetEncoding(1251));
var sb_source = new StringBuilder(source, Source.Length);
Dictionary<string, int> F = new Dictionary<string, int>();
// ---
// тут вставляем код заполнения F, у меня получается около 70000 пар
// заполнение происходит очень быстро
// ---
foreach (var elem in F)
{
    // а вот тут был string и работало это, как мы все понимаем 200 лет
    // теперь тут StringBuilder, работает быстрее, но не слишком
    // можно сделать Parallels.ForEach, для моего i5 ускорится в ~4 раза
    sb_source = sb_source.Replace(elem.Key, "\0\0\0");
};

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
 
namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
            //Читаем имя файла
            var fileName = Console.ReadLine();
 
            //Читаем текст
            var text = File.ReadAllBytes(fileName.Trim('\"'));
 
            //Максимальное число разных значений, которое может принять байт
            int maxDifferentByteCount = 256;
            //Например, если у нас только строчные латинские буквы + пробел, то
            //Это будет не 256, а 23
 
            //Словари, у которых ключ - это строка
            //Любят постоянно считать хэши строк. Не всегда, но любят.
            //Для того, чтобы ускорить всё, сделаем пару штук:
            //1) Хэш считаем самостоятельно
            //2) Для расчёта хэша не создаем новые строки - работаем напрямую с памятью
            //3) При ключе long хэш всё равно будет досчитываться, но для long он уже довольно быстрый
 
            //Короче, алгоритм хранит не частоту подстрок
            //а частоту хэшей этих подстрок
            var frequencyDicitonary = new Dictionary<int, hashInfo>();
 
 
            var st = new Stopwatch();
            st.Reset();
            st.Start();
            //Заполняем словари
            FillFrequences(text, 1, 8, frequencyDicitonary, maxDifferentByteCount);
            st.Stop();
 
            //Находим самый частый хэш
            var maxFqKeyValue = FindMax(frequencyDicitonary, a => a.Value.RepeatCount);
            var maxFqHash = maxFqKeyValue.Key;
 
 
            //Выводим
            var foundBytes = text[maxFqKeyValue.Value.StartPosition..maxFqKeyValue.Value.EndPosition];
            var foundBytesText = foundBytes.Length + " байт: " + string.Join(", ", foundBytes.ToList().ConvertAll(a => a.ToString()));
 
            Console.WriteLine($"{maxFqKeyValue.Value.RepeatCount} повторений фрагмента {foundBytesText}");
            Console.WriteLine($"Обработка длилась {st.ElapsedMilliseconds} мс");
            Console.ReadLine();
        }
        static T FindMax<T>(IEnumerable<T> collection, Func<T, int> num)
        {
            var n = int.MinValue;
            T lastResult = default(T);
            foreach (var item in collection)
            {
                var newN = num(item);
                if (newN > n)
                {
                    newN = n;
                    lastResult = item;
                }
            }
            return lastResult;
        }
        static long[] power31Table; //Табличка степеней 31, интерпретированных как long
 
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static unsafe int FastHash(void* begin, int byteCount, long* power31Ptr)
        {
            //Быстрый хэш, не требующий создания новой подстроки. Работает на фрагменте памяти
            long hashedValue = 0;
            unchecked
            {
                //Считаем сразу по 4 символа за раз, интерпретируя их как long
                var longCount = byteCount / sizeof(long);
                var tail = byteCount % sizeof(long);
                long* ptr = (long*)begin;
                long* end = ptr + longCount;
                //hashedValue += (long)byteCount * *power31Ptr++;
                //i++;
 
                while (ptr < end)
                {
                    hashedValue += *ptr * *power31Ptr++;
                    ptr++;
                }
 
 
                //Досчитываем хвостик
                byte* tailEnd = (byte*)begin + byteCount;
                byte* tailPtr = tailEnd - tail;
                while (tailPtr < tailEnd)
                {
                    hashedValue += *tailPtr * *power31Ptr++;
                    tailPtr++;
                }
            }
            return (int)hashedValue ^ (int)(hashedValue >> 32);
        }
        //Заполнение таблицы степеней
        static void BuildPower31TableIfNeed(int maxByteCount)
        {
            //Число итераций хэш функции
            var maxHashIterationCount = maxByteCount / sizeof(long) + maxByteCount % sizeof(long) + 1;
 
            //Если таблица ещё не создана или она меньше, чем нам надо
            if (power31Table == null || power31Table.Length < maxHashIterationCount)
            {
                //Создаём новый экземпляр таблицы в отдельной переменной
                var newPower31Table = new long[maxHashIterationCount * 2];
                unsafe
                {
                    //заполняем
                    for (int i = 0; i < newPower31Table.Length; i++)
                    {
                        var v = Math.Pow(31, i);
                        newPower31Table[i] = *(long*)&v;
                    }
                }
                //и только потом приравниваем статическую переменную к нашей новой таблице
                power31Table = newPower31Table;
                //это делает данный метод потокобезопасным без блокировок
                //максимум, что может случится - лишний раз просчитается таблица
            }
        }
 
 
        class hashInfo
        {
            public int StartPosition;
            public int Length;
            public int EndPosition => StartPosition + Length - 1;
            public int RepeatCount;
 
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public unsafe void SnapshotAndIncrement(byte* dataBegin, byte* fragmentBegin, int byteCount)
            {
                StartPosition = (int)(fragmentBegin - dataBegin);
                Length = byteCount;
                RepeatCount++;
            }
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public void Increment()
            {
                RepeatCount++;
            }
        }
 
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static unsafe void AddOrIncHash(Dictionary<int, hashInfo> outputDictionary, int hash, byte* dataBegin, byte* fragmentBegin, int byteCount)
        {
            if (outputDictionary.TryGetValue(hash, out var hi))
                hi.Increment();
            else
            {
                hi = new hashInfo();
                hi.SnapshotAndIncrement(dataBegin, fragmentBegin, byteCount);
            }
        }
 
        static void FillFrequences(byte[] text, int minLength, int maxLength, Dictionary<int, hashInfo> outputDictionary, int maxDifferentByteCount = 256)
        {
            BuildPower31TableIfNeed(maxLength * sizeof(byte));
            outputDictionary.Clear();
            int[] hashCounts = new int[256 * 256 * 256];
            unsafe
            {
                //Получаем прямой доступ к памяти
                fixed (byte* textPtrBegin = text)
                {
                    if (minLength <= 1)
                    {
                        core1(text, outputDictionary, textPtrBegin, maxDifferentByteCount);
                        Console.WriteLine("Длина 1 байт обработана");
                        minLength++;
                    }
                    if (minLength <= 2 && maxLength >= 2)
                    {
                        core2(text, outputDictionary, textPtrBegin, maxDifferentByteCount);
                        Console.WriteLine("Длина 2 байт обработана");
                        minLength++;
                    }
                    if (minLength <= 3 && maxLength >= 3)
                    {
                        core3(text, outputDictionary, textPtrBegin, hashCounts, maxDifferentByteCount);
                        Console.WriteLine("Длина 3 байт обработана");
                        minLength++;
                    }
                    if (minLength <= 4 && maxLength >= 4)
                    {
                        core4(text, outputDictionary, textPtrBegin);
                        Console.WriteLine("Длина 4 байт обработана");
                        minLength++;
                    }
                    for (int n = 5; n <= 7; n++)
                        if (minLength <= n && maxLength >= n)
                        {
                            core567(text, outputDictionary, textPtrBegin, n);
                            Console.WriteLine($"Длина {n} байт обработана");
                            minLength++;
                        }
                    //Внешний цикл - перебор всех искомых длинн
                    for (int len = minLength; len <= maxLength; len++)
                    {
                        coreUniversal(text, outputDictionary, textPtrBegin, len);
                        Console.WriteLine($"Длина {len} байт обработана");
                    }
                }
            }
        }
        private static unsafe void core1(byte[] text, Dictionary<int, hashInfo> outputDictionary, byte* textPtrBegin, int maxDifferentByteCount)
        {
            var len = 1;
            byte* begin = textPtrBegin;
            byte* end = begin + text.Length - len + 1;
            byte* ptr = begin;
            int msk = 0b1010011110010001001110001001010;
 
            var byteCount = len;
            for (int i = 0; i < 256; i++)
            {
                outputDictionary[i ^ msk] = new hashInfo();
            }
            int* countOf = stackalloc int[256];
            int strSetCount = 0;
            //Внутренний цикл использует арифметику указателей
            //чтобы быть быстрым
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                var index = *ptr;// FastHash(ptr, byteCount);
                //Увеличиваем счетчик
                countOf[index]++;
 
                if (countOf[index] == 1)
                {
                    var hash = index ^ msk;
                    //Запоминаем строку чтобы восстановить из хэша
                    var item = outputDictionary[hash];
                    item.SnapshotAndIncrement(begin, ptr, len);
                    strSetCount++;
                    if (strSetCount >= maxDifferentByteCount)
                        break;
                }
 
                //Следующий символ
                ptr++;
            }
 
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                var index = *ptr;// FastHash(ptr, byteCount);
 
                //Увеличиваем счетчик
                countOf[index]++;
                //Следующий символ
                ptr++;
            }
            for (int i = 0; i < 256; i++)
                outputDictionary[i ^ msk].RepeatCount = countOf[i];
        }
        private static unsafe void core2(byte[] text, Dictionary<int, hashInfo> outputDictionary, byte* textPtrBegin, int maxDifferentByteCount)
        {
            var len = 2;
            byte* begin = textPtrBegin;
            byte* end = begin + text.Length - len + 1;
            byte* ptr = begin;
 
            var byteCount = len;
            for (int i = ushort.MinValue; i <= ushort.MaxValue; i++)
            {
                if (i < 256)
                    outputDictionary[~i] = new hashInfo();
                else
                    outputDictionary[i] = new hashInfo();
            }
 
            int* countOf = stackalloc int[ushort.MaxValue + 1];
            int maxDifPow2 = maxDifferentByteCount * maxDifferentByteCount;
 
            int strSetCount = 0;
            //Внутренний цикл использует арифметику указателей
            //чтобы быть быстрым
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                int index = *(ushort*)ptr;// FastHash(ptr, byteCount);
 
                //Увеличиваем счетчик
                countOf[index]++;
                if (countOf[index] == 1)
                {
                    int hash = index;
                    if (hash < 256)
                        hash = ~hash;
 
                    //Запоминаем строку чтобы восстановить из хэша
                    //AddHashString(hash, begin, ptr, len, stringByHashDictionary);
                    outputDictionary[hash].SnapshotAndIncrement(begin, ptr, len);
 
                    //strSet[hash] = true;
                    strSetCount++;
                    if (strSetCount >= maxDifPow2)
                        break;
                }
                //Следующий символ
                ptr++;
            }
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                int index = *(ushort*)ptr;// FastHash(ptr, byteCount);
 
                //Увеличиваем счетчик
                countOf[index]++;
 
                //Следующий символ
                ptr++;
            }
            for (int i = ushort.MinValue; i <= ushort.MaxValue; i++)
            {
                int hash = i;
                if (hash < 256)
                    hash = ~hash;
                outputDictionary[hash].RepeatCount = countOf[i];
            }
        }
        private static unsafe void core3(byte[] text, Dictionary<int, hashInfo> outputDictionary, byte* textPtrBegin, int[] hashCounts, int maxDifferentByteCount)
        {
            var len = 3;
            byte* begin = textPtrBegin;
            byte* end = begin + text.Length - len + 1;
            byte* ptr = begin;
 
            var byteCount = len;
 
            int setCount = 0;
            Array.Clear(hashCounts, 0, hashCounts.Length);
            int maxSetCount = maxDifferentByteCount * maxDifferentByteCount * maxDifferentByteCount;
 
            uint maxIndex = 0;
 
            //Внутренний цикл использует арифметику указателей
            //чтобы быть быстрым
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                var index = (uint)*(ushort*)ptr;
                index *= 256;
                index += *(ptr + 2);
 
 
                hashCounts[index]++;
 
                if (hashCounts[index] == 1)
                {
                    var hash = (int)index;
                    if (hash <= ushort.MaxValue)
                        hash = ~hash;
 
                    maxIndex = Math.Max(maxIndex, index);
                    hashCounts[index]++;
                    //Запоминаем строку чтобы восстановить из хэша
                    //AddHashString((int)hash, begin, ptr, len, stringByHashDictionary);
                    var hi = new hashInfo();
                    hi.SnapshotAndIncrement(begin, ptr, len);
                    outputDictionary[hash] = hi;
                    setCount++;
                    if (setCount >= maxSetCount)
                        break;
                }
 
                //Следующий символ
                ptr++;
            }
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                var index = (uint)*(ushort*)ptr;
                index *= 256;
                index += *(ptr + 2);
                hashCounts[index]++;
                //Следующий символ
                ptr++;
            }
            if (maxIndex > int.MaxValue)
                maxIndex = int.MaxValue;
 
            for (int i = 0; i < maxIndex; i++)
            {
                var hashCount = hashCounts[i];
                if (hashCount > 0)
                {
                    var hash = i;
                    if (hash <= ushort.MaxValue)
                        hash = ~hash;
 
                    outputDictionary[hash].RepeatCount = hashCount;
                }
            }
        }
 
        private static unsafe void core4(byte[] text, Dictionary<int, hashInfo> outputDictionary, byte* textPtrBegin)
        {
            var len = 4;
            byte* begin = textPtrBegin;
            byte* end = begin + text.Length - len + 1;
            byte* ptr = begin;
 
            var byteCount = len;
            var hashDictionary = new HashSet<int>();
            int invertThreshold = short.MaxValue;
            invertThreshold *= 256;
            invertThreshold--;
 
            //Внутренний цикл использует арифметику указателей
            //чтобы быть быстрым
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                var hash = *(int*)ptr;// FastHash(ptr, byteCount);
                if (hash <= invertThreshold)
                    hash = ~hash;
 
                AddOrIncHash(outputDictionary, hash, begin, ptr, len);
 
                //Следующий символ
                ptr++;
            }
        }
 
        private static unsafe void core567(byte[] text, Dictionary<int, hashInfo> outputDictionary, byte* textPtrBegin, int len)
        {
            //ВАЖНО! Этот метод не обрабатывает для 5 байтовых фрагментов - 3 последних, для 6 байтовых - 2 последних, для 7 байтовых - 1 последний
            byte* begin = textPtrBegin;
            byte* end = begin + text.Length - 8 + 1;
            byte* ptr = begin;
 
            var byteCount = len;
            var hashDictionary = new HashSet<int>();
 
            long mask = 0;
            if (len == 7) mask = 0b00000000_11111111_11111111_11111111_11111111_11111111_11111111_11111111;
            else if (len == 6) mask = 0b00000000_00000000_11111111_11111111_11111111_11111111_11111111_11111111;
            else if (len == 5) mask = 0b00000000_00000000_00000000_11111111_11111111_11111111_11111111_11111111;
            //Внутренний цикл использует арифметику указателей
            //чтобы быть быстрым
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                var hashLong = *(long*)ptr;// FastHash(ptr, byteCount);
                hashLong &= mask;
 
                var hash = (unchecked((int)((long)hashLong)) ^ (int)(hashLong >> 32));
 
                AddOrIncHash(outputDictionary, hash, begin, ptr, len);
                
 
                //Следующий символ
                ptr++;
            }
 
        }
 
        private static unsafe void core8(byte[] text, Dictionary<int, hashInfo> outputDictionary, byte* textPtrBegin)
        {
            var len = 8;
            byte* begin = textPtrBegin;
            byte* end = begin + text.Length - len + 1;
            byte* ptr = begin;
 
            var byteCount = len;
            var hashDictionary = new HashSet<int>();
            //Внутренний цикл использует арифметику указателей
            //чтобы быть быстрым
            while (ptr < end)
            {
                //Считаем хэш фрагмента памяти
                var hashLong = *(long*)ptr;// FastHash(ptr, byteCount);
                var hash = (unchecked((int)((long)hashLong)) ^ (int)(hashLong >> 32));
 
                AddOrIncHash(outputDictionary, hash, begin, ptr, len);
 
                //Следующий символ
                ptr++;
            }
        }
 
 
        private static unsafe void coreUniversal(byte[] text, Dictionary<int, hashInfo> outputDictionary, byte* textPtrBegin, int len)
        {
            byte* begin = textPtrBegin;
            byte* end = begin + text.Length - len + 1;
            byte* ptr = begin;
 
            var byteCount = len;
 
            fixed (long* power31ptr = power31Table)
            {
                //Внутренний цикл использует арифметику указателей
                //чтобы быть быстрым
                while (ptr < end)
                {
                    //Считаем хэш фрагмента памяти
                    var hash = FastHash(ptr, byteCount, power31ptr);
 
                    AddOrIncHash(outputDictionary, hash, begin, ptr, len);
 
                    //Следующий символ
                    ptr++;
                }
            }
        }
    }
}