Побайтовый поиск в бинарном файле

pattern - байты, которые надо найти. Совпадений может быть много.

        public static void DisassembleDefault(Stream streamInput,
            Action<long, long> progress, Action<long> matchFound,
            ComparerDelegate comparer, byte[] pattern, int matchOffset)
        {
            if (pattern == null || comparer == null || matchFound == null) { return; }

            int patternLength = pattern.Length;
            int bufferSize = patternLength * 100000;
            int diff = bufferSize - patternLength;
            long max = streamInput.Length - bufferSize;

            DateTime lastTime = DateTime.Now;
            for (long streamPositionByte = 0L; streamPositionByte < max; streamPositionByte += diff)
            {
                byte[] buffer = streamInput.GetChunk(streamPositionByte, bufferSize);
                if (buffer == null) { break; }

                for (int j = 0; j < diff; ++j)
                {
                    if (comparer.Invoke(buffer, pattern, j))
                    {
                        matchFound.Invoke(j + streamPositionByte - matchOffset);
                    }

                    if (progress != null)
                    {
                        TimeSpan timeSpan = DateTime.Now - lastTime;
                        if (timeSpan.TotalMilliseconds >= 100)
                        {
                            progress.Invoke(streamPositionByte, streamInput.Length);
                            lastTime = DateTime.Now;
                        }
                    }
                }
            }
        }

        public static byte[] GetChunk(this Stream stream, long pos, int len)
        {
            stream.Position = pos;
            byte[] bytes = new byte[len];
            int read = stream.Read(bytes, 0, len);
            if (read == 0)
            {
                return null;
            }
            return bytes;
        }
    }

Можно как-то ускорить сиё непотребство?

Стартовый пост не читал, но надо вот это:

Я, предсказуемо, нифига не понял :man_shrugging: Там в псевдокоде не понятны некоторые переменные.

Ты бы лучше не скоростью занялся, а корректностью. Как твой алгоритм будет искать образец, если он пересекает границу чанка?

Хотя я пригляделся, и у тебя там выделяется буфер с большиииим запасом (100000 - столько не нужно, лишний расход памяти)

Я думаю, что:

  1. длину образца надо прибавлять, а не умножать на неё;
  2. можно попробовать запустить несколько поисков параллельно (с разных позиций),
    но поможет это мало, потому что проблема не в оперативной памяти, а в скорости чтения.

Так вроде он и не сможет пересечь :thinking: Размер буфера кратен размеру искомого (для этого и умножается). А сам буфер нужен для того, чтобы не читать файл маленькими порциями. Так изначально пробовал - это ещё в разы медленнее.

Это про какую строчку?

Во всём коде только один символ “звёздочка”…

Попробуй посмотреть на Memory mapped IO, в .Net вроде библиотека для этого есть.

«The MemoryMappedFile class in the System.IO.MemoryMappedFiles namespace»

Это позволит всю работу с буферами убрать (переложить на операционную систему).

А сравнивать тогда с чем? :thinking:

Ты отображаешь весь файл на диапазон адресов. И у тебя получается единообразный доступ ко всему, потом берешь библиотеку с реализацией КМП-алгоритма (с какого-нибудь github), и скармливаешь им твой образец и где искать.

Это что значит?

Сами мы не местные…

        using (var mmf = MemoryMappedFile.CreateFromFile("path/to/file.txt", FileMode.OpenOrCreate, "myMappedFile"))
        {
            using (var view = mmf.CreateViewAccessor())
            {
                // Получение указателя на память
                byte* ptr = null;
                view.SafeMemoryMappedViewHandle.AcquirePointer(ref ptr);

                // Чтение и запись данных через указатель
                byte value = ptr[0];
                ptr[0] = 10;

                // Освобождение указателя
                view.SafeMemoryMappedViewHandle.ReleasePointer();

                // Вывод значения переменной
                Console.WriteLine(value);
            }
        }

А, понял. Он напрямую с указателями работает? Так бы и сказали :man_shrugging:

Какая тебе разница, если ты байты ищешь? Искал бы ты подстроки - можно было бы говорить о различных кодировках в файле…

Тогда не понял, в чем разница? :thinking:

Я про строки и кодировки не говорил :man_shrugging:

