apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Brian Pane <bp...@pacbell.net>
Subject Re: What to do about tables?
Date Mon, 05 Nov 2001 08:35:16 GMT
Greg Stein wrote:

>On Sun, Nov 04, 2001 at 03:00:43PM -0800, Brian Pane wrote:
>
>>...
>>2. Change the performance-sensitive fields in the httpd's request_rec
>>   from apr_table_t (like r->headers_in) to some different data type
>>   (e.g., "ap_http_headers_t") that supports O(log(n)) or O(1) get/set
>>   operations
>>      Pros:
>>        * Performance improvement for the httpd
>>        * Other code that uses apr_table_t isn't affected
>>      Cons:
>>        * Lots of changes required to the httpd core and all modules
>>
>
>This is the most optimal approach. You can build a structure that is O(1)
>for the common headers (by using tokens for the headers rather than
>strings). Other headers can also be heavily optimized through a hash lookup.
>I think this custom type would be a wrapper around an apr_hash_t.
>

This would work well in combination with an enhancement to apr_hash_t.
The big problem with apr_hash_t is that it's inefficient when the keys
are case-insensitive strings.  Currently, the caller has to make a copy
of the key, normalize it to all-lowercase or all-caps, and then call
apr_hash_(get|set).  This defeats some of the performance benefits of
using a hash table.

IMHO, hash tables with case-insensitive string keys are an important
enough special case to justify custom code within apr_hash_t.  E.g.,

   apr_hash_t *apr_hash_make_case_insensitive(apr_pool_t *p);
   /* works the same as apr_hash_make, except that it sets a flag inside
    * the resulting hash table that tells the apr_hash_get functions to
    * use a case-insensitive hash function and strncasecmp instead of
    * memcmp
    */

There are some places in the current Apache 2.0 code where this would
let us optimize away some "strdup+tolower" operations; filter registration
is one good example.

--Brian



Mime
View raw message