You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@apr.apache.org by Brian Pane <bp...@pacbell.net> on 2001/11/18 08:35:24 UTC
[PATCH] optimization for hash tables and pool userdata
This patch speeds up the apr_hash_t implementation's
handling of APR_HASH_KEY_STRING.
The original logic was:
call strlen to get the length of the key;
then iterate through the key to compute the hash;
This patch combines the two into a single pass.
It also changes apr_pool_userdata_get() to take
advantage of this optimization.
--Brian
Re: [PATCH] optimization for hash tables and pool userdata
Posted by Brian Pane <br...@cnet.com>.
Mladen Turk wrote:
[...]
>How about to add here something like:
>(in apr_hash.h add #define APR_HASH_KEY_UCASE (-2)
>
>+ else if (klen == APR_HASH_KEY_UCASE) {
>+ for (p = key; *p; p++) {
>+ hash = hash * 33 + apr_tolower(*p);
>+ }
>+ klen = p - (const unsigned char *)key;
>+ }
>
>that will give you the case insensitive hash table
>
I like this idea, with one modification: I think the
case-insensitive-string-key support should be an attribute
of the hash table that's set when the table is created,
rather than a parameter passed to apr_table_(get|set).
If it's passed on each get/set request, it's possible
for the table to get into a corrupted state. For
example, if somebody does this:
apr_hash_set(t, "Key", APR_HASH_KEY_STRING, value1);
apr_hash_set(t, "Key", APR_HASH_KEY_UCASE, value2);
then apr_hash_get(t, "Key", ...) will return either value1
or value2, depending on whether it's called with
APR_HASH_KEY_STRING_UCASE or not. That will really
confuse people.
So I'd prefer to do:
apr_hash_string_make(apr_pool_t *p, int is_case_sensitive)
which would create a hash table optimized for string keys.
There's actually a very good reason to do something like
this: the add_any_filter() function in Apache is slow because
it has to make lowercase copies of strings before passing
them to apr_hash_get(). Having a specialization of apr_hash_t
will support for case-insensitive string keys would improve
the performance. I'll post a patch for this sometime soon.
--Brian
RE: [PATCH] optimization for hash tables and pool userdata
Posted by Mladen Turk <mt...@mappingsoft.com>.
> -----Original Message-----
> From: Ian Holsman [mailto:ianh@cnet.com]
> Sent: Wednesday, November 21, 2001 6:03 PM
> To: Brian Pane
> Cc: dev@apr.apache.org
> Subject: Re: [PATCH] optimization for hash tables and pool userdata
>
>
> On Sat, 2001-11-17 at 23:35, Brian Pane wrote:
> > This patch speeds up the apr_hash_t implementation's
> > handling of APR_HASH_KEY_STRING.
> >
> > Index: srclib/apr/tables/apr_hash.c
> > + if (klen == APR_HASH_KEY_STRING) {
> > + for (p = key; *p; p++) {
> > + hash = hash * 33 + *p;
> > + }
> > + klen = p - (const unsigned char *)key;
> > + }
How about to add here something like:
(in apr_hash.h add #define APR_HASH_KEY_UCASE (-2)
+ else if (klen == APR_HASH_KEY_UCASE) {
+ for (p = key; *p; p++) {
+ hash = hash * 33 + apr_tolower(*p);
+ }
+ klen = p - (const unsigned char *)key;
+ }
that will give you the case insensitive hash table
> > + else {
> > + for (p = key, i = klen; i; i--, p++) {
> > + hash = hash * 33 + *p;
> > + }
> > + }
Re: [PATCH] optimization for hash tables and pool userdata
Posted by Ian Holsman <ia...@cnet.com>.
On Sat, 2001-11-17 at 23:35, Brian Pane wrote:
> This patch speeds up the apr_hash_t implementation's
> handling of APR_HASH_KEY_STRING.
>
> The original logic was:
> call strlen to get the length of the key;
> then iterate through the key to compute the hash;
>
> This patch combines the two into a single pass.
> It also changes apr_pool_userdata_get() to take
> advantage of this optimization.
>
> --Brian
>
Commited
Thanks Brian
>
> ----
>
> Index: srclib/apr/tables/apr_hash.c
> ===================================================================
> RCS file: /home/cvspublic/apr/tables/apr_hash.c,v
> retrieving revision 1.27
> diff -u -r1.27 apr_hash.c
> --- srclib/apr/tables/apr_hash.c 2001/11/10 17:58:36 1.27
> +++ srclib/apr/tables/apr_hash.c 2001/11/18 07:16:32
> @@ -222,9 +222,6 @@
> int hash;
> apr_ssize_t i;
>
> - if (klen == APR_HASH_KEY_STRING)
> - klen = strlen(key);
> -
> /*
> * This is the popular `times 33' hash algorithm which is used by
> * perl and also appears in Berkeley DB. This is one of the best
> @@ -263,8 +260,17 @@
> * -- Ralf S. Engelschall <rs...@engelschall.com>
> */
> hash = 0;
> - for (p = key, i = klen; i; i--, p++)
> - hash = hash * 33 + *p;
> + if (klen == APR_HASH_KEY_STRING) {
> + for (p = key; *p; p++) {
> + hash = hash * 33 + *p;
> + }
> + klen = p - (const unsigned char *)key;
> + }
> + else {
> + for (p = key, i = klen; i; i--, p++) {
> + hash = hash * 33 + *p;
> + }
> + }
>
> /* scan linked list */
> for (hep = &ht->array[hash & ht->max], he = *hep;
> Index: srclib/apr/memory/unix/apr_pools.c
> ===================================================================
> RCS file: /home/cvspublic/apr/memory/unix/apr_pools.c,v
> retrieving revision 1.115
> diff -u -r1.115 apr_pools.c
> --- srclib/apr/memory/unix/apr_pools.c 2001/10/29 14:54:19 1.115
> +++ srclib/apr/memory/unix/apr_pools.c 2001/11/18 07:16:33
> @@ -1312,7 +1312,7 @@
> if (cont->prog_data == NULL)
> *data = NULL;
> else
> - *data = apr_hash_get(cont->prog_data, key, strlen(key));
> + *data = apr_hash_get(cont->prog_data, key, APR_HASH_KEY_STRING);
> return APR_SUCCESS;
> }
>
--
Ian Holsman IanH@cnet.com
Performance Measurement & Analysis
CNET Networks - (415) 344-2608