apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Joe Schaefer <joe+gm...@sunstarsys.com>
Subject Re: [PATCH] Re: Frankentables
Date Sun, 18 May 2003 21:00:23 GMT
Brian Pane <brian.pane@cnet.com> writes:

[...]

> Thanks for posting the oprofile data.  The results 
> look good.  I haven't had time to read through the
> code in detail yet, but I'll do that this afternoon.

Thanks alot, Brian!

> Based on a first glance at the code, the only thing
> that worries me is the comment about apr_table_compress()
> taking quadratic time.  I think it's possible to use a
> mergesort-based algorithm to do the compress in
> n*log(n) time and linear space, though.

It'll likely be slower for small-sized tables, though,
just like the red-black tree implementation. IIRC httpd has
a cutoff for the maximum number of input headers, so this 
"worst-case-quadratic-time" shouldn't present a DOS-able
issue for httpd.

In any case, it's no problem to keep the complex
algorithms here for larger tables; but apr_tables_get()
is still going to be O(n) in such cases.  Unfortunately,
any sort of conditionals in apr_tables_get tends to kill
its httpd (many small tables) performance.

Maybe the documentation should just recommend apr_hash in
cases where the number of elements is more than what is
typical (a few dozen?) for httpd.

-- 
Joe Schaefer


Mime
View raw message