#:g1: Common Lispでこれより速いtaraiの書き方があったら教えて欲しい

Posted 2022-09-15 20:38:15 GMT

こちらの記事のtaraiを使ったマイクロベンチでCommon Lispが登場しているのですが、gcc等はインライン展開で高速化されています。
ということで、Common Lispでもインライン展開されるようなコードをコメントしたのですが、恐らくコメントがスパム箱行きかなにかになって届かないようなので自分のブログに書くことにしました。 コメント拾って頂けました! ありがとうございます🙇

とりあえずインライン展開するようなコードですが、sbclの--scriptで処理するならこんなところでしょうか。

(defun tarai (x y z)
  (declare (optimize (speed 3) (debug 0) (safety 0)))
  (labels ((tarai (x y z)
             (declare (fixnum x y z))
             (the fixnum
                  (if (> x y)
                      (tarai (tarai (1- x) y z)
                             (tarai (1- y) z x)
                             (tarai (1- z) x y))
                      y))))
    (declare (inline tarai))
    (tarai x y z)))

(compile 'tarai)

(princ (time (tarai 14 7 0))) (terpri)

計時

SBCL 1.4.8 / Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz

Evaluation took:
  0.648 seconds of real time
  0.650000 seconds of total run time (0.650000 user, 0.000000 system)
  100.31% CPU
  2,134,123,542 processor cycles
  0 bytes consed

14

SBCL 2.2.3 / Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz

Evaluation took:
  0.710 seconds of real time
  0.710000 seconds of total run time (0.710000 user, 0.000000 system)
  100.00% CPU
  2,310,773,613 processor cycles
  0 bytes consed

14

なぜか新しいSBCL 2.2.3の方が遅いようですが何故なのか。

Cとの比較

さて基準となるCとの比較ですが、こんな感じに書きました。
cl-benchの形式で結果出力させています。

#include <stdio.h>
#include <time.h>

struct BenchTime {
  char* name;
  double real_time;
  double user_time;
  int sys;
  int consed;
};

struct BenchTime bench_time(void (*fctn)(void), int times, char *name) { struct timespec begin_time, end_time;

clock_gettime(CLOCK_REALTIME, &begin_time); for (int i=0; i<times; i++ ) { fctn(); } clock_gettime(CLOCK_REALTIME, &end_time);

float dur = end_time.tv_sec - begin_time.tv_sec + (float)(end_time.tv_nsec - begin_time.tv_nsec) / 1000000000; struct BenchTime bt = {name, dur, dur, 0, 0}; return bt; }

void run(char *name, int times, void(*fctn)(void)) { struct BenchTime bt = bench_time(fctn, times, name); printf(";;; running #<benchmark %s for %d runs>\n", name, times); printf("(\"%s\" %f %f %d %d)\n", bt.name, bt.real_time, bt.user_time, bt.sys, bt.consed); }

int tarai(int x, int y, int z) { if (x > y) { return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)); } else { return y; } }

void run_tarai() { tarai(14, 7, 0); }

int main(void) { #ifdef __clang__ printf("(\"clang %d.%d\"\n", __clang_major__, __clang_minor__); #elif __GNUC__ printf("(\"gcc %d.%d\"\n", __GNUC__, __GNUC_MINOR__); #else printf("cc\n"); #endif run("TARAI", 1, &run_tarai); printf(")\n"); return 0; }

clan 14.0 / Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz

clang -O3 tarai.c -o tarai_clang && ./tarai_clang
("clang 14.0"
;;; running #<benchmark TARAI for 1 runs>
("TARAI" 0.792847 0.792847 0 0)
)

sbclはclangには勝ちました!

gcc 12.0 / Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz

gcc -O3 tarai.c -o tarai_gcc && ./tarai_gcc
("gcc 12.2"
;;; running #<benchmark TARAI for 1 runs>
("TARAI" 0.419369 0.419369 0 0)
)

しかし、gccがやたら速い!!

まとめ

sbclはclangには勝ちましたが、gccには負けました。
gccは、fibの場合は、-O3を付けると-O2より遅くなったりしますが、taraiだと-O3を付けるとかなり速くなります。
一体どんな最適化が発動しているのだろう……。調べてみてCommon Lispで真似できるなら真似してみたいところです。

関連


HTML generated by 3bmd in LispWorks 7.0.0

comments powered by Disqus