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

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

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

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

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

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

10.08.2008 03:07:39
7 ОТВЕТОВ
РЕШЕНИЕ

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

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

9
10.08.2008 03:19:36

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

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

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

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

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

1
10.08.2008 03:59:52

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

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
3
10.08.2008 04:41:43

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

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

9
10.08.2008 05:21:43

@lomaxx

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

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

0
11.08.2008 00:02:20

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

1
11.08.2008 05:04:40

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

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

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

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

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

0
17.09.2008 04:27:08