Ну теперь тебе надо написать три-четыре реализации, сравнить их по скорости между собой и написать о результатах. Мы за тебя это делать не будем :slight_smile:

Так вы просто объясните, для чего именно нужен MemoryMappedFile. Я уже несколько постов это вытягиваю.

Так сказано уже выше:

перевожу на русский:
Отображение файла в память — Википедия.

После MemoryMappedFile ты можешь обращаться к любому байту файла так, как будто у тебя уже весь файл уже загружен в один большой буфер в памяти.

Это явно удобнее, чем вычитывать куски файла в буфер.
Насчёт эффективности ничего не скажу.
Можешь сам замерить и нам сказать.

В википедии сказано, что просадки в скорости при записи (а не при чтении, как здесь), поэтому в этом топике от мэппинга сплошной профит. Чисто теоретически, можно было бы обойтись без замеров, расчётами. Но… это будет долго и мучительно. Надо построить модель процессора, шин, ОЗУ, диска и потом выполнить расчёты. Научные работы с такими (подобными) моделями есть в интернете. Есть два принципиально разных случая - используется HDD или используется SSD. Во втором случае нет разницы с какого места считывать, значит параллелизация будет работать по-другому. Но топикстартер скрывает, с чего он читает свои файлы.

1 лайк

Если просадки при записи, а тут только чтение, откуда тогда профит? :thinking: Не логично! :point_up:

Это ни разу не понятное определение :man_shrugging:

Вот так намного понятнее. Я так и предполагал, но нужно было уточнить, правильно ли я понял.

Только для чтения или запись тоже?

В данный момент, с HDD TOSHIBA DT01ACA300. По-идее, должен быть почти не фрагментирован. Но это не точно.
При выполнении вышеописанной процедуры, лампочка почти не мигает. Значит, он и на 30% не загружен.

HDD TOSHIBA DT01ACA300

объем = 3 ТБ (CMR), SATA III, 6 Гбит/с
Передача данных = 227 Мбайт/сек
кэш-память = 64 МБ
Скорость = 7200 об/мин
Среднее время задержки = 4.17 мс

он и на 30% не загружен

Это странно, возможно Вы ошибаетесь.

Только для чтения или запись тоже?

И на запись тоже, но для задачи это ведь не важно, поэтому вопрос не имеет смысла.

При открытии файла можно использовать один из перегруженных методов с параметром типа

там есть режим
Read 1 - Read-only access to the file.

Поэтому если очень хочется, то можно гарантировать, что записи не будет.

Не логично!

Логично. При использовании файлов, отображаемых на память, происходит меньшее количество копирований данных (чем при использовании функций чтения из рантайма языка), и при этом нет просадки производительности, так как нет записи. Просадка производительности - это плохо, хорошо, что её не будет в случае поиска.

А так же, теперь Вы знаете как можно добиться повышения производительности конкретно на вашем сетапе - купить SSD специально под задачу поиска и переписать алгоритм для работы в многопоточном режиме. Ну и ещё есть другое стандартное (традиционное) решение - купить несколько (N) штук, чтобы расширить канал чтения в N раз (организовать диски в массив RAID 0). Так же лучше использовать NVME-диски (которые подключаются по шине PCIe, которая быстрее, чем SATA-3). Я это всё перечисляю, потому что конкретно на моём компьютере в принципе можно сделать такое.

Можно как-то ускорить сиё непотребство?

Да, только аппаратно-организационными решениями можно повысить скорость примерно в N * C * K раз, где N - количество дисков, С - количество ядер процессора, K - отношение пропускной способности шины PCIe x1 4.0 по отношению к SATA III. В сумме ускорение может достигнуть

«PCIe 4.0 doubles the data transfer speed of the previous generation (PCIe 3.0) from 1GB/s per lane to 2GB/s per lane»

В моём случае можно ожидать ускорения в 4*16*7.4 = ~473 раза.

Возможно на практике меньше, если контроллер NVME-диска будет ограничивать скорость чтения. Или шина передачи данных с диска в память или память-процессор (не смотрел их параметры)

На этой строчке падает в экскепшен: System.IO.IOException: "Недостаточно ресурсов памяти для обработки этой команды."