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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

Answer 5

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

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

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

ETA: звучит очень похоже на второе решение Wolfbyte. : -)

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

Answer 6

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

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

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

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

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

Answer 7

@ lomaxx

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

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