Здравствуйте, syomin, Вы писали:
S>1. Время обработки файла практически не зависит от того, где расположен обрабатываемый файл: на SDD и HDD. В обоих случаях время одно и то же. S>Как можно объяснить такое поведение программы? Можно ли как-то увеличить скорость обработки не прибегая к многопоточности?
У вас структура файла и задачи разработана без учёта реалий IO.
Дело в том, что все современные устройства (включая SDD) — блочные. Т.е. прочитать из них 38 байт невозможно физически. При каждом чтении у вас с диска фактически читается блок минимального размера (если он не найден в кэше). Таким образом, вы гарантированно убиваете скорость чтения.
Различия при работе в один или в два потока явно связаны с различиями Cache Hit Ratio — видимо, "второй" поток успевает почаще обратиться к окрестностям недавнего чтения "первого" потока, чем помогает работе.
Поэтому структуру файлов в СУБД, к примеру, последние 20 лет дизайнят на основе страничной организации, и стараются минимизировать количество затронутых страниц при выполнении популярных операций. А 38-байтные записи были типичны для ISAM-СУБД типа dBase, и вышли из моды ещё до 1995 года.
Увеличить скорость обработки будет можно, если вы постараетесь упорядочить доступ к файлу так, чтобы максимизировать "линейные чтения". Точнее советовать трудно, не зная деталей вашего алгоритма — зачем ему обходить записи в определённом порядке, и можно ли этот порядок хотя бы частично изменить.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Tom, Вы писали:
VC>>mmf всегда был на 2 порядка и больше быстрее filestream Tom>пруф в студию
для чистоты эксперимента сначала обсудим требования:
1. перфоманс стресс должен сравнить производительность mmf и filestream доступа к файлу размером 1 гиг.
2. свободной памяти при стрессе должно быть достаточно что бы закешировать (без использования буффередстрим) 1 гиг в памяти перед стрессом с помощбю файлстрима. свободной памяти должно быть достаточно что бы отобразить в озу 1 гиг с помощью ммф одним куском без использования свопа.
3. стресс должен выполнять рандом рид по 1/4/8/38 байт.
4. стресс должен выполнять пункт 3 в 1/2/4 потока.
Здравствуйте, syomin, Вы писали:
S>1. Время обработки файла практически не зависит от того, где расположен обрабатываемый файл: на SDD и HDD. В обоих случаях время одно и то же.
во-первых, файл после первой же обработки кешируется и лежит в озу. так что считай, у тебя filestream читает данные из гигабайтного буфера в озу
S>2. Если сделать обработку файлов в 2 потока, то время обработки уменьшается в 1,5 раза. И по прежнему не зависит от того, где он расположен (SDD или HDD).
вся обработка сводится к тому чтобы скопировать 38 байт в памяти, выполнить какие-то операции над ними и повторить снова. поэтому чем больше потоков cpu ты используешь, тем быстрее это будет
замечу что даже при работе с озу последовательный доступ куда быстрее случайного. наиболее быстрое решение твоей задачи имхо состоит в том чтобы в первом проходе разбить файл на N частей по диапазону GUID, а затем обработать каждую часть в памяти, отсортировав её. так ты избежишь произвольного доступа к ОЗУ
алтернативный вариант — разбить файл на N частей, отсортировать их и записать на диск, затем выполнить N-путёвое слияние
Здравствуйте, syomin, Вы писали:
S>Я решил её следующим образом. Файл обрабатывается в два прохода. При первом проходе из файла последовательно считываются все GUID'ы и для каждого из них считается хеш. В зависимости от значения хеш-суммы, GUID'ы распределяеются по "корзинам" — в одну корзину попадают GUID'ы с одинаковыми значениями хеша. В корзине сохраняется не сам GUID, а его порядковый номер в файле.
S>При втором проходе файл обрабатывается "покорзинно". Все GUID'ы, входящие в корзину, заново загружаются из файла в HashSet для поиска дубликатов.
Я бы в памяти просто строил дерево на каждом guid (один символ — один уровень дерева). С каждым следующим гуидом дерево достраивается, если соответствующая ветка уже есть на нижнем уровне, то гуид имеет смысл вывести на экран. Проход по файлу будет один, по идее. А по поводухешей для гуидов — если считаете интами, возможны коллизии
Здравствуйте, 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 биту.
Для этого алгоритма есть патологический случай, в котором он будет делать много проходов или вообще упадёт с нехваткой памяти. Но вне его он должен работать приемлемо
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, 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'ы в System.Guid). Нужно вывести на экран все повторяющиеся GUID'ы, их по условию задачи очень мало.
S>Я решил её следующим образом. Файл обрабатывается в два прохода. При первом проходе из файла последовательно считываются все GUID'ы и для каждого из них считается хеш. В зависимости от значения хеш-суммы, GUID'ы распределяеются по "корзинам" — в одну корзину попадают GUID'ы с одинаковыми значениями хеша. В корзине сохраняется не сам GUID, а его порядковый номер в файле.
Хм. А это счастье влазит в память??? Ну потому если почти все гуиды разные, и функция хеширования — хорошая, то корзин получается примерно столько же сколько гуидов.
Здравствуйте, syomin, Вы писали:
S>Скажу честно, задача несколько оторвана от реальности, но мне она показалась интересной в качестве разминки для ума. Есть большой текстовый файл, в каждой строчке которого записан GUID. Файл настолько большой, что его невозможно загрузить в память целиком (даже если распарсить GUID'ы в System.Guid). Нужно вывести на экран все повторяющиеся GUID'ы, их по условию задачи очень мало.
Достаточно большой файл (~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бит железо.
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Здравствуйте, Codechanger, Вы писали:
C>Я бы в памяти просто строил дерево на каждом guid (один символ — один уровень дерева). С каждым следующим гуидом дерево достраивается, если соответствующая ветка уже есть на нижнем уровне, то гуид имеет смысл вывести на экран. Проход по файлу будет один, по идее. А по поводухешей для гуидов — если считаете интами, возможны коллизии
ты предлагаешь по сути загрузить все гуиды в TreeSet. По условию задачи на это не хватит памяти.
Здравствуйте, Jack128, Вы писали:
J>Здравствуйте, Codechanger, Вы писали:
C>>Я бы в памяти просто строил дерево на каждом guid (один символ — один уровень дерева). С каждым следующим гуидом дерево достраивается, если соответствующая ветка уже есть на нижнем уровне, то гуид имеет смысл вывести на экран. Проход по файлу будет один, по идее. А по поводухешей для гуидов — если считаете интами, возможны коллизии
J>ты предлагаешь по сути загрузить все гуиды в TreeSet. По условию задачи на это не хватит памяти.
Всегда есть внешняя память в виде жесткого диска. Немного поясню мысль про дерево. Guid у нас состоит из 36 символов, соответственно, в дереве будет максимально 36 уровней. Новые ветки будут добавляться только в случае, если такого пути не существует.Отсюда вытекает другая интересная задачка- Каков максимальный объем гуидов, которые полностью не совпадают с друг другом по путям? Подозреваю, что тоже в оперативную память может не влезть
J>Хм. А это счастье влазит в память??? Ну потому если почти все гуиды разные, и функция хеширования — хорошая, то корзин получается примерно столько же сколько гуидов.
Основная идея в том, чтобы разбить GUID'ы на группы (корзины), которые влезут в память. Сейчас используется хеш-функция, возвращая 2 байта.
Здравствуйте, syomin, Вы писали:
S>Я решил её следующим образом. Файл обрабатывается в два прохода. При первом проходе из файла последовательно считываются все GUID'ы и для каждого из них считается хеш. В зависимости от значения хеш-суммы, GUID'ы распределяеются по "корзинам" — в одну корзину попадают GUID'ы с одинаковыми значениями хеша. В корзине сохраняется не сам GUID, а его порядковый номер в файле.
Подозреваю, 64 последовательных чтения файла будут работать быстрее одного в случайном порядке.
Т.е. можно вычислять 6-битные хэши при чтении и на каждой итерации брать guid-ы для одного значения хэша.
В зависимости от размера файла и свобной памяти можно подбирать оптимальную битность хэша (в предположение его равномерной распределенности).
Здравствуйте, Codechanger, Вы писали:
C> Отсюда вытекает другая интересная задачка — каков максимальный объем гуидов, которые полностью не совпадают с друг другом по путям? Подозреваю, что тоже в оперативную память может не влезть
В оперативную?!? Подозреваете?
Очевидно это будет 16 деревьев с глубиной 36. 1636 = 2144. Если что, йоттабайт — это 280.
ЗЫ. Кстати, цифр там 32, откуда 36-то? Но это сути не меняет.
S>Я решил её следующим образом. Файл обрабатывается в два прохода. При первом проходе из файла последовательно считываются все GUID'ы и для каждого из них считается хеш. В зависимости от значения хеш-суммы, GUID'ы распределяеются по "корзинам" — в одну корзину попадают GUID'ы с одинаковыми значениями хеша. В корзине сохраняется не сам GUID, а его порядковый номер в файле.
S>При втором проходе файл обрабатывается "покорзинно". Все GUID'ы, входящие в корзину, заново загружаются из файла в HashSet для поиска дубликатов.
Сделай Индексы по типу B+ деревьев.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, syomin, Вы писали:
S>Всем привет!
S>Достаточно большой файл (~1 Гб) читается блоками фиксированного размера (38 байт). Внутри файла блоки следуют друг за другом, но читаются в произвольном порядке. Каждый блок читается один и только один раз. Обработка блока в программе очень простая и занимает минимальное время.
S>Работа с файлом происходит напрямую через FileStream. Создание объекта выполняется так: S>
S>Явное указание размера блока и опции FileOptions.RandomAccess существенно ускорило обработку файла.
S>Чтение блока происходит так: S>
S>stream.Seek(position * 38, SeekOrigin.Begin);
S>var _buffer = new byte[38];
S>var n = stream.Read(_buffer, 0, _buffer.Length);
S>
S>В моём представлении, узким местом, определяющим скорость обработки, является дисковая подсистема. Результаты профилирования показывают, что основное время тратится на методы Read(72%) и Seek(20%). Но есть вещи, которые я объяснить не могу:
S>1. Время обработки файла практически не зависит от того, где расположен обрабатываемый файл: на SDD и HDD. В обоих случаях время одно и то же. S>2. Если сделать обработку файлов в 2 потока, то время обработки уменьшается в 1,5 раза. И по прежнему не зависит от того, где он расположен (SDD или HDD).
S>Как можно объяснить такое поведение программы? Можно ли как-то увеличить скорость обработки не прибегая к многопоточности?
1. Результаты теста у вас некорректные ибо как уже сказали файл кешируется.
2. Последовательное чтение на порядок быстрее чем рандомный доступ.
3. Seek это зло
4. Лучше всего читать файл последовательно в одном потоке блоками, а вот потом распределять прочитанные блоки по потокам для обработки.
Возможно это даже будет быстрее мапинга файл в памяти ибо вы раньше начнёте обработку ещё до того как файл будет полностью прочитан.
В целом читать весь файл в память можно конечно но лучше что бы это сделала сама OS а не вы, ибо если вы явно это будете делать то это может быть более медленым вариантом ибо выделение целого куска памяти может быть задачей не лёгкой для OS.
Здравствуйте, VladCore, Вы писали:
VC>mmf всегда был на 2 порядка и больше быстрее filestream. почему так тормозит filestream не скажу — не знаю. ваш кэп
всё зависит от конкретног сценария работы. в данном случае, если не будет своппинга, выигрыш на два порядка не исключён (за счёт того что не надо переключаться в kernel mode и обратно), если будет (а по условиям задачи именно так) — то обычный I/O быстрее. хотя у меня читалось в среднем 4 КБ за раз, так что надо пробовать. другое дело что в любом случае, произвольный доступ к диску — это на порядки медленней, чем последовательный, хоть с mmf хоть без них
Здравствуйте, VladCore, Вы писали:
VC>>>mmf всегда был на 2 порядка и больше быстрее filestream VC>для чистоты эксперимента сначала обсудим требования:
собственно ты описал единственный случай когда mmf может быть на пару порядков быстрее i/o. а как насчёт других случаев? например последовательное чтение мегабайтными кусками некешированного файла
