Всем привет!

Достаточно большой файл (~1 Гб) читается блоками фиксированного размера (38 байт). Внутри файла блоки следуют друг за другом, но читаются в произвольном порядке. Каждый блок читается один и только один раз. Обработка блока в программе очень простая и занимает минимальное время.

Работа с файлом происходит напрямую через FileStream. Создание объекта выполняется так:

var stream = new FileStream(path, FileMode.Open, FileAccess.Read,
                FileShare.Read, _buffer.Length, FileOptions.RandomAccess);

Явное указание размера блока и опции FileOptions.RandomAccess существенно ускорило обработку файла.

Чтение блока происходит так:

stream.Seek(position * 38, SeekOrigin.Begin);
var _buffer = new byte[38];
var n = stream.Read(_buffer, 0, _buffer.Length);

В моём представлении, узким местом, определяющим скорость обработки, является дисковая подсистема. Результаты профилирования показывают, что основное время тратится на методы Read(72%) и Seek(20%). Но есть вещи, которые я объяснить не могу:

1. Время обработки файла практически не зависит от того, где расположен обрабатываемый файл: на SDD и HDD. В обоих случаях время одно и то же.
2. Если сделать обработку файлов в 2 потока, то время обработки уменьшается в 1,5 раза. И по прежнему не зависит от того, где он расположен (SDD или HDD).

Как можно объяснить такое поведение программы? Можно ли как-то увеличить скорость обработки не прибегая к многопоточности?

Здравствуйте, syomin, Вы писали:

S>Достаточно большой файл (~1 Гб) читается блоками фиксированного размера (38 байт). Внутри файла блоки следуют друг за другом, но читаются в произвольном порядке. Каждый блок читается один и только один раз. Обработка блока в программе очень простая и занимает минимальное время.

S>1. Время обработки файла практически не зависит от того, где расположен обрабатываемый файл: на SDD и HDD. В обоих случаях время одно и то же.
S>2. Если сделать обработку файлов в 2 потока, то время обработки уменьшается в 1,5 раза. И по прежнему не зависит от того, где он расположен (SDD или HDD).

Либо у вас файл попадает в кеш , либо обработка блока не настолько быстрая.

S>Как можно объяснить такое поведение программы? Можно ли как-то увеличить скорость обработки не прибегая к многопоточности?

Попробуйте отобразить файл на память и работать с ним "напрямую"

TK>Либо у вас файл попадает в кеш , либо обработка блока не настолько быстрая.
Да, похоже, что дело именно в этом. Дело в том, что есть ещё один проход по файлу, строго последовательный, который выполняется перед вторым проходом, который я описал в исходном сообщении. Если между проходами выполнить очистку дискового кеша, то скорость обработки сильно падает...

TK>Попробуйте отобразить файл на память и работать с ним "напрямую"
Файл может быть больше 4 Гб. Будет ли это проблемой?

Здравствуйте, syomin, Вы писали:

TK>>Либо у вас файл попадает в кеш , либо обработка блока не настолько быстрая.
S>Да, похоже, что дело именно в этом. Дело в том, что есть ещё один проход по файлу, строго последовательный, который выполняется перед вторым проходом, который я описал в исходном сообщении. Если между проходами выполнить очистку дискового кеша, то скорость обработки сильно падает...

TK>>Попробуйте отобразить файл на память и работать с ним "напрямую"
S>Файл может быть больше 4 Гб. Будет ли это проблемой?

На 32бит и с 1гб проблемы скорее всего будут. Если без "приседаний" то, надо ориентироваться на 64бит железо.

Здравствуйте, syomin, Вы писали:

S>1. Время обработки файла практически не зависит от того, где расположен обрабатываемый файл: на SDD и HDD. В обоих случаях время одно и то же.
S>Как можно объяснить такое поведение программы? Можно ли как-то увеличить скорость обработки не прибегая к многопоточности?
У вас структура файла и задачи разработана без учёта реалий IO.
Дело в том, что все современные устройства (включая SDD) — блочные. Т.е. прочитать из них 38 байт невозможно физически. При каждом чтении у вас с диска фактически читается блок минимального размера (если он не найден в кэше). Таким образом, вы гарантированно убиваете скорость чтения.
Различия при работе в один или в два потока явно связаны с различиями Cache Hit Ratio — видимо, "второй" поток успевает почаще обратиться к окрестностям недавнего чтения "первого" потока, чем помогает работе.

