[svn-r6252] Purpose:

    Lots of performance improvements & a couple new internal API interfaces.

Description:
    Performance Improvements:
        - Cached file offset & length sizes in shared file struct, to avoid
            constantly looking them up in the FCPL.
        - Generic property improvements:
            - Added "revision" number to generic property classes to speed
                up comparisons.
            - Changed method of storing properties from using a hash-table
                to the TBBT routines in the library.
            - Share the propery names between classes and the lists derived
                from them.
            - Removed redundant 'def_value' buffer from each property.
            - Switching code to use a "copy on write" strategy for
                properties in each list, where the properties in each list
                are shared with the properties in the class, until a
                property's value is changed in a list.
        - Fixed error in layout code which was allocating too many buffers.
        - Redefined public macros of the form (H5open()/H5check, <variable>)
            internally to only be (<variable>), avoiding innumerable useless
            calls to H5open() and H5check_version().
        - Reuse already zeroed buffers in H5F_contig_fill instead of
            constantly re-zeroing them.
        - Don't write fill values if writing entire dataset.
        - Use gettimeofday() system call instead of time() system when
            checking the modification time of a dataset.
        - Added reference counted string API and use it for tracking the
            names of objects opening in a file (for the ID->name code).
        - Removed redundant H5P_get() calls in B-tree routines.
        - Redefine H5T datatype macros internally to the library, to avoid
            calling H5check redundantly.
        - Keep dataspace information for dataset locally instead of reading
            from disk each time.  Added new module to track open objects
            in a file, to allow this (which will be useful eventually for
            some FPH5 metadata caching issues).
        - Remove H5AC_find macro which was inlining metadata cache lookups,
            and call function instead.
        - Remove redundant memset() calls from H5G_namei() routine.
        - Remove redundant checking of object type when locating objects
            in metadata cache and rely on the address only.
        - Create default dataset object to use when default dataset creation
            property list is used to create datasets, bypassing querying
            for all the property list values.
        - Use default I/O vector size when performing raw data with the
            default dataset transfer property list, instead of querying for
            I/O vector size.
        - Remove H5P_DEFAULT internally to the library, replacing it with
            more specific default property list based on the type of
            property list needed.
        - Remove redundant memset() calls in object header message (H5O*)
            routines.
        - Remove redunant memset() calls in data I/O routines.
        - Split free-list allocation routines into malloc() and calloc()-
            like routines, instead of one combined routine.
        - Remove lots of indirection in H5O*() routines.
        - Simplify metadata cache entry comparison routine (used when
            flushing entire cache out).
        - Only enable metadata cache statistics when H5AC_DEBUG is turned
            on, instead of always tracking them.
        - Simplify address comparison macro (H5F_addr_eq).
        - Remove redundant metadata cache entry protections during dataset
            creation by protecting the object header once and making all
            the modifications necessary for the dataset creation before
            unprotecting it.
        - Reduce # of "number of element in extent" computations performed
            by computing and storing the value during dataspace creation.
        - Simplify checking for group location's file information, when file
            has not been involving in file-mounting operations.
        - Use binary encoding for modification time, instead of ASCII.
        - Hoist H5HL_peek calls (to get information in a local heap)
            out of loops in many group routine.
        - Use static variable for iterators of selections, instead of
            dynamically allocation them each time.
        - Lookup & insert new entries in one step, avoiding traversing
            group's B-tree twice.
        - Fixed memory leak in H5Gget_objname_idx() routine (tangential to
            performance improvements, but fixed along the way).
        - Use free-list for reference counted strings.
        - Don't bother copying object names into cached group entries,
            since they are re-created when an object is opened.

        The benchmark I used to measure these results created several thousand
        small (2K) datasets in a file and wrote out the data for them.  This is
        Elena's "regular.c" benchmark.

        These changes resulted in approximately ~4.3x speedup of the
        development branch when compared to the previous code in the
        development branch and ~1.4x speedup compared to the release
        branch.

        Additionally, these changes reduce the total memory used (code and
        data) by the development branch by ~800KB, bringing the development
        branch back into the same ballpark as the release branch.

        I'll send out a more detailed description of the benchmark results
        as a followup note.

    New internal API routines:
        Added "reference counted strings" API for tracking strings that get
            used by multiple owners without duplicating the strings.
        Added "ternary search tree" API for text->object mappings.

Platforms tested:
    Tested h5committest {arabica (fortran), eirene (fortran, C++)
	modi4 (parallel, fortran)}
    Other platforms/configurations tested?
        FreeBSD 4.7 (sleipnir) serial & parallel
        Solaris 2.6 (baldric) serial

1 files changed, 91 insertions, 115 deletions

diff --git a/src/H5Oplist.c b/src/H5Oplist.c
index 554d0b7..352df06 100644
--- a/src/H5Oplist.c
+++ b/src/H5Oplist.c
@@ -65,6 +65,12 @@ static int interface_initialize_g = 0;
 /* Declare external the free list for hsize_t arrays */
 H5FL_ARR_EXTERN(hsize_t);
 
+/* Declare the external free list for the H5P_genprop_t struct */
+H5FL_EXTERN(H5P_genprop_t);
+
+/* Declare the external free list for the H5P_genplist_t struct */
+H5FL_EXTERN(H5P_genplist_t);
+
 #define UINT_ENCODE(dst, src)   \
         if (sizeof(src) == 2) {                 \
             UINT16ENCODE(dst, src);             \
@@ -131,7 +137,7 @@ H5O_plist_decode(H5F_t UNUSED *f, const uint8_t *p, H5O_shared_t UNUSED *sh)
     H5P_genclass_t *pclass; /* property list class to modify        */
     hid_t new_plist_id;     /* property list ID of new list created */
     int version;            /* message version number               */
-    unsigned int i, nprops, hashsize;
+    unsigned int i, nprops;
     void *ret_value;
     
     FUNC_ENTER_NOAPI(H5O_plist_decode, NULL);
@@ -169,11 +175,9 @@ H5O_plist_decode(H5F_t UNUSED *f, const uint8_t *p, H5O_shared_t UNUSED *sh)
         ++p;
 
     UINT_DECODE(p, nprops);
-    UINT_DECODE(p, hashsize);
 
     /* Allocate new property list */
-    if ((new_plist = H5MM_calloc(sizeof(H5P_genplist_t) +
-                                 ((hashsize - 1) * sizeof(H5P_genprop_t *)))) == NULL)
+    if ((new_plist = H5FL_CALLOC(H5P_genplist_t)) == NULL)
         HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
 
     /* Initialize new property list */
@@ -183,7 +187,11 @@ H5O_plist_decode(H5F_t UNUSED *f, const uint8_t *p, H5O_shared_t UNUSED *sh)
     new_plist->class_init = 0;  /* Initially, wait until the class
                                    callback finishes to set */
 
-    /* Create new property list */
+    /* Initialize the TBBT to hold the properties */
+    if((new_plist->props=H5TB_fast_dmake(H5TB_FAST_STR_COMPARE))==NULL)
+        HGOTO_ERROR(H5E_PLIST,H5E_CANTMAKETREE,NULL,"can't create TBBT for properties");
+
+    /* Insert properties into property list */
     for (i = 0; i < nprops; ++i) {
         H5P_genprop_t *tprop;
         unsigned str_len;
@@ -192,35 +200,19 @@ H5O_plist_decode(H5F_t UNUSED *f, const uint8_t *p, H5O_shared_t UNUSED *sh)
          * Allocate and initialize the property structure which is going
          * to hold the information we're reading in.
          */
-        if (NULL == (tprop = H5MM_malloc(sizeof(H5P_genprop_t))))
+        if (NULL == (tprop = H5FL_CALLOC(H5P_genprop_t)))
             HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
 
-        tprop->create = NULL;
-        tprop->def_value = NULL;
-        tprop->set = NULL;
-        tprop->get = NULL;
-        tprop->del = NULL;
-        tprop->copy = NULL;
-        tprop->close = NULL;
-        tprop->next = NULL;
-
-        /* Grab the XORed value of the name and get the length of the name */
-        UINT_DECODE(p, tprop->xor_val);
+        /* Grab the length of the name */
         UINT_DECODE(p, str_len);
 
-        if (str_len) {
-            /* If there is a name, allocate space for it and copy */
-            if (NULL == (tprop->name = H5MM_malloc(str_len + 1))) {
-                H5MM_xfree(tprop);
-                HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
-            }
-
-            HDmemcpy(tprop->name, p, str_len + 1);
-            p += str_len + 1;
-        } else {
-            tprop->name = NULL;
-            ++p;
+        /* Allocate space for the name and copy it */
+        if (NULL == (tprop->name = H5MM_malloc(str_len + 1))) {
+            H5FL_FREE(H5P_genprop_t,tprop);
+            HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
         }
+        HDmemcpy(tprop->name, p, str_len + 1);
+        p += str_len + 1;
 
         /* Grab the size of the "value" data */
         UINT_DECODE(p, tprop->size);
@@ -228,18 +220,21 @@ H5O_plist_decode(H5F_t UNUSED *f, const uint8_t *p, H5O_shared_t UNUSED *sh)
         /* Allocate and memcpy the value part of the property. */
         if ((tprop->value = H5MM_malloc(tprop->size)) == NULL) {
             H5MM_xfree(tprop->name);
-            H5MM_xfree(tprop);
+            H5FL_FREE(H5P_genprop_t,tprop);
             HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed");
         }
 
         HDmemcpy(tprop->value, p, tprop->size);
         p += tprop->size;
 
+        /* Set the property's type */
+        tprop->type=H5P_PROP_WITHIN_LIST;
+
         /* Insert the initialized property into the property list */
-        if (H5P_add_prop(new_plist->props, new_plist->pclass->hashsize, tprop) < 0) {
+        if (H5P_add_prop(new_plist->props, tprop) < 0) {
             H5MM_xfree(tprop->value);
             H5MM_xfree(tprop->name);
-            H5MM_xfree(tprop);
+            H5FL_FREE(H5P_genprop_t,tprop);
             HGOTO_ERROR(H5E_PLIST, H5E_CANTINSERT, NULL, "Can't insert property into list");
         }
 
@@ -292,9 +287,8 @@ static herr_t
 H5O_plist_encode(H5F_t UNUSED *f, uint8_t *p, const void *mesg)
 {
     const H5P_genplist_t *plist = (const H5P_genplist_t *)mesg;
+    char *class_path;           /* Pointer to class path generated for property list */
     herr_t ret_value = SUCCEED;
-    unsigned int i;
-    char *class_path;
 
     FUNC_ENTER_NOAPI(H5O_plist_encode, FAIL);
 
@@ -333,45 +327,47 @@ H5O_plist_encode(H5F_t UNUSED *f, uint8_t *p, const void *mesg)
 
     HDfree(class_path);
     UINT_ENCODE(p, plist->nprops);
-    UINT_ENCODE(p, plist->pclass->hashsize);
 
-    for (i = 0; i < plist->pclass->hashsize; ++i) {
-        H5P_genprop_t *tprop = plist->props[i];
+    /* Encode the properties for this property list */
+    if(plist->nprops>0) {
+        H5TB_NODE *curr_node;   /* Current node in TBBT */
+        H5P_genprop_t *tprop;   /* Pointer to property */
+
+        /* Walk through the properties in the old class */
+        curr_node=H5TB_first(plist->props->root);
+        while(curr_node!=NULL) {
+            size_t s;           /* Length of property name */
 
-        /* Walk through the list of properties at each hash location */
-        while (tprop) {
-            const char *n = tprop->name;
+            /* Get a pointer to the property from the node */
+            tprop=curr_node->data;
+            assert(tprop->name);  /* Properties are guaranteed to have names */
 
             /*
              * Copy the meat of the generic property:
              *
-             *      1. The XORed version of the name
+             *      1. The length of the property name
              *      2. The name of the property
              *      3. The size of the property value
              *      4. The property value
              */
-            UINT_ENCODE(p, tprop->xor_val);
 
-            if (n && *n) {
-                size_t s = HDstrlen(n);
+            /* Get the name's length & encode it */
+            s = HDstrlen(tprop->name);
+            UINT_ENCODE(p, s);
 
-                UINT_ENCODE(p, s);
-                HDmemcpy(p, n, s + 1);
-                p += s + 1;
-            } else {
-                /* if there isn't a name, put a NULL there */
-                UINT_ENCODE(p, 0u);
-                *p++ = '\0';
-            }
+            /* Encode the name itself */
+            HDmemcpy(p, tprop->name, s + 1);
+            p += s + 1;
 
+            /* Encode the property value's size & data */
             UINT_ENCODE(p, tprop->size);
             HDmemcpy(p, tprop->value, tprop->size);
             p += tprop->size;
 
-            /* Go to next registered property in class */
-            tprop = tprop->next;
-        }
-    }
+            /* Get the next property node in the TBBT */
+            curr_node=H5TB_next(curr_node);
+        } /* end while */
+    } /* end if */
 
 done:
     FUNC_LEAVE(ret_value);
@@ -398,37 +394,17 @@ static size_t
 H5O_plist_size(H5F_t UNUSED *f, const void *mesg)
 {
     const H5P_genplist_t *plist = (const H5P_genplist_t *)mesg;
-    const H5P_genclass_t *pclass;
+    char *class_path=NULL;      /* Pointer to class path generated for property list */
     size_t ret_value;
-    char *class_path = NULL;
-    unsigned i;
 
     FUNC_ENTER_NOAPI(H5O_plist_size, 0);
 
     /* check args */
     assert(plist);
 
-    ret_value = 2 +                             /*version info          */
+    ret_value = 1 +                             /*version info          */
                 1;                              /*reserved              */
 
-    /*
-     * Loop through the class and its parent(s) to gather the complete
-     * length of the name. The class name encoded will look like:
-     *
-     *      DerivedClass/ParentClass/.../BaseClass
-     */
-    pclass = plist->pclass;
-
-    while (pclass) {
-        if (pclass->name)
-            ret_value += HDstrlen(pclass->name);/*length of class name  */
-
-        if ((pclass = pclass->parent) != NULL)
-            ++ret_value;                        /*separating "/"        */
-    }
-
-    ++ret_value;                                /*terminating NULL      */
-
     class_path = H5P_get_class_path(plist->pclass);
 
     if (class_path)
@@ -437,31 +413,29 @@ H5O_plist_size(H5F_t UNUSED *f, const void *mesg)
         ++ret_value;
 
     HDfree(class_path);
-    ret_value += sizeof(plist->nprops) +           /*num properties     */
-                 sizeof(plist->pclass->hashsize);  /*hash size          */
 
-    for (i = 0; i < plist->pclass->hashsize; ++i) {
-        H5P_genprop_t *tprop = plist->props[i];
+    ret_value += sizeof(plist->nprops);            /*num properties     */
 
-        /* Walk through the list of properties at each hash location */
-        while (tprop) {
-            const char *n = tprop->name;
+    /* Calculate the size of the properties for this property list */
+    if(plist->nprops>0) {
+        H5TB_NODE *curr_node;   /* Current node in TBBT */
+        H5P_genprop_t *tprop;   /* Pointer to property */
 
-            ret_value += sizeof(tprop->xor_val) + /*xored value         */
-                         sizeof(size_t);          /*length of the name  */
+        /* Walk through the properties in the old class */
+        curr_node=H5TB_first(plist->props->root);
+        while(curr_node!=NULL) {
+            /* Get a pointer to the property from the node */
+            tprop=curr_node->data;
 
-            if (n && *n)
-                ret_value += HDstrlen(n) + 1;   /*the name              */
-            else
-                ++ret_value;                    /*the name: NULL        */
+            ret_value += sizeof(size_t);            /*length of the name  */
+            ret_value += HDstrlen(tprop->name) + 1; /*the name              */
+            ret_value += sizeof(tprop->size) +      /*size of data size     */
+                         tprop->size;               /*the data              */
 
-            ret_value += sizeof(tprop->size) +  /*size of data size     */
-                         tprop->size;           /*the data              */
-
-            /* Go to next registered property in class */
-            tprop = tprop->next;
-        }
-    }
+            /* Get the next property node in the TBBT */
+            curr_node=H5TB_next(curr_node);
+        } /* end while */
+    } /* end if */
 
 done:
     FUNC_LEAVE(ret_value);
@@ -513,8 +487,7 @@ H5O_plist_debug(H5F_t UNUSED *f, const void *mesg, FILE *stream,
                 int indent, int fwidth)
 {
     const H5P_genplist_t *plist = (const H5P_genplist_t *)mesg;
-    herr_t ret_value = SUCCEED;
-    unsigned int i;
+    herr_t ret_value=SUCCEED;
 
     FUNC_ENTER_NOAPI(H5O_plist_debug, FAIL);
 
@@ -531,27 +504,30 @@ H5O_plist_debug(H5F_t UNUSED *f, const void *mesg, FILE *stream,
     HDfprintf(stream, "%*sProperties {\n", indent, "");
     indent += 2;
 
-    for (i = 0; i < plist->pclass->hashsize; ++i) {
-        H5P_genprop_t *tprop = plist->props[i];
+    /* Calculate the size of the properties for this property list */
+    if(plist->nprops>0) {
+        H5TB_NODE *curr_node;   /* Current node in TBBT */
+        H5P_genprop_t *tprop;   /* Pointer to property */
 
-        /* Walk through the list of properties at each hash location */
-        while (tprop) {
+        /* Walk through the properties in the old class */
+        curr_node=H5TB_first(plist->props->root);
+        while(curr_node!=NULL) {
             register unsigned int j;
 
+            /* Get a pointer to the property from the node */
+            tprop=curr_node->data;
+
             HDfprintf(stream, "%*sProperty {\n", indent, "");
             indent += 2;
 
             /*
-             * Copy the meat of the generic property:
+             * Print the meat of the generic property:
              *
              *      1. The name of the property
-             *      2. The XORed version of the name
-             *      3. The size of the property value
-             *      4. The property value
+             *      2. The size of the property value
+             *      3. The property value
              */
-            HDfprintf(stream, "%*sName: ", indent, "");
-            HDfprintf(stream, "%s\n", tprop->name ? tprop->name : "(null)");
-            HDfprintf(stream, "%*sXOR Value: %d\n", indent, "", tprop->xor_val);
+            HDfprintf(stream, "%*sName: %s\n", indent, "", tprop->name);
             HDfprintf(stream, "%*sValue Size: %d\n", indent, "", tprop->size);
             HDfprintf(stream, "%*sValue: ", indent, "");
 
@@ -561,10 +537,10 @@ H5O_plist_debug(H5F_t UNUSED *f, const void *mesg, FILE *stream,
             indent -= 2;
             HDfprintf(stream, "\n%*s}\n", indent, "");
 
-            /* Go to next registered property in class */
-            tprop = tprop->next;
-        }
-    }
+            /* Get the next property node in the TBBT */
+            curr_node=H5TB_next(curr_node);
+        } /* end while */
+    } /* end if */
 
     indent -= 2;
     HDfprintf(stream, "%*s}\n", indent, "");