Mailing-List: contact new-httpd-help@apache.org; run by ezmlm
Precedence: bulk
Reply-To: new-httpd@apache.org
Message-ID: <01cc01c12692$acba8470$c6431b09@sashimi>
From: "Bill Stoddard" <bill@wstoddard.com>
To: <new-httpd@apache.org>
References: <01081607250701.27473@koj.rkbloom.net>
 <04e601c1267c$dc4fc4e0$96c0b0d0@roweclan.net>
 <013a01c1267e$f6e23840$c6431b09@sashimi>
 <057901c12681$173ee8c0$96c0b0d0@roweclan.net>
 <01a601c1268e$07d7f6d0$c6431b09@sashimi>
Subject: Re: 2.0.24 tagged.
Date: Thu, 16 Aug 2001 16:33:14 -0400
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Status: O

> > > 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