apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Cliff Woolley <cliffwool...@yahoo.com>
Subject Re: [PATCH] speedup for apr_table_t
Date Sat, 17 Nov 2001 22:20:28 GMT
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


Mime
View raw message