benchmark.pl 2016 Winter – ベンチマークから考える効率的なロジック

※このエントリはPerl5 Advent Calendar 2016 第13日目のエントリです。

どーも、わいとんです。

タイトルはイベント名っぽくすることで、このエントリを毎年恒例にしていくぞ、という心構えを形にしたもので、特に大きな意味はありません。

効率的なロジック。プログラムを書くときに、突き詰めていくと気になってきますよね。

そんな時、自分の書いたコードに対してベンチマークを取ったりすることかと思います。

ベンチマークを取る?

早い話が「処理速度を測定する」ってことです。こう書いてしまえば身も蓋もないですねw

Perlでベンチマークを取るには

CPANにはBenchmarkというそのものズバリなネーミングのモジュールが存在します。

Benchmarkは、perl-5.004の頃からコアモジュールに含まれており(つまりperlが使える環境ならBenchmarkも使える)、時代の流れとともに進化してきた経緯があります。

基礎的なケースのベンチマーク

どんなプログラムも、基礎の組み合わせで成り立っています。今回は基礎的なケースをいくつか例に実際にベンチマークをとって、より効率的なロジックの模索をしていきたいと思います。

なお、ベンチマークは以下の環境(MacOSX + plenv + perl-5.24.0)で実施しました。基礎的なケースばかりですので環境ごとの揺らぎはほぼないと思いますが、念のため参考としてください。

$ perl -v

This is perl 5, version 24, subversion 0 (v5.24.0) built for darwin-2level
(with 1 registered patch, see perl -V for more detail)

Copyright 1987-2016, Larry Wall

Perl may be copied only under the terms of either the Artistic License or the
GNU General Public License, which may be found in the Perl 5 source kit.

Complete documentation for Perl, including FAQ lists, should be found on
this system using "man perl" or "perldoc perl".  If you have access to the
Internet, point your browser at http://www.perl.org/, the Perl Home Page.

配列への一括処理

ベンチマークのために書いたスクリプトは以下の通りです。

use strict;
use warnings;
use Benchmark ':all';
use Test::More;

## 処理対象となる配列
my @list = (0 .. 10000);


## 各パターンの定義

#- 配列でforを回してpushするタイプ
my $for_array_push = sub {
    my @result;
    for my $row (@list) {
        push @result, "num=".$row;
    }
    return @result;
};

#- 配列インデックスでforを回して直接インデックス指定して代入するタイプ。
my $for_array_index = sub {
    my @result;
    for my $i (0 .. $#list) {
        $result[$i] = "num=".$list[$i];
    }
    return @result;
};

#- Cスタイルのforで直接インデックス指定して代入するタイプ。
my $for_cstyle_index = sub {
    my @result;
    for (my $i=0; $i<=$#list; $i++) {
        $result[$i] = "num=".$list[$i];
    }
    return @result;
};

#- forを使わないでmapで写像を得るタイプ
my $mapping = sub {
    return map { "num=".$_ } @list;
};

## for_array_push を基準に、各パターンが同じ出力になることを確認する
is_deeply [$for_array_push->()], [$for_array_index->()], 'for_array_push eq for_array_index';
is_deeply [$for_array_push->()], [$for_cstyle_index->()], 'for_array_push eq for_cstyle_index';
is_deeply [$for_array_push->()], [$mapping->()], 'for_array_push eq mapping';

## 処理時間の測定
my $result = timethese(10000, {
    'for_array_push'   => $for_array_push,
    'for_array_index'  => $for_array_index,
    'for_cstyle_index' => $for_cstyle_index,
    'mapping'          => $mapping,
});

## 測定結果の比較表示
cmpthese($result);

## テスト完了
done_testing();

for_array_push for_array_index for_cstyle_index mapping の4つのパターンを用意し、それぞれ同じ結果となることを is_deeply で確認してから timethese で速度測定。最後に cmpthese で測定結果の比較を表示しています。

なおこのスクリプトはperlで実行可能ですので、手元でもお試しいただけます。

結果はmapping圧勝

以下、実行結果です。

$ perl ./loop.pl
ok 1 - for_array_push eq for_array_index
ok 2 - for_array_push eq for_cstyle_index
ok 3 - for_array_push eq mapping
Benchmark: timing 10000 iterations of for_array_index, for_array_push, for_cstyle_index, mapping...
for_array_index: 25 wallclock secs (24.37 usr +  0.01 sys = 24.38 CPU) @ 410.17/s (n=10000)
for_array_push: 23 wallclock secs (22.86 usr +  0.02 sys = 22.88 CPU) @ 437.06/s (n=10000)
for_cstyle_index: 31 wallclock secs (31.14 usr +  0.05 sys = 31.19 CPU) @ 320.62/s (n=10000)
mapping:  6 wallclock secs ( 6.09 usr +  0.03 sys =  6.12 CPU) @ 1633.99/s (n=10000)
                Rate for_cstyle_index for_array_index for_array_push  mapping
for_cstyle_index  321/s               --            -22%           -27%     -80%
for_array_index   410/s              28%              --            -6%     -75%
for_array_push    437/s              36%              7%             --     -73%
mapping          1634/s             410%            298%           274%       --
1..3

Cスタイルでの書き方に比べて、mapを使った書き方はなんと4.1倍も速いのがわかりますね。

このことから、配列を全件処理して別の配列を作る場合はmapを使うと速くて短く書ける、という結論が得られました。

ただ注意して欲しいのは、配列を全件処理するだけ(つまり別の配列を作らない)場合にmapを使うことは、可読性という面では好ましくないと考えます(ループ処理だけしたいのか、加工された配列が欲しいのか判断がつかない)。そういうケースでは for my $row (@list) {...} のやり方のほうが意図が読み取りやすいですね。

条件分岐

こちらのベンチマークコードは以下の通りです。

use strict;
use warnings;
use Benchmark ':all';
use Test::More;

## 処理対象の配列
my @list = map {[int(rand(6)+1), int(rand(6)+1)]} 1..10000;

## 処理パターン定義

#- if/elsif/elseを使った条件分岐
my $if_else = sub {
    map {
        if    ($_->[0] == $_->[1])      {1}
        elsif ($_->[0] + $_->[1] >= 10) {2}
        else {0}
    } @list;
};

#- 三項演算子を使った条件分岐
my $ternary = sub {
    map {
        $_->[0] == $_->[1]       ? 1 :
        $_->[0] +  $_->[1] >= 10 ? 2 :
        0;
    } @list;
};

#- ハッシュを使った分岐
my $map = {
    '1:1' => 1, '2:2' => 1, '3:3' => 1,
    '4:4' => 1, '5:5' => 1, '6:6' => 1,
    '4:6' => 2, '5:6' => 2,
    '6:4' => 2, '6:5' => 2,
};
my $hashmap = sub {
    map { $map->{join(':', $_->[0], $_->[1])} || 0 } @list;
};

## if_elseパターンを基準に同一性の担保をする
is_deeply [$if_else->()], [$ternary->()], 'if_else eq ternary';
is_deeply [$if_else->()], [$hashmap->()], 'if_else eq hashmap';

## 速度計測
my $result = timethese(10000, {
    if_else => $if_else,
    ternary => $ternary,
    hashmap => $hashmap,
});

## 結果比較
cmpthese($result);

## テスト完了
done_testing();

if_else ternary hashmap の3つのパターンを用意し、それぞれ同じ結果となることを is_deeply で確認してから timethese で速度測定。最後に cmpthese で測定結果の比較を表示しています。

なおこちらもコピペで実験できます。

三項演算子は速い

こちらが実行結果です。

$ perl ifelse.pl
ok 1 - if_else eq ternary
ok 2 - if_else eq hashmap
Benchmark: timing 10000 iterations of hashmap, if_else, ternary...
hashmap: 18 wallclock secs (18.45 usr +  0.01 sys = 18.46 CPU) @ 541.71/s (n=10000)
if_else: 20 wallclock secs (19.80 usr +  0.05 sys = 19.85 CPU) @ 503.78/s (n=10000)
ternary: 13 wallclock secs (12.22 usr +  0.03 sys = 12.25 CPU) @ 816.33/s (n=10000)
        Rate if_else hashmap ternary
if_else 504/s      --     -7%    -38%
hashmap 542/s      8%      --    -34%
ternary 816/s     62%     51%      --
1..2

目に見えて三項演算子が速いですね。可読性はよろしくないので、使いどころは単純な二分岐にとどめておいたほうが良いと思いますが、変数代入の判断基準のための二分岐にはもってこいと言えそうです。

まとめ

今回は基本的なケースでのベンチマークを試しました。

時代が進んでperlのインターナルな実装に手が入った時、どういうロジックが速くなるのか、ということは都度ベンチマークをする必要があります。そのため、「現時点ではこのくらいの感じなんだなぁ」という程度に参考にしてもらえると幸いです。