Недавно связывался с компанией XYZ, хотел на работу устроиться. Выслали тестовое задание. Кратко, суть в следующем: написать многопоточную программу для сжатия файлов в формат gzip. На вход поступает имя исходного и результирующего файла. Программа должна работать, используя все доступные процессоры и уметь обрабатывать файлы, размер которых превышает объем доступной оперативной памяти. Задание само по себе не очень сложное. Я написал программу, которая сжимает файл блоками параллельно в нескольких потоках. Алгоритм следующий: 1. Вычисляются границы блоков (начало, длина) 2. Раздаются задания потокам: каждый поток сжимает свой блок и записывает во временный файл 3. Основной поток ждет завершения всех рабочих потоков 4. Полученные файлы объединяются Выслал. Пришел следующий ответ: программа работает хорошо, но только медленно. Ускорьте в 4 (четыре) раза, тогда поговорим. Такой ответ меня удивил, поскольку при тестировании программа показала 100% загрузку всех процессоров практически на всем протяжении работы. Подумал немного, почитал доки. Решил что дело в одновременном чтении-записи нескольких файлов из нескольких потоков. Платформа - Виндовс. Провел эксперименты с параллельным и последовательным чтением-записью, с размерами буферов. В итоге более чем на 25% увеличить производительность не получилось. Пришел к выводу что ускорить программу в 4 раза невозможно теоретически. В чем подвох? Забыл добавить: алгоритм сжатия по условиям задания библиотечный, т.е. самому его писать не надо было.
А Чё алгоритм gzip поддаётся распаралеливанию? Можно вкратце его суть ? Это одна из модификаций Лемпеля-Зива?
Да, Лемпель-Зив. Но сам алгоритм не поддается распараллеливанию - он по существу последовательный. Здесь помогает та его особенность, что если исходный файл распилить на куски, куски сжать по отдельности, а потом склеить в таком же порядке, то получится вполне корректный zip-архив, который открывается, например WinRar-ом.
ну ёлки-палки, производительность программы в первую очередь можно завалить непотребным обращением к фс. может, это и в конце, может и занимает на хорошем железе пару секунд, но некрасиво, особенно в качестве показательной работы.
Portman Это интересно. Если можно, выложите исходники (вместе с библиотекой сжатия). Может всё-таки удастся увидеть какие-то возможности...
А факт того, что программе может быть дано сразу несколько файлов на сжатие, учли? UPD. Все new byte[] повыносить из циклов. Создать единожды при старте. UPD2. Поиграться с размерами буферов. UPD3. А почему склейка в один поток?
SadKo По условиям задания входной файл один. Насчет byte[] верно, упустил. С буферами играл, до 10Мб дает небольшое увеличение, потом не влияет. А есть смысл склейку распараллеливать - диск-то все равно один? green Да.
Ну если так можно, то распаралеливается.... (а ведь и впрям можно) Разве нельзя писать в поток сразу (не создавая временные файлы)?? Покопай вроде у .НЕТ в ФайлСтрим можно?
Portman > 3. Основной поток ждет завершения всех рабочих потоков зачем? тут не нужен основной поток. зачем ему ждать? пусть тоже работает. > 4. Полученные файлы объединяются тут сильная просадка производительности, очевидно. двойная запись на диск. а зачем? > Ускорьте в 4 (четыре) раза, тогда поговорим. вероятно, они сравнивали скорость с эталоном (программой, которую написали сами). отсюда и 4 раза. хотя, может, и с потолка цифру взяли. > Такой ответ меня удивил, поскольку при тестировании программа > показала 100% загрузку всех процессоров практически на всем протяжении работы. это ни о чем не говорит. > Решил что дело в одновременном чтении-записи нескольких файлов из нескольких потоков. это действительно узкое место. > Пришел к выводу что ускорить программу в 4 раза невозможно теоретически. возьмите архиватор с поддержкой многопоточности и посмотрите сколько он будет сживать тот же самый файл. обычно, готовые программы неплохо оптимизированы и вполне могут быть эталоном. так же имеет смысл времено отключить сжатие, возввщая фиктивный блок данных заданного размера, чисто для оценки сколько времени расходуется на в/в, а сколько на сжатие.
Portman - Вы в корне не правильно распаралелили задачи ... Вам требует главный поток и еще один для записи на диск. Программный код написан плохо. Сихшный подход, генерация исключений без их обработки.
Portman Думаю, следует уменьшить размер сжимаемого блока, отвяжите размер блока от количества рабочих потоков - пусть он ограничивается снизу только из соображений эффективности и качества сжатия. Далее, не привязывайте каждый поток к фиксированному смещению (смещениям), пусть получает просто следующий блок из файла. Во-первых, это увеличит локальность чтения входного файла, а во-вторых - позволит обойтись без промежуточных файлов (т.е. можно будет писать в MemoryStream). Кстати, один из потоков может писать сразу в выходной файл.
green А ведь точно! Сжимать небольшими блоками, тогда можно будет писать сразу в выходной файл, когда очередная порция блоков будет сжата. Надо попробовать...
ntkernelspawn Я никогда не понимал, зачем нужен главный поток. Главный поток -- как и любое начальство: делать ничего не делает, только никому ненужные указания раздаёт, а ресурсы потребляет. Portman Не надо временных файлов. Это лишние копирования данных. Как минимум копирования вида RAM->RAM, как максимум RAM->HDD и, даже, HDD->RAM. Копирование с/на HDD будет влиять на производительность, лишь если программа выбирает всю скорость жёстких дисков. Но даже копирования RAM->RAM -- это ужос. Прежде чем писать алгоритмы компрессии, надо написать две функции, первая для получения следующего блока для сжатия, вторая для отправления сжатого блока на вывод. Первая пишется тривиально, вторая чуть хитрее, она должна переупорядочивать сжатые блоки, располагать их по-порядку, и, по-мере возможности, писать на диск. Причём либо писать асинхронно, либо, как тут советовали, придётся заводить отдельный поток для записи на диск. Ещё один поток -- по-моему, правильнее, ведь его можно заодно озадачить вопросами чтения исходного файла, чтобы рабочие треды не связывались бы с вводом/выводом, сделать эдакий prefetch блоков в адресное пространство процесса: если сжатие происходит быстрее чтения, то это позволит выжать максимум из жёсткого диска. kaspersky Что в нём узкого? Эти несколько файлов, по-идее должны находиться в дисковом кеше и не должно возникать необходимости трясти головками жёсткого диска. Эти файлы будут читаться из RAM, которая по-определению рандом-акцесс, и ей плевать в каком порядке будут читаться данные. Проблема не в том, что их несколько и io происходит одновременно, проблема в том, что этот io вообще есть. Хотя, с другой стороны, если сжимать гигабайт несколько, то да, эти файлы начнут пропадать из дискового кеша, и тогда будут уже серьёзные тормоза.
r90 Ну, это действительно может быть узким местом. Особенно при чтении, если верить вот этой статье http://www.ixbt.com/storage/wd4000ncq.shtml. Особенно интересна третья диаграмма сверху . Согласно ей, при многопоточном чтении из далеко отстоящих областей диска скорость получения данных может падать на порядок.
Portman И где системное мышление? В статье идёт речь о чтении именно с жёсткого диска. Ты же читаешь файлы, которые только что записал. Эти файлы кешируются в RAM ядром. И их чтение не порождает никакого общения с жёстким диском. Это действительно может быть узким местом:
