Perl初心者がxsモジュールを作るまで

Random::choiceという、配列から任意数の要素をランダムに取得するモジュール書きました。
https://github.com/nubilum/Random

せっかくxsモジュール書いたので、完成するまでに参考にした資料などをまとめてみます。

1. xsモジュールの雛形作成
   =============================

モジュールの一式を作成する際に、下記のサイトを参考にしました。

◯ h2xs方式
http://d.hatena.ne.jp/higepon/20050615/1118829090

◯minil方式
http://blog.papix.net/entry/2013/06/11/125932

minilはインストールしてなかったので、今回はオーソドックスにh2xsを使いました。

1. CPANのxsモジュールを読む
   =============================

xsモジュールを書く前に、既存のOSSのコード読んどこうと思い、いくつかxsモジュール読みました。
今回は配列操作ということで、List::Utilのコードの

・shuffle（ランダム抽選処理部分）
・pairs（受け取った配列を戻り値用の別配列に詰める処理）

を中心に読みました。

◯Scalar-List-Utils
https://github.com/Scalar-List-Utils/Scalar-List-Utils/blob/master/ListUtil.xs#L707-L732
https://github.com/Scalar-List-Utils/Scalar-List-Utils/blob/master/ListUtil.xs#L778-L815

1. XSモジュールの詳細な仕様を把握する
   =================================

順番逆じゃね？　という気もしますが、大まかなプログラムの流れを把握したあと、
どこでなにしてるのかを知るために、xsモジュールのドキュメントなどを読みました。

◯AV、SVなどxs独特の記法の説明
http://d.hatena.ne.jp/ksmemo/20081221/p2

◯xsの配列操作関係
http://d.hatena.ne.jp/perlcodesample/20100819/1278596435

◯返り値（RETVAL）関係
http://perldoc.jp/docs/perl/5.8.8/perlxs.pod#The32RETVAL32Variable
http://perldoc.jp/docs/perl/5.8.8/perlxs.pod#Returning32SVs44-32AVs32and32HVs32through32RETVAL

◯引数の...をitemsとして扱う挙動について
http://perldoc.jp/docs/perl/5.8.8/perlxs.pod#Variable-length32Parameter32Lists

1. 配列の扱いでハマる
   ===============================

ここまでの情報で大抵の人は目的のものが出来上がってる気がしますが、自分はCを業務で書いたこともないクソエンジニアなので、まだ躓きます。

具体的には下記のコード。

Random.xs

    for ( index = items; index > 1; ) {
        int swap = (int)(Drand01() * (double)(index--)) + i;
        SV *tmp = ST(swap);
        ST(swap) = ST(index);
        ST(index) = tmp;
        
        ST(reti++) = sv_2mortal(newSVsv(tmp));
        
        if (max == reti) {
                break;
            }
    }

やってることは、

・抽選回数分ループさせる
・必要回数の抽選を終えたら処理を終了する
・ループ中、2回同じものが抽選されないように、一度抽選された要素は配列の一番最後のものと入れ替えて、抽選対象から外す
・抽選したものを新しい配列につめて、最終的にreturnする

というシンプルなもの。だがうまく動かない。
printfでデバッグした結果、配列の要素数が全体の半分に達すると、なぜか同じ要素を取ってくるようになってしまうようです。

1. 解決
   ==========================

結論から言うと、下記のコードが問題でした。

Random.xs

        SV *tmp = ST(swap);
        ST(swap) = ST(index);
        ST(index) = tmp;
        ...
        ST(reti++) = sv_2mortal(newSVsv(tmp));

ここで

1. 抽選した要素と、一番最後の配列要素のポインタを入れ替える
2. 戻り値用の配列のn番目に詰める

と処理してるのですが、indexが5,4,3...と減っていくのに対して、retiが0,1,2...と増えていくので、戻り値の配列に結果を詰めている際に、まだ抽選を終えていないitemsのポインタを汚染していたのでした。

0. 渡された引数
num=5、items=(1,2,3,4,5)

1. ランダムで要素を抽選
swap=4

2. ランダム要素と配列の最後を入れ替え
items=(1,2,3,5,4)

3. 結果の配列に詰める
items=(4,2,3,5,4)　←　ここで未抽選の1,2,3,5が汚染され、4,2,3,5に変わってしまう

原因に気づくと問題は単純だったので、「配列の最後と入れ替えて抽選対象から外す」としていた部分を、
「配列の最初と入れ替えて抽選から外す」ように修正しました。

ちなみにメソッド定義部分が「choice(num,...)」だった時、itemsの0番目にはnumが来るので、0番目を
配列の一部として扱わないよう注意しましょう。

Random.xs

    int i;
    int reti = 0;
    int max = SvIV(num);
    int random_scope = items - 1;
    for ( i = 1; i < items; i++ ) {
        int swap = (int)(Drand01() * (double)(random_scope--)) + i;
        SV *tmp = ST(swap);
        ST(swap) = ST(i);
        
        ST(reti++) = sv_2mortal(newSVsv(tmp));
        
        if (max == reti) {
                break;
            }
    }

1. make
   ==================================

動くコードができたら、あとはmake、make test、make installするだけです。
ここらはもう説明不要でしょう。

実際に動かしてみると、同じようなコードをPerlで書いた時との速度差が実感できます。
Perlの速度に限界感じたら書いてみましょう。

enjoy, Perl and xs!