Самый быстрый способ разбора больших строк (многопоточный)

Question

Я собираюсь начать проект, который будет собирать блоки текста, разбивая в них множество данных, в какой-то объект, который затем можно сериализовать, хранить и получать статистические данные / данные. Это должно быть как можно быстрее, так как у меня есть> 10 000 000 блоков текста, с которых мне нужно начать, и я буду получать 100 000 из тысячи в день.

Я использую это в системе с 12 ядрами xeon + гиперпоточность. Я также имею доступ / знаю немного о программировании CUDA, но для строковых вещей думаю, что это не подходит. Из каждой строки мне нужно разобрать много данных, и некоторые из них я знаю точные позиции, некоторые я не знаю, и мне нужно использовать регулярные выражения / что-то умное.

Итак, рассмотрим что-то вроде этого:

object[] parseAll (string [] stringsToParse)
{
     parallel foreach 
          parse( string[n] )
}

object parse(string s)
{
     try to use exact positions / substring etc here instead of regex's
}

Итак, мои вопросы:

• Насколько медленнее использовать регулярные выражения для подстановки.
• .NET будет значительно медленнее, чем другие языки.
• Какую оптимизацию (если есть) я могу сделать, чтобы максимизировать параллелизм.
• Что-нибудь еще, что я не учел?

Спасибо за любую помощь! Извините, если это слишком затянуто.

Answer 1

Насколько медленнее использовать регулярные выражения для подстановки.
Если вы ищете точную строку, substr будет быстрее. Регулярные выражения, однако, высоко оптимизированы. Они (или, по крайней мере, части) скомпилированы в IL, и вы даже можете сохранить эти скомпилированные версии в отдельной сборке, используя Regex.CompileToAssembly. См. http://msdn.microsoft.com/en-us/library/9ek5zak6.aspx для получения дополнительной информации.

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

Какую оптимизацию (если есть) я могу сделать, чтобы максимизировать параллелизм.
С Task.Factory.StartNew вы можете запланировать выполнение задач в пуле потоков. Вы также можете взглянуть на TPL (параллельная библиотека задач, частью которой является Task). Это имеет множество конструкций, которые помогают вам распараллелить работу, и позволяет таким конструкциям, как Parallel.ForEach(), выполнять итерацию в нескольких потоках. См. http://msdn.microsoft.com/en-us/library/dd460717.aspx для получения дополнительной информации.

Что-нибудь еще, что я не учел?
Одна из вещей, которая поразит вас этим объемом данных, - управление памятью. Несколько вещей, которые нужно учитывать:

• Ограничение выделения памяти: попробуйте повторно использовать одни и те же буферы для одного документа, а не копировать их, когда вам нужна только часть. Скажем, вам нужно работать с диапазоном, начинающимся с 1000 до 2000 символов, не копировать этот диапазон в новый буфер, а создать свой код для работы только в этом диапазоне. Это сделает ваш код сложнее, но сэкономит вам память;

• StringBuilder - важный класс. Если вы еще не знаете об этом, посмотрите.

Answer 2

Я не знаю, какую обработку вы здесь делаете, но если вы говорите сотни тысяч строк в день, это кажется довольно небольшим числом. Давайте предположим, что вы получаете 1 миллион новых строк для обработки каждый день, и вы можете полностью выполнить задачу из 10 из этих 12 ядер Xeon. Это 100 000 строк на ядро ​​в день. В дне 86 400 секунд, поэтому мы говорим 0,864 секунды на строку. Это много анализа.

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

Насколько медленнее использование регулярных выражений для подстановки?

Это полностью зависит от того, насколько сложны ваши регулярные выражения. Как сказал @Pieter, если вы ищете одну строку, String.Contains, вероятно, будет быстрее. Вы также можете использовать String.IndexOfAny, если ищете постоянные строки. Регулярные выражения не нужны, если вы не ищете шаблоны, которые не могут быть представлены в виде константных строк.

.NET будет значительно медленнее, чем другие языки?

В приложениях, интенсивно использующих процессор, .NET может работать медленнее, чем собственные приложения. Иногда. Если это так, то обычно он составляет от 5 до 20 процентов, а чаще всего от 7 до 12 процентов. Это просто код, выполняемый изолированно. Вы должны принять во внимание другие факторы, например, сколько времени вам понадобится, чтобы построить программу на этом другом языке, и насколько сложно обмениваться данными между собственным приложением и остальной частью вашей системы.

Answer 3

Если вы хотите выполнить быстрый разбор строк в C #, вы можете рассмотреть возможность просмотра нового проекта NLib . Он содержит расширения строк для быстрого поиска строк различными способами. Например, IndexOfAny (string []) и IndexOfNotAny. Они также содержат перегрузки с аргументом StringComparison.

Answer 4

Google недавно объявил о своем внутреннем языке обработки текста (который выглядит как подмножество Python / Perl, предназначенное для сильно параллельной обработки).

http://code.google.com/p/szl/ - Sawzall.