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
|