List::Flatten::XS をリリースしました

先日 Okinawa.pm の Slack で複雑なリストのフラット化を行う話で盛り上がりました。（Okinawa.pm の Slack へはこちらから参加できます！）
その中で @yasuXS さんが考案したフラット化のコードがシンプルの上に、フラット化が高速でした。以下がそのコードになります。

use strict;
use warnings;
sub flatten {
    my @args = @_ > 1 ? @_ : @{$_[0]};
    my @result;
    while (@args) {
        my $a = shift @args;
        if (ref $a eq 'ARRAY') {
                unshift @args, @{$a};
        } else {
                push @result, $a;
        }
    }
    return @result;
}

my $arr = [[1,2,3],[4,5,[6,7,[8,9,[1,2,3]]]]];

print flatten($arr);

リストを shift を使って取り出し、もし配列リファレンスなら、デリファレンスして元のリストへ unshift をして、それ以外なら返り値ように用意した変数へ push するといったシンプルなコードです。
これを XS で書き直そうと思い、List::Flatten::XS を作成し始めたんですが、メモリリークで悩んでいたところ、@tompng さんにRuby の flatten のコードを参考にしてはという助言をいただいて、「引数に渡されたレベルに合わせてフラット化する」機能も取り入れました。
以下は Pure Perl と List::Flatten::XS のベンチマークに使ったコードとその結果です。

use strict;
use warnings;
use v5.10;
use Data::Dumper;
use List::Flatten::XS 'flatten';

use Benchmark qw/cmpthese/;


my $arr = [[[[[[[[[[[[1], 2], 3], 4], 5], 6], 7], 8], 9], 1], 2], 3];

cmpthese 0, {
    nonrecursive => sub { flat($arr) },
    xs => sub { flatten($arr) }
};

sub flat {
    my $list = shift;
    my @args = @{$list};
    my @result;
    while (@args) {
        my $a = shift @args;
        if (ref $a eq 'ARRAY') {
            unshift @args, @{$a};
        } else {
            push @result, $a;
        }
    }
    return @result;
}

結果

                 Rate nonrecursive           xs
nonrecursive 117657/s           --         -70%
xs           394824/s         236%           --

約 2 倍の速さは出てるっぽいです。
以下が SYNOPSIS を少し弄ったコードです。ぜひ試してみてください。

#!/usr/bin/env perl

use strict;
use warnings;
use v5.10;
use Data::Dumper;
use List::Flatten::XS 'flatten';
 
my $ref_1 = +{a => 10, b => 20, c => 'Hello'};
my $ref_2 = bless +{a => 10, b => 20, c => 'Hello'}, 'Nyan';
my $ref_3 = bless $ref_2, 'Waon';
 
my $complex_list = [[["foo", "bar", 3], "baz", 5], $ref_1, "hoge", [$ref_2, ["huga", [1], "K"], $ref_3]];
 
# got: ["foo", "bar", 3, "baz", 5, $ref_1, "hoge", $ref_2, "huga", 1, "K", $ref_3];
my $flatted = flatten($complex_list);
say Dumper $flatted;
say "-"x20;

# got: ("foo", "bar", 3, "baz", 5, $ref_1, "hoge", $ref_2, "huga", 1, "K", $ref_3);
my @flatted_with_array = flatten($complex_list);
say Dumper @flatted_with_array;
say "-"x20;

# got: [["foo", "bar", 3], "baz", 5, $ref_1, "hoge", $ref_2, ["huga", [1], "K"], $ref_3]
my $flatted_level = flatten($complex_list, 1);
say Dumper $flatted_level;
say "-"x20;


# got: (["foo", "bar", 3], "baz", 5, $ref_1, "hoge", $ref_2, ["huga", [1], "K"], $ref_3)
my @flatted_level_with_array = flatten($complex_list, 1);
say Dumper @flatted_level_with_array;

最後に

明日は Okinawa.pm #4 です。
そこで XS で得た苦労して知見を共有しようと思います。

github.com