Mеханика XS: Введение

От переводчика

Решил перевести на русский язык статью XS Mechanics Стива МакДугалла (Steven W. McDougall). Не смотря на то, что написана она была в далеком 2000 году, она не потеряла своей актуальности. Ну, или начинает терять, ведь у нас появился Perl 6 :P Но речь не о нем.

Статья расчитана на программистов, интересующихся в написании модулей для Perl 5, используя XS. Для выполнения примеров из статьи необходимы базовые знания по C. Примеры одинаково хорошо работают как в GNU/Linux, так и в Windows.

Если вы ранее этим не занимались, но хотите с чего-то начать, тогда эта статья то, что вам нужно. Если вы уже программируете на XS, то в этой статье вы, скорее всего, не найдете ничего нового. Более того, вполне вероятно, что вы с нее и начинали.

Для тех, кто интересуется внутренним устройством Perl, рекомендуется прочитать вторую часть статьи. В ней довольно подробно описываются механизмы того, что происходит “под капотом” в Perl.

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


Соглашения, используемые в переводе:

  • routine, subroutine: на протяжении всей статьи автор обильно использует оба этих термина. Однако, в русском языке они все имеют одно значение: подпрограмма. Считается, что routine вызывает subroutine, тем самым подчеркнуть, что является родительской подпрограммой, а что дочерней. Иногда под routine понимается большая функция (или процедура), которая содержит много более мелких подпрограмм (например, функцию main() в С вполне можно именовать как routine). В контексте программ на C в переводе иногда используется термин функция, именно так как их принято называть в современном мире. В контексте других языков программирования термины routine, subroutine и подпрограмма объединяют следующие понятия: функция, процедура, метод.
  • glue routine: переведено как клей-подпрограмма. Данный термин используется для определения функций, которые связывают код на C с кодом на Perl C API. Не смотря на то, что в общем понимании это все код на C (макросы XS это макросы C), данное различие подчеркивается специально. В статье дается детальное объяснение данного термина.
  • macro expander: переведено как раскрыватель макросов; программа, которая считывает определения макросов из указанного файла и заменяет имена макросов на их значения. По сути, макрос состоит двух частей: имени (короткая форма) и значения (в более длинной форме), скрытое от глаз программиста. Поэтому “раскрытие” макроса это действие, которое заменяет [короткое] имя макроса на его значение [более длинное]. Сокрытие значения макроса в виде короткого имени позволяет писать более компактные и надежные программы, т.к. макрос, будучи написан раз, может использоваться на протяжении всей программы. Также, один и тот же макрос может использоваться в различных программах.
  • bless: в контексте создания экземпляров класса Perl я не смог подобрать более лучшего варианта перевода, чем ассоциирование с именем пакета. По сути, Perl для образования экземпляра всего лишь добавляет имя класса/пакета к структуре (на C, во внутреннем представлении Perl) обычного объекта данных: скаляру, массиву и хэшу. Ну, хорошо, добавляет еще парочку флажков :). Более того, это ассоциированное имя можно изменять в ходе выполнения программы. В отличие от других языков программирования, где такое преобразование потребовало бы полное пересоздание экземпляра класса, в Perl это обычная практика: внутренние данные объекта остается неизменными, в то время как методы после пере-ассоциирования (re-bless) наследуются от нового выбранного имени класса (доступ к старым методам, естественно, теряется).

Не лезьте в дела волшебников, вы, хрустяшки, вкусные с кетчупом.^

Механика XS

Введение

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

Данная статья состоит из пяти частей:

Ноябрь Введение мотивация, определения, примеры
Декабрь Архитектура интерпретатор Perl, соглашения вызывов, представление данных
Январь Инструменты h2xs, xsubpp, DynaLoader
Февраль Модули Math::Ackermann, Set::Bit
Март Align::NW глобальное оптимальное выравнивание последовательностей Нидлмана-Вунша

Что это

XS это (фонетический?) акроним для выражения eXternal Subroutine (внешняя подпрограмма), где external (внешняя) означает внешняя для Perl, т.е. написанная на каком-то другом языке программирования, таком как C или C++. Используя XS, мы можем вызывать подпрограммы C прямо из кода на Perl, так, как будто это подпрограммы самого Perl.

Точнее, XS это имя связуемого языка, который используется для описания интерфейсов подпрограмм и представления данных, необходимых, чтобы вызывать [код] C из Perl. В более широком смысле, XS включает набор системных программ и возможностей, которые работают вместе, чтобы обеспечить все необходимое для работы: h2xs, MakeMaker, xsubpp, DynaLoader, и сам язык XS. Мы поговорим обо всем этом позднее.

Зачем это

Perl это армейский швейцарский нож, но имеется ряд вещей, которые невозможны в Perl. Например,

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

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

Напротив, C и C++ это примеры системных языков программирования. Они предоставляют контроль над каждым циклом ЦП и каждом байтом, чтобы внутренние циклы были быстрыми, а критические структуры данных малыми. Платой за это является необходимость программирования каждого цикла ЦП и каждого байта во всей программе: даже тех частей, которые не привязаны к процессору.

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

Вилка на дороге

Теперь вы должны решить хотите ли вы писать на XS, или хотите просто сделать свою работу.

Если вы хотите просто сделать свою работу, обратите внимание на Simplified Wrapper and Interface Generator (SWIG). SWIG это инструмент разработки программ, который соединяет известные прикладные языки программирования, такие как Perl, Python, или Tcl, с известными системными языками программирования, такими как C, C++, и Objective-C.

SWIG очень легок в использовании. В самом простейшем случае, вам нужно просто указать ему файл .c, указать какой ваш прикладной язык программирования, а обо всем остальном он позаботится сам. Вот пример, немного откорректированный из документации к SWIG:

unix> swig -perl5 -module example example.c
unix> gcc -c example.c example_wrap.c
unix> ld -G example.o example_wrap.o -o example.so
unix> perl5.005
use example;
print example::factorial(4), "\n";
<ctrl-d>
24

Я мог бы написать руководство по SWIG, но оно было бы избыточным: SWIG уже располагает обширной документацией. SWIG доступен в Сети, свободный, и он работает. Если вам нужно просто сделать свое дело, то SWIG это то, что вам нужно.

Изучая XS

Если вы хотите писать на XS, вы должны его изучить. Изучить XS очень тяжело, на это есть две причины.

Первая заключается в том, что внутренняя документация по Perl, такая как perlxs и perlguts, молчаливо предполагает, что вы уже понимаете XS. Соответственно, в них упускаются или приукрашиваются важные предпосылки и исходная информация. Это звучит ужасно, но на самом деле это довольно часто встречается в мире Unix.

Вторая причина – вы не можете изучить XS. Ну, не совсем. Не сверху вниз. Эта проблема более глубокая, чем первая, и она не основывается на каких-либо несоответствиях в документации, кроме тех фактов, что является XS, а что – нет.

Документация Perl ссылается на XS как на язык, но на самом деле это не так. XS это набор макросов. Процессор языка XS это программа, которая называется xsubpp, где pp это сокращение для PreProcessor, а препроцессор это вежливый термин для раскрывателей макроcов (macro expander). xsubpp раскрывает макрос XS в кусочки кода на C, необходимых для соединения интерпретатора Perl с вашими подпрограммами на языке С.

Так как XS это не язык, он не имеет структуры. Нижележащий код на C имеет структуру, но вы не можете ее видеть, потому что она скрыта за макросами. Из-за этого почти невозможно изучить XS, основываясь на его терминах. [На самом деле, узнать структуру (описания) самих макросов можно из соответствующих заголовочных файлов Perl. Хотя сам этот процесс потребует глубокого вникания в устройство самого Perl. – прим. пер.]

Возвращаясь к основам

Для того, чтобы изучить XS, вам следует двигаться снизу вверх. Вам нужно изучить Perl C API. Вам необходимо понять внутренние структуры данных Perl. Вам нужно понять как работает стек Perl, как подпрограмма на C получает доступ к нему. Вам необходимо понять как подпрограмма на C линкуется с исполняемым файлом Perl. Вам необходимо понять каким образом в модуле DynaLoader происходит связывание имени подпрограммы Perl с точкой входа подпрограммы на C.

Как только вы все это поймете, вам, грубо говоря, не понадобится XS: вы можете программировать прямо на Perl C API, а ваш код на C будет линковаться и запускаться под управлением интерпретатора Perl.

Если вы пишите код, используя только Perl C API, вы скоро обнаружите, что это тяжело, легко подвергается созданию ошибок, утомительно, и имеет природу повторяемости. Вы продолжаете писать те же самые куски кода, чтобы передвигать параметры на стеке Perl; чтобы сконвертировать данные из внутреннего представления Perl к представлению на C; чтобы проверить нуль-указатели и другие Плохие Вещи. Когда вы допустите ошибку, вы не получите результата о плохом деянии: вы сломаете интерпретатор. [Речь об segmentation fault – прим. пер.]

Прозрение

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

Теперь вы понимаете XS.

Еще более сложная проблема

Первая вещь, которую вам нужно получить перед тем как написать модуль XS, это программа, которую однозначно нельзя написать на чистом Perl. Писать на C и XS, когда вы можете сразу написать её на Perl, будет вопиющей ошибкой Лени.

Моим фаворитом для число-дробилки является Быстрая Трансформация Фурье, но на момент этих слов я думаю, что она, ну, устарела. Она такая классическая, такая прямолинейная, старый хлам (old-tech). Между тем, алгоритм имеет сложность O(n*log(n)), что практически сопоставимо с реализацией на Perl.

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

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

Для теста производительности, я выравнил 2 последовательности, состоящих из 200 символов каждая. Это довольно скромная задача по стандартам геномики. Реализация на Perl выравнивает их примерно за 200 или 400 секунд. Точное время здесь не играет существенной роли: это занимает больше времени, чем я хочу ждать.

Шаг O(n3) в алгоритме NW образуется в счетной матрице; все остальное выполняется за линейное время. Я написал программу на C, которая заполняет счетную матрицу.

Она выполняет тест выравнивания 200x200 за 3 секунды, или почти в 100 раз быстрее, чем реализация на Perl.

Я не хочу переписывать всю реализацию с Perl на C. Части алгоритма замысловатые, а сам алгоритм сильно полагается на Perl в вопросах управления памятью и всем остальным. Это пример кода, который выглядит игрушкой на языке Perl, и бременем на C.

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

В следующем месяце: Архитектура

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

Имеется множество материала, который следует объяснить, однако, либо вы поймете архитектуру, которая лежит в основе XS, или вы хрустяшка, вкусная с кетчупом.


Заметки

Не лезьте в дела ...

Do not meddle in the affairs of wizards, for you are crunchy and good with ketchup.

Отсылка к Толкиену. – прим. переводчика.

довольно часто

Я все еще помню о своем замешательстве, когда я впервые увидел мануал к awk(1).

pp это сокращение для PreProcessor

На самом деле, pp это сокращение для Perl Pseudocode, но зато звучит лучше…

преимущества

Другое преимущество написания кода на XS в том, что он защищает вас от изменений в Perl C API.

устарела

1965, на момент появления.

    1. Cooley and J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series”, Mathematics of Computation, Vol. 19, 1965, pp. 297-301.
Нидлман-Вунш

Needleman, S.B. and Wunsch, C.D. 1970. “A general method applicable to the search for similarities in the amino acid sequences of two proteins” Journal of Molecular Biology. 48: 443-453.

Смотрите также

Smith, T.F. and Waterman, M.S. 1981. “Identification of common molecular subsequences” Journal of Molecular Biology. 147: 195-197

O(n^3)

O(n2), если штраф за разрыв равен нулю (the gap-open penalty is zero).

линейное время

Алгоритм Смита-Ватермана требует время O(n2) для нахождения самой весомой ячейки в матрице.