はじめに
Brainfuck は言語仕様が限定的で、プログラムは内容の割には冗長になりがちですが、それをいまどきの最適化コンパイラに掛けたらどんなコードが出力されるのかな? という実験です。
GCC や LLVM に Brainfuck のフロントエンドを用意するというのがスマートな方法とは思うのですが、そんな技術は持ち合わせてはいないので Brainfuck のプログラムを一旦 C のプログラム に変換し、それをコンパイルしてみることとします。
実装
Brainfuck は予約語として '+', '-', ',', '.', '<', '>', '[', ']' の文字のみを識別し、それ以外を無視します。
C で
#define + (*ptr)++;
#define - (*ptr)--;
#define , *ptr = comma();
#define . period(*ptr);
#define < ptr--;
#define > ptr++;
#define [ while (*ptr) {
#define ] }
等マクロを定義し、Brainfuck のプログラムを C に置き換えできればラクチンかと思ったのですが、C のマクロはマクロ名として識別子でないと使用できないのでこの手は使えませんでした。仕方がないので Perl のスクリプトで変換することとしました。
bf2c.pl
#!/usr/bin/perl
print <<END;
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int comma(void) __attribute__((noinline));
int comma(void)
{
int c = getchar();
if (c == EOF) {
exit(0);
}
return c;
}
void period(int c) __attribute__((noinline));
void period(int c)
{
putchar(c);
fflush(stdout);
}
int main(void)
{
uint8_t mem[30000] = {0};
uint8_t* ptr = mem;
END
while (<>) {
s/[^\+,-.<>\[\]]//g;
s/\+/(*ptr)++;/g;
s/-/(*ptr)--;/g;
s/,/*ptr = comma();/g;
s/\./period(*ptr);/g;
s/</ptr--;/g;
s/>/ptr++;/g;
s/\[/while (*ptr) {/g;
s/\]/}/g;
print " " . $_ . "\n";
}
print <<END;
}
END
実行
コマンドラインで
$ ./bf2c.pl program.bf
等とすると、標準出力に C に変換されたコードが出力されます。
https://github.com/pablojorge/brainfuck で公開されてる hello.bf を与えた結果が以下となります。
$ ./bf2c.pl hello.bf
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int comma(void) __attribute__((noinline));
int comma(void)
{
int c = getchar();
if (c == EOF) {
exit(0);
}
return c;
}
void period(int c) __attribute__((noinline));
void period(int c)
{
putchar(c);
fflush(stdout);
}
int main(void)
{
uint8_t mem[30000] = {0};
uint8_t* ptr = mem;
(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;
while (*ptr) {
ptr++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;
ptr++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;
ptr++;(*ptr)++;(*ptr)++;(*ptr)++;
ptr++;(*ptr)++;
ptr--;ptr--;ptr--;ptr--;(*ptr)--;
}
ptr++;(*ptr)++;(*ptr)++;period(*ptr);
ptr++;(*ptr)++;period(*ptr);
(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;period(*ptr);
period(*ptr);
(*ptr)++;(*ptr)++;(*ptr)++;period(*ptr);
ptr++;(*ptr)++;(*ptr)++;period(*ptr);
ptr--;ptr--;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;(*ptr)++;period(*ptr);
ptr++;period(*ptr);
(*ptr)++;(*ptr)++;(*ptr)++;period(*ptr);
(*ptr)--;(*ptr)--;(*ptr)--;(*ptr)--;(*ptr)--;(*ptr)--;period(*ptr);
(*ptr)--;(*ptr)--;(*ptr)--;(*ptr)--;(*ptr)--;(*ptr)--;(*ptr)--;(*ptr)--;period(*ptr);
ptr++;(*ptr)++;period(*ptr);
ptr++;period(*ptr);
}
$
これをコンパイルするにはパイプを使うのが便利です。ついでにプログラムの実行を行った結果を以下に示します。
$ ./bf2c.pl hello.bf | gcc -O2 -xc - -o hello && ./hello
Hello World!
$
コード評価
gcc のコマンドラインに `-S' を指定するとコンパイラの出力コードが確認できます。これを実行した結果が以下です。
$ ./bf2c.pl hello.bf | gcc -O2 -xc - -S -o -
.file ""
.section .text.unlikely,"x"
.LCOLDB0:
.text
.LHOTB0:
.p2align 4,,15
.globl comma
.def comma; .scl 2; .type 32; .endef
.seh_proc comma
comma:
subq $40, %rsp
.seh_stackalloc 40
.seh_endprologue
call __getreent
movq 8(%rax), %rcx
call getc
cmpl $-1, %eax
je .L4
addq $40, %rsp
ret
.L4:
xorl %ecx, %ecx
call exit
nop
.seh_endproc
.section .text.unlikely,"x"
.LCOLDE0:
.text
.LHOTE0:
.section .text.unlikely,"x"
.LCOLDB1:
.text
.LHOTB1:
.p2align 4,,15
.globl period
.def period; .scl 2; .type 32; .endef
.seh_proc period
period:
pushq %rbx
.seh_pushreg %rbx
subq $32, %rsp
.seh_stackalloc 32
.seh_endprologue
movl %ecx, %ebx
call __getreent
movq 16(%rax), %rdx
movl %ebx, %ecx
call putc
call __getreent
movq 16(%rax), %rcx
addq $32, %rsp
popq %rbx
jmp fflush
.seh_endproc
.section .text.unlikely,"x"
.LCOLDE1:
.text
.LHOTE1:
.def __main; .scl 2; .type 32; .endef
.section .text.unlikely,"x"
.LCOLDB2:
.section .text.startup,"x"
.LHOTB2:
.p2align 4,,15
.globl main
.def main; .scl 2; .type 32; .endef
.seh_proc main
main:
subq $40, %rsp
.seh_stackalloc 40
.seh_endprologue
call __main
movl $72, %ecx
call period
movl $101, %ecx
call period
movl $108, %ecx
call period
movl $108, %ecx
call period
movl $111, %ecx
call period
movl $32, %ecx
call period
movl $87, %ecx
call period
movl $111, %ecx
call period
movl $114, %ecx
call period
movl $108, %ecx
call period
movl $100, %ecx
call period
movl $33, %ecx
call period
movl $10, %ecx
call period
xorl %eax, %eax
addq $40, %rsp
ret
.seh_endproc
.section .text.unlikely,"x"
.LCOLDE2:
.section .text.startup,"x"
.LHOTE2:
.ident "GCC: (GNU) 5.4.0"
.def __getreent; .scl 2; .type 32; .endef
.def getc; .scl 2; .type 32; .endef
.def exit; .scl 2; .type 32; .endef
.def putc; .scl 2; .type 32; .endef
.def fflush; .scl 2; .type 32; .endef
$
見るべき箇所は main: 以下で、最適化されたコードが出力されていることがわかります。
main:
subq $40, %rsp
.seh_stackalloc 40
.seh_endprologue
call __main
movl $72, %ecx ; 'H'
call period
movl $101, %ecx ; 'e'
call period
movl $108, %ecx ; 'l'
call period
movl $108, %ecx ; 'l'
call period
movl $111, %ecx ; 'o'
call period
movl $32, %ecx ; ' '
call period
movl $87, %ecx ; 'W'
call period
movl $111, %ecx ; 'o'
call period
movl $114, %ecx ; 'r'
call period
movl $108, %ecx ; 'l'
call period
movl $100, %ecx ; 'd'
call period
movl $33, %ecx ; '!'
call period
movl $10, %ecx ; '\n'
call period
xorl %eax, %eax
addq $40, %rsp
ret
速度比較
時間の掛かるマンデルブロート集合を表示するプログラム を `gcc -O3' でコンパイルした Brainfuck インタプリタで実行した結果が以下です。
$ time brainfuck mandelbrot.bf
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK MKJIJO N R X YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O TN S NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN Q UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU O O PR LLJJJKL OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR RMLMN NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ QPR NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ VX HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ VX HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ QPR NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR RMLMN NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU O O PR LLJJJKL OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN Q UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O TN S NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK MKJIJO N R X YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
real 0m45.795s
user 0m43.171s
sys 0m0.093s
$
これを今回の C に変換する方式で実行した結果が以下となります。gcc の最適化による高速化が際立っています。
$ ./bf2c.pl mandelbrot.bf | gcc -O2 -xc - -o mandelbrot && time ./mandelbrot
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK MKJIJO N R X YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O TN S NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN Q UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU O O PR LLJJJKL OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR RMLMN NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ QPR NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ VX HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ VX HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ QPR NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR RMLMN NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU O O PR LLJJJKL OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN Q UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O TN S NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK MKJIJO N R X YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
real 0m1.501s
user 0m1.078s
sys 0m0.046s
$
追記
ちょっとぐぐったところ、『Optimizing brainfuck compiler』という記事をみつけました。これは、Brainfuck のプログラムを C や Java、Python に変換して実行しようというものですが、各言語処理系での最適化の前に Brainfuck のプログラムから各言語に変換する際に最適化を行い実行効率の向上を試みるというものです。詳しくは記事を参照してくださいというところですが、簡単に説明すると、例えば本稿の『速度比較』で動作させてるマンデルブロート集合を表示するプログラムでは、
[-]
という記述が 124箇所あります。これは C で表現すると
while (*ptr) {
(*ptr)--;
}
と同等です。*ptr の値が 0 になるまで *ptr の値をデクリメントするということで、
*ptr = 0;
に最適化可能です。
同様に、
[->>>>>>>>>+<<<<<<<<<]
という記述は 23箇所あります。これは C で表現すると
while (*ptr) {
(*ptr)--;
ptr += 9;
(*ptr)++;
ptr -= 9;
}
と同等で、*ptr の値が 0 になるまで *ptr の値をデクリメントし、*(ptr + 9) の値をインクリメントするというものです。これは
ptr[9] += ptr[0];
ptr[0] = 0;
と最適化可能です。
『Optimizing brainfuck compiler』ではこのような最適化手法を駆使し、C 言語で 4割程の実行時間の削減に成功している模様です。本記事は Brainfuck の冗長なプログラムをいまどきの C コンパイラの最適化に任せたらどうなるだろうという試みであり趣旨が異なりますが、興味深い内容なのでいずれパク取り組んでみたいと思います。
とりあえずの試しとして頭の悪い対応をしてみたのですが
$ cat bf2c.pl
#!/usr/bin/perl
print <<END;
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int comma(void) __attribute__((noinline));
int comma(void)
{
int c = getchar();
if (c == EOF) {
exit(0);
}
return c;
}
void period(int c) __attribute__((noinline));
void period(int c)
{
putchar(c);
fflush(stdout);
}
int main(void)
{
uint8_t mem[30000] = {0};
uint8_t* ptr = mem;
END
$all="";
while (<>) {
s/[^+,-.<>\[\]]//g;
$all.=$_;
}
$_=$all;
s/\[-\]/*ptr = 0;\n/g;
s/\[->\+<\]/*(ptr P 1) P= *ptr; *ptr = 0;\n/g;
s/\[->-<\]/*(ptr P 1) M= *ptr; *ptr = 0;\n/g;
s/\[-<\+>\]/*(ptr M 1) P= *ptr; *ptr = 0;\n/g;
s/\[-<->\]/*(ptr M 1) M= *ptr; *ptr = 0;\n/g;
s/\[->>\+<<\]/*(ptr P 2) P= *ptr; *ptr = 0;\n/g;
s/\[->>-<<\]/*(ptr P 2) M= *ptr; *ptr = 0;\n/g;
s/\[-<<\+>>\]/*(ptr M 2) P= *ptr; *ptr = 0;\n/g;
s/\[-<<->>\]/*(ptr M 2) M= *ptr; *ptr = 0;\n/g;
s/\[->>>\+<<<\]/*(ptr P 3) P= *ptr; *ptr = 0;\n/g;
s/\[->>>-<<<\]/*(ptr P 3) M= *ptr; *ptr = 0;\n/g;
s/\[-<<<\+>>>\]/*(ptr M 3) P= *ptr; *ptr = 0;\n/g;
s/\[-<<<->>>\]/*(ptr M 3) M= *ptr; *ptr = 0;\n/g;
s/\[->>>>\+<<<<\]/*(ptr P 4) P= *ptr; *ptr = 0;\n/g;
s/\[->>>>-<<<<\]/*(ptr P 4) M= *ptr; *ptr = 0;\n/g;
s/\[-<<<<\+>>>>\]/*(ptr M 4) P= *ptr; *ptr = 0;\n/g;
s/\[-<<<<->>>>\]/*(ptr M 4) M= *ptr; *ptr = 0;\n/g;
s/\[->>>>>\+<<<<<\]/*(ptr P 5) P= *ptr; *ptr = 0;\n/g;
s/\[->>>>>-<<<<<\]/*(ptr P 5) M= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<\+>>>>>\]/*(ptr M 5) P= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<->>>>>\]/*(ptr M 5) M= *ptr; *ptr = 0;\n/g;
s/\[->>>>>>\+<<<<<<\]/*(ptr P 6) P= *ptr; *ptr = 0;\n/g;
s/\[->>>>>>-<<<<<<\]/*(ptr P 6) M= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<<\+>>>>>>\]/*(ptr M 6) P= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<<->>>>>>\]/*(ptr M 6) M= *ptr; *ptr = 0;\n/g;
s/\[->>>>>>>\+<<<<<<<\]/*(ptr P 7) P= *ptr; *ptr = 0;\n/g;
s/\[->>>>>>>-<<<<<<<\]/*(ptr P 7) M= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<<<\+>>>>>>>\]/*(ptr M 7) P= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<<<->>>>>>>\]/*(ptr M 7) M= *ptr; *ptr = 0;\n/g;
s/\[->>>>>>>>\+<<<<<<<<\]/*(ptr P 8) P= *ptr; *ptr = 0;\n/g;
s/\[->>>>>>>>-<<<<<<<<\]/*(ptr P 8) M= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<<<<\+>>>>>>>>\]/*(ptr M 8) P= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<<<<->>>>>>>>\]/*(ptr M 8) M= *ptr; *ptr = 0;\n/g;
s/\[->>>>>>>>>\+<<<<<<<<<\]/*(ptr P 9) P= *ptr; *ptr = 0;\n/g;
s/\[->>>>>>>>>-<<<<<<<<<\]/*(ptr P 9) M= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<<<<<\+>>>>>>>>>\]/*(ptr M 9) P= *ptr; *ptr = 0;\n/g;
s/\[-<<<<<<<<<->>>>>>>>>\]/*(ptr M 9) M= *ptr; *ptr = 0;\n/g;
s/\+/(*ptr)++;/g;
s/-/(*ptr)--;/g;
s/,/*ptr = comma();/g;
s/\./period(*ptr);/g;
s/</ptr--;/g;
s/>/ptr++;/g;
s/\[/while (*ptr) {/g;
s/\]/}/g;
tr/PM/+-/;
print " " . $_ . "\n";
print <<END;
}
END
$ ./bf2c.pl mandelbrot.bf | gcc -O2 -xc - -o mandelbrot && time ./mandelbrot
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK MKJIJO N R X YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O TN S NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN Q UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU O O PR LLJJJKL OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR RMLMN NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ QPR NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ VX HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ VX HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ QPR NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR RMLMN NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU O O PR LLJJJKL OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN Q UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O TN S NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK MKJIJO N R X YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
real 0m1.111s
user 0m0.765s
sys 0m0.015s
$
お、ちょっと速くなった。