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
■
UNIV_EXPECT
gccでは以下のように定義される。
# define UNIV_EXPECT(expr,constant) __builtin_expect(expr, constant)
__builtin_expectはプログラマが指定できる分岐予測の情報で、exprで指定した条件がconstantで指定した結果になる可能性が高いことをコンパイラに知らせる。
以下のマクロも定義されている。
#define UNIV_LIKELY_NULL(ptr) __builtin_expect((ulint) ptr, 0) #define UNIV_LIKELY(cond) UNIV_EXPECT(cond, TRUE) #define UNIV_UNLIKELY(cond) UNIV_EXPECT(cond, FALSE)
例：
if(UNIV_LIKELY(a == 1)) {
/* こちらが実行される可能性が高い */
} else {
}
if(UNIV_UNLIKELY(a == 1)) {
} else {
/* こちらが実行される可能性が高い */
}
transaction
read_view_open_now
read_view_t(現在実行中のトランザクションIDのリスト: PostgreSQLのsnapshotに相当する)を作成する。
(1)read_view_create_lowでメモリを確保。
実行中のトランザクション数は、trx_sys->trx_listに登録されている。
(2)view->low_limit_noとview->low_limit_idに、trx_sys->max_trx_idを設定。
low_limit_noは後続の処理で変更される場合がある。
(3)view->trx_ids配列に、アクティブなトランザクションIDを追加する。
(4)view->up_limit_idに、trx_ids内の最小トランザクションIDを追加する。
read_view_tはトランザクションの分離レベルがREPEATABLE READの場合、トランザクションが終了するまで保持される。
分離レベルをREAD COMMITTED以下にすると、毎回削除される。
if (trx->isolation_level <= TRX_ISO_READ_COMMITTED
&& trx->global_read_view) {
/* At low transaction isolation levels we let
each consistent read set its own snapshot */
read_view_close_for_mysql(trx);
}
read_view_sees_trx_id
取り出したタプルが現在のトランザクションから参照可能か評価する。
ha_innobase::index_first
-> ha_innobase::index_read
-> row_search_for_mysql
-> lock_clust_rec_cons_read_sees
-> read_view_sees_trx_id trx_id: タプルのトランザクションID
view: 現在のトランザクションの情報 (snapshot)
(1)trx_idがview->up_limit_idより小さかったら見える
(2)trx_idがview->low_limit_id以上だったら見えない
(3)view->trx_idsに登録されているトランザクションID(=実行中のトランザクション)と一致したら見えない
/* We go through the trx ids in the array smallest first: this order
may save CPU time, because if there was a very long running
transaction in the trx id array, its trx id is looked at first, and
the first two comparisons may well decide the visibility of trx_id. */
n_ids = view->n_trx_ids;
for (i = 0; i < n_ids; i++) {
cmp = ut_dulint_cmp(trx_id,
read_view_get_nth_trx_id(view, n_ids - i - 1));
if (cmp <= 0) {
return(cmp < 0);
}
} read_view_get_nth_trx_idで、view->trx_idx配列からトランザクションIDを取得する。trx_id == view->trx_idx[X]になったら、実行中のトランザクションが更新したタプルなので、参照できない。(FALSEを返す)
view->trx_ids配列には、降順でトランザクションIDが入っていて、小さいトランザクションから比較している。trx_id < view->trx_idx[X]が成立した時点で、それ以降にtrx_idと一致することはないので、TRUEを返すことができる。
長時間実行中のトランザクションが1つある場合、最初の2回の比較で結果が分かる可能性が高いので、小さい方からチェックしている。
トランザクションの分離レベルがREAD UNCOMMITTEDの場合、commit前であっても常に最新のタプルを参照するためread_view_sees_trx_idは実行されない。
また、分離レベルがSERIALIZABLEのときは、テーブルを共有ロックしてから検索するため、read_view_sees_trx_idは実行されない。（共有ロックが取得できたということは、更新中(未commit)のタプルが存在しないから。）
Improvement of search for a binary operator
http://archives.postgresql.org/pgsql-patches/2006-04/msg00228.php
'='などの演算子(operator)を、どのように処理するか決める処理を高速化するパッチ。operatorはシステムカタログpg_operatorに登録されており、ユーザーがcreate operatorで登録することもできる。
pg_operatorのprimary keyは以下のようになっている。
・operatorの文字列
・operatorの左右に指定されたデータの型
・現在のセッションのnamespaceのサーチパス
従来の処理：
(1)システムカタログ(pg_operator)を演算子名をキーに検索する。検索結果からnamespaceの優先順位を考慮した演算子のリストを作成する。この処理はOpernameGetCandidate()で実行される。'='などの一般的なoperatorの場合、リストの大きさが50以上になり負荷が大きい。
(2)(1)のリストから、operatorの左右に指定されたデータ型に一致するoperatorを探す。
(3)(2)で見つからない場合、データ型の変換ルールを適用して、リストから一致するoperatorを探す。
OpernameGetCandidateの処理が重いので、(1)と(2)を入れ替える。(2)ではリストを検索する代わりに、演算子名と左右のデータ型をキーにシステムカタログ(pg_operator)を検索する。システムカタログに一致するデータが見つからない場合、(1)と(3)の処理を実行する。
memory manager (2)
mem_heap_create_func
memory heapを作成する。mem_heap_createなどのマクロから実行される。
(関数名がXXXXX_funcなどとなっている場合、マクロ経由で実行される)
引数
n: 先頭のブロックサイズを指定する。0を指定した場合はデフォルトサイズ
(MEM_BLOCK_START_SIZE)になる。
init_blockを指定した場合は、init_blockのサイズを指定する。
init_block: memory heapの作成を高速化したい場合に、mem_heap_create_funcの呼び出し側で先頭のブロックのメモリを確保してinit_blockに指定する。これにより、mem_heap_create_func内で先頭のブロックをmalloc/freeする必要がなくなる。
type: heap typeを指定。
file_name: mem_heap_createなどのマクロを実行したファイル名
line: マクロを実行した行番号
(1)mem_heap_create_blockで先頭ブロック(block)を作成
(2)UT_LIST_INITでblock->baseを初期化
(3)UT_LIST_ADD_FIRSTでblockをリストの先頭に登録
(4)コンパイルオプションにUNIV_MEM_DEBUGが指定されているときは、mem_hash_insertでblockを登録する
(5)blockをreturnする
mem_heap_free_func
memory heapを開放する。mem_heap_freeマクロから実行される。
(1)最後のブロックを取得
block = UT_LIST_GET_LAST(heap->base);
(2)heap->free_blockがある場合、それを開放する。
(3)ループでブロックリストを前にたどりながら、全部のブロックを開放していく。先頭ブロックがheap自身なので、これでheapを開放できる。
mem_heap_alloc
memory heapからメモリを割り当てる。
(1)heap->baseのブロックリストから一番後ろのブロックを取得
block = UT_LIST_GET_LAST(heap->base);
(2)ブロックの空き領域が足りなかったら、mem_heap_add_blockで新しいブロックを追加する。ブロックが作成できなかったらNULLを返す。
if (mem_block_get_len(block)
< mem_block_get_free(block) + MEM_SPACE_NEEDED(n)) {
block = mem_heap_add_block(heap, n);(3)ブロックの空き領域のオフセットを取得。
free = mem_block_get_free(block);
(4)使用するバッファの先頭位置を計算する。
buf = (byte*)block + free;
(5)ブロックの空き領域のオフセット位置を移動する。
mem_block_set_free(block, free + MEM_SPACE_NEEDED(n));
(6)確保したメモリのポインタを返す。
mem_heap_get_heap_top
memory heapの現在の空き領域の先頭ポインタを取得する。
(1)最後のブロックを取得
block = UT_LIST_GET_LAST(heap->base);
(2)空き領域のポインタを取得
buf = (byte*)block + mem_block_get_free(block);
return(buf);
mem_heap_get_free_heap_top
引数(old_top)で指定した位置以降に確保したメモリを開放する。
mem_heap_get_heap_topで空き領域の先頭位置を取得しておいて、複数のメモリを取得したあと、mem_heap_get_free_heap_topを実行することによって、メモリの開放をまとめて実行できる。スタックポインタをシフトすることによってメモリを開放する動作に似ている。
(mem_heap_get_heap_top/mem_heap_get_free_heap_topの仕組みを利用している
箇所は見当たらなかった。mem_heap_get_free_heap_topはmem_heap_emptyで使用
されている。)
(1)最後のブロックを取得
block = UT_LIST_GET_LAST(heap->base);
(2)old_topが含まれるブロックが見つかるまで、リストを前にたどっていく
old_topが含まれないブロックは、mem_heap_block_freeで開放していく
while (block != NULL) {
if (((byte*)block + mem_block_get_free(block) >= old_top)
&& ((byte*)block <= old_top)) {
/* Found the right block */
break;
}
/* Store prev_block value before freeing the current block
(the current block will be erased in freeing) */
prev_block = UT_LIST_GET_PREV(list, block);
mem_heap_block_free(heap, block);
block = prev_block;
}(3)ブロックの空き領域のoffsetを、old_topに設定する
mem_block_set_free(block, old_top - (byte*)block);
(4)ブロックのstartとfreeが同じになった場合、そのブロックは全く使用されて
いないので開放する。ただし先頭ブロックは開放しない。
(先頭ブロックかどうかはheap != blockでチェックしている)
/* If free == start, we may free the block if it is not the first
one */
if ((heap != block) && (mem_block_get_free(block) ==
mem_block_get_start(block))) {
mem_heap_block_free(heap, block);
}
mem_heap_empty
memory heapを空にする。
先頭ブロックのバッファの開始位置を指定して、mem_heap_free_heap_topを実行している。
mem_heap_free_heap_top(heap, (byte*)heap + mem_block_get_start(heap)); heap->free_blockがある場合、それも開放する。
memory manager
innobaseのmemory managerはmemory poolとmemory heapで構成されている。
memory poolは、最初にmysqlのパラメータinnobase_additional_mem_pool_sizeで指定された大きさのバッファを確保して、そこから必要なメモリを割り当てていく。このバッファからメモリを割り当てることが出来なくなったら、ut_mallocでメモリを割り当てる。(ut_mallocはmallocのラッパ)
memory heapはmemory poolからメモリを割り当てて作成される。
mem_pool_create
memory poolを作成する。sizeはバッファサイズ。
(1)ut_mallocでmem_pool_tのメモリを割り当てる
pool = ut_malloc(sizeof(mem_pool_t));
(2)ut_malloc_lowでpool->bufのメモリを割り当てる
pool->buf = ut_malloc_low(size, FALSE, TRUE);
2番目の引数をFALSEにして、確保したメモリを0で初期化しないようにしている
(3)pool->sizeを設定
(4)pool->mutexを作成
(5)freeリストを初期化(64個ある)
for (i = 0; i < 64; i++) {
UT_LIST_INIT(pool->free_list[i]);
}(6)free listにメモリを登録
できるだけ大きいメモリブロック単位で、リストに登録する
used = 0;
while (size - used >= MEM_AREA_MIN_SIZE) {
i = ut_2_log(size - used);
if (ut_2_exp(i) > size - used) {
/* ut_2_log rounds upward */
i--;
}
area = (mem_area_t*)(pool->buf + used);
mem_area_set_size(area, ut_2_exp(i));
mem_area_set_free(area, TRUE);
UT_LIST_ADD_FIRST(free_list, pool->free_list[i], area);
used = used + ut_2_exp(i);
}(7)pool->reservedを設定
(8)poolを返す
mem_pool_fill_free_list
iで指定したfree listよりも大きいサイズのfree listに登録されているメモリを分割して、iのfree listに割り当てる。
(1)free_list[i + 1]のメモリを取得
area = UT_LIST_GET_FIRST(pool->free_list[i + 1]);
(2)free_list[i + 1]が空だったら、mem_pool_fill_free_listを再帰コールして、さらに上のリストのメモリを、free_list[i + 1]に割り当てる
if (area == NULL) {
ret = mem_pool_fill_free_list(i + 1, pool);
if (ret == FALSE) {
return(FALSE);
}
area = UT_LIST_GET_FIRST(pool->free_list[i + 1]);
}(3)free list[i + 1]から先頭のメモリ(area)を削除する
UT_LIST_REMOVE(free_list, pool->free_list[i + 1], area);
(4)areaを2分割してfree list[i]に登録
// 後ろ半分の処理
area2 = (mem_area_t*)(((byte*)area) + ut_2_exp(i)); // 位置を計算
mem_area_set_size(area2, ut_2_exp(i)); // サイズを設定
mem_area_set_free(area2, TRUE); // free flagを設定
UT_LIST_ADD_FIRST(free_list, pool->free_list[i], area2); // listに登録
// 前半分の処理 (free flagは変更する必要がない)
mem_area_set_size(area, ut_2_exp(i)); // サイズを設定
UT_LIST_ADD_FIRST(free_list, pool->free_list[i], area); // listに登録
mem_area_alloc
memory poolからメモリを割り当てる
(1)使用するfree listを計算
n = ut_2_log(ut_max(size + MEM_AREA_EXTRA_SIZE, MEM_AREA_MIN_SIZE));
(2)mutexをロック
mutex_enter(&(pool->mutex));
mem_n_threads_inside++;(3)free_list[n]からmemory areaを取得
area = UT_LIST_GET_FIRST(pool->free_list[n]);
(4)free_list[n]が空だった場合、mem_pool_fill_free_listでfree_list[n + 1]以降から、free_list[n]にメモリを割り当てる
free_list[n + 1]以降からメモリが割り当てられなかった場合、ut_mallocでメモリを割り当てて返す。
if (area == NULL) {
ret = mem_pool_fill_free_list(n, pool);
if (ret == FALSE) {
/* Out of memory in memory pool: we try to allocate
from the operating system with the regular malloc: */
mem_n_threads_inside--;
mutex_exit(&(pool->mutex));
return(ut_malloc(size));
}
area = UT_LIST_GET_FIRST(pool->free_list[n]);
}(5)使用するmemory areaのfree flagを降ろす
mem_area_set_free(area, FALSE);
(6)memory areaをfree_list[n]から削除
UT_LIST_REMOVE(free_list, pool->free_list[n], area);
(7)pool->reservedを増加させる
pool->reserved += mem_area_get_size(area);
(8)mutexを開放
mem_n_threads_inside--;
mutex_exit(&(pool->mutex));(9)確保したメモリを返す
areaの先頭はstruct mem_area_structの領域なので、その後ろのポインタを返す。
return((void*)(MEM_AREA_EXTRA_SIZE + ((byte*)area)));
mem_area_get_buddy
memory areaの兄弟エリアを取得する
(1)areaとbufの差が(2 * size)で割り切れるとき、buddyは右(higher address)にある
if (((((byte*)area) - pool->buf) % (2 * size)) == 0) {
/* The buddy is in a higher address */
buddy = (mem_area_t*)(((byte*)area) + size);
// pool->bufをオーバーしないようにする
if ((((byte*)buddy) - pool->buf) + size > pool->size) {
/* The buddy is not wholly contained in the pool:
there is no buddy */
buddy = NULL;
}(2)areaとbufの差が(2 * size)で割り切れないとき、buddyは左(lower address)にある
} else {
/* The buddy is in a lower address; NOTE that area cannot
be at the pool lower end, because then we would end up to
the upper branch in this if-clause: the remainder would be
0 */
buddy = (mem_area_t*)(((byte*)area) - size);
}
mem_area_free
mem_area_allocで割り当てたメモリを開放する。
(1)ptrがpool->buf〜(pool->buf + pool->size)の間にない場合、ut_mallocで
割り当てられたメモリなので、ut_freeを実行する。
if ((byte*)ptr < pool->buf || (byte*)ptr >= pool->buf + pool->size) {
ut_free(ptr);
return;
}(2)ptrからmemory areaのポインタを計算
area = (mem_area_t*) (((byte*)ptr) - MEM_AREA_EXTRA_SIZE);
(3)memory areaのサイズを取得
size = mem_area_get_size(area);
(4)memory areaの兄弟area(隣のarea)を取得
buddy = mem_area_get_buddy(area, size, pool);
(5)free_listのindexを計算
n = ut_2_log(size);
(6)mutexをロック
(7)兄弟areaが存在して、兄弟areaが未使用(mem_area_get_freeがTRUE)で、
兄弟areaのサイズがfreeするareaと同じとき、2つのareaをくっつけて
上位のfree_list[n + 1]に登録する。
if (buddy && mem_area_get_free(buddy)
&& (size == mem_area_get_size(buddy))) {
/* The buddy is in a free list */
if ((byte*)buddy < (byte*)area) { // buddyがareaの左にある
// buddyをfree_list[n + 1]に登録するための準備
new_ptr = ((byte*)buddy) + MEM_AREA_EXTRA_SIZE;
mem_area_set_size(buddy, 2 * size);
mem_area_set_free(buddy, FALSE);
} else { // buddyがareaの右にある
// ptrをfree_list[n + 1]に登録するための準備
new_ptr = ptr;
mem_area_set_size(area, 2 * size);
}
/* Remove the buddy from its free list and merge it to area */
// buddyをfree_list[n]から削除
UT_LIST_REMOVE(free_list, pool->free_list[n], buddy);
pool->reserved += ut_2_exp(n);
mem_n_threads_inside--;
mutex_exit(&(pool->mutex));
// mem_area_freeを再帰コールして、free_list[n + 1]に登録する
mem_area_free(new_ptr, pool);
return;(8)buddyが使えない場合((7)の条件を満たさない場合)、ptrをfree_list[n]に登録する
UT_LIST_ADD_FIRST(free_list, pool->free_list[n], area);
mem_area_set_free(area, TRUE);
ut_ad(pool->reserved >= size);
pool->reserved -= size;(9)mutexを開放
hash
mysqlのハッシュテーブルは、PostgreSQLと同じリニアハッシュ・アルゴリズムを使用している。
(PostgreSQLのハッシュテーブル:http://www.hi-ho.ne.jp/a_ogawa/document/pg_dynahash.pdf)
PostgreSQLと違う点。
- ハッシュテーブルにデータを登録するたびに、テーブルを拡張する。 (データ数 = Bucket数になる)
- ハッシュ番地が衝突したときは、データを空いているBucketに登録して、 線形リストでリンクする。
typedef struct st_hash {
uint key_offset,key_length; /* Length of key if const length */
uint records,blength,current_record;
uint flags;
DYNAMIC_ARRAY array; /* Place for hash_keys */
hash_get_key get_key;
void (*free)(void *);
CHARSET_INFO *charset;
} HASH;
_hash_init
HASHを初期化する。
CALLER_INFOを受け取るために、hash_initマクロ経由で実行される。
CHARSET_INFO
include/m_ctype.hで定義されている。
my_hash_insert
ハッシュテーブルにデータを登録する。
関数の前半部分は、リニアハッシュのBucketを拡張する処理。
後半部分(/* Check if we are at the empty position */以降)がデータ登録処理。
rec_hashnr
unsigned int rec_hashnr(HASH *hash,const byte *record)
{
uint length;
byte *key= (byte*) hash_key(hash,record,&length,0);
return calc_hash(hash,key,length);
}hash_keyでキーを取り出した後、calc_hashでハッシュ値を計算する
hash_key
static inline char*
hash_key(HASH *hash,const byte *record,uint *length,my_bool first)
{
if (hash->get_key)
return (*hash->get_key)(record,length,first);
*length=hash->key_length;
return (byte*) record+hash->key_offset;
} ハッシュのキーとキーの長さを取り出す。
HASH->get_keyに関数ポインタが設定されているときは、その関数を使う。
たとえばtable_def_cacheでは、get_keyにtable_def_key関数が使われる。
get_keyが指定されていないときは、長さ(length)にHASH->key_lengthが設定され、キーにrecord + hash->key_offsetを返す。
calc_hash
static uint calc_hash(HASH *hash,const byte *key,uint length)
{
ulong nr1=1, nr2=4;
hash->charset->coll->hash_sort(hash->charset,(uchar*) key,length,&nr1,&nr2);
return nr1;
} HASH->charset->coll->hash_sortの関数を使って、ハッシュ値を計算する。
たとえばtable_def_cacheでは、hash_sortにmy_hash_sort_binが使用される。
