apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Brian Pane <bp...@pacbell.net>
Subject [PATCH] Turn apr_table_t into a hash table
Date Fri, 07 Sep 2001 21:23:55 GMT
The attached patches change the apr_table_t implementation from
a linear list to a hash table (not an apr_hash_t, though!).  With
this change, I'm seeing a ~3% improvement in throughput when
delivering a 0-byte file over the loopback on Linux.  (I used this
0-byte test case to measure the inherent overhead in the httpd, without
transmission time clouding the results.)

Design notes:

  * The apr_table_t API is almost completely unchanged.  The one
    exception is that I removed the apr_array_elts macro and
    replaced it with a const iterator API.  The second of the
    attached patches changes the six places in the httpd-2.0 source
    that were impacted by this.

    Note: We could probably get even better performance through
    more radical reimplementations of the data structure for
    request_rec->headers_in, but I chose this more conservative
    approach because IMHO it's too late in the 2.0 development
    cycle to break that much code.  However, this patch does
    open the door to more optimizations in the future, by making
    apr_table_t an abstract data type.

  * The implementation is a chained hash table, with the elements
    in each chain kept in sorted order as a small additional
    optimization.

  * Each element in the hash table uses an array to support the
    storage of multiple values for the same key.  This complicates
    the code a bit, but I wanted to make sure that apr_table_addn()
    could still append values in O(1) time instead of O(n^2).

--Brian



Mime
View raw message