You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2012/05/03 09:16:11 UTC
svn commit: r1333326 - in /subversion/trunk/subversion:
include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c
libsvn_subr/hash.c
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++)
+ 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);
+}
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h
libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Stefan Fuhrmann <eq...@web.de>.
Hyrum K Wright wrote:
> On Thu, May 3, 2012 at 2:16 AM,<st...@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
>
Yup. I've already stumbled across that one when I ran
some benchmarks for Philip. Fixed in r1333779.
-- Stefan^2.
Re: svn commit: r1333326 - in /subversion/trunk/subversion:
include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Hyrum K Wright <hy...@wandisco.com>.
On Thu, May 3, 2012 at 2:16 AM, <st...@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/
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h
libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Stefan Fuhrmann <eq...@web.de>.
Greg Stein wrote:
> On Thu, May 3, 2012 at 3:16 AM,<st...@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
> It would be great to just use svn_subr_private.h.
I've been mislead by svn_string_private.h & friends.
But having just one private header per lib definitely
makes more sense.
Moved in r1333340.
>> ...
>> +++ subversion/trunk/subversion/libsvn_subr/hash.c Thu May 3 07:16:11 2012
>> ...
>> +#if SVN_UNALIGNED_ACCESS_IS_OK
>> +# define READ_CHUNK(p)\
>> + *(const apr_uint32_t *)(p);
> erroneous trailing semicolon. this can stay on a single line, too.
Oops. Fixed in r1333354.
Thanks for the review!
-- Stefan^2.
Re: svn commit: r1333326 - in /subversion/trunk/subversion:
include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Greg Stein <gs...@gmail.com>.
On Thu, May 3, 2012 at 3:16 AM, <st...@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
It would be great to just use svn_subr_private.h.
>...
> +++ subversion/trunk/subversion/libsvn_subr/hash.c Thu May 3 07:16:11 2012
>...
> +#if SVN_UNALIGNED_ACCESS_IS_OK
> +# define READ_CHUNK(p)\
> + *(const apr_uint32_t *)(p);
erroneous trailing semicolon. this can stay on a single line, too.
>...
Cheers,
-g
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Julian Foad <ju...@btopenworld.com>.
Greg Stein wrote:
> Branko Čibej wrote:
>> I'd really like to see you explain why this change of yours (33 ->
>> 33^4) is relevant in practice. It's not at all clear that this
>> multiplier gives a better key distribution than the time-honoured 33.
>
> Actually, there are some reasoned/studied arguments for 33 ("it works
> well, but nobody knows why"). And 33^4 is likely a poor replacement
> :-P
Stefan's version is not using a different multiplier, it's just unrolling the loop to do four of the multiplications at once, AFAICT.
- Julian
Re: svn commit: r1333326 - in /subversion/trunk/subversion:
include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Greg Stein <gs...@gmail.com>.
On Wed, May 23, 2012 at 12:44 AM, Branko Čibej <br...@apache.org> wrote:
>...
> I'd really like to see you explain why this change of yours (33 -> 33^4)
> is relevant in practice. It's not at all clear that this multiplier
> gives a better key distribution than the time-honoured 33.
Actually, there are some reasoned/studied arguments for 33 ("it works
well, but nobody knows why"). And 33^4 is likely a poor replacement
:-P
For PoCore's hash table[1], I did a survey of the research around
hashing functions. I selected the FNV-1 hash function:
http://www.isthe.com/chongo/tech/comp/fnv/
Comparisons of functions are here:
http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
The 33 variety is named as the "Bernstein hash".
> It's my considered opinion that this fiddling around with hash function
> implementations is way overboard. Just use apr_hashfunc_default already.
> Unless you can prove that using your "optimized" version results in
> siginificant savings in space and/or time, anything else is just piling
> on more lines of code that need to be maintained for no good reason.
I'm assuming Stefan ran some tests, and (iirc) saw a few percent
increase. For that, maybe a new hash function is okay. (it isn't like
he built a whole new type; just a new func)
Cheers,
-g
[1] http://pocore.googlecode.com/svn/trunk/src/hash.c
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h
libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Branko Čibej <br...@apache.org>.
On 22.05.2012 21:01, Stefan Fuhrmann wrote:
> Am 21.05.2012 12:38, schrieb Julian Foad:
>> Stefan Fuhrmann wrote:
>>> Julian Foad wrote:
>>>>> URL:http://svn.apache.org/viewvc?rev=1333326&view=rev
>>>>> 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.
>>>> Would it be sensible to propose these (the hash-functions) for
>>>> inclusion in APR itself?
>>> Certainly. The question would be whether Apache is
>>> meant to run on CPUs without a decent MUL.
>> I don't understand why that question is relevant.
>
> APRs implementation uses 33 as multiplier which
> can conveniently be implemented as shift & add.
> My code uses factors up to 33^4 where that
> optimization / workaround would no longer be
> useful. A non-pipelined MUL operation may take
> as much as 40 ticks (i386) instead of 2 .. 6 ticks for
> shift&add.
I'd really like to see you explain why this change of yours (33 -> 33^4)
is relevant in practice. It's not at all clear that this multiplier
gives a better key distribution than the time-honoured 33.
It's my considered opinion that this fiddling around with hash function
implementations is way overboard. Just use apr_hashfunc_default already.
Unless you can prove that using your "optimized" version results in
siginificant savings in space and/or time, anything else is just piling
on more lines of code that need to be maintained for no good reason.
-- Brane
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h
libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Stefan Fuhrmann <eq...@web.de>.
Am 21.05.2012 12:38, schrieb Julian Foad:
> Stefan Fuhrmann wrote:
>> Julian Foad wrote:
>>>> URL:http://svn.apache.org/viewvc?rev=1333326&view=rev
>>>> 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.
>>> Would it be sensible to propose these (the hash-functions) for
>>> inclusion in APR itself?
>> Certainly. The question would be whether Apache is
>> meant to run on CPUs without a decent MUL.
> I don't understand why that question is relevant.
APRs implementation uses 33 as multiplier which
can conveniently be implemented as shift & add.
My code uses factors up to 33^4 where that
optimization / workaround would no longer be
useful. A non-pipelined MUL operation may take
as much as 40 ticks (i386) instead of 2 .. 6 ticks for
shift&add.
I don't know of any popular CPUs that have this
problem but OTOH, I don't know all exotic platforms /
embedded devices that Apache is being run on.
>>>> 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
>>>> +/*** 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.
>>> Such specific details should at least refer to a specific version
>>> of apr_hashfunc_default(). Perhaps also (for the "1 op per 3 cycles"
>>> part, in particular) a specific system architecture or compiler.
>> r1340601 explains why that is a reasonable assumption.
> What's missing is a statement that this is an optimized version of
> "apr_hashfunc_default in APR 1.4.5".
Added the version info in r1341271.
-- Stefan^2.
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Julian Foad <ju...@btopenworld.com>.
Stefan Fuhrmann wrote:
> Julian Foad wrote:
>>> URL:http://svn.apache.org/viewvc?rev=1333326&view=rev
>>> 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.
>>
>> Would it be sensible to propose these (the hash-functions) for
>> inclusion in APR itself?
>
> Certainly. The question would be whether Apache is
> meant to run on CPUs without a decent MUL.
I don't understand why that question is relevant.
>> I suggest changing the names to
>>
>> svn_hash__make_compatible
>> svn_hash__make # faster than the 'compatible' one
>>
>> [...]
>
> The "fast" variant had a potential page overflow (segfault).
> Fixing that issue would have made it slower than the
> compatible version for the APR_HASH_KEY_STRING case.
> Because the latter constitutes the vast majority of uses
> within SVN, I remove the *_fast code in r1340590.
Great, it's better to just have one version.
>>> 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
>>> +/*** 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.
>>
>> Such specific details should at least refer to a specific version
>> of apr_hashfunc_default(). Perhaps also (for the "1 op per 3 cycles"
>> part, in particular) a specific system architecture or compiler.
>
> r1340601 explains why that is a reasonable assumption.
What's missing is a statement that this is an optimized version of
"apr_hashfunc_default in APR 1.4.5".
- Julian
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h
libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Stefan Fuhrmann <eq...@web.de>.
Julian Foad wrote:
>> URL:http://svn.apache.org/viewvc?rev=1333326&view=rev
>> 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.
> Would it be sensible to propose these (the hash-functions) for inclusion in APR itself?
Certainly. The question would be whether Apache is
meant to run on CPUs without a decent MUL.
>> 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
> s/hask/hash/
Thanks for fixing!
>> 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
> I suggest changing the names to
>
> svn_hash__make_compatible
>
> svn_hash__make # faster than the 'compatible' one
>
> because being compatible is a specific requirement that some callers have (that might compromise speed or other properties), so we make this property explicit, whereas being "fast" is a vague and relative term that no caller specifically needs or doesn't need, it's just generally good for any function to be as fast as possible within its specific constraints.
>
>
> If we still have code that depends on the original hash ordering, then we wouldn't be able to drop in 'svn_hash__make' (the non-compatible version) as a direct replacement for apr_hash_make() throughout the code base -- but I don't know that we do have any such dependencies.
>
The "fast" variant had a potential page overflow (segfault).
Fixing that issue would have made it slower than the
compatible version for the APR_HASH_KEY_STRING case.
Because the latter constitutes the vast majority of uses
within SVN, I remove the *_fast code in r1340590.
>> 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
>> +/*** 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.
> Such specific details should at least refer to a specific version of apr_hashfunc_default(). Perhaps also (for the "1 op per 3 cycles" part, in particular) a specific system architecture or compiler.
r1340601 explains why that is a reasonable assumption.
>> + */
>> +static unsigned int
>> +hashfunc_compatible(const char *char_key, apr_ssize_t *klen)
> - Julian
>
Thanks for the review!
-- Stefan^2.
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Julian Foad <ju...@btopenworld.com>.
> URL: http://svn.apache.org/viewvc?rev=1333326&view=rev
> 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.
Would it be sensible to propose these (the hash-functions) for inclusion in APR itself?
> 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
s/hask/hash/
> 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
I suggest changing the names to
svn_hash__make_compatible
svn_hash__make # faster than the 'compatible' one
because being compatible is a specific requirement that some callers have (that might compromise speed or other properties), so we make this property explicit, whereas being "fast" is a vague and relative term that no caller specifically needs or doesn't need, it's just generally good for any function to be as fast as possible within its specific constraints.
If we still have code that depends on the original hash ordering, then we wouldn't be able to drop in 'svn_hash__make' (the non-compatible version) as a direct replacement for apr_hash_make() throughout the code base -- but I don't know that we do have any such dependencies.
> * 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/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
s/faster...then/faster...than/
>+ * order does not match any APR default.
>+ *
>+ * @since New in 1.8.
>+ */
>+apr_hash_t *
>+svn_hash__make_fast(apr_pool_t *pool);
>+
>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
>+/*** 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.
Such specific details should at least refer to a specific version of apr_hashfunc_default(). Perhaps also (for the "1 op per 3 cycles" part, in particular) a specific system architecture or compiler.
>+ */
>+static unsigned int
>+hashfunc_compatible(const char *char_key, apr_ssize_t *klen)
- Julian
Re: svn commit: r1333326 - in /subversion/trunk/subversion:
include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Hyrum K Wright <hy...@wandisco.com>.
On Thu, May 3, 2012 at 2:16 AM, <st...@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/
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h
libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Stefan Fuhrmann <eq...@web.de>.
Philip Martin wrote:
> Philip Martin<ph...@wandisco.com> writes:
>
>> stefan2@apache.org writes:
>>
>>> 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.
>> How do you benchmark something like that? What is 2 to 4 times faster?
>> Is it the runtime of the function? Does it include or exclude function
>> call overhead? What sort of data? Is it relatively short data like
>> paths or much larger data?
This patch is about two things:
* become (somewhat) independent of changes to the
APR default hash function
* make building hashes and data lookup faster (2 .. 4 times)
IMO, the first point alone would warrant the usage of the
new function(s).
I originally wrote the hash functions for the revprop caching
(whole hash gets read from cache but often only one entry
will eventually be used). So, the keys were quite short. Also,
the largest speedup is being reached when the key length
is known in advance - which is the case for cached items.
> Is the hash function showing up as significant when you profile
> Subversion on some workload?
>
(Rev)prop or directory heavy operations should benefit
significantly. For a fair benchmark, I simply profiled svnserve
when running the "large_dirs.sh" benchmark against it. So,
for a mixture of 'svn ls', 'svn co' and 'svn ci', the overall
speedup was still 1.5% when all calls to apr_hash_make
were replaced with svn_hash__make.
-- Stefan^2.
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Philip Martin <ph...@wandisco.com>.
Philip Martin <ph...@wandisco.com> writes:
> stefan2@apache.org writes:
>
>> 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.
>
> How do you benchmark something like that? What is 2 to 4 times faster?
> Is it the runtime of the function? Does it include or exclude function
> call overhead? What sort of data? Is it relatively short data like
> paths or much larger data?
Is the hash function showing up as significant when you profile
Subversion on some workload?
--
uberSVN: Apache Subversion Made Easy
http://www.uberSVN.com
Re: svn commit: r1333326 - in /subversion/trunk/subversion: include/private/svn_hash_private.h libsvn_fs_fs/temp_serializer.c libsvn_subr/hash.c
Posted by Philip Martin <ph...@wandisco.com>.
stefan2@apache.org writes:
> 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.
How do you benchmark something like that? What is 2 to 4 times faster?
Is it the runtime of the function? Does it include or exclude function
call overhead? What sort of data? Is it relatively short data like
paths or much larger data?
On my system the compiled code is 425 bytes, compared to 102 bytes for
the APR code. That means your code pushes over 300 other bytes out
of the cache. Does that mean something else gets slower?
Should this code be in APR rather than Subversion?
--
Philip