Механика XS: Align::NW

Механика XS

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

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

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

Align::NW

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

Выравнивание последовательности

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

Взяв две последовательности

abcdeffh
bdefghijkl

мы хотим найти наилучший путь выравнивания по всей их длине: что-то вроде этого

abcdeffh
 | ||| |
 b.defghijkl

Это выравнивание имеет 5 совпадений, одно несовпадение, и один разрыв длиной равной 1. Мы производим расчет выравнивания в соответствии с платежной матрицей

совпадение 4
несовпадение -3
разрыв -2
продление разрыва -1

и узнаем, что выравнивание имеет счет (или вес)

5*4 + 1*(-3) + 1*(-2-1) = 20 - 3 - 3 = 14

Из всех возможных выравниваний, мы хотим найти одно, которое дает наивысший вес для данной платежной матрицы.

Мы будем ссылаться на последовательности как на A и B, а на их длины как на lA и lB, соответственно. Число возможных выравниваний растет экспоненциально по отношению к lA и lB, поэтому последовательное перечисление и расчет всех значений, чтобы найти наилучший вес, очевидно, неподатливо.

Алгоритм Нидлмана-Вунша

Алгоритм динамического программирования Нидлмана-Вунша создает матрицу счета, с одной последовательностью cверху и другой вниз по левому краю. Записи в матрице называются ячейками.

   | b | c | d | e 
---+---+---+---+---
 a |   |   |   |   
-------------------
 b |   |   |   |   
-------------------
 c |   |   |   |   
-------------------
 d |   |   |   |   

Затем, алгоритм заполняет матрицу со счетом, начиная работу с верхнего левого края, и завершая в правом нижнем.

   |  b  |  c  |  d  |  e  
---+-----+-----+-----+-----
 a | -3  | -3  | -3  | -3
---+-----+-----+-----+-----
 b |  4  |  1  |  0  | -1
---+-----+-----+-----+-----
 c |  1  |  8  |  5  |  4
---+-----+-----+-----+-----
 d |  0  |  5  | 12  |  9

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

abcd
 |||
 bcde

Правила подсчета матрицы и обхода не сложно объяснить, но нам не нужно думать о них. Интересующиеся этим вопросом читатели могут узнать об этом из исходников Align::NW, или прочитать из списка литературы указанного в документации POD модуля. Доказательство того, что эти правила на самом деле приводят к нахождению оптимального выравнивания сложнее объяснить: Нидлман и Вунш заработали имена в названии алгоритма именно за эту работу.

План

Наш общий план действий для реализации алгоритма NW в виде XS модуля состоит в следующем.

  1. Создать на чистом Perl реализацию алгоритма.
  2. Проанализировать (или замерить) код в вопросе производительности.
  3. Переписать критичные методы, влияющие на производительность, на C.
  4. Написать XS, чтобы соединить подпрограммы C с модулем на Perl.

Реализация на Perl

Первая вещь, которая нужна любому модулю это его имя. Мы назовем свой Align::NW.

Реализация на Perl для модуля XS не всегда возможна, но она может быть очень полезной. Она позволяет нам адресовывать вопросы архитектуры к Perl, не запутываясь в кодинге на языке C. Ниже дана реализация Align::NW на чистом Perl.

Метод new создает новый объект Align::NW, вот так

my $nw = {
  a       => $a,
  b       => $b,
  rows    => $rows,
  cols    => $cols,
  dp      => $dp,
  payoff  => $payoff,
  options => \%options
};

$a и $b – две последовательности для выравнивания. $dp это счетная матрица; обращение по индексам делается так

$cell = $dp->[$row][$col];

Записи в счетной матрице являются ячейками. Каждая ячейка выглядит как показано ниже

$cell = {
  row   => $row,
  col   => $col,
  score => $score,
  prev  => $prev
};

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

Анализ производительности

Метод score заполняет матрицу. В матрице находятся ячейки lA*lB. Более того, вычисления веса каждой ячейки требуют использования цикла как для строк, так и цикла для столбцов, следовательно, заполнение матрицы требует O(lA*lB*(lA+lB)) операций. Это лучше, чем экспоненциальное, но все еще плохое, делая реализацию на C актуальной.

Метод align обходит в обратном направлении матрицу и генерирует выравнивание. Концепция обхода простая, но скорее замысловатая в исполнении. Более того, она работает за O(lA+lB). Реализация align на C может быть сложной, и не даст прироста производительности.

Реализация на C

Ниже дана реализация метода score, выполненная на C, вместе с main() для её запуска. Она не выравнивает последовательности; она не контролирует входные и выходные данные; она не имеет опций. Всё что она делает – заполняет матрицу.

Конвертирование метода из Perl на C поднимает два особых вопроса

  • конвертирование кода
  • конвертирование данных

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

Структуры C

Структуры данных транслируются из Perl в C прямым образом:

typedef struct
{
    int match;
    int mismatch;
    int open;
    int extend;
} Payoff;

typedef struct Cell
{
    int          row;
    int          col;
    int          score;
    struct Cell *prev;
} Cell;

typedef struct
{
    Payoff   payoff;
    char    *pszA;
    char    *pszB;
    int      nRows;
    int      nCols;
    Cell   **ppCell;
} NW;

Структуры Cell и NW безусловно должны быть выполнены на C ради производительности. Структура Payoff – нет: её значения постоянны, таким образом, мы можем оставить её в Perl и указать score делать её локальную копию.

Если мы оставим Payoff в Perl, то score должна получать доступ к ней с помощью Perl C API; если мы сконвертируем ее в C, то наш код на Perl получит доступ к ней через интерфейс XS. Это лишь вопрос стиля и удобства. В данной реализации я сконвертировал Payoff на C.

Интерфейс структур C

Когда данные расположены в C, нам нужен XS для оперирования ими из Perl. Это значит, что нам придется добавить интерфейсы к каждой нашей структуре на C. Вот пример интерфейса для структуры Payoff.

Payoff *new    (int match, int mismatch, int open, int extend);
void    DESTROY(Payoff *pPayoff);

Т.к. мы кодируем на C, а не Perl, мы самостоятельно отвечаем за управление памятью. Подпрограмма new выделяет память для структуры и инициализирует её; метод DESTROY освобождает память.

Интерфейс к структуре Matrix похожий

Matrix *new    (char *pszA, char *pszB, Payoff *pPayoff);
void    DESTROY(Matrix *pMatrix);
void    score  (Matrix *pMatrix);
Cell   *cell   (Matrix *pMatrix, int nRow, int nCol);
void    dump   (Matrix *pMatrix);

В дополнении к подпрограммам new и DESTROY, у нее есть score для заполнения счетной матрицы, cell для возвращения указателя к определенной ячейки в матрице, и dump для отладки.

Интерфейс к структуре Cell очень простой. Подпрограмма cell для структуры Matrix выделяет и освобождает память для ячеек в матрице. Все, что остается для интерфейса Cell это акцессоры.

int   row  (Cell *pCell);
int   col  (Cell *pCell);
int   score(Cell *pCell);
Cell *prev (Cell *pCell);

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

Payoff *payoff_new    (int match, int mismatch, int open, int extend);
void    payoff_DESTROY(Payoff *pPayoff);

int     cell_row      (Cell *pCell);
int     cell_col      (Cell *pCell);
int     cell_score    (Cell *pCell);
Cell   *cell_prev     (Cell *pCell);

Matrix *matrix_new    (char *pszA, char *pszB, Payoff *pPayoff);
void    matrix_DESTROY(Matrix *pMatrix);
void    matrix_score  (Matrix *pMatrix);
void    matrix_dump   (Matrix *pMatrix);
Cell   *matrix_cell   (Matrix *pMatrix, int nRow, int nCol);

От структур к объектам

Давайте взглянем на ситуацию. Мы начали с модуля на Perl Align::NW. Для повышения производительности, мы решили переделать метод score на C. Методу score приходится таскать свои данные с собой, поэтому мы создали три структуры на C. Каждой структуре нужен интерфейс, чтобы мы могли управлять ими из Perl. Кроме этого, эти интерфейсы имеют 11 точек входа. Каждая точка входа нуждается в XS коде для соединения ее с Perl.

Мы могли бы просто установить все 11 точек входа в пакете Align::NW, но теряется структурированность. Вместо этого, мы будем рассматривать каждую структуру как объект, а оставшиеся подпрограммы, которые оперируют ими как методы.

В Perl, пакет предоставляет пространство имен для методов класса. Мы создаем отдельный пакет на каждую структуру, и устанавливаем подпрограммы для каждой структуры в соответствующем пакете. Эти структуры являются частью модуля Align::NW, поэтому мы вкладываем пакеты внутрь пространства имен Align::NW

  • Align::NW::Matrix
  • Align::NW::Cell
  • Align::NW::Payoff

Код XS

Далее, мы напишем код XS для соединения наших подпрограмм C с Perl. Как всегда, мы начинаем с h2xs

.../development>h2xs -A -n Align::NW
.../development>cp score.c Align/NW/
.../development>cp score.h Align/NW/

h2xs генерирует для нас NW.xs

#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

MODULE = Align::NW              PACKAGE = Align::NW

и мы добавляем

#include "score.h"

чтобы подключить наш заголовочный файл.

MODULE и PACKAGE

Теперь рассмотрим директивы MODULE и PACKAGE. Изначально сгенерированное значение MODULE правильное. Значение директивы PACKAGE – нет. Мы, на самом деле, хотим три различных директивы PACKAGE по одной на каждую структуру C. Мы также включаем прототипы для каждого пакета.

MODULE = Align::NW   PACKAGE = Align::NW::Matrix
PROTOTYPES: ENABLE

MODULE = Align::NW   PACKAGE = Align::NW::Cell
PROTOTYPES: ENABLE

MODULE = Align::NW   PACKAGE = Align::NW::Payoff
PROTOTYPES: ENABLE

Для каждого пакета после соответствующей директивы PACKAGE будут размещены xsub’ы. Хотя мы пишем модуль Align::NW, нам не нужна директива PACKAGE со значением Align::NW, потому что мы не устанавливаем никаких xsub’ов в пакете Align::NW.

typemap

Мы сделаем записи в карте типов, чтобы указать xsubpp как происходит конвертирование типов данных между Perl и C. Обзор интерфейса C показывает нам, что на самом деле мы не передаем никакие структуры внутри него, но скорее указатели на структуры. Из обсуждения в предыдущем месяце, мы использовали XS-тип T_PTROBJ для конвертирования указателей на структуры C в объекты Perl.

Cell   *       T_PTROBJ
Matrix *       T_PTROBJ
Payoff *       T_PTROBJ
xsubs

Теперь мы готовы приступить к написанию xsub’ов. Сигнатура для matrix_new это

Matrix *matrix_new(char *pszA, char *pszB, Payoff *pPayoff);

В XS мы пишем следующее

Matrix *
matrix_new(pszA, pszB, pPayoff)
        char   * pszA
        char   * pszB
        Payoff * pPayoff

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

конструктор

Мы хотим вызывать matrix_new как конструктор

$matrix = matrix_new Align::NW::Matrix $a, $b, $payoff;

Когда мы так делаем, Perl передает имя пакета первым аргументом. Мы должны объявить это соглашение, и потом добавить директиву CODE, чтобы мы могли этот аргумент проигнорировать

Matrix *
matrix_new(package, pszA, pszB, pPayoff)
        char   * package
        char   * pszA
        char   * pszB
        Payoff * pPayoff
        CODE:
        RETVAL = matrix_new(pszA, pszB, pPayoff);
        OUTPUT:
        RETVAL
пакет

xsubpp сгенерирует код для установки matrix_new в пакете Align::NW::Matrix, потому что мы разместили xsub для matrix_new после строчки

MODULE = Align::NW   PACKAGE = Align::NW::Matrix

в файле NW.xs. Однако, указатель, который возвращает matrix_new, ассоциирован с пакетом, названным с типом возврата xsub matrix_new. Написано, что этот тип Matrix *, и соответствующий пакет Perl будет MatrixPtr, а не Align::NW::Matrix.

Возникает два вопроса

  • как получить префикс Align::NW::
  • как убрать суффикс Ptr

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

Нам определенно нужен префикс Align::NW::. В противном случае, мы загрязняем вышестоящее пространство имен именами наших структур на C.

Определившись с префиксом и суффиксом, имя пакета получается Align::NW::MatrixPtr. Чтобы ассоциировать наш [указатель] Matrix * с этим пакетом, мы объявляем xsub следующим образом

Align::NW::Matrix *
matrix_new(package, pszA, pszB, pPayoff)
...

Мы можем дополнить наш код на C, добавив typedef в score.h

typedef Matrix Align__NW__Matrix;

Мы хотим, чтобы наши методы были в том же самом пакете, где находятся объекты, поэтому мы изменяем директиву PACKAGE соответственно

MODULE = Align::NW      PACKAGE = Align::NW::MatrixPtr

Все выше сказанное применимо и к структурам Score и Payoff, и мы используем для них соответсвующие псевдонимы typedef и директивы PACKAGE.

Имя метода

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

$matrix = matrix_new Align::NW::MatrixPtr $a, $b, $payoff;

префикс matrix_ выглядит уродливыи и излишним. Более того, у нас имеется метод с именем matrix_DESTROY, который предназначен быть деструктором. Это совсем не будет работать: Perl ожидает, что имя деструктора для объекта Align::NW::MatrixPtr было Align::NW::MatrixPtr::DESTROY, а не Align::NW::MatrixPtr::matrix_DESTROY.

Мы используем директиву PREFIX, чтобы избавиться от префикса matrix_ в коде Perl. Директива PREFIX располагается на той же строчке, где находятся директивы MODULE и PACKAGE. Если мы запишем

MODULE = Align::NW  PACKAGE = Align::NW::MatrixPtr  PREFIX = matrix_

тогда xsubpp удалит строку matrix_ в начале каждого имени xsub перед тем, как ее установить. Таким образом, имя нашего конструктора Align::NW::MatrixPtr::new, поэтому мы можем написать

$matrix = new Align::NW::MatrixPtr $a, $b, $payoff;

Вот финальные версии строк MODULE для наших трех структур C

MODULE = Align::NW  PACKAGE = Align::NW::MatrixPtr  PREFIX = matrix_
  
MODULE = Align::NW  PACKAGE = Align::NW::CellPtr    PREFIX = cell_
  
MODULE = Align::NW  PACKAGE = Align::NW::PayoffPtr  PREFIX = payoff_

Оставшиеся xsub’ы окажутся простыми. Align::NW::PayoffPtr::payoff_new это конструктор, поэтому нам нужна директива CODE, такая же как у Align::NW::MatrixPtr::matrix_new. Для других xsub’ов, все что нам остается сделать это написать их сигнатуры.

Обновление карт типов

Мы изменили имена для наших типов данных, когда мы добавляли префекс Align::NW:: и согласились использовать суффикс Ptr. Мы должны скорректировать записи в карте типов соответсвующим образом

Align::NW::Cell   * T_PTROBJ
Align::NW::Matrix *   T_PTROBJ
Align::NW::Payoff *   T_PTROBJ

Тест

Теперь мы можем скомпилировать и собрать наш модуль. Добавьте ключ OBJECT в вызов WriteMakefile() в Makefile.PL

OBJECT => 'NW.o score.o',

и выполните

.../development/Align/NW>perl Makefile.PL
.../development/Align/NW>make test

Результат должен быть таким

t/nw................ok
All tests successful.

Дистрибутив

Ниже представлены исходники и дистрибутив реализации Align::NW на XS

Остатки модулей

На протяжении 4 месяцев, введение этой статьи обещало о заготовке модуля, который вы могли бы использовать в своих начинаниях при написании XS модулей. Это не удалось сделать. Как всегда, имеется несколько путей, чтобы выполнить задачу. Math::Ackermann, Bit::Vector, и Align::NW показали три различных варианта написания XS модулей. Каждый из них можно использовать в качестве макета для своих модулей.


Заметки

динамического программирования

Вот краткое описание динамического программирования, в виде простейшей задачи.

Aling::NW

Align:: это, наверное, слишком обобщенный термин для высшего уровня имен в CPAN, но адекватное для наших задач. Если бы мы реализовали соответсвующий алгоритм Смита-Ватермана для локального оптимального выравнивания последовательностей, то могли бы назвать его Aling::SW.

dp

dp сокращение для динамического программирования.