faster version of AllocSetFreeIndex for x86 architecture

http://archives.postgresql.org/pgsql-hackers/2009-06/msg00159.php

Postgresqlのmemory managerで、空きブロックリストのインデックスを計算する処理を高速化するパッチ。

現在のコードは、以下のようにループして計算しているが

static inline int
AllocSetFreeIndex(Size size)
{
	int         idx = 0;

	if (size > 0)
	{
		size = (size - 1) >> ALLOC_MINBITS;
		while (size != 0)
		{
			idx++;
			size >>= 1;
		}
		Assert(idx < ALLOCSET_NUM_FREELISTS);
	}

	return idx;
}

これを、x86 CPUのbsrで計算するようにした

static inline int
AllocSetFreeIndex(Size size)
{
    int idx;

    if (__builtin_expect(size < (1 << ALLOC_MINBITS), 0))
		size = (1 << ALLOC_MINBITS);

    /* bsr(Bit Scan Reverse): Search the most significant set bit */
    __asm__ ("bsr %1, %0" :"=r"(idx) :"g"(size - 1));

    return idx - (ALLOC_MINBITS - 1);
}

パッチの効果 (pgbench -c 1 -t 50000を実行し、oprofileで計測)

パッチ適用前

CPU: P4 / Xeon with 2 hyper-threads, speed 2793.55 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events
samples  %        symbol name
66854     6.6725  AllocSetAlloc
11817     1.1794  AllocSetFree

パッチ適用後

CPU: P4 / Xeon with 2 hyper-threads, speed 2793.55 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events
with a unit mask of 0x01 (mandatory) count 100000
samples  %        symbol name
47610     4.9333  AllocSetAlloc
6248      0.6474  AllocSetFree