リリカル☆Lisp開発日記

前のエントリーで書いたdfa-multi-searchの展開形がメモリを食う原因は、
labelsで作った関数を呼んでいたことみたいです。
インライン化して、ついでに型宣言と最適化オプションもつけたところ、
だいぶ速くなってきました。

;;; CLISP
Real time: 0.427904 sec.
Run time: 0.416979 sec.
Space: 0 Bytes
;;; SBCL
Evaluation took:
0.025 seconds of real time
0.024786 seconds of total run time (0.024786 user, 0.000000 system)
100.00% CPU
37,124,872 processor cycles
0 bytes consed

このあたりまできたら、Cとも張り合えるんじゃないかと思い、
似たようなソースをCで書いてみました。

#include <stdio.h>
#include <string.h>
#include <sys/time.h>
char test_data[4][64] = {"This ''text'' is bold sample.",
"This '''text''' is italic sample.",
"This %%text%% is torikeshi sample.",
"This ((text)) is footnote sample."};
int aho_search (char *str)
{
if (strstr(str, "'''")) {
return 0;
}
else if (strstr(str, "''")) {
return 1;
}
else if (strstr(str, "%%")) {
return 2;
}
else if (strstr(str, "((")) {
return 3;
}
return -1;
}
int baka_search(char *str)
{
int state = 0;
for (;;) {
if (*str == '\'') {
if (state == 1) state = 2;
else if (state == 2) return 0;
else state = 1;
}
else if (state == 2) {
return 1;
}
else if (*str == '%') {
if (state == 11) return 2;
else state = 11;
}
else if (*str == '(') {
if (state == 21) return 3;
else state = 21;
}
else {
state = 0;
}
if (*str == '\0') {
break;
}
str++;
}
return -1;
}

strstrを使ったアホな検索をするaho_search、
出来の悪い状態遷移を使ったbaka_search、
この二つをCLの時と同様に10000回ずつ呼んでみました。
処理系はGCC4.2.1で最適化オプションは無しです。

0.038932sec (aho_search)
0.011319sec (baka_search)

SBCLとならかなりいい勝負になってます。
「いい勝負とか言いながら、2倍以上差がついとるで！」
という意見ももちろんあるでしょうが、
baka_searchみたいな関数を、あまり手書きで書きたくないことも考慮に入れれば、
CLの方が勝っていると言えるだろうという私の独断と偏見を書いておきます(笑)
それにしてもstrstrは速いですね。どうなってるんだろ…
*追記*
CMUCLでも試したら、その速さに驚きました。
ただ、searchはSBCLより遅いみたいです。

;;; CMUCL
* (bench)
;; aho-search
; Evaluation took:
;   0.77 seconds of real time
;   0.756969 seconds of user run time
;   0.0 seconds of system run time
;   1,154,705,100 CPU cycles
;   0 page faults and
;   0 bytes consed.
;; use-dfa
; Evaluation took:
;   0.02 seconds of real time
;   0.017071 seconds of user run time
;   0.0 seconds of system run time
;   29,234,741 CPU cycles
;   0 page faults and
;   0 bytes consed.

This entry was posted on 日曜日, 3月 15th, 2009 at 5:48 PM and is filed under プログラミング. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.