Mailing-List: contact dev-help@apr.apache.org; run by ezmlm
Precedence: bulk
Date: Mon, 05 Nov 2001 00:35:16 -0800
From: Brian Pane <bpane@pacbell.net>
Subject: Re: What to do about tables?
To: dev@apr.apache.org
Message-id: <3BE64F44.1060102@pacbell.net>
MIME-version: 1.0
Content-type: text/plain; charset=us-ascii; format=flowed
Content-transfer-encoding: 7BIT
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.5) Gecko/20011012
References: <3BE5C89B.2080907@pacbell.net> <20011104190517.R13242@lyra.org>

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