From 0a8d8c54b249b81c58e4ab7d6481d737e2857c7a Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Tue, 13 Jul 2004 12:44:01 -0500 Subject: [svn-r8865] Purpose: Code optimization Description: Re-work the insertion of a new child into an existing node, to exploit some speedups for adding the rightmost child, since this is a very common case when appending records to an unlimited size dataset. Also, hoist the checks for the tree's 'K' value into a field in the shared information about the tree, instead of re-calculating them all the time. Platforms tested: Solaris 2.7 (arabica) FreeBSD 4.10 (sleipnir) w/parallel Too minor to require h5committest --- src/H5B.c | 113 ++++++++++++++++++++++++++++++------------------------- src/H5Bprivate.h | 5 ++- src/H5Distore.c | 6 ++- src/H5Gnode.c | 3 +- 4 files changed, 70 insertions(+), 57 deletions(-) diff --git a/src/H5B.c b/src/H5B.c index f6149d3..bdcca7c 100644 --- a/src/H5B.c +++ b/src/H5B.c @@ -135,13 +135,12 @@ static H5B_ins_t H5B_insert_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, uint8_t *rt_key, hbool_t *rt_key_changed, haddr_t *retval); -static herr_t H5B_insert_child(const H5F_t *f, - H5B_t *bt, unsigned idx, haddr_t child, +static herr_t H5B_insert_child(H5B_t *bt, unsigned idx, haddr_t child, H5B_ins_t anchor, const void *md_key); static herr_t H5B_split(H5F_t *f, hid_t dxpl_id, H5B_t *old_bt, haddr_t old_addr, unsigned idx, void *udata, haddr_t *new_addr/*out*/); -static H5B_t * H5B_copy(const H5F_t *f, const H5B_t *old_bt); +static H5B_t * H5B_copy(const H5B_t *old_bt); static herr_t H5B_serialize(H5F_t *f, H5B_t *bt); #ifdef H5B_DEBUG static herr_t H5B_assert(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type, @@ -234,7 +233,7 @@ H5B_create(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, void *udata, shared=H5RC_GET_OBJ(bt->rc_shared); HDassert(shared); if (NULL==(bt->native=H5FL_BLK_MALLOC(native_block,shared->sizeof_keys)) || - NULL==(bt->child=H5FL_SEQ_MALLOC(haddr_t,(size_t)(2*H5F_KVALUE(f,shared->type))))) + NULL==(bt->child=H5FL_SEQ_MALLOC(haddr_t,shared->two_k))) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree root node") if (HADDR_UNDEF==(*addr_p=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->sizeof_rnode))) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree root node") @@ -311,7 +310,7 @@ H5B_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata) shared=H5RC_GET_OBJ(bt->rc_shared); HDassert(shared); if (NULL==(bt->native=H5FL_BLK_MALLOC(native_block,shared->sizeof_keys)) || - NULL==(bt->child=H5FL_SEQ_MALLOC(haddr_t,(size_t)(2*H5F_KVALUE(f,type))))) + NULL==(bt->child=H5FL_SEQ_MALLOC(haddr_t,shared->two_k))) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") if (H5F_block_read(f, H5FD_MEM_BTREE, addr, shared->sizeof_rnode, dxpl_id, shared->page)<0) @@ -622,7 +621,7 @@ H5B_compute_size(H5F_t *f, H5B_t *bt, size_t *size_ptr) HDassert(shared->type); HDassert(size_ptr); - size = H5B_nodesize(f, shared->type, NULL, shared->sizeof_rkey); + size = H5B_nodesize(f, shared, NULL); if ( size == 0 ) { @@ -790,7 +789,6 @@ H5B_split(H5F_t *f, hid_t dxpl_id, H5B_t *old_bt, haddr_t old_addr, H5P_genplist_t *dx_plist; /* Data transfer property list */ H5B_shared_t *shared; /* Pointer to shared B-tree info */ H5B_t *new_bt = NULL, *tmp_bt = NULL; - unsigned k; /* B-tree 'K' value for the maximum number of entries in node */ unsigned nleft, nright; /* Number of keys in left & right halves */ double split_ratios[3]; /* B-tree split ratios */ herr_t ret_value = SUCCEED; /* Return value */ @@ -809,9 +807,7 @@ H5B_split(H5F_t *f, hid_t dxpl_id, H5B_t *old_bt, haddr_t old_addr, */ shared=H5RC_GET_OBJ(old_bt->rc_shared); HDassert(shared); - assert(old_bt->nchildren == 2 * H5F_KVALUE(f, shared->type)); - k = H5F_KVALUE(f, shared->type); - + assert(old_bt->nchildren == shared->two_k); /* Get the dataset transfer property list */ if (NULL == (dx_plist = H5I_object(dxpl_id))) @@ -835,7 +831,7 @@ H5B_split(H5F_t *f, hid_t dxpl_id, H5B_t *old_bt, haddr_t old_addr, side = "MIDDLE"; } fprintf(H5DEBUG(B), "H5B_split: %3u {%5.3f,%5.3f,%5.3f} %6s", - 2*k, split_ratios[0], split_ratios[1], split_ratios[2], side); + shared->two_k, split_ratios[0], split_ratios[1], split_ratios[2], side); } #endif @@ -844,11 +840,11 @@ H5B_split(H5F_t *f, hid_t dxpl_id, H5B_t *old_bt, haddr_t old_addr, * and the new node. */ if (!H5F_addr_defined(old_bt->right)) { - nleft = (unsigned)(2 * (double)k * split_ratios[2]); /*right*/ + nleft = (unsigned)((double)shared->two_k * split_ratios[2]); /*right*/ } else if (!H5F_addr_defined(old_bt->left)) { - nleft = (unsigned)(2 * (double)k * split_ratios[0]); /*left*/ + nleft = (unsigned)((double)shared->two_k * split_ratios[0]); /*left*/ } else { - nleft = (unsigned)(2 * (double)k * split_ratios[1]); /*middle*/ + nleft = (unsigned)((double)shared->two_k * split_ratios[1]); /*middle*/ } /* @@ -856,12 +852,12 @@ H5B_split(H5F_t *f, hid_t dxpl_id, H5B_t *old_bt, haddr_t old_addr, * result in nodes that have an unused child when data is written * sequentially, but it simplifies stuff below. */ - if (idxtwo_k) { --nleft; } else if (idx>=nleft && 0==nleft) { nleft++; } - nright = 2*k - nleft; + nright = shared->two_k - nleft; #ifdef H5B_DEBUG if (H5DEBUG(B)) fprintf(H5DEBUG(B), " split %3d/%-3d\n", nleft, nright); @@ -1048,7 +1044,7 @@ H5B_insert(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, bt->cache_info.is_dirty = TRUE; /* Make a copy of the old root information */ - if (NULL == (new_bt = H5B_copy(f, bt))) { + if (NULL == (new_bt = H5B_copy(bt))) { HCOMMON_ERROR(H5E_BTREE, H5E_CANTLOAD, "unable to copy old root"); if (H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, FALSE) != SUCCEED) @@ -1115,7 +1111,7 @@ done: *------------------------------------------------------------------------- */ static herr_t -H5B_insert_child(const H5F_t *f, H5B_t *bt, unsigned idx, haddr_t child, +H5B_insert_child(H5B_t *bt, unsigned idx, haddr_t child, H5B_ins_t anchor, const void *md_key) { H5B_shared_t *shared; /* Pointer to shared B-tree info */ @@ -1126,25 +1122,43 @@ H5B_insert_child(const H5F_t *f, H5B_t *bt, unsigned idx, haddr_t child, assert(bt); shared=H5RC_GET_OBJ(bt->rc_shared); HDassert(shared); - assert(bt->nchildren<2*H5F_KVALUE(f, shared->type)); + assert(bt->nchildrentwo_k); bt->cache_info.is_dirty = TRUE; - /* Make room for the new key */ - base=bt->native + (idx+1) * shared->type->sizeof_nkey, - HDmemmove(base + shared->type->sizeof_nkey, base, - (bt->nchildren - idx) * shared->type->sizeof_nkey); - HDmemcpy(base, md_key, shared->type->sizeof_nkey); - - /* The MD_KEY is the left key of the new node */ - if (H5B_INS_RIGHT == anchor) - idx++; + /* Check for inserting right-most key into node (common when just appending + * records to an unlimited dimension chunked dataset) + */ + base=H5B_NKEY(bt,shared,(idx+1)); + if((idx+1)==bt->nchildren) { + /* Make room for the new key */ + HDmemcpy(base + shared->type->sizeof_nkey, base, + shared->type->sizeof_nkey); /* No overlap possible - memcpy() OK */ + HDmemcpy(base, md_key, shared->type->sizeof_nkey); + + /* The MD_KEY is the left key of the new node */ + if (H5B_INS_RIGHT == anchor) + idx++; /* Don't have to memmove() child addresses down, just add new child */ + else + /* Make room for the new child address */ + bt->child[idx+1] = bt->child[idx]; + } /* end if */ + else { + /* Make room for the new key */ + HDmemmove(base + shared->type->sizeof_nkey, base, + (bt->nchildren - idx) * shared->type->sizeof_nkey); + HDmemcpy(base, md_key, shared->type->sizeof_nkey); + + /* The MD_KEY is the left key of the new node */ + if (H5B_INS_RIGHT == anchor) + idx++; + + /* Make room for the new child address */ + HDmemmove(bt->child + idx + 1, bt->child + idx, + (bt->nchildren - idx) * sizeof(haddr_t)); + } /* end if */ - /* Make room for the new child address */ - HDmemmove(bt->child + idx + 1, bt->child + idx, - (bt->nchildren - idx) * sizeof(haddr_t)); bt->child[idx] = child; - bt->nchildren += 1; FUNC_LEAVE_NOAPI(SUCCEED) @@ -1404,7 +1418,7 @@ H5B_insert_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type /* * If this node is full then split it before inserting the new child. */ - if (bt->nchildren == 2 * H5F_KVALUE(f, type)) { + if (bt->nchildren == shared->two_k) { if (H5B_split(f, dxpl_id, bt, addr, idx, udata, new_node_p/*out*/)<0) HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, H5B_INS_ERROR, "unable to split node") if (NULL == (twin = H5AC_protect(f, dxpl_id, H5AC_BT, *new_node_p, type, udata, H5AC_WRITE))) @@ -1420,7 +1434,7 @@ H5B_insert_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type } /* Insert the child */ - if (H5B_insert_child(f, tmp_bt, idx, child_addr, my_ins, md_key) < 0) + if (H5B_insert_child(tmp_bt, idx, child_addr, my_ins, md_key) < 0) HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert child") } @@ -1527,7 +1541,7 @@ H5B_iterate (H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, H5B_operator_t op * We've reached the left-most leaf. Now follow the right-sibling * pointer from leaf to leaf until we've processed all leaves. */ - if (NULL==(child=H5FL_SEQ_MALLOC(haddr_t,(size_t)(2*H5F_KVALUE(f,type)))) || + if (NULL==(child=H5FL_SEQ_MALLOC(haddr_t,shared->two_k)) || NULL==(key=H5FL_BLK_MALLOC(native_block,shared->sizeof_keys))) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") @@ -2028,8 +2042,8 @@ done: *------------------------------------------------------------------------- */ size_t -H5B_nodesize(const H5F_t *f, const H5B_class_t *type, - size_t *total_nkey_size/*out*/, size_t sizeof_rkey) +H5B_nodesize(const H5F_t *f, const H5B_shared_t *shared, + size_t *total_nkey_size/*out*/) { size_t size; @@ -2039,22 +2053,22 @@ H5B_nodesize(const H5F_t *f, const H5B_class_t *type, * Check arguments. */ assert(f); - assert(type); - assert(sizeof_rkey > 0); - assert(H5F_KVALUE(f, type) > 0); + assert(shared); + assert(shared->two_k > 0); + assert(shared->sizeof_rkey > 0); /* * Total native key size. */ if (total_nkey_size) - *total_nkey_size = (2 * H5F_KVALUE(f, type) + 1) * type->sizeof_nkey; + *total_nkey_size = (shared->two_k + 1) * shared->type->sizeof_nkey; /* * Total node size. */ size = (H5B_SIZEOF_HDR(f) + /*node header */ - 2 * H5F_KVALUE(f, type) * H5F_SIZEOF_ADDR(f) + /*child pointers */ - (2 * H5F_KVALUE(f, type) + 1) * sizeof_rkey); /*keys */ + shared->two_k * H5F_SIZEOF_ADDR(f) + /*child pointers */ + (shared->two_k + 1) * shared->sizeof_rkey); /*keys */ FUNC_LEAVE_NOAPI(size) } @@ -2078,11 +2092,10 @@ H5B_nodesize(const H5F_t *f, const H5B_class_t *type, *------------------------------------------------------------------------- */ static H5B_t * -H5B_copy(const H5F_t *f, const H5B_t *old_bt) +H5B_copy(const H5B_t *old_bt) { H5B_t *new_node = NULL; H5B_shared_t *shared; /* Pointer to shared B-tree info */ - size_t nkeys; H5B_t *ret_value; FUNC_ENTER_NOAPI(H5B_copy, NULL) @@ -2090,7 +2103,6 @@ H5B_copy(const H5F_t *f, const H5B_t *old_bt) /* * Check arguments. */ - assert(f); assert(old_bt); shared=H5RC_GET_OBJ(old_bt->rc_shared); HDassert(shared); @@ -2102,16 +2114,13 @@ H5B_copy(const H5F_t *f, const H5B_t *old_bt) /* Copy the main structure */ HDmemcpy(new_node,old_bt,sizeof(H5B_t)); - /* Compute the number of keys in this node */ - nkeys=2*H5F_KVALUE(f,shared->type); - if ( NULL==(new_node->native=H5FL_BLK_MALLOC(native_block,shared->sizeof_keys)) || - NULL==(new_node->child=H5FL_SEQ_MALLOC(haddr_t,nkeys))) + NULL==(new_node->child=H5FL_SEQ_MALLOC(haddr_t,shared->two_k))) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree root node") /* Copy the other structures */ HDmemcpy(new_node->native,old_bt->native,shared->sizeof_keys); - HDmemcpy(new_node->child,old_bt->child,(size_t)(sizeof(haddr_t)*nkeys)); + HDmemcpy(new_node->child,old_bt->child,(sizeof(haddr_t)*shared->two_k)); /* Increment the ref-count on the raw page */ H5RC_INC(new_node->rc_shared); @@ -2207,7 +2216,7 @@ H5B_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int f HDfprintf(stream, "%*s%-*s %u (%u)\n", indent, "", fwidth, "Number of children (max):", - bt->nchildren, (2 * H5F_KVALUE(f, type))); + bt->nchildren, shared->two_k); /* * Print the child addresses diff --git a/src/H5Bprivate.h b/src/H5Bprivate.h index 2dfd0e1..961c7d9 100644 --- a/src/H5Bprivate.h +++ b/src/H5Bprivate.h @@ -78,6 +78,7 @@ typedef struct H5B_t H5B_t; */ typedef struct H5B_shared_t { const struct H5B_class_t *type; /* Type of tree */ + unsigned two_k; /* 2*"K" value for tree's nodes */ size_t sizeof_rkey; /* Size of raw (disk) key */ size_t sizeof_rnode; /* Size of raw (disk) node */ size_t sizeof_keys; /* Size of native (memory) key node */ @@ -125,8 +126,8 @@ typedef struct H5B_class_t { /* * Library prototypes. */ -H5_DLL size_t H5B_nodesize(const H5F_t *f, const H5B_class_t *type, - size_t *total_nkey_size, size_t sizeof_rkey); +H5_DLL size_t H5B_nodesize(const H5F_t *f, const H5B_shared_t *shared, + size_t *total_nkey_size); H5_DLL herr_t H5B_create (H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, void *udata, haddr_t *addr_p/*out*/); H5_DLL herr_t H5B_find (H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, diff --git a/src/H5Distore.c b/src/H5Distore.c index 52b1f65..4520e65 100644 --- a/src/H5Distore.c +++ b/src/H5Distore.c @@ -955,9 +955,10 @@ H5D_istore_init (H5F_t *f, H5D_t *dset) /* Set up the "global" information for this file's groups */ shared->type= H5B_ISTORE; + shared->two_k=2*H5F_KVALUE(f,H5B_ISTORE); shared->sizeof_rkey = H5D_istore_sizeof_rkey(f, &udata); assert(shared->sizeof_rkey); - shared->sizeof_rnode = H5B_nodesize(f, H5B_ISTORE, &shared->sizeof_keys, shared->sizeof_rkey); + shared->sizeof_rnode = H5B_nodesize(f, shared, &shared->sizeof_keys); assert(shared->sizeof_rnode); if(NULL==(shared->page=H5FL_BLK_MALLOC(chunk_page,shared->sizeof_rnode))) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree page") @@ -3287,9 +3288,10 @@ H5D_istore_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE * stream, int inden /* Set up the "global" information for this file's groups */ shared->type= H5B_ISTORE; + shared->two_k=2*H5F_KVALUE(f,H5B_ISTORE); shared->sizeof_rkey = H5D_istore_sizeof_rkey(f, &udata); assert(shared->sizeof_rkey); - shared->sizeof_rnode = H5B_nodesize(f, H5B_ISTORE, &shared->sizeof_keys, shared->sizeof_rkey); + shared->sizeof_rnode = H5B_nodesize(f, shared, &shared->sizeof_keys); assert(shared->sizeof_rnode); if(NULL==(shared->page=H5FL_BLK_MALLOC(chunk_page,shared->sizeof_rnode))) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree page") diff --git a/src/H5Gnode.c b/src/H5Gnode.c index a879e54..279d9da 100644 --- a/src/H5Gnode.c +++ b/src/H5Gnode.c @@ -1750,9 +1750,10 @@ H5G_node_init(H5F_t *f) /* Set up the "global" information for this file's groups */ shared->type= H5B_SNODE; + shared->two_k=2*H5F_KVALUE(f,H5B_SNODE); shared->sizeof_rkey = H5G_node_sizeof_rkey(f, NULL); assert(shared->sizeof_rkey); - shared->sizeof_rnode = H5B_nodesize(f, H5B_SNODE, &shared->sizeof_keys, shared->sizeof_rkey); + shared->sizeof_rnode = H5B_nodesize(f, shared, &shared->sizeof_keys); assert(shared->sizeof_rnode); if(NULL==(shared->page=H5FL_BLK_MALLOC(grp_page,shared->sizeof_rnode))) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree page") -- cgit v0.12