From c708028588d0d79e8ffc9dc96cbdb4dc0f63025a Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Mon, 6 Oct 2003 14:14:15 -0500 Subject: [svn-r7553] Purpose: Improved algorithm (bug fix, sorta) Description: The internal algorithm for adding new IDs in the ID manager code (H5I) was adding new IDs to the front of the linked list and never adjusting the order of the items on the list (unless an ID was deleted). If many new objects were created, they would push earlier ones _way_ down the list (especially if the objects were being leaked in the application, as they appear to be in the current HDF-EOS5 library) and would cause O(n) search time for items on the list. The ID caching code in the ID manager was avoiding this behavior sometimes, but it was adding IDs that were looked up to the very tail of the cache and they would frequently leave the cache before helping. Solution: Implemented a "move to front" scheme for the linked list of IDs, which improves the lookup situation for frequently accessed objects. Removed ID caching code now, as the "move to front" algorithm actually works better. Platforms tested: FreeBSD 4.9 (sleipnir) too minor to require h5committest --- release_docs/RELEASE.txt | 2 ++ src/H5I.c | 94 ++++++++---------------------------------------- 2 files changed, 17 insertions(+), 79 deletions(-) diff --git a/release_docs/RELEASE.txt b/release_docs/RELEASE.txt index 0cbdfa7..8133a50 100644 --- a/release_docs/RELEASE.txt +++ b/release_docs/RELEASE.txt @@ -76,6 +76,8 @@ Bug Fixes since HDF5-1.6.0 release Library ------- + - Changed implementation of internal ID searching algorithm to avoid + O(n) behavior for many common cases. QAK 2003/10/06 - Allow partial parallel writing to compact datasets. QAK - 2003/10/06 - Correctly create reference to shared datatype in attribute, instead of making a copy of the shared datatype in the attribute. diff --git a/src/H5I.c b/src/H5I.c index b4b8323..c04b6c5 100644 --- a/src/H5I.c +++ b/src/H5I.c @@ -66,13 +66,6 @@ static int interface_initialize_g = 0; */ #define HASH_SIZE_POWER_2 -/* Define the following macro for atom caching over all the atoms */ -#define IDS_ARE_CACHED - -#ifdef IDS_ARE_CACHED -# define ID_CACHE_SIZE 4 /*# of previous atoms cached */ -#endif - #ifdef HASH_SIZE_POWER_2 /* * Map an ID to a hash location (assumes s is a power of 2 and smaller @@ -115,11 +108,6 @@ typedef struct { /*-------------------- Locally scoped variables -----------------------------*/ -#ifdef IDS_ARE_CACHED -/* ID Cache */ -static H5I_id_info_t *H5I_cache_g[ID_CACHE_SIZE]; -#endif - /* Array of pointers to atomic groups */ static H5I_id_group_t *H5I_id_group_list_g[H5I_NGROUPS]; @@ -387,7 +375,7 @@ H5I_clear_group(H5I_type_t grp, hbool_t force) H5I_id_info_t *tmp=NULL; /* Temporary node ptr */ int ret_value = SUCCEED; unsigned delete_node; /* Flag to indicate node should be removed from linked list */ - unsigned i,j; + unsigned i; FUNC_ENTER_NOAPI(H5I_clear_group, FAIL); @@ -398,16 +386,6 @@ H5I_clear_group(H5I_type_t grp, hbool_t force) if (grp_ptr == NULL || grp_ptr->count <= 0) HGOTO_ERROR(H5E_ATOM, H5E_BADGROUP, FAIL, "invalid group"); -#ifdef IDS_ARE_CACHED - /* - * Remove atoms from the global atom cache. - */ - for (i=0; iid) == grp) - H5I_cache_g[i] = NULL; - } -#endif /* IDS_ARE_CACHED */ - /* * Call free method for all objects in group regardless of their reference * counts. Ignore the return value from from the free method and remove @@ -481,16 +459,6 @@ H5I_clear_group(H5I_type_t grp, hbool_t force) last->next=next; } /* end else */ -#ifdef IDS_ARE_CACHED - /* Scan through cache & remove node, if present */ - /* (node's 'free' callback function could have made an H5I */ - /* call, which would probably put the node back in */ - /* the cache - QAK) */ - for(j=0; jnext; } -#ifdef IDS_ARE_CACHED - /* Delete object from cache */ - for (i = 0; i < ID_CACHE_SIZE; i++) - if (H5I_cache_g[i] && H5I_cache_g[i]->id == id) { - H5I_cache_g[i] = NULL; - break; /* we assume there is only one instance in the cache */ - } -#endif /* IDS_ARE_CACHED */ - if (curr_id != NULL) { if (last_id == NULL) { /* ID is the first in the chain */ @@ -1116,14 +1072,12 @@ done: static H5I_id_info_t * H5I_find_id(hid_t id) { - H5I_id_group_t *grp_ptr = NULL; /*ptr to the group */ - H5I_id_info_t *id_ptr = NULL; /*ptr to the new ID */ + H5I_id_group_t *grp_ptr; /*ptr to the group */ + H5I_id_info_t *last_id; /*ptr to the last ID */ + H5I_id_info_t *id_ptr; /*ptr to the new ID */ H5I_type_t grp; /*ID's group */ unsigned hash_loc; /*bucket pointer */ H5I_id_info_t *ret_value = NULL; /*return value */ -#ifdef IDS_ARE_CACHED - int i; -#endif FUNC_ENTER_NOINIT(H5I_find_id); @@ -1135,30 +1089,6 @@ H5I_find_id(hid_t id) if (grp_ptr == NULL || grp_ptr->count <= 0) HGOTO_ERROR(H5E_ATOM, H5E_BADGROUP, NULL, "invalid group"); -#ifdef IDS_ARE_CACHED - /* - * Look for the ID in the cache first. Implement a simple "move - * forward" caching scheme by swapping the found cache item with the - * previous cache item. This gradually migrates used cache items toward - * the front of the cache and unused items toward the end. For instance, - * finding `e' in the cache results in: - * - * Before: a b c d e f g h i j - * | | | X | | | | | - * After: a b c e d f g h i j - */ - for (i=0; iid == id) { - ret_value = H5I_cache_g[i]; - if (i > 0) { - H5I_id_info_t *tmp = H5I_cache_g[i-1]; - H5I_cache_g[i-1] = H5I_cache_g[i]; - H5I_cache_g[i] = tmp; - } - HGOTO_DONE(ret_value); - } -#endif /* IDS_ARE_CACHED */ - /* Get the bucket in which the ID is located */ hash_loc = (unsigned)H5I_LOC(id, grp_ptr->hash_size); id_ptr = grp_ptr->id_list[hash_loc]; @@ -1166,17 +1096,23 @@ H5I_find_id(hid_t id) HGOTO_ERROR(H5E_ATOM, H5E_BADATOM, NULL, "invalid ID"); /* Scan the bucket's linked list for a match */ + last_id=NULL; while (id_ptr) { if (id_ptr->id == id) break; + last_id=id_ptr; id_ptr = id_ptr->next; } - ret_value = id_ptr; -#ifdef IDS_ARE_CACHED - /* Add id to the end of the cache */ - H5I_cache_g[ID_CACHE_SIZE-1] = id_ptr; -#endif /* IDS_ARE_CACHED */ + /* If we found an object, move it to the front of the list, if it isn't there already */ + if(id_ptr!=NULL && last_id!=NULL) { + last_id->next=id_ptr->next; + id_ptr->next=grp_ptr->id_list[hash_loc]; + grp_ptr->id_list[hash_loc]=id_ptr; + } /* end if */ + + /* Set the return value */ + ret_value = id_ptr; done: FUNC_LEAVE_NOAPI(ret_value); -- cgit v0.12