N-QueenをXSを使って実装してみた

とりあえず実装してみた

まずは Makefile.PLの作成

use strict;
use ExtUtils::MakeMaker;

WriteMakefile (
    NAME => 'Solver::NQueen::XS',
    VERSION_FROM => 'lib/Solver/NQueen/XS.pm',
);

次にモジュールファイルの作成.
モダンPerl入門のまま.

package Solver::NQueen::XS;
use strict;
use warnings;
use XSLoader;

our $VERSION = '0.00001';

XSLoader::load __PACKAGE__, $VERSION;

1;

次に .xsファイルの作成. SVとかAVとかを積極的に使うことは
ちょっとまだできないですが、今回は int型の解を返したいだけ
なので普通の Cにほぼ等しいですね。

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

void nqueen_sub(int n, int now, int *array, int *answer);

int nqueen(int size)
{
        int array[32];
        int answer;

        answer = 0;
        nqueen_sub(size, 0, array,  &answer);

        return answer;
}

void nqueen_sub(int n, int now, int *array, int *answer)
{
    int i, j;
    int flag;

    for (i = 0; i < n; i++) {
        flag = 1;

        for (j = 0; j < now; j++) {
            if (i == array[j]) {
                flag = 0;
                break;
            }

            if (i - (now - j) == array[j]) {
                flag = 0;
                break;
            }

            if (i + (now - j) == array[j]) {
                flag = 0;
                break;
            }
        }

        if (flag == 1) {
            array[now] = i;
            if (now == n - 1) {
                (*answer)++;
            } else {
                nqueen_sub(n, now + 1, array, answer);
            }
        }
    }
}

MODULE = Solver::NQueen::XS PACKAGE = Solver::NQueen::XS

PROTOTYPES: DISABLED

int
nqueen(size)
           int size

構築をする。

 % perl Makefile.PL
 % make

結構エラーが出て意味わからね〜ってなりましたけど、よくよく
見るとパッケージ名が間違っているとかそんなんでした。

で、ベンチマーク。コードは以下のような具合です

#!/usr/bin/perl
use strict;
use warnings;

use lib  qw(../lib);
use blib qw(../blib);
use Benchmark qw(cmpthese);

use Solver::NQueen::Pure qw(nqueen);
use Solver::NQueen::XS;

cmpthese(-10, {
    Pure => sub { Solver::NQueen::Pure::nqueen(8) },
    XS   => sub { Solver::NQueen::XS::nqueen(8)},
});

平等にするために, PurePerlの方も関数スタイルにしました。
オブジェクト版で計測したらすごく差が出て、何かの間違いなのかな
って思って関数版にしてみたんだけど、結局ずいぶん差がでました.

以下結果です

       Rate   Pure     XS
Pure 21.9/s     --   -99%
XS   3225/s 14608%     --

146倍 XS版の方が早い.
ここまで差が出るものなのかな？どこか間違ってるんじゃないかって
思いたくなるほどですね。素直に受け取るなら, これは書く価値がある
な〜ってなりますね。Cライブラリのバインディングが主なものかと
思っていたんですけど、速度面でも大きなものが得られるんですね.

感想. XSって書いたことなかったけど, ただ Cの関数を呼ぶだけで
あるならば簡単に使えることがわかった. SV, AV, HVなどを積極的に
利用するとなると perlapiとか perlgutsの内容を理解していないと
いけないんでしょうけど, それはこれからというところですね.
その辺を理解して, もうちょっと複雑なものにチャレンジしたいです.
あと既存の Cライブラリのバインディングも作成してみたいですね.
誰かが CPANにあげている可能性が高そうですけど、練習ということで
やってみたいです

なお環境は
Ubuntu 9.04 Linux Kernel 2.6.28.15
Core2duo 2.2GHz Memory 3GHz

修正した Pure Perlの実装

package Solver::NQueen::Pure;

require Exporter;
@ISA       = qw(Exporter);
@EXPORT_OK = qw(nqueen);

sub nqueen {
    my $size = shift;
    my $answer = 0;

    _nqueen_sub($size, 0, [], \$answer);

    return $answer;
}

sub _nqueen_sub {
    my ($size, $now, $array_ref, $answer_ref) = @_;

    for ( my $i = 0; $i < $size; $i++ ) {
        my $flag = 1;

        for ( my $j = 0; $j < $now; $j++) {
            my $pos = $array_ref->[$j];

            if ($i == $pos) {
                $flag = 0;
                last;
            }

            if ($i - ($now - $j) == $pos) {
                $flag = 0;
                last;
            }

            if ($i + ($now - $j) == $pos) {
                $flag = 0;
                last;
            }
        }

        if ($flag == 1) {
            $array_ref->[$now] = $i;
            if ($now == $size - 1) {
                ${$answer_ref}++;
            } else {
                _nqueen_sub($size, $now + 1, $array_ref, $answer_ref);
            }
        }
    }
}

1;