文字列の繰り返し

c

rubyのソースコードを眺めていたらrb_str_timesの実装がおもしろかったので、実際そういった書き方をすることでどれだけパフォーマンスに差が出てくるのか試してみました。

http://codepad.org/AQbS4Ilu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

inline unsigned long long rdtsc() {
    unsigned long long ret;
    __asm__ volatile ("rdtsc" : "=A" (ret));
    return ret;
}

char *times_simple(char *str, size_t times) {
    size_t i, len = strlen(str);
    char *str2 = malloc(len*times + 1);
    for(i=0;i<len*times;i+=len) {
	memcpy(str2+i, str, len);
    }
    str2[len*times] = '\0';
    return str2;
}
char *times_log(char *str, size_t times) {
    size_t n, len = strlen(str);
    char *str2 = malloc(len*times + 1);
    n = len;
    memcpy(str2, str, n);
    while(n <= len*times/2) {
	memcpy(str2+n, str2, n);
	n *= 2;
    }
    memcpy(str2+n, str2, len*times-n);
    str2[len*times] = '\0';
    return str2;
}
int main(int argc, char **argv) {
    static char *str = "hoge";
    char *str2;
    size_t times = 100;
    unsigned long long start, end;

    start = rdtsc();
    str2 = times_simple(str, times);
    end= rdtsc();
    printf("%s x %d = %s\n", str, times, str2);
    printf("time stamp counter: %llu\n", end - start);

    start = rdtsc();
    str2 = times_log(str, times);
    end= rdtsc();
    printf("%s x %d = %s\n", str, times, str2);
    printf("time stamp counter: %llu\n", end - start);

    return 0;
}

memcpyを単純に100回繰り返すtimes_simpleと、memcpyの回数が8回で済むtimes_logの速度比較。時間計測はRDTSC命令で。

hoge x 100 = hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge
time stamp counter: 1871674
hoge x 100 = hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge
time stamp counter: 2430

すごく差がでました。


「アルゴリズムって大事ですね！」という締めはあちこちで見るので、ここでは「偉い人が書いたパーツを使って、なるべく自分でループとか書かないようにすると勝手に高速化されてたりしてて嬉しいですよ！」と言っておきます。

2009/2/2 2:46 追記

codepadの実行結果とかどういうものなのかいまいちわからんので手元の

% cat /proc/cpuinfo
...
model name      : AMD Athlon(tm)64 X2 Dual Core Processor  4600+
stepping        : 1
cpu MHz         : 1000.000
cache size      : 512 KB
...

みたいなマシンの結果だと

hoge x 100 = hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge
time stamp counter: 135745
hoge x 100 = hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge
time stamp counter: 2326

この程度に。

test