Есть ли более быстрый способ разбора, чем путем обхода каждого байта?

Question

Есть ли более быстрый способ разбора текста, чем обход каждого байта текста?

Интересно, есть ли какая-нибудь специальная инструкция CPU (x86 / x64) для строковых операций, используемая библиотекой строк, которая каким-то образом используется для оптимизации процедуры синтаксического анализа.

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

* edited-> note: Я спрашиваю больше об алгоритме, а не об архитектуре процессора, поэтому мой настоящий вопрос в том, существует ли какой-либо специальный алгоритм или особый метод, который мог бы оптимизировать процедуру манипуляции со строками, учитывая текущую архитектуру процессора. *

Answer 1

В x86 было несколько строковых инструкций, но они потеряли популярность на современных процессорах, потому что они стали медленнее, чем более примитивные инструкции, которые делают то же самое.

Мир процессоров все больше движется в сторонуRISC, то есть упрощенные наборы инструкций.

Цитата из Википедия (выделено мое):

Первые сильно (или сильно) конвейерные реализации x86, 486Проекты Intel, AMD, Cyrix и IBM поддерживали все инструкции, которые выполняли их предшественники, но достигали максимальной эффективности только на довольно простом подмножестве x86, которое напоминало лишь немного больше, чем типичный набор команд RISC (т.е.без типичных ограничений хранилища нагрузки RISC).

Это по-прежнему справедливо для современных процессоров x86.

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

Answer 2

Да, есть специальные инструкции процессора;и библиотека времени выполнения, которая реализует такие функции, как strchr, может быть написана на ассемблере.

Один метод, который может быть быстрее, чем обходные байты, - это обход двойных слов, то есть обработка данных 32 бита ввремя.

---

Проблема с перемещением фрагментов блока памяти, размер которых превышает наименьшую, в контексте строк, заключается в выравнивании

Вы добавляете код в начале и конце своей функции (до и после цикла), чтобы обрабатывать байты [s] с неравномерным / невыровненным форматом.(пожимает плечами) Это делает ваш код быстрее: не проще.Ниже приведен пример исходного кода, который претендует на то, чтобы быть улучшенной версией strchr.Он использует специальные инструкции процессора, но он не прост (и имеет дополнительный код для невыровненных байтов):

PATCH: Оптимизация strchr / strrchr с SSE4.2 - «Этот патч добавляетSSE4.2 оптимизировал strchr / strrchr. Он может ускорить strchr / strrchr в 2 раза на Intel Core i7 "

Answer 3

Хотя (некоторые) процессоры имеют строковые инструкции, они мало полезны для создания более быстрого кода.Прежде всего, как заметил @ zildjohn01, они часто медленнее, чем другие инструкции с текущими процессорами.Что еще более важно, в любом случае это редко имеет большое значение - если вы сканируете много текста вообще, узким местом обычно является пропускная способность от памяти до ЦП, поэтому, по сути, ничего, что вы делаете с изменением инструкций, скорее всего, не окажет существенного влиянияв любом случае.

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

Answer 4

Ну, вы должны смотреть на все, чтобы знать все о тексте, на каком-то уровне. Возможно, у вас может быть какой-то структурированный текст, который дает вам дополнительную информацию о том, куда идти в каждой точке, в своего рода n-арном пространстве. Но затем «синтаксический анализ» был частично выполнен еще при создании файла. Начиная с 0 информации, вам нужно будет коснуться каждого байта, чтобы знать все.

Answer 5

Есть ли более быстрый способ разбора текста, чем обход каждого байта текста?

Да, иногда вы можете пропустить данные.На этой идее основан алгоритм поиска строки Бойера-Мура .

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

Answer 6

Несмотря на то, что этот вопрос давно ушел, у меня есть для вас другой ответ.

Самый быстрый способ разбора - вообще не разбирать. А?! * * 1003

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

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

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

Как видно в "C # '88", QuickC 2.0 и VC ++ 4.0, инкрементная перекомпиляция.

Счастливого взлома!

Answer 7

Да.Поскольку ваше редактирование специально запрашивает алгоритмы, я хотел бы добавить пример для этого.

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

Пример:

01234567890123456789
FOO        BAR    

При сканировании следующего токена вы будете проверять 4,6,8,10 и 12. Только когда вы видите A, вы оглядываетесь назад на 11, чтобы найти B. Вы никогда не смотрели на 3,5,7 и 9.

Это особый случай Алгоритм поиска Бойера – Мура