malloc

某所でmallocについての講演が有ったという事で、前々から気になっていたDoug Lea mallocを覗いてみた。色々テクニックが駆使されているのは分かるのだが、いまいち全体像が掴めなかったのでソースコード中から参照されている"Dynamic Storage Allocation: A Survey and Critical Review (1995)"を読み始めた。多少古いが、歴史的経緯も含めてかなり良くまとまっている。ptmallocというmultithread-awareなmallocもあるらしくなんだか気になる。触りだけならこの記事がまとまっている。

テスト前の現実逃避。スケジュール的には夏休みに入っているのに全く夏休みな気がしない。実質8/1ぐらいからだろうな。

java.util.concurrent

こんなパッケージが有ったのか。バイトでthread-safeなQueueを書いたのに。ConcurrentLinkedQueueを使えば一瞬。

mallocされた領域のサイズを動的に知る

大体のallocatorでheader fieldが有るのでこういう事ができるはず。下の方のbitはフラグに使われてたりするのでアラインメントに合わせてクリアする。

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    size_t *buf = (size_t*)malloc(2048);
    size_t size = *(buf - 1);
    printf("size = %d\n", size & ~0xf);

    size_t *buf1 = (size_t*)malloc(1);
    size_t size1 = *(buf1 - 1);
    printf("size = %d\n", size1 & ~0xf);
}

vmkzk% gcc mallocheader.c; ./a.out
size = 2048
size = 16

64bit環境の人は適当に変えて下さい (id:kosakiさんのアドバイスにより変更)。しかしよく考えればfreeをO(1)でやるにはポインタからサイズを取得する必要が有るので、こういう事が出来るのは当り前か。