subversion-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Hyrum K Wright <hyrum.wri...@wandisco.com>
Subject Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Date Thu, 03 May 2012 19:53:27 GMT
On Thu, May 3, 2012 at 2:16 AM,  <stefan2@apache.org> wrote:
> Author: stefan2
> Date: Thu May  3 07:16:11 2012
> New Revision: 1333326
>
> URL: http://svn.apache.org/viewvc?rev=1333326&view=rev
> Log:
> Introduce private API functions that wrap apr_hash_make_custom
> and return hash tables that are 2 to 4 times faster than the APR default.
> Both yield repeatable results (each instance will store items in the same
> order if the keys are the same). The first, svn_hask__make will return
> a hash table that behaves like pre APR 1.4.6 default hashes.
>
> * subversion/include/private/svn_hash_private.h
>  (svn_hash__make, svn_hash__make_fast): new private API
> * subversion/libsvn_subr/hash.c
>  (svn_hash_from_cstring_keys): use new API
>  (hashfunc_compatible, LOWER_7BITS_SET, BIT_7_SET, READ_CHUNK,
>   hashfunc_fast): implement efficient hash functions
>  (svn_hash__make, svn_hash__make_fast): implement new private API
> * subversion/libsvn_fs_fs/temp_serializer.c
>  (deserialize_dir, svn_fs_fs__deserialize_properties): use new API
>
> Modified:
>    subversion/trunk/subversion/include/private/svn_hash_private.h
>    subversion/trunk/subversion/libsvn_fs_fs/temp_serializer.c
>    subversion/trunk/subversion/libsvn_subr/hash.c
>
> Modified: subversion/trunk/subversion/include/private/svn_hash_private.h
> URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/include/private/svn_hash_private.h?rev=1333326&r1=1333325&r2=1333326&view=diff
> ==============================================================================
> --- subversion/trunk/subversion/include/private/svn_hash_private.h (original)
> +++ subversion/trunk/subversion/include/private/svn_hash_private.h Thu May  3 07:16:11
2012
> @@ -102,6 +102,31 @@ svn_hash__get_bool(apr_hash_t *hash,
>
>  /** @} */
>
> +/**
> + * @defgroup svn_hash_create Create optimized APR hash tables
> + * @{
> + */
> +
> +/** Returns a hash table, allocated in @a pool, with the same ordering of
> + * elements as APR 1.4.5 or earlier (using apr_hashfunc_default) but uses
> + * a faster hash function implementation.
> + *
> + * @since New in 1.8.
> + */
> +apr_hash_t *
> +svn_hash__make(apr_pool_t *pool);
> +
> +/** Returns a hash table, allocated in @a pool, that is faster to modify
> + * and access then the ones returned by @ref svn_hash__make. The element
> + * order does not match any APR default.
> + *
> + * @since New in 1.8.
> + */
> +apr_hash_t *
> +svn_hash__make_fast(apr_pool_t *pool);
> +
> +/** @} */
> +
>  /** @} */
>
>  #ifdef __cplusplus
>
> Modified: subversion/trunk/subversion/libsvn_fs_fs/temp_serializer.c
> URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/temp_serializer.c?rev=1333326&r1=1333325&r2=1333326&view=diff
> ==============================================================================
> --- subversion/trunk/subversion/libsvn_fs_fs/temp_serializer.c (original)
> +++ subversion/trunk/subversion/libsvn_fs_fs/temp_serializer.c Thu May  3 07:16:11 2012
> @@ -30,6 +30,7 @@
>
>  #include "private/svn_fs_util.h"
>  #include "private/svn_temp_serializer.h"
> +#include "private/svn_hash_private.h"
>
>  #include "temp_serializer.h"
>
> @@ -359,7 +360,7 @@ serialize_dir(apr_hash_t *entries, apr_p
>  static apr_hash_t *
>  deserialize_dir(void *buffer, hash_data_t *hash_data, apr_pool_t *pool)
>  {
> -  apr_hash_t *result = apr_hash_make(pool);
> +  apr_hash_t *result = svn_hash__make(pool);
>   apr_size_t i;
>   apr_size_t count;
>   svn_fs_dirent_t *entry;
> @@ -678,7 +679,7 @@ svn_fs_fs__deserialize_properties(void *
>                                   apr_size_t data_len,
>                                   apr_pool_t *pool)
>  {
> -  apr_hash_t *hash = apr_hash_make(pool);
> +  apr_hash_t *hash = svn_hash__make(pool);
>   properties_data_t *properties = (properties_data_t *)data;
>   size_t i;
>
>
> Modified: subversion/trunk/subversion/libsvn_subr/hash.c
> URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/hash.c?rev=1333326&r1=1333325&r2=1333326&view=diff
> ==============================================================================
> --- subversion/trunk/subversion/libsvn_subr/hash.c (original)
> +++ subversion/trunk/subversion/libsvn_subr/hash.c Thu May  3 07:16:11 2012
> @@ -40,6 +40,7 @@
>  #include "svn_pools.h"
>
>  #include "private/svn_dep_compat.h"
> +#include "private/svn_string_private.h"
>  #include "private/svn_hash_private.h"
>
>  #include "svn_private_config.h"
> @@ -496,7 +497,7 @@ svn_hash_from_cstring_keys(apr_hash_t **
>                            apr_pool_t *pool)
>  {
>   int i;
> -  apr_hash_t *hash = apr_hash_make(pool);
> +  apr_hash_t *hash = svn_hash__make(pool);
>   for (i = 0; i < keys->nelts; i++)
>     {
>       const char *key =
> @@ -561,3 +562,127 @@ svn_hash__get_bool(apr_hash_t *hash, con
>   return default_value;
>  }
>
> +
> +
> +/*** Optimized hash functions ***/
> +
> +/* Optimized version of apr_hashfunc_default. It assumes that the CPU has
> + * 32-bit multiplications with high throughput of at least 1 operation
> + * every 3 cycles. Latency is not an issue. Another optimization is a
> + * mildly unrolled main loop.
> + */
> +static unsigned int
> +hashfunc_compatible(const char *char_key, apr_ssize_t *klen)
> +{
> +    unsigned int hash = 0;
> +    const unsigned char *key = (const unsigned char *)char_key;
> +    const unsigned char *p;
> +    apr_ssize_t i;
> +
> +    if (*klen == APR_HASH_KEY_STRING)
> +      {
> +        for (p = key; ; p+=4)
> +          {
> +            unsigned int new_hash = hash * 33 * 33 * 33 * 33;
> +            if (!p[0]) break;
> +            new_hash += p[0] * 33 * 33 * 33;
> +            if (!p[1]) break;
> +            new_hash += p[1] * 33 * 33;
> +            if (!p[2]) break;
> +            new_hash += p[2] * 33;
> +            if (!p[3]) break;
> +            hash = new_hash + p[3];
> +          }
> +        for (; *p; p++)
> +            hash = hash * 33 + *p;
> +
> +        *klen = p - key;
> +      }
> +    else
> +      {
> +        for (p = key, i = *klen; i >= 4; i-=4, p+=4)
> +          {
> +            hash = hash * 33 * 33 * 33 * 33
> +                 + p[0] * 33 * 33 * 33
> +                 + p[1] * 33 * 33
> +                 + p[2] * 33
> +                 + p[3];
> +          }
> +        for (; i; i--, p++)
> +            hash = hash * 33 + *p;
> +      }
> +
> +    return hash;
> +}
> +
> +#define LOWER_7BITS_SET 0x7f7f7f7f
> +#define BIT_7_SET       0x80808080
> +
> +#if SVN_UNALIGNED_ACCESS_IS_OK
> +#  define READ_CHUNK(p)\
> +     *(const apr_uint32_t *)(p);
> +#else
> +#  define READ_CHUNK(p) \
> +     (   (apr_uint32_t)p[0]        \
> +      + ((apr_uint32_t)p[1] << 8)  \
> +      + ((apr_uint32_t)p[2] << 16) \
> +      + ((apr_uint32_t)p[3] << 24))
> +#endif
> +
> +/* Similar to the previous but operates on 4 bytes at once instead of the
> + * classic unroll. This is particularly fast when unaligned access is
> + * supported.
> + */
> +static unsigned int
> +hashfunc_fast(const char *char_key, apr_ssize_t *klen)
> +{
> +    unsigned int hash = 0;
> +    const unsigned char *key = (const unsigned char *)char_key;
> +    const unsigned char *p;
> +    apr_ssize_t i;
> +    apr_uint32_t chunk, test;
> +
> +    if (*klen == APR_HASH_KEY_STRING)
> +      {
> +        for (p = key; ; p += sizeof(chunk))
> +          {
> +            /* This is a variant of the well-known strlen test: */
> +            chunk = READ_CHUNK(p);
> +            test = chunk | ((chunk & LOWER_7BITS_SET) + LOWER_7BITS_SET);
> +            if ((test & BIT_7_SET) != BIT_7_SET)
> +              break;
> +
> +            hash = (hash + chunk) * 0xd1f3da69;
> +          }
> +        for (; i; i--, p++)

i is being used uninitialized here, giving potential bogus results.

-Hyrum

> +            hash = hash * 33 + *p;
> +
> +        *klen = p - key;
> +      }
> +    else
> +      {
> +        for ( p = key, i = *klen
> +            ; i >= sizeof(chunk)
> +            ; i -= sizeof(chunk), p += sizeof(chunk))
> +          {
> +            chunk = READ_CHUNK(p);
> +            hash = (hash + chunk) * 0xd1f3da69;
> +          }
> +        for (; i; i--, p++)
> +            hash = hash * 33 + *p;
> +      }
> +
> +    return hash;
> +}
> +
> +apr_hash_t *
> +svn_hash__make(apr_pool_t *pool)
> +{
> +  return apr_hash_make_custom(pool, hashfunc_compatible);
> +}
> +
> +apr_hash_t *
> +svn_hash__make_fast(apr_pool_t *pool)
> +{
> +  return apr_hash_make_custom(pool, hashfunc_fast);
> +}
>
>



-- 

uberSVN: Apache Subversion Made Easy
http://www.uberSVN.com/

Mime
View raw message