10 億回のループ

アルゴリズムコンテストの挑み方というところを見ていて、C 言語であれば大体どのくらいで 10 億回のループを計算できるかが想像できたのですが、awk が C 言語と比較してどのくらい低速なのかが分からなかったので取り上げてみます。

アルゴリズムコンテストの挑み方に掲載されているコードと同じものを awk で組んでみます。 awk は C 言語とほぼ同じ機能を用い、ほぼ同じアルゴリズムで組むことができるのも特徴のひとつと言えるでしょう。

#! /usr/bin/gawk -f
# 1_billion_calculation.awk

BEGIN {
    if (ARGC >= 2) {
        sum = 0;

        n = ARGV[1];                # n := コマンドの第一引数
        for (i = 0; i < n; ++i)     # 0 から n-1 まで足し算
            sum += i;
        printf("%d\n", sum);
    }
}

さて、これを実行してみますが、ここでは nawk, mawk, gawk の 3 種類の awk で試してみます。

$ gawk -f 1_billion_calculation.awk 1000000000
499999999067108992
gawk -f 1_billion_calculation.awk 1000000000  134.75s user 0.20s system 98% cpu 2:16.37 total
$ time mawk -f 1_billion_calculation.awk 1000000000
2147483647
mawk -f 1_billion_calculation.awk 1000000000  92.54s user 0.13s system 99% cpu 1:33.10 total
$ time nawk -f 1_billion_calculation.awk 1000000000
-2147483648
nawk -f 1_billion_calculation.awk 1000000000  195.64s user 0.62s system 99% cpu 3:17.94 total

正確に計算結果を出しているのは gawk だけのようですが、これは gawk が 53 bit 程度の精度で計算しているからです。 それ以外の awk は 32 bit を越えると正確に計算できていません。

今回の話題は、そこではなく、速度に着目します。 mawk が非常に高速に処理していることが分かりますが、gawk が構文木を愚直に再帰的に解釈していくのに対してバイトコードに変換していくため、高速に動作します。 nawk は互換性を優先させているため、低速だとどこかで聞いた覚えがあります。

では、C 言語で計算させてみましょう。

$ gcc 1_billion_calculation.c
$ time ./a.out 1000000000
499999999500000000
./a.out 1000000000  3.83s user 0.01s system 99% cpu 3.863 total

(値は丸まっているようですが) 非常に高速に計算できています。 これが C 言語と awk の速度差なのです。

ちなみに Perl は得意ではありませんが、以下のスクリプトで実行してみました。

#! /usr/bin/perl
# 1_billion_calculation.pl

use strict;
use warnings;

if (@ARGV > 0) {
    my $sum = 0;

    my $n = $ARGV[0];
    my $i;
    for ($i = 1; $i < $n; ++$i) {
        $sum += $i;
    }
    printf("%d\n", $sum);
}

結果は思いの外、遅くなってしまいました。

$ time perl 1_billion_calculation.pl 1000000000
-1
perl 1_billion_calculation.pl 1000000000  322.40s user 0.44s system 98% cpu 5:26.19 total

というわけで、このあたりが LL と C 言語の速度の壁なのではないでしょうか。 もっとも、Perl などでもっと高速に動作させることは可能かもしれませんが、見た目のコードの互換性を重視させていただきました。