Author: Steven McDougall

Translated by Wowessays

Введение

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

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

• |November| Introduction| motivation, definitions, examples|
• |December| Architecture| the Perl interpreter, calling conventions, data representation|
• |January| Tools| h2xs, xsubpp, DynaLoader|
• |February| Modules| Math::Ackermann, Set::Bit|
• |March| Align::NW| Needleman-Wunsch global optimal sequence alignment|

Что это такое

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 или просто хотите выполнить работу.
Если вы хотите просто выполнить работу, подумайте об использовании упрощенного генератора обёрток и интерфейсов (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, а PreProcessor - вежливый термин для расширителя макросов. xsubpp расширяет макросы XS в биты кода C, необходимые для соединения интерпретатора Perl с вашими подпрограммами языка C.

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

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

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

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

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

Достаточно сложная проблема

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

Когда-то моим любимым средством обработки чисел было быстрое преобразование Фурье, но сейчас, когда я думаю о нем, оно кажется мне устаревшим. Оно такое классическое, такое линейное, такое старомодное. Кроме того, он работает за O(n*log(n)), что почти не поддается обработке на Perl.

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

• Некоторые мотивы проблем выравнивания последовательностей
• Краткое описание динамического программирования в применении к более простой задаче
• Описание NW алгоритма
• Прямая реализация алгоритма NW на языке Perl

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

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

Шаг O(n^3) в алгоритме NW - это заполнение матрицы оценок; все остальное выполняется за линейное время. Я написал программу на языке Си, которая заполняет матрицу оценок.

• align.c
• align.h
• main.c

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

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

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

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

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

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

ПРИМЕЧАНИЯ

довольно распространенный
Я до сих пор помню свое недоумение, когда впервые наткнулся на man- страницу awk.
pp - сокращение от PreProcessor
На самом деле pp - это сокращение от Perl Pseudocode, но звучит неплохо...
преимущество
Еще одним преимуществом кодирования в XS является то, что это защищает ваш код от изменений в Perl C API.
датировано
1965 год, как это бывает.
J. В. Кули и Дж. В. Тьюки, "Алгоритм машинного вычисления сложных рядов Фурье", Математика вычислений, том 19, 1965, стр. 297-301.
Нидлман-Вунш
Нидлман, С.Б. и Вунш, К.Д. 1970. "Общий метод, применимый к поиску сходства в аминокислотных последовательностях двух белков" Журнал молекулярной биологии. 48: 443-453.
См. также
Смит, Т.Ф. и Уотерман, М.С. 1981. "Идентификация общих молекулярных подпоследовательностей" Журнал молекулярной биологии. 147: 195-197
O(n^3)
O(n^2), если штраф за разрыв-открытие равен нулю
линейное время
Алгоритму Смита-Ватермана требуется O(n^2) времени, чтобы найти клетку с наивысшим баллом в матрице.