Переписал программу в соответствии с идеей green. На самом деле алгоритм получился даже проще: основной поток в цикле считывает N блоков небольшого размера, раздает их рабочим потокам для сжатия, ждет завершения сжатия и записывает в выходной файл. Этот цикл повторяется пока не закончится входной файл. Таким образом, все операции ввода-вывода производятся последовательно, а параллельно идет только сжатие. Сегодня вечером потестирую на двухъядерной машине...
Есть прогресс. Тестировал на двухъядерном пентиуме, сжимал файлы разного размера. Привожу показательный результат для файла размером 2,65 Гб: новая версия: 3:54 мин старая версия: 5:04 мин В обоих случаях запускались два потока.
Portman Там ещё много резервов для оптимизации. Например, зачем программа ждёт завершения работы всех потоков в каждой итерации? Нужно давать потокам работу по мере их освобождения.
Заведи структуру с атомарным доступом (а-ля synchronized). В неё помести размер файла. Каждый поток получает доступ к структуре, и анализирует текущее смещение. Если текущее смещение уже больше размера файла, то поток завершает работу. Если меньше - то поток запоминает текущее смещение и прибавляет к нему размер блока, с которым будет работать. После этого он выполняет операцию сжатия.
r90 > Что в нём узкого? Эти несколько файлов, по-идее должны находиться в дисковом кеше вроде бы в задании сказали обрабатывать файлы больше размера памяти. так что в кэше они быть ну никак не могут. я не знаю с какой скоростью жмет gzip в net, но zlib на моем ноуте жмет намного быстрее, чем диск успевает поставлять данные. возможно с sdd ситуация окажется иной, но тут не тестировал. у меня стояла задача расжимать zlib с максимально возможной скоростью и в/в оказался узким местом даже на сервере. понятно, что расжатие сильно отличается от сжатия. и у меня не было потоков, а только процессы без разделяемой памяти. и все процессы (от 1 до 16ти по числу свободных ядер) равноправны. вывод в пайп и каждый очередной запущенный процесс либо занимается расжатием, либо читает с диска данные, либо скидывает уже расжатое на диск в зависимости от состояния пайпа. так вот -- основная нагрузка была на в/в. хорошо, что на сервере скази и читать можно с одного диска, а писать на другой. именно на это и уходило основное время. а само расжатие -- фигня. > Эти файлы будут читаться из RAM, Файл сначала нужно прочесть с диска. и только потом его сжимать. и по хорошему нужно параллелить так: [чтение] [сжатие | запись]
kaspersky Точно. Это я упустил из виду. Я говорил о временных файлах. Но эти мои разговоры оказались неактуальными ввиду размера исходных данных.
Передо мной стоит подобная задача, правда я сам её себе поставил. Нужно распаковать не файл по блокам, а архив по файлам. Благо, файлы небольшие. Тут, как справедливо отметил green, следует создать некоторую очередь блоков, из которой потоки будут брать данные по мере освобождения потоков. Т.е. управляющий поток не будет ждать пока отработают все четыре потока перед передачей следующего блока, а как только освободится один поток, он возьмёт новый необработанный блок. Соответственно, после того как один из потоков обработает свои данные, он их либо ставит в другую очередь на запись (в этом случае потребуется дополнительный поток на запись), либо самостоятельно записывает блок на диск (как предложил kaspersky - один поток читает данные, остальные обрабатывают и записывают), но в этом случае понадобится синхронизация по записи. В обоих случаях следует синхронизировать чтение с записью. Всё казалось бы просто, если бы не одно но. Та очередь из входных блоков вряд ли не ограничена по размерам. Ограничим её некоторым количеством, пусть 8 блоков. Таким образом, очередь уже сложно назвать очередью, ведь потоки не будут обрабатывать блоки последовательно один за другим, а скорее в случайном порядке. В этом случае управляющему потоку придётся каким-то образом определять, какой из 8 слотов освободился и помещать в него следующий блок. Лично мне понравилось решение, предложенное Джеффри Рихтером в его книге Windows via C/C++ (гл. 8 или 9 не помню точно, пример называется Queue). Суть в том, что после обработки блока, все необработанные блоки сдвигались влево к началу "очереди", а синхронизация выполнялась с помощью семафоров. Не знаю есть ли подобное в .NET. Т.е. каков итог: при реализации непрерывной распаковки в несколько потоков будут огромные проблемы с синхронизацией, но, если всё удастся, будет очень красивое, элегантное решение, притом в независимости от результатов (будет ли ускорение в 4 раза или нет), работодателю несомненно понравится, я уверен.
Всё что естественно, то не безобразно. Учитесь программированию у природы. Отношение "начальство - подчинённые" одно из основополагающих в обществе. Везде следует искать аналогии в природе, это сильно помогает понять суть задачи и найти верный путь решения. К примеру данный случай. Предположим, что есть склад неупакованной бытовой техники [исходный файл], которую нужно упаковать. Есть координатор [управляющий поток] и N упаковщиков [рабочие потоки]. Координатор выкладывает [файловый ввод-вывод] в окно товары по очереди, упаковщики из числа свободных товар забирают, упаковывают и отдают обратно через то же окно [ставят в очередь на запись, при этом за окном есть еще один рабочий, относящий товары на склад с упакованным товаром], либо самостоятельно относят товары на склад (возможная причина задержки). На данный момент у ТС ситуация такая: три упаковщика упаковали товар и ждут четвертого, чтобы упакованный товар всунуть обратно в то же окно. Тут и косяк. Во первых - простаивают три упаковщика пока четвёртый трудится (ведь товары бывают разные, на упаковку утюга и телевизора уйдёт разное время), во вторых, все четыре одновременно подготовленных товара в одно окно не влезут, можно передавать только по очереди. Как делать надо: тот из упаковщиков, который освободился, отдаёт товар в окно и берёт следующий. Но и тут не всё гладко, как казалось бы на первый взгляд. Предположим, координатор передал четыре утюга на упаковку, упаковщики их упаковали мгновено (опытные очень), и суют ему в окно, что тот не успевает забирать. В итоге, пока все четыре утюга не вернут, координатор новые товары не даст. Чтобы такого не происходило, координатор за время упаковки первых четырех утюгов должен выставить из окна еще некоторое количество товаров [поставить в очередь на упаковку], но это количество ограничено размерами платформы [оперативной памятью], на которую он эти товары выставляет. Довольно грубое представление, надо немного доработать момент касающийся прихода товаров со склада/ухода на склад. Оба склада находятся за одной дверью. Стоит ли нанимать второго сотрудника, относящего товары на склад, или ограничиться координатором.
Отключи вообще запись на винт - и временных кусков, и их склейку, и посмотри, во сколько раз будет быстрее.
Ezrah все вы правильно говорите, но зачем разделение на специализацию?! имеем N потоков (от 1 и выше). разбиваем задачу на фазы (чтение-упаковка-запись) и объявляем каждую фазу "заданием". задания ставятся в очередь. из пула потоков выбираются потоки и выгребают текующее задание. и каждый поток может быть и чтецом и писцов и сжимателем. что такое поток? это сущность выполнения. что такое чтец/песец/сжиматель? это грубо говоря функции. если функции могут выполняться независимо (а они могут, но только со сдвигом по фазе), то мы заполняем очередь потоков до тех пор, пока не достигается полного распараллеливания. в данном случае двух потоков вполне хватит и дальнейший рост производительности будет мизерным. а вот загружать все ядра -- смысла нет. лучше их отдать тем приложениям, которые в них нуждаются. и тут самое сложное -- это оптимизировать ввод/вывод. поток записи при работе с маленькими блоками может использовать кэш винта и работать асинхронно даже в синхронном режиме, т.к. ось отдаст управление еще до завершения записи. итого, запись можно совместить со сжатием. поток чтения по хорошему не нагружает ядро вообще никак, т.к. ось вгоняет поток в спячку до завершения операции ввода. итого, при ~90% загрузке одного ядра мы решаем задачу практически на полной скорости. два ядра имеем смысл нагружать только в случае высокопроизводительной дисковой подсистемы и торомозного алгоритма сжатия. (тут и с окном самого gzip стоит поиграться).
kaspersky Увеличение числа потоков вовсе не приводит к увеличению числа загруженных ядер. Если имеем четыре потока, а данные с диска успевают считываться только для одного, (т.е. упаковка идёт быстрее чтения), то остальные три потока будут простаивать. Возможно хватит двух потоков, но я не стал бы загадывать, алгоритм gzip довольно тормозной, чтение с диска, AFAIK, происходит гораздо быстрее. Такую модель я продумывал, но, к сожалению, у меня ничего не получилось.
Можно еще чуть ускориться, если использвать не System.IO.Compression.GZipStream, а оболочку для исходной zlib, говорят выигрыш будет, правда тут придётся что-то делать с заголовком архива, а так же неизвестно, можно ли будет паковать поблочно.
2:55 мин! Время работы третьей версии (см. пост 22). Пока еще не 4х, а примерно 1.8х. Суть модификаций в следующем. Программа теперь работает по принципу конвейера: - отдельный поток читает блоки и ставит в очередь на сжатие - рабочие потоки извлекают блоки из очереди, сжимают и ставят в список на запись - отдельный поток записывает сжатые блоки Ezrah, проблемы с синхронизацией здесь не такие огромные. Достаточно лишь учесть, что сжатые блоки могут поступать не по порядку, для этого блоки нумеруются, а дальше как в протоколе TCP/IP Но есть один момент, который мне не нравится. Если посмотреть в код, там есть строка Код (Text): Thread.CurrentThread.Priority = ThreadPriority.AboveNormal; Если ее убрать, то есть если приоритет главного потока будет такой же как у остальных, то произойдет следующее. Основной поток по какой-то причине будет получать слишком мало процессорного времени, в результате чего список блоков на запись будет периодически переполняться. Это вызывает включение обратной связи в виде объекта синхронизации ManualResetEvent jam, который приостанавливает поток, читающий блоки. В этот момент процесс притормаживается и происходит спад производительности. Таким образом, мы имеем разновидность хард-кодинга: неизвестно как программа будет себя вести в других условиях. Причина в целом понятна. Здесь есть три скорости: скорость поступления блоков в очередь сжатия, скорость поступления сжатых блоков в список и скорость записи их на диск. Понятно, что если скорость чтения превышает скорость записи, то данные будут накапливаться. Необходим какой-то хитрый механизм регуляции...
Я вроде не очень похож на иднуса, но всякое может быть. Ваш вариант с обратной связью мне нравится. Могу предложить лишь вариант, в котором поток, подающий блоки, будет следить за очередью на запись, чтобы в очереди на запись было на N блоков меньше, чем в очереди на распаковку. Если превышает, то N подбирается экспериментально и вряд ли превышает 10.
Ezrah Меня всегда бесила эта глупейшая фраза. Если я едучи в общественном транспорте захочу посрать, сниму штаны и навалю кучу на пол -- это ведь естественно? Естественно. Но разве не безобразно? 1. Природа не умеет программировать, и поэтому глупо учиться программированию у неё. 2. Отношения "начальство-подчинённые" -- это изобретение человечества, и не может считаться "естественной" и "природной" фичой. Вам никогда не приходилось работать в команде равноправных работников? Среди которых нет главного, когда все сами знают, что им надо делать, и завершив одну операцию, никто не останавливается в ожидании дальнейших указаний начальства, а немедленно переходит к выполнению следующей операции. Но можно ведь делать и без "координатора". Задача координатора, если приглядеться -- заказывать операции ввода/вывода дисковой подсистеме, и дожидаться их завершения. То есть координатор, по-сути, будет постоянно простаивать. Ну и зачем он тогда такой нужен? Заказывать операцию ввода/вывода может и рабочий поток, тогда когда он из списка прочитанных блоков забирает один на обработку.
r90 Вовсе нет, качества лидера присущи не каждому живому существу. Вспомните хотя бы вожака стаи, либо птицу, ведущую весь косяк. Никогда, и не представляю как это возможно. Видимо у них заранее был план, который нужно выполнить, составленный кем-то. На сем заканчиваю оффтоп.
как-то так: 1. Задаем размер блока, число потоков, лимит памяти 2. Создаем семафор с параметром=число потоков Цикл: 3. захват семафора 4. выделяем память(память выделяем сразу для чтения и для сжатия), читаем блок(не забываем нумеровать блоки). В функцию чтения можно завернуть префетч 5. создаем поток сжатия 6. освобождаем память 7. гоуту Цикл 8. принт ништяк поток сжатия: 1. выделяем память для вывода 2. сжимаем 3. ставим в очередь на запись(очередь отсортирована по порядковому номеру) 4. освобождаем семафор поток записи: 1. Если номер следующего блока > предыдущего на 1, то 2. тупо заливаем в файл 3. Освобождаем блок 4. гоуто 1(сюда можно слип на пару сек влепить, чтобы зря проц не мучить) в функи выделения/освобождения памяти завернуть мутекс/евент и проверку лимита памяти, чтобы ждать, пока память освоботится, иначе при тормозах записи будет утечка памяти. лимит памяти>=(размер блока+максимальный размер сжатых данных должен)*число ядер Вывод: как бы несложно.
Ezrah часто наблюдая животных предложу вам отвлечься от них и от прочих примеров из книжек. посмотрите на более знакомых вам людей. на верх, в большинстве случаев, выбирается наиболее нахальный и беспринципный человек. очень часто и полезность обществу от него достаточно сомнительна. простой пример - перечислите из известной вам истории имена царей принесших своему народу/государству или человечеству/миру заметную пользу? а, например, ученых? почему ученые != цари (2 исключения)? и стоит ли итти за тем кто очень рвется вас вести, что говорит история, куда, обычно, ведут эти "лидеры"? можно вспомнить, например, о жанне дарк и французском короле большинство опенсорсных проектов пишется подобным образом. продуктом пользуются дописывая (иногда чужими руками за деньги) нехватающие нужные части. если эти части востребованы, они могут переноситься в основное дерево. иногда проекты разделяются. иногда, объединяются. планы на проекты покрупнее трудно составлять. и ситуация меняется, и планы не учитывают открывающихся по пути возможностей или сложно преодолимых препятствий.