Поэтому структуру файлов в СУБД, к примеру, последние 20 лет дизайнят на основе страничной организации, и стараются минимизировать количество затронутых страниц при выполнении популярных операций. А 38-байтные записи были типичны для ISAM-СУБД типа dBase, и вышли из моды ещё до 1995 года.

Увеличить скорость обработки будет можно, если вы постараетесь упорядочить доступ к файлу так, чтобы максимизировать "линейные чтения". Точнее советовать трудно, не зная деталей вашего алгоритма — зачем ему обходить записи в определённом порядке, и можно ли этот порядок хотя бы частично изменить.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, syomin, Вы писали:

S>>1. Время обработки файла практически не зависит от того, где расположен обрабатываемый файл: на SDD и HDD. В обоих случаях время одно и то же.
S>>Как можно объяснить такое поведение программы? Можно ли как-то увеличить скорость обработки не прибегая к многопоточности?
S>У вас структура файла и задачи разработана без учёта реалий IO.
S>Дело в том, что все современные устройства (включая SDD) — блочные. Т.е. прочитать из них 38 байт невозможно физически. При каждом чтении у вас с диска фактически читается блок минимального размера (если он не найден в кэше). Таким образом, вы гарантированно убиваете скорость чтения.
S>Различия при работе в один или в два потока явно связаны с различиями Cache Hit Ratio — видимо, "второй" поток успевает почаще обратиться к окрестностям недавнего чтения "первого" потока, чем помогает работе.

S>Поэтому структуру файлов в СУБД, к примеру, последние 20 лет дизайнят на основе страничной организации, и стараются минимизировать количество затронутых страниц при выполнении популярных операций. А 38-байтные записи были типичны для ISAM-СУБД типа dBase, и вышли из моды ещё до 1995 года.

S>Увеличить скорость обработки будет можно, если вы постараетесь упорядочить доступ к файлу так, чтобы максимизировать "линейные чтения". Точнее советовать трудно, не зная деталей вашего алгоритма — зачем ему обходить записи в определённом порядке, и можно ли этот порядок хотя бы частично изменить.

Скажу честно, задача несколько оторвана от реальности, но мне она показалась интересной в качестве разминки для ума. Есть большой текстовый файл, в каждой строчке которого записан GUID. Файл настолько большой, что его невозможно загрузить в память целиком (даже если распарсить GUID'ы в System.Guid). Нужно вывести на экран все повторяющиеся GUID'ы, их по условию задачи очень мало.

Я решил её следующим образом. Файл обрабатывается в два прохода. При первом проходе из файла последовательно считываются все GUID'ы и для каждого из них считается хеш. В зависимости от значения хеш-суммы, GUID'ы распределяеются по "корзинам" — в одну корзину попадают GUID'ы с одинаковыми значениями хеша. В корзине сохраняется не сам GUID, а его порядковый номер в файле.

При втором проходе файл обрабатывается "покорзинно". Все GUID'ы, входящие в корзину, заново загружаются из файла в HashSet для поиска дубликатов.

Здравствуйте, syomin, Вы писали:

S>Я решил её следующим образом. Файл обрабатывается в два прохода. При первом проходе из файла последовательно считываются все GUID'ы и для каждого из них считается хеш. В зависимости от значения хеш-суммы, GUID'ы распределяеются по "корзинам" — в одну корзину попадают GUID'ы с одинаковыми значениями хеша. В корзине сохраняется не сам GUID, а его порядковый номер в файле.

S>При втором проходе файл обрабатывается "покорзинно". Все GUID'ы, входящие в корзину, заново загружаются из файла в HashSet для поиска дубликатов.

Я бы в памяти просто строил дерево на каждом guid (один символ — один уровень дерева). С каждым следующим гуидом дерево достраивается, если соответствующая ветка уже есть на нижнем уровне, то гуид имеет смысл вывести на экран. Проход по файлу будет один, по идее. А по поводухешей для гуидов — если считаете интами, возможны коллизии

Здравствуйте, syomin, Вы писали:

S>Скажу честно, задача несколько оторвана от реальности, но мне она показалась интересной в качестве разминки для ума. Есть большой текстовый файл, в каждой строчке которого записан GUID. Файл настолько большой, что его невозможно загрузить в память целиком (даже если распарсить GUID'ы в System.Guid). Нужно вывести на экран все повторяющиеся GUID'ы, их по условию задачи очень мало.


S>Я решил её следующим образом. Файл обрабатывается в два прохода. При первом проходе из файла последовательно считываются все GUID'ы и для каждого из них считается хеш. В зависимости от значения хеш-суммы, GUID'ы распределяеются по "корзинам" — в одну корзину попадают GUID'ы с одинаковыми значениями хеша. В корзине сохраняется не сам GUID, а его порядковый номер в файле.

Хм. А это счастье влазит в память??? Ну потому если почти все гуиды разные, и функция хеширования — хорошая, то корзин получается примерно столько же сколько гуидов.

Здравствуйте, Codechanger, Вы писали:

C>Я бы в памяти просто строил дерево на каждом guid (один символ — один уровень дерева). С каждым следующим гуидом дерево достраивается, если соответствующая ветка уже есть на нижнем уровне, то гуид имеет смысл вывести на экран. Проход по файлу будет один, по идее. А по поводухешей для гуидов — если считаете интами, возможны коллизии

ты предлагаешь по сути загрузить все гуиды в TreeSet. По условию задачи на это не хватит памяти.

Здравствуйте, Jack128, Вы писали:

J>Здравствуйте, Codechanger, Вы писали:

C>>Я бы в памяти просто строил дерево на каждом guid (один символ — один уровень дерева). С каждым следующим гуидом дерево достраивается, если соответствующая ветка уже есть на нижнем уровне, то гуид имеет смысл вывести на экран. Проход по файлу будет один, по идее. А по поводухешей для гуидов — если считаете интами, возможны коллизии

J>ты предлагаешь по сути загрузить все гуиды в TreeSet. По условию задачи на это не хватит памяти.

Всегда есть внешняя память в виде жесткого диска. Немного поясню мысль про дерево. Guid у нас состоит из 36 символов, соответственно, в дереве будет максимально 36 уровней. Новые ветки будут добавляться только в случае, если такого пути не существует.Отсюда вытекает другая интересная задачка- Каков максимальный объем гуидов, которые полностью не совпадают с друг другом по путям? Подозреваю, что тоже в оперативную память может не влезть

J>Хм. А это счастье влазит в память??? Ну потому если почти все гуиды разные, и функция хеширования — хорошая, то корзин получается примерно столько же сколько гуидов.

Основная идея в том, чтобы разбить GUID'ы на группы (корзины), которые влезут в память. Сейчас используется хеш-функция, возвращая 2 байта.

Здравствуйте, syomin, Вы писали:

S>Скажу честно, задача несколько оторвана от реальности, но мне она показалась интересной в качестве разминки для ума. Есть большой текстовый файл, в каждой строчке которого записан GUID. Файл настолько большой, что его невозможно загрузить в память целиком (даже если распарсить GUID'ы в System.Guid). Нужно вывести на экран все повторяющиеся GUID'ы, их по условию задачи очень мало.

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

Здравствуйте, syomin, Вы писали:



S>Как можно объяснить такое поведение программы? Можно ли как-то увеличить скорость обработки не прибегая к многопоточности?

Система кэширует файл особенно часто используемые страницы. 1GB может спокойно поместиться в память.

Здравствуйте, syomin, Вы писали:

S>Я решил её следующим образом. Файл обрабатывается в два прохода. При первом проходе из файла последовательно считываются все GUID'ы и для каждого из них считается хеш. В зависимости от значения хеш-суммы, GUID'ы распределяеются по "корзинам" — в одну корзину попадают GUID'ы с одинаковыми значениями хеша. В корзине сохраняется не сам GUID, а его порядковый номер в файле.

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

Здравствуйте, syomin, Вы писали:

S>1. Время обработки файла практически не зависит от того, где расположен обрабатываемый файл: на SDD и HDD. В обоих случаях время одно и то же.

во-первых, файл после первой же обработки кешируется и лежит в озу. так что считай, у тебя filestream читает данные из гигабайтного буфера в озу

S>2. Если сделать обработку файлов в 2 потока, то время обработки уменьшается в 1,5 раза. И по прежнему не зависит от того, где он расположен (SDD или HDD).

вся обработка сводится к тому чтобы скопировать 38 байт в памяти, выполнить какие-то операции над ними и повторить снова. поэтому чем больше потоков cpu ты используешь, тем быстрее это будет

замечу что даже при работе с озу последовательный доступ куда быстрее случайного. наиболее быстрое решение твоей задачи имхо состоит в том чтобы в первом проходе разбить файл на N частей по диапазону GUID, а затем обработать каждую часть в памяти, отсортировав её. так ты избежишь произвольного доступа к ОЗУ

алтернативный вариант — разбить файл на N частей, отсортировать их и записать на диск, затем выполнить N-путёвое слияние

Здравствуйте, syomin, Вы писали:

S>Скажу честно, задача несколько оторвана от реальности, но мне она показалась интересной в качестве разминки для ума. Есть большой текстовый файл, в каждой строчке которого записан GUID. Файл настолько большой, что его невозможно загрузить в память целиком (даже если распарсить GUID'ы в System.Guid). Нужно вывести на экран все повторяющиеся GUID'ы, их по условию задачи очень мало.
Можно ли модифицировать исходный файл? Можно ли создавать временные файлы?
Без модификации файла быстрее будет модифицировать вашу идею следующим образом: выполнять повторные чтения — множество проходов, увеличивая глубину сканирования "хеша" (в GUID данные уже хорошо перемешаны, поэтому префикс даёт вполне приличный хеш)

Т.е. на первом проходе берём K1 первых бит от каждого GUID; подсчитываем количество GUID, которые начинаются с каждого из этих префиксов.
После окончания сканирования можно выбросить все "неудачные" префиксы — те, с которых начинается 0 или 1 GUID.
На последующем проходе мы просматриваем ещё K2 бит тех GUID, которые начинаются с одного из кандидатных префиксов. И так, пока K1+...+KN не станет = 128.
K1, K2, KN можно выбирать, исходя из ограничения по памяти — нам надо сделать так, чтобы хватило на все счётчики.
На счётчик мы тратим 2 бита (нам, в сущности, неважно, сколько у кандидата есть продолжений, если их больше 1), размер массива = 2 * 2^Ki бит.
Если у нас есть M бит памяти, то вычисляем K1 как log2(M)-1.
На следующем этапе нам нужно хранить список кандидатов размером в N1 — количество найденных на первом шаге префиксов с >1 продолжений.

Для каждого кандидата нам нужнеа такая же структура — K2 двухбитных счётчиков, так что вычисляем K2 = log2(M')-1-log2(N1).
M' — это M, поправленное на доп.расходы по хранению K1 префиксов с указателями на таблицы продолжений.
После окончания второго прохода у нас остаётся N2 (K1+K2)-битных префиксов.
И так продолжаем, пока не окучим весь файл.
Для реалистичных оценок: если M у нас = 1GB, т.е. 2^33 бит, то K1 = 32, начинаем просматривать по 4 байта сразу.
А дальше — как пойдёт: если будет найден 1 кандидат, то следующий просмотр подхватит ещё 4 байта; а если 2 — то будем просматривать по 31 биту.

Для этого алгоритма есть патологический случай, в котором он будет делать много проходов или вообще упадёт с нехваткой памяти. Но вне его он должен работать приемлемо

Здравствуйте, Codechanger, Вы писали:

C> Отсюда вытекает другая интересная задачка — каков максимальный объем гуидов, которые полностью не совпадают с друг другом по путям? Подозреваю, что тоже в оперативную память может не влезть

В оперативную?!? Подозреваете?
Очевидно это будет 16 деревьев с глубиной 36. 16³⁶ = 2¹⁴⁴. Если что, йоттабайт — это 2⁸⁰.

ЗЫ. Кстати, цифр там 32, откуда 36-то? Но это сути не меняет.

P>ЗЫ. Кстати, цифр там 32, откуда 36-то? Но это сути не меняет.
Дефисы, символ перевода строки, символ возврата каретки.

Здравствуйте, syomin, Вы писали:

S>Дефисы, символ перевода строки, символ возврата каретки.

Речь была о деревьях в памяти. Значимых цифр в гуиде 32.

Здравствуйте, pugv, Вы писали:

P>ЗЫ. Кстати, цифр там 32, откуда 36-то? Но это сути не меняет.

GUID — это ровно 16 байт, зачем их литералами хранить?