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
|