[PATCH] speedup for apr_table_t

[Brian Pane <bp...@pacbell.net>]

This patch adds a cache to each element in an apr_table_t.
The cache consists of a 32-bit int containing the first 4 bytes
of the element's key, converted to uppercase.

This makes it possible to replace strcasecmp calls with inline
integer comparisons.  If the integer comparison fails, we can skip
the strcasecmp.  If the integer comparison succeeds, we can at
least skip the first 4 bytes of the strcmp.

In the httpd, this roughly doubles the speed of the
apr_table_get and apr_table_setn operations.

Two important notes:
* This patch increases the size of the apr_table_entry_t struct,
  so it requires a "make clean."
* The addition of an extra int to the apr_table_entry_t breaks
  mod_isapi.c, which assumes that the struct contains nothing
  but char* fields.  The patch includes a diff for mod_isapi.c
  to fix this, but that part is untested because I don't have
  a win32 compilation environment.

--Brian

Re: [PATCH] speedup for apr_table_t

[Brian Pane <bp...@pacbell.net>]

I wrote:
[...]

> I used the more complicated, shift-based approach because it
> guarantees that greater-than/less-than comparisons on the prefix
> will yield the same results as strcasecmp on the first 4 bytes.
> This makes it possible to use the prefix in the comparator
> function in the big qsort in apr_table_overlap, which does
> a *lot* of strcasecmp calls otherwise. 


hmmm...I'm having second thoughts about optimizing the prefix
design for apr_table_overlap.  Rather than trying to eliminate
strcasecmp calls within the qsort, it may be better to eliminate
the qsort altogether.

I have an idea for how to do this...if it works, we can use
Cliff's faster prefix code for get/set operations and still
speed up apr_table_overlap.

If all goes well, I'll post an updated patch later this weekend.

--Brian

Re: [PATCH] speedup for apr_table_t

[Brian Pane <bp...@pacbell.net>]

Cliff Woolley wrote:

>On Sat, 17 Nov 2001, Brian Pane wrote:
>
>>This patch adds a cache to each element in an apr_table_t.
>>The cache consists of a 32-bit int containing the first 4 bytes
>>of the element's key, converted to uppercase.
>>
>
>How about something like this:
>
>#ifndef EBCDIC
>#define CASE_MASK 0xdfdfdfdf
>#else
>#define CASE_MASK 0x0 /* whatever this is supposed to be */
>#endif
>
>#define COMPUTE_KEY_PREFIX(key, prefix)         \
>{                                               \
>    if (key[0] && key[1] && key[2] && key[3]) { \
>        prefix = (*((int *)(key))) & CASE_MASK; \
>    }                                           \
>    else {                                      \
>        prefix = 0;                             \
>    }                                           \
>

The only problem with this is that the bytes in the integer end up
"backwards" on little-endian machines.  That means that, while you
can check for equality on the prefix, you can't do greater-than/less-than
comparisons.

I used the more complicated, shift-based approach because it
guarantees that greater-than/less-than comparisons on the prefix
will yield the same results as strcasecmp on the first 4 bytes.
This makes it possible to use the prefix in the comparator
function in the big qsort in apr_table_overlap, which does
a *lot* of strcasecmp calls otherwise.

--Brian

Re: [PATCH] speedup for apr_table_t

[Cliff Woolley <cl...@yahoo.com>]

On Sat, 17 Nov 2001, Brian Pane wrote:

> This patch adds a cache to each element in an apr_table_t.
> The cache consists of a 32-bit int containing the first 4 bytes
> of the element's key, converted to uppercase.

How about something like this:

#ifndef EBCDIC
#define CASE_MASK 0xdfdfdfdf
#else
#define CASE_MASK 0x0 /* whatever this is supposed to be */
#endif

#define COMPUTE_KEY_PREFIX(key, prefix)         \
{                                               \
    if (key[0] && key[1] && key[2] && key[3]) { \
        prefix = (*((int *)(key))) & CASE_MASK; \
    }                                           \
    else {                                      \
        prefix = 0;                             \
    }                                           \
}

That means we're only optimizing the case where the key is at least four
bytes long, but if it isn't, are we really gaining a whole lot anyway?  It
does however mean that you can't skip the first 4 bytes in the
strcasecmp() if the two prefixes are equal and both 0.

This method yields much prettier looking assembly, at least (gcc -O2 on a
PIII), and might be a tad faster.  It still has to do four comparisons and
conditional branches, but it skips all the extra mov's and shifts, and
with this version you don't have to precompute all the touppers and then
look them up out of the table (though I will say that was an interesting
optimization).

Thoughts?  Are we really better off with one of these strategies than with
a fully indexed table or with an actual hash table?  I haven't gotten a
sure sense of that yet.

--Cliff

PS: I ran the two just to verify them:

Brian's encoder:
key = abcDEFghiJKLmnoPQRstuVWXyz
key prefix = 0x41424344 (1094861636)
prefix decoded = DCBA

Mine:
key = abcDEFghiJKLmnoPQRstuVWXyz
key prefix = 0x44434241 (1145258561)
prefix decoded = ABCD

Got a good way for me to benchmark these?  Just run them a million times
and see how long it takes?

--Cliff

--------------------------------------------------------------
   Cliff Woolley
   cliffwoolley@yahoo.com
   Charlottesville, VA