Judy

練習がてら、Judyの記事を書き写しておきます。

弾さんのところで、C言語用のmemoizeライブラリ"Judy"が紹介されていました。
http://blog.livedoor.jp/dankogai/archives/50707970.html

ここにかかれているサンプルは、snprintfを使っているため、オーバーヘッドが多いような気がしたので、すこし書き換えてみました。

とりあえず、サイクル数を計ってみました。
rdtscで計っているので、他ののプロセスの影響を多少受けています。
そのため、サイクル数は平均で示してあります。
(rdtsc については、こちら http://www.super-computing.org/sr8000/timer.html )

キーの作成と一致比較の部分のみを計測しています。
以下のソースは、mtak関数のみを示してあります。

int mtak(int x, int y, int z){
    unsigned long long t1,t2;
    Word_t *pvalue, value;
    uint8_t key[KEYLEN];
    count++;
    RDTSC(t1);
    snprintf((char *)key, KEYLEN, "%d,%d,%d", x, y, z);
    JSLG(pvalue, PJSLArray, key);
    if (pvalue != NULL){
	RDTSC(t2);
	printf("elapsed tsc=%lld\n",t2-t1);
	return (int)*pvalue;
    }
    RDTSC(t2);
    printf("elapsed tsc=%lld\n",t2-t1);
    value = (x <= y) ? y : mtak( mtak (x-1, y, z),
	    mtak (y-1, z, x),
	    mtak (z-1, x, y) );
    pvalue = &value;
    JSLI(pvalue, PJSLArray, key);
    return value;
}

以下のパラメータで実行しました。

./judy-tak-rdtsc 10 5 0

出てきた数字をawkでまとめたところ、以下のようになりました。

一致比較の回数：249回
平均：4880.84サイクル

やはり、sprintnfのせいで、だいぶ重くなっています。
Judyには、いろいろな関数（マクロ）があるようなので、ちょっと
遊んでみました。

http://judy.sourceforge.net/doc/JudyHS_3x.htm

先ほどのは、JudySLという文字列をキーにするものでしたが、
ここではJudyHSという長さが指定された配列をキーにするものを
使ってみます。

弾さんのソースを元に、書き換えてみました。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <Judy.h>
#define KEYLEN 3

static int count = 0;
Pvoid_t PJHSArray = (Pvoid_t) NULL; // initialize JudySL array

int mtak(int x, int y, int z){
    Word_t *pvalue, value;
    uint8_t key[KEYLEN];
    count++;
    key[0] = x;
    key[1] = y;
    key[2] = z;

    JHSG(pvalue, PJHSArray, key, 3);
    if (pvalue != NULL) return (int)*pvalue;
    value = (x <= y) ? y : mtak( mtak (x-1, y, z),
	    mtak (y-1, z, x),
	    mtak (z-1, x, y) );
    pvalue = &value;
    JHSI(pvalue, PJHSArray, key, 3);
    return value;
}

int main(int argc, char **argv){
    int x = 10;
    int y = 5;
    int z = 0;
    if (argc > 3){
	x = atoi(argv[1]);
	y = atoi(argv[2]);
	z = atoi(argv[3]);
    }
    int nbytes;
    int v = mtak(x, y, z);
    JHSFA(nbytes, PJHSArray)

	printf("mtak(%d, %d, %d) = %d; mtak() called %d times.\n",
		x, y, z, v, count);
    printf("PJHSArray used %d bytes.\n", nbytes);
    return 0;
}

先ほどと同じパラメータで実行しました。

$ ./judy-tak-rdtsc 10 5 0

一致比較の回数：249回
平均：759.968サイクル

snprintfの分だけ早くなりましたが、それでもまだ結構かかっています。
フィボナッチのような再利用率の高い高階段関数の場合には良いのですが、一般的な関数やループにたいしての再利用に使うには厳しいサイクル数です。
もっとも、memoizeはそもそも、再利用率の高いところに明示的に使うものなので、それで良いのでしょうけど。

他に、1word のキーで検索する JudyL やビット単位で検索する
Judy1 があるようです。