Brian Pane <[EMAIL PROTECTED]> 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
