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
[EMAIL PROTECTED]
Charlottesville, VA
