福野泰介の一日一創 - create every day

アルゴリズムの工夫や、マシン語化で速くなることを体験しました。 今回、それぞれ実測してみましょう。

まずはシンプルに引き算を続けるBASIC版から、CLTとTICK()を使って計測します。コンピューターくんへの課題は「10000/7」とします。

10 N=10000 20 M=7 25 CLT 30 A=0 40 N=N-M:IF N>=0 A=A+1:CONT 50 N=N+M 55 ?TICK() 60 ?A;"...";N RUN 370 1428...4

BASICでは369、TICK()は1秒間に60進むので、6.1秒です。(IchigoJam上で10倍して60で割ると小数1位まで計算できます。また、IchigoJamのバージョンによって数は変わります)

?3690/60 61

BASIC筆算版はどのくらい速いでしょう?

10 N=10000 20 M=7 25 CLT 30 A=0 40 FOR I=10 TO 0 STEP -1 50 L=M<<I 60 IF N>=L N=N-L:A=A+1<<I 70 NEXT 75 ?TICK() 80 ?A;"...";N RUN 5 1428...4

なんと、0.08秒(5/60秒)。73倍も速くなってます。アルゴリズムって大事ですね。

続いて、マシン語の単純ループ版。

POKE#700,7,33,2,70,0,32,1,48,82,26,252,218,2,56,81,24,112,71 OK CLT:U=USR(#700,10000):?TICK() 0

0、つまり1/60秒未満。この時点で単純ループ版でもBASIC筆算版を上回る速度がでていることがわかります。 ただ、0ではどのくらい速いかわからないので、ループを使います。

CLT:FORI=1TO1000:U=USR(#700,10000):NEXT:?TICK() 283

1000回で283、4.7秒でした。・・・が、待ってください。BASICの処理で時間がかかっているかもしれません。そこで何もせず帰ってくるだけのマシン語(=RET #4770)でも測ります。

[0]=#4770:CLT:FORI=1TO1000:U=USR(#800,10000):NEXT:?TICK() 264 ?283-264 19

やはり、ほとんどがBASICの処理時間でした。差分は19、0.31秒/1000回。1回あたり310マイクロ秒(=0.31ミリ秒)、BASIC版の2万倍も速いことがわかります。

次に、マシン語筆算版を計測してみます。

POKE#700,7,33,16,181,2,70,0,32,1,35,27,4,12,70,92,67,162,66,1,219,18,27,24,68,91,8,247,209,17,70,16,189 OK CLT:FORI=1TO1000:U=USR(#700,10000):NEXT:?TICK() 264 ?264-264 0

速すぎて、差分が0になってしまいました。ループ回数を10倍の10000回にして比較します。

[0]=#4770:CLT:FORI=1TO10000:U=USR(#800,10000):NEXT:?TICK() 2643 CLT:FORI=1TO10000:U=USR(#700,10000):NEXT:?TICK() 2648 ?2648-2643 5 ?5*1000/60 83

10000回で0.083秒。つまり1回あたり8.3マイクロ秒。ループ版から37倍、速くなりました。
BASIC筆算版の約1万倍速と、高速化具合は似たようなものですね。

まとめ
1. アルゴリズムによる速度差は環境を変えても変わらない(工夫の価値)
2. 遅いアルゴリズムでも言語や環境を変えるとなんとかなってしまう(力技)

いくらコンピューターが高速化しようとも、同じ環境上でいかにアルゴリズムの工夫で高速化できるかが、電気代やサーバー台数など、かかる費用に直結します。 また、同じ機能のアプリなら、サクサク快適に動く方がうれしいですよね? これが流行る流行らないの決定的な差になったりします。アルゴリズム、大事。

アルゴリズムなど理論ばかり見ていてもどう使えるのかイメージが沸かずつまらないし、プログラミング言語の文法だけ学んでもアルゴリズムが弱いとせっかくのパワーが活かせません。

IchigoJam BASICのスピードは、アルゴリズム変更が人間にとってリアルにコンピューターを体感できる速度域。入門時の学習がむしろ、手軽で速いはず。

アルゴリズムやコンピューターを学ぶコツをさえ身に着けたら、数億倍速い環境が待ってます。
世界中にある様々な課題、新しい問題解決手法(アルゴリズム)を創りましょう!
Enjoy to create own Algorithm with Computers!

- 連載、IchigoJamではじめる、Armマシン語入門
1. はじめてのマシン語
2. ハンドアセンブルで超速計算!
3. マシン語メモリアクセスで画面超速表示!
4. マシン語でLEDを光らせよう!
5. 楽しさ広がるマルチバイトメモリアクセスとスタック
6. マシン語使いこなしTIPS
7. カジュアルに使うインラインマシン語
8. アセンブラを使って楽しよう
9. マシン語で高速SPI
10. マシン語を制するもの時間を制す
11. 画面をイチゴで埋め尽くす12の方法
12. レジスタ不足に上位レジスタとスタック操作
13. コンパイラはじめのいっぽ、EVAL実現法とマシン語生成
14. サイズを取るかスピードを取るか、割り算のアルゴリズムとマシン語実装
15. マシン語化で1万倍速!? セットで学ぶアルゴリズムとコンピューター

Tweet
クリエイティブ・コモンズ・ライセンス
この作品は「Creative Commons — CC BY 4.0」の下に提供されています。
CC BY 福野泰介 - Taisuke Fukuno / @taisukef / アイコン画像 / プロフィール画像