httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Bill Stoddard" <b...@wstoddard.com>
Subject Re: 2.0.24 tagged.
Date Thu, 16 Aug 2001 20:33:14 GMT
> > > Where do we spend cycles in mod_mime today (in httpd-1.3)? In merge or in lookups?
> Using
> > > the hash table will clearly improve look-up times.  One of the major reasons
we do
> merges
> > > is to handle .htaccess files. If we have .htaccess files, I would venture that
we
> spend
> > > MUCH more time doing file i/o than we would spend in doing hash table merges.
In
other
> > > words, improving the merge performance -may- not significantly improve overall
> performance
> > > in the .htaccess file case.
> >
> > My issue is that table merges are a o*n problem, while hash merges are an o*n2 problem
> :(
> >
>
> Hash merge is O(mn) in the worst case (the case when your hash function completely sucks
> :-).  The merge will tend to O(mlogn).
>
> Bill
>

Okay, I've thought about this some.  Your veto of my patch is unreasonable.

We should commit the simpified hash table patch I poster earlier. The hash implementation
will clearly outperform tables during lookups.  Hash merges are O(mlogn) and one of the
hash tables is typically small so my conclusion is that the merge operation will probably
not contribute significant overhead (as compared to a table merge), especially in the
cases where merges occur often (like when we open .htaccess files, where the overhead of
file io dominates the transaction).

The simplfied hash patch is better than tables, IMHO, so it should go in.

I am not opposed to better implementations but we should not introduce wicked complexity
for a bit extra performance, especially without benchmarking.

Bill


Mime
View raw message