call for vote Re: [PATCH] Re: Frankentables

[Brian Pane <br...@cnet.com>]

Thanks.  IMHO, a 4x increase in CPU usage for the worst
case isn't a problem, as that's a 4x increase in an operation
that's only a few percent of the total cycles anyway.

But since the 4x degradation in the worst case may be
controversial, I'd like to have a vote first.  I'm +1 for
making this change in APR. Can a few other committers weigh in?

Thanks,
Brian

On Tue, 2003-05-20 at 17:25, Joe Schaefer wrote:
> Brian Pane <br...@cnet.com> writes:
> 
> > Thanks, it works much better with that change.
> > One more question: do you have a way to get "before" and
> > "after" profile data for a request with a ridiculously
> > large number of header fields (e.g., 90 different Cookie
> > or Accept lines that need to get merged)?  A default httpd
> > config will allow up to a 100-line header, which is a large
> > enough 'n' to make me paranoid about O(n^2) DoS vulnerabilities.
> 
> I had to patch ab to allow it to take a large enough 
> set of headers.
> 
> % perl -wle '$xx="aa";$args.="-H Cook".++$xx.":foo=bar " for 1..48; \
>   exec qq{ab $args $args -n 50000 -c 50 http://127.0.0.1:8080/foo}'
> 
> % oprofile -rl /home/joe/apache2/bin/httpd | head
> 
> 
> UNPATCHED:
> vma      samples  %           symbol name             
> 00075fb4 9007     20.0071     __GI___strcasecmp       
> 00009d3c 8553     18.9986     __pthread_internal_tsd_address 
> 0000cf00 2294     5.09563     overlap_hash            
> 0000d13c 1900     4.22044     apr_table_overlap       
> 0808852c 1867     4.14714     ap_rgetline_core        
> 000762d8 1254     2.78549     memcpy                  
> 000177d4 787      1.74815     apr_palloc              
> 0808ddbc 551      1.22393     core_input_filter       
> 00075b10 482      1.07066     __memchr                
> 
> 
> PATCHED:
> vma      samples  %           symbol name             
> 00075fb4 35642    35.7866     __GI___strcasecmp       
> 00009d3c 35549    35.6932     __pthread_internal_tsd_address 
> 0000c41c 3134     3.14671     apr_table_compress      
> 000762d8 1454     1.4599      memcpy                  
> 0808852c 1453     1.45889     ap_rgetline_core        
> 0000c010 1450     1.45588     apr_array_pstrjoin      
> 00017bb8 811      0.81429     apr_palloc              
> 00006214 621      0.623519    apr_brigade_split_line  
> 0808ddbc 578      0.580345    core_input_filter       
> 
> So it looks like the worst case scenario is 
> worsened by a factor of 4.

Re: call for vote Re: [PATCH] Re: Frankentables

[Joe Schaefer <jo...@sunstarsys.com>]

Bill Stoddard <bi...@wstoddard.com> writes:

[...]

> At about how many headers is the performance benefits of this patch
> lost? 

It's hard to give a brief answer to this question, but I'll 
give it a try.

The patch leverages the checksum & table index code; it will
win whenever those optimizations are working well, and 
it will lose when they are working poorly.

There are essentially two factors that go into this:

  1) the quality of the key_checksum,
  2) the spread between index_first and index_last.

The checksum is good whenever headers are distinguishable
by their first 4 letters, since it eliminates calls to
strcasecmp.  The spread between index_first & index_last
measures the "clumpiness" of the distribution of the 
headers' first letters.

Normally both of these factors are in the patch's favor.
Typically the key_checksum can distinguish most headers, 
and the spread between index_first & index_last for 
each letter is less than 16.  I would expect the patch 
to win in such cases.

For example, the headers range here from "Acommon" to
"Pcommon" and are duplicated once.  Even though the
spread for each letter ("A" .. "P") is 16, which is
atypically large, the  key_checksum can distinguish 
headers and the patch wins:

% perl -wle '$X="A";$args.="-H ".$X++."common:foo=bar " for 1..16; \
  exec qq{ab $args $args -n 50000 -c 50 http://127.0.0.1:8080/foo}'

=> UNPATCHED   : 895 requests/second
   APR PATCHED : 913 requests/second

But the pathological case is when all headers have at
least the first four letters in common. In such a situation,
the above optimizations are worthless, and the patch 
underperforms the current code at about 8 headers 
(because strcasecmp is grinding up the CPU).


-- 
Joe Schaefer

Re: call for vote Re: [PATCH] Re: Frankentables

[Bill Stoddard <bi...@wstoddard.com>]

Brian Pane wrote:

>Thanks.  IMHO, a 4x increase in CPU usage for the worst
>case isn't a problem, as that's a 4x increase in an operation
>that's only a few percent of the total cycles anyway.
>
>But since the 4x degradation in the worst case may be
>controversial, I'd like to have a vote first.  I'm +1 for
>making this change in APR. Can a few other committers weigh in?
>
>Thanks,
>Brian
>

At about how many headers is the performance benefits of this patch lost?

Bill