httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dean gaudet <d...@arctic.org>
Subject Re: [PATCH 2] speedup for apr_table_t
Date Tue, 20 Nov 2001 08:22:31 GMT
On Sun, 18 Nov 2001, Brian Pane wrote:

> Good point--it's possible to construct an O(n^2) attack with this
> patch.  The same is true of qsort, which is O(n^2) in the worst
> case, but it's admittedly a lot harder to construct the worst-case
> data set with qsort.

hmm yeah i guess that's true.

> The most straightforward solution that I can think of is to
> build a balanced tree, rather than a chained hash table, out
> of the "overlap_key" nodes.  I'll post a revised patch once
> I get a tree implementation working.

dude you're hard core.

wouldn't a heap sort be better?  it's guaranteed O(n lg n), but the
constant factor tends to be 2x qsort's constant factor (which is why it's
not generally used).  however it needs less memory than a tree does.

btw we might want to just continue with qsort or your hash or something
for n less than some fixed constant -- and fall back to heap sort or a
tree for large n.  that way you get the perf benefit you desired with the
DoS protection.

-dean




Mime
View raw message