Анализ многоядерных текстовых файлов

Question

У меня четырехъядерный компьютер, и я хотел бы написать код для анализа текстового файла, который использует преимущества всех четырех ядер.Текстовый файл обычно содержит одну запись в строке.

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

Моя первая мысль — прочитать все строки в какую-то очередь, а затем раскрутить потоки, чтобы вытащить строки из очереди и обработать их, но это означает, что очередь должна существовать в памяти, а это довольно большие файлы, поэтому я Мне не очень нравится эта идея.

Мои следующие мысли — иметь какой-то контроллер, который будет читать строку и назначать ей поток для анализа, но я не уверен, станет ли контроллер узким местом, если потоки обрабатывают строки быстрее, чем он может. прочитайте и задайте их.

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

Answer 1

Я бы согласился с вашей оригинальной идеей.Если вы обеспокоены тем, что очередь может стать слишком большой, создайте для нее буферную зону (т.Если оно превысит 100 строк, чтение файла прекратится, а если оно станет меньше 20, начните чтение снова.Вам нужно будет провести некоторое тестирование, чтобы найти оптимальные барьеры).Сделайте так, чтобы любой из потоков потенциально мог быть «потоком чтения», поскольку ему в любом случае приходится блокировать очередь, чтобы вытащить элемент, он также может проверить, не была ли затронута «область низкого буфера», и начать чтение снова.Пока он это делает, другие потоки могут считывать остальную часть очереди.

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

Answer 2

Ответ Марка — более простое и элегантное решение.Зачем создавать сложную программу с межпотоковой связью, если в этом нет необходимости?Создать 4 потока.Каждый поток вычисляет размер файла/4, чтобы определить его начальную точку (и точку остановки).Тогда каждый поток может работать совершенно независимо.

А только Причина добавления специального потока для обработки чтения заключается в том, что вы ожидаете, что обработка некоторых строк займет очень много времени. и вы ожидаете, что эти строки сгруппированы в одной части файла.Добавление межпотоковой связи, когда она вам не нужна, очень плохая идея.Вы значительно увеличиваете вероятность появления неожиданных узких мест и/или ошибок синхронизации.

Answer 3

Это устранит узкие места, связанные с чтением одного потока:

open file
for each thread n=0,1,2,3:
    seek to file offset 1/n*filesize
    scan to next complete line
    process all lines in your part of the file

Answer 4

Мой опыт работы связан с Java, а не с C#, поэтому приношу извинения, если эти решения не применимы.

Непосредственное решение, которое я могу придумать, - это иметь исполнителя, который запускает 3 потока (используя Executors.newFixedThreadPool, сказать).Для каждой строки/записи, считанной из входного файла, запускайте задание у исполнителя (используя ExecutorService.submit).Исполнитель поставит запросы в очередь и распределит их между тремя потоками.

Вероятно, существуют лучшие решения, но, надеюсь, они справятся со своей задачей.:-)

Расчетное время прибытия:Очень похоже на второе решение Wolfbyte.:-)

Расчетное время прибытия 2: System.Threading.ThreadPool звучит как очень похожая идея в .NET.Я никогда им не пользовался, но, возможно, оно того стоит!

Answer 5

Поскольку при работе с файлами узким местом обычно является обработка, а не чтение, я бы выбрал производитель-потребитель шаблон.Чтобы избежать блокировки, я бы посмотрел на списки без блокировки.Поскольку вы используете C#, вы можете взглянуть на книгу Джулиана Бакнелла. Список без блокировки код.

Answer 6

@lomaxx

@Дерек и Марк:Мне бы хотелось, чтобы был способ принять 2 ответа.В конечном итоге мне придется использовать решение Wolfbyte, потому что, если я разделю файл на n разделов, существует вероятность того, что поток столкнется с пакетом «медленных» транзакций, однако, если бы я обрабатывал файл, в котором каждый процесс гарантированно требовал равного объема обработки, то мне очень нравится ваше решение: просто разбить файл на фрагменты, назначить каждый фрагмент потоку и покончить с этим.

Не беспокойся.Если кластерные «медленные» транзакции представляют собой проблему, то лучше всего подойдет решение с организацией очередей.В зависимости от того, насколько быстрой или медленной является средняя транзакция, вы также можете рассмотреть возможность одновременного назначения нескольких строк каждому работнику.Это позволит сократить расходы на синхронизацию.Аналогичным образом вам может потребоваться оптимизировать размер буфера.Конечно, обе эти оптимизации, вероятно, следует выполнять только после профилирования.(Нет смысла беспокоиться о синхронизации, если она не является узким местом.)

Answer 7

Если текст, который вы анализируете, состоит из повторяющихся строк и токенов, разбейте файл на фрагменты, и для каждого фрагмента вы можете предварительно проанализировать его в одном потоке на токены, состоящие из ключевых слов, «пунктуации», строк идентификатора и значений.Сравнение и поиск строк могут быть довольно дорогостоящими, и передача этого нескольким рабочим потокам может ускорить чисто логическую/семантическую часть кода, если ему не нужно выполнять поиск и сравнение строк.

Предварительно проанализированные фрагменты данных (где вы уже выполнили все сравнения строк и «маркировали» их) затем можно передать в ту часть кода, которая фактически будет проверять семантику и порядок токенизированных данных.

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

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

Альтернативно, большие файлы могут быть отображены в памяти и загружены «по требованию».Если у вас больше потоков, работающих над обработкой файла, чем процессоров (обычно потоки = 1,5–2 раза процессоров — хорошее число для приложений подкачки по запросу), потоки, которые останавливаются при вводе-выводе для файла, отображаемого в памяти, автоматически останавливаются из ОС до тех пор, пока не будут память готова, и другие потоки продолжат обработку.