サイズによるmalloc(3)の負荷の違い

ネットワークIOのバッファリングを行うコードを書く必要があったので、確保するメモリのサイズによってmalloc(3)にかかる時間がどれくらい違うのか調べてみた。
環境は：

Linux vcore.local 2.6.22.9-vcore16 #1 SMP Sun Oct 14 22:13:32 JST 2007 x86_64 AMD Athlon(tm) 64 X2 Dual Core Processor 5000+ GNU/Linux

malloc() → free() を 1,000,000回繰り返し、かかった時間を計測した結果：

$ ./a.out 8 16 32 64 128 256 512 1024 8192 16384 32768
   bytes: seconds
       8: 0.042706
      16: 0.042608
      32: 0.042998
      64: 0.042607
     128: 0.093424
     256: 0.093280
     512: 0.092128
    1024: 0.092512
    8192: 0.089559
   16384: 0.091815
   32768: 0.091766

64バイトまでと、128バイト以降では倍以上の差がある。

malloc(3)のメモリ管理構造 VA Linux Systems Japan を読むと、72バイトまでのチャンクは「fastbins」に登録される、「fastbinsは要求メモリを迅速に確保する為に用意されたchunkのリストヘッダ」とある。

そこで72バイト周辺をもう一度調べてみると、確かに72バイトを境界に速度に大きな差が出る。

$ ./a.out 71 72 73 74
   bytes: seconds
      71: 0.042752
      72: 0.042665
      73: 0.092959
      74: 0.093006

72バイトを越えると32KBまでほとんど変わらないので、バッファリング用には一定のサイズ決め打ちでメモリを確保すれば良さそう。
クライアントの数だけバッファリング用のメモリを保持しなければならないが、Linuxは楽観的にメモリを確保するので、確保するだけではメモリを消費したことにならないから問題ないはず。

他のOSで単純に大きなバッファをバンバン確保すると、クライアントの数が増えたときにメモリを確保できなくなるかもしれない。Linuxでもovercommitに頼りすぎるといざという時にOOM Killerが走り出して良くないので、C10Kな規模のクライアントが接続してくる場合は別なバッファリング戦略が必要かもしれない。

テストに使ったコード：

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

static double g_timer;

double gettimeofday_sec()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + (double)tv.tv_usec  * 1e-6;
}

void timer_init() {
    g_timer = gettimeofday_sec();
}

void timer_show() {
    printf("%f\n", gettimeofday_sec() - g_timer);
}

#define NUM_LOOP 1000000

int main(int argc, char* argv[])
{
    int i, j;
    printf("   bytes: seconds\n");
    for(i=1; i < argc; ++i) {
        size_t sz = atoi(argv[i]);
        printf("%8lu: ",sz);
        timer_init();
        for(j=0; j < NUM_LOOP; ++j) {
            char* buf = (char*)malloc(sz);
            free(buf);
        }
        timer_show();
    }
    return 0;
}