From 0b2827f9ced045e36e4a88e16cfef7ca9250c89e Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Tue, 13 Jul 2004 12:44:05 -0500 Subject: [svn-r8866] 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 | 111 ++++++++++++++++++++++++++++++------------------------- src/H5Bprivate.h | 5 ++- src/H5Distore.c | 6 ++- src/H5Gnode.c | 78 ++++++++++++++++++++++++++++---------- 4 files changed, 126 insertions(+), 74 deletions(-) diff --git a/src/H5B.c b/src/H5B.c index 9ea4735..ed773f2 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, @@ -236,7 +235,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") @@ -313,7 +312,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) @@ -731,7 +730,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 */ @@ -750,9 +748,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))) @@ -776,7 +772,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 @@ -785,11 +781,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*/ } /* @@ -797,12 +793,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); @@ -989,7 +985,7 @@ H5B_insert(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, bt->cache_info.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) @@ -1056,7 +1052,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 */ @@ -1067,25 +1063,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.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) @@ -1345,7 +1359,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))) @@ -1361,7 +1375,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") } @@ -1468,7 +1482,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") @@ -1969,8 +1983,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; @@ -1980,22 +1994,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) } @@ -2019,11 +2033,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) @@ -2031,7 +2044,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); @@ -2043,16 +2055,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); @@ -2148,7 +2157,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 2a85991..fb21b75 100644 --- a/src/H5Distore.c +++ b/src/H5Distore.c @@ -963,9 +963,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") @@ -3295,9 +3296,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 0b24fd6..5009b2c 100644 --- a/src/H5Gnode.c +++ b/src/H5Gnode.c @@ -62,6 +62,7 @@ typedef struct H5G_node_key_t { #define PABLO_MASK H5G_node_mask /* PRIVATE PROTOTYPES */ +static herr_t H5G_node_serialize(H5F_t *f, H5G_node_t *sym, size_t size, uint8_t *buf); static size_t H5G_node_size(H5F_t *f); static herr_t H5G_node_shared_free(void *shared); @@ -463,7 +464,7 @@ done: static herr_t H5G_node_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5G_node_t *sym) { - uint8_t *buf = NULL, *p = NULL; + uint8_t *buf = NULL; size_t size; int i; herr_t ret_value=SUCCEED; /* Return value */ @@ -499,24 +500,9 @@ H5G_node_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5G_node_ /* Allocate temporary buffer */ if ((buf=H5FL_BLK_MALLOC(symbol_node,size))==NULL) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed"); - p=buf; - /* magic number */ - HDmemcpy(p, H5G_NODE_MAGIC, H5G_NODE_SIZEOF_MAGIC); - p += 4; - - /* version number */ - *p++ = H5G_NODE_VERS; - - /* reserved */ - *p++ = 0; - - /* number of symbols */ - UINT16ENCODE(p, sym->nsyms); - - /* entries */ - H5G_ent_encode_vec(f, &p, sym->entry, sym->nsyms); - HDmemset(p, 0, size - (p - buf)); + if (H5G_node_serialize(f, sym, size, buf) < 0) + HGOTO_ERROR(H5E_SYM, H5E_WRITEERROR, FAIL, "node serialization failed"); if (H5F_block_write(f, H5FD_MEM_BTREE, addr, size, dxpl_id, buf) < 0) HGOTO_ERROR(H5E_SYM, H5E_WRITEERROR, FAIL, "unable to write symbol table node to the file"); @@ -541,6 +527,59 @@ done: /*------------------------------------------------------------------------- + * Function: H5G_node_serialize + * + * Purpose: Serialize the symbol table node + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Bill Wendling + * wendling@ncsa.uiuc.edu + * Sept. 16, 2003 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +H5G_node_serialize(H5F_t *f, H5G_node_t *sym, size_t size, uint8_t *buf) +{ + uint8_t *p; + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI_NOINIT(H5G_node_serialize); + + /* check args */ + assert(f); + assert(sym); + assert(buf); + + p = buf; + + /* magic number */ + HDmemcpy(p, H5G_NODE_MAGIC, H5G_NODE_SIZEOF_MAGIC); + p += 4; + + /* version number */ + *p++ = H5G_NODE_VERS; + + /* reserved */ + *p++ = 0; + + /* number of symbols */ + UINT16ENCODE(p, sym->nsyms); + + /* entries */ + if (H5G_ent_encode_vec(f, &p, sym->entry, sym->nsyms) < 0) + HGOTO_ERROR(H5E_SYM, H5E_CANTENCODE, FAIL, "can't serialize") + HDmemset(p, 0, size - (p - buf)); + +done: + FUNC_LEAVE_NOAPI(ret_value); +} + + +/*------------------------------------------------------------------------- * Function: H5G_node_dest * * Purpose: Destroy a symbol table node in memory. @@ -1536,9 +1575,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