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
Index: srclib/apr/include/apr_tables.h
===================================================================
RCS file: /home/cvspublic/apr/include/apr_tables.h,v
retrieving revision 1.24
diff -u -r1.24 apr_tables.h
--- srclib/apr/include/apr_tables.h 2001/11/11 22:31:04 1.24
+++ srclib/apr/include/apr_tables.h 2001/11/17 07:12:19
@@ -130,6 +130,12 @@
*/
/** The value for the current table entry */
char *val;
+
+ /** The first 4 bytes of the key, converted to
+ * upppercase and packed into an int to support
+ * a fast, inline "mini-strcasecmp"
+ */
+ apr_uint32_t key_prefix;
};
/**
@@ -421,6 +427,12 @@
APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
unsigned flags);
+
+/**
+ * APR-private function for initializing the table package
+ * @internal
+ */
+void apr_table_init(void);
/** @} */
#ifdef __cplusplus
Index: srclib/apr/misc/unix/start.c
===================================================================
RCS file: /home/cvspublic/apr/misc/unix/start.c,v
retrieving revision 1.56
diff -u -r1.56 start.c
--- srclib/apr/misc/unix/start.c 2001/11/05 20:00:26 1.56
+++ srclib/apr/misc/unix/start.c 2001/11/17 07:12:19
@@ -83,6 +83,8 @@
return APR_ENOPOOL;
}
+ apr_table_init();
+
#if !defined(BEOS) && !defined(OS2) && !defined(WIN32) && !defined(NETWARE)
apr_unix_setup_lock();
apr_proc_mutex_unix_setup_lock();
Index: srclib/apr/tables/apr_tables.c
===================================================================
RCS file: /home/cvspublic/apr/tables/apr_tables.c,v
retrieving revision 1.17
diff -u -r1.17 apr_tables.c
--- srclib/apr/tables/apr_tables.c 2001/08/02 03:18:44 1.17
+++ srclib/apr/tables/apr_tables.c 2001/11/17 07:12:19
@@ -277,6 +277,51 @@
* The "table" functions.
*/
+/* Mapping from character codes to their uppercase equivalents */
+static apr_uint32_t toupper_cache[256];
+
+void apr_table_init(void)
+{
+ int i;
+ for (i = 0; i < 256; i++) {
+ if (isalpha(i)) {
+ toupper_cache[i] = apr_toupper(i);
+ }
+ else {
+ toupper_cache[i] = i;
+ }
+ }
+}
+
+/* Compute the "prefix" for a key, consisting of the first
+ * 4 bytes, converted to uppercase and packed into an int...
+ * this prefix allows us to do a single integer comparison
+ * as a fast, special-case strcasecmp alternative
+ */
+#define COMPUTE_KEY_PREFIX(key, prefix) \
+{ \
+ const char *k = (key); \
+ apr_uint32_t c = toupper_cache[(int)*k]; \
+ (prefix) = c; \
+ (prefix) <<= 8; \
+ if (c) { \
+ c = toupper_cache[(int)*++k]; \
+ prefix |= c; \
+ } \
+ (prefix) <<= 8; \
+ if (c) { \
+ c = toupper_cache[(int)*++k]; \
+ prefix |= c; \
+ } \
+ (prefix) <<= 8; \
+ if (c) { \
+ c = toupper_cache[(int)*++k]; \
+ prefix |= c; \
+ } \
+}
+
+#define KEY_PREFIX_LEN 4
+
/*
* XXX: if you tweak this you should look at is_empty_table() and table_elts()
* in alloc.h
@@ -333,13 +378,16 @@
{
apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
int i;
+ apr_uint32_t prefix;
if (key == NULL) {
return NULL;
}
+ COMPUTE_KEY_PREFIX(key, prefix);
for (i = 0; i < t->a.nelts; ++i) {
- if (!strcasecmp(elts[i].key, key)) {
+ if ((prefix == elts[i].key_prefix) &&
+ !strcasecmp(elts[i].key + KEY_PREFIX_LEN, key + KEY_PREFIX_LEN)) {
return elts[i].val;
}
}
@@ -353,9 +401,13 @@
register int i, j, k;
apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
int done = 0;
+ apr_uint32_t prefix;
+
+ COMPUTE_KEY_PREFIX(key, prefix);
for (i = 0; i < t->a.nelts; ) {
- if (!strcasecmp(elts[i].key, key)) {
+ if ((prefix == elts[i].key_prefix) &&
+ !strcasecmp(elts[i].key + KEY_PREFIX_LEN, key + KEY_PREFIX_LEN)) {
if (!done) {
elts[i].val = apr_pstrdup(t->a.pool, val);
done = 1;
@@ -365,6 +417,7 @@
for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) {
elts[j].key = elts[k].key;
elts[j].val = elts[k].val;
+ elts[j].key_prefix = elts[k].key_prefix;
}
--t->a.nelts;
}
@@ -378,6 +431,7 @@
elts = (apr_table_entry_t *) table_push(t);
elts->key = apr_pstrdup(t->a.pool, key);
elts->val = apr_pstrdup(t->a.pool, val);
+ elts->key_prefix = prefix;
}
}
@@ -387,6 +441,7 @@
register int i, j, k;
apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
int done = 0;
+ apr_uint32_t prefix;
#ifdef POOL_DEBUG
{
@@ -401,8 +456,11 @@
}
#endif
+ COMPUTE_KEY_PREFIX(key, prefix);
+
for (i = 0; i < t->a.nelts; ) {
- if (!strcasecmp(elts[i].key, key)) {
+ if ((prefix == elts[i].key_prefix) &&
+ !strcasecmp(elts[i].key + KEY_PREFIX_LEN, key + KEY_PREFIX_LEN)) {
if (!done) {
elts[i].val = (char *)val;
done = 1;
@@ -412,6 +470,7 @@
for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) {
elts[j].key = elts[k].key;
elts[j].val = elts[k].val;
+ elts[j].key_prefix = elts[k].key_prefix;
}
--t->a.nelts;
}
@@ -425,6 +484,7 @@
elts = (apr_table_entry_t *) table_push(t);
elts->key = (char *)key;
elts->val = (char *)val;
+ elts->key_prefix = prefix;
}
}
@@ -432,9 +492,13 @@
{
register int i, j, k;
apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
+ apr_uint32_t prefix;
+
+ COMPUTE_KEY_PREFIX(key, prefix);
for (i = 0; i < t->a.nelts; ) {
- if (!strcasecmp(elts[i].key, key)) {
+ if ((prefix == elts[i].key_prefix) &&
+ !strcasecmp(elts[i].key + KEY_PREFIX_LEN, key + KEY_PREFIX_LEN)) {
/* found an element to skip over
* there are any number of ways to remove an element from
@@ -444,6 +508,7 @@
for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) {
elts[j].key = elts[k].key;
elts[j].val = elts[k].val;
+ elts[j].key_prefix = elts[k].key_prefix;
}
--t->a.nelts;
}
@@ -458,9 +523,13 @@
{
apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
int i;
+ apr_uint32_t prefix;
+
+ COMPUTE_KEY_PREFIX(key, prefix);
for (i = 0; i < t->a.nelts; ++i) {
- if (!strcasecmp(elts[i].key, key)) {
+ if ((prefix == elts[i].key_prefix) &&
+ !strcasecmp(elts[i].key + KEY_PREFIX_LEN, key + KEY_PREFIX_LEN)) {
elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL);
return;
}
@@ -469,6 +538,7 @@
elts = (apr_table_entry_t *) table_push(t);
elts->key = apr_pstrdup(t->a.pool, key);
elts->val = apr_pstrdup(t->a.pool, val);
+ elts->key_prefix = prefix;
}
APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
@@ -476,6 +546,7 @@
{
apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
int i;
+ apr_uint32_t prefix;
#ifdef POOL_DEBUG
{
@@ -490,8 +561,11 @@
}
#endif
+ COMPUTE_KEY_PREFIX(key, prefix);
+
for (i = 0; i < t->a.nelts; ++i) {
- if (!strcasecmp(elts[i].key, key)) {
+ if ((prefix == elts[i].key_prefix) &&
+ !strcasecmp(elts[i].key + KEY_PREFIX_LEN, key + KEY_PREFIX_LEN)) {
elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL);
return;
}
@@ -500,22 +574,28 @@
elts = (apr_table_entry_t *) table_push(t);
elts->key = (char *)key;
elts->val = (char *)val;
+ elts->key_prefix = prefix;
}
APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
const char *val)
{
- apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
+ apr_table_entry_t *elts;
+ apr_uint32_t prefix;
+ COMPUTE_KEY_PREFIX(key, prefix);
+
elts = (apr_table_entry_t *) table_push(t);
elts->key = apr_pstrdup(t->a.pool, key);
elts->val = apr_pstrdup(t->a.pool, val);
+ elts->key_prefix = prefix;
}
APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
const char *val)
{
- apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
+ apr_table_entry_t *elts;
+ apr_uint32_t prefix;
#ifdef POOL_DEBUG
{
@@ -530,9 +610,12 @@
}
#endif
+ COMPUTE_KEY_PREFIX(key, prefix);
+
elts = (apr_table_entry_t *) table_push(t);
elts->key = (char *)key;
elts->val = (char *)val;
+ elts->key_prefix = prefix;
}
APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p,
@@ -626,8 +709,15 @@
int rv, i;
argp = va_arg(vp, char *);
do {
+ apr_uint32_t prefix = 0;
+ if (argp) {
+ COMPUTE_KEY_PREFIX(argp, prefix);
+ }
for (rv = 1, i = 0; rv && (i < t->a.nelts); ++i) {
- if (elts[i].key && (!argp || !strcasecmp(elts[i].key, argp))) {
+ if (elts[i].key && (!argp ||
+ ((prefix == elts[i].key_prefix) &&
+ !strcasecmp(elts[i].key + KEY_PREFIX_LEN,
+ argp + KEY_PREFIX_LEN)))) {
rv = (*comp) (rec, elts[i].key, elts[i].val);
}
}
@@ -645,6 +735,7 @@
typedef struct {
char *key;
char *val;
+ apr_uint32_t key_prefix;
int order;
} overlap_key;
@@ -654,7 +745,13 @@
const overlap_key *b = vb;
int r;
- r = strcasecmp(a->key, b->key);
+ if (a->key_prefix < b->key_prefix) {
+ return -1;
+ }
+ if (a->key_prefix > b->key_prefix) {
+ return 1;
+ }
+ r = strcasecmp(a->key + KEY_PREFIX_LEN, b->key + KEY_PREFIX_LEN);
if (r) {
return r;
}
@@ -699,6 +796,7 @@
while (e < last_e) {
cat_keys[nkeys].key = e->key;
cat_keys[nkeys].val = e->val;
+ cat_keys[nkeys].key_prefix = e->key_prefix;
cat_keys[nkeys].order = nkeys;
++nkeys;
++e;
@@ -709,6 +807,7 @@
while (e < last_e) {
cat_keys[nkeys].key = e->key;
cat_keys[nkeys].val = e->val;
+ cat_keys[nkeys].key_prefix = e->key_prefix;
cat_keys[nkeys].order = nkeys;
++nkeys;
++e;
@@ -750,6 +849,7 @@
char *strp;
char *value;
size_t len;
+ apr_table_entry_t *new_elt;
/* Have to merge some headers. Let's re-use the order field,
* since it's handy... we'll store the length of val there.
@@ -776,7 +876,10 @@
*strp++ = ' ';
}
*strp = 0;
- apr_table_addn(a, (left-1)->key, value);
+ new_elt = table_push(a);
+ new_elt->key = (left-1)->key;
+ new_elt->val = value;
+ new_elt->key_prefix = (left-1)->key_prefix;
}
}
}
@@ -784,11 +887,15 @@
left = cat_keys;
last = left + nkeys;
while (left < last) {
+ apr_table_entry_t *new_elt;
right = left + 1;
while (right < last && !strcasecmp(left->key, right->key)) {
++right;
}
- apr_table_addn(a, (right-1)->key, (right-1)->val);
+ new_elt = table_push(a);
+ new_elt->key = (right-1)->key;
+ new_elt->val = (right-1)->val;
+ new_elt->key_prefix = (right-1)->key_prefix;
left = right;
}
}
Index: modules/arch/win32/mod_isapi.c
===================================================================
RCS file: /home/cvspublic/httpd-2.0/modules/arch/win32/mod_isapi.c,v
retrieving revision 1.51
diff -u -r1.51 mod_isapi.c
--- modules/arch/win32/mod_isapi.c 2001/11/11 22:31:03 1.51
+++ modules/arch/win32/mod_isapi.c 2001/11/17 07:12:20
@@ -567,13 +567,15 @@
/* lf delimited, colon split, comma seperated and
* null terminated list of HTTP_ vars
*/
- const char * const *env = (const char* const *)
apr_table_elts(r->subprocess_env)->elts;
- int nelts = 2 * apr_table_elts(r->subprocess_env)->nelts;
+ const apr_array_header_t *arr = apr_table_elts(r->subprocess_env);
+ const apr_table_entry_t *elts = (const apr_table_entry_t *)arr->elts;
int i;
- for (len = 0, i = 0; i < nelts; i += 2)
- if (!strncmp(env[i], "HTTP_", 5))
- len += strlen(env[i]) + strlen(env[i + 1]) + 2;
+ for (len = 0, i = 0; i < arr->nelts; i++) {
+ if (!strncmp(elts[i].key, "HTTP_", 5)) {
+ len += strlen(elts[i].key) + strlen(elts[i].val) + 2;
+ }
+ }
if (*lpdwSizeofBuffer < len + 1) {
*lpdwSizeofBuffer = len + 1;
@@ -581,15 +583,16 @@
return FALSE;
}
- for (i = 0; i < nelts; i += 2)
- if (!strncmp(env[i], "HTTP_", 5)) {
- strcpy(lpvBuffer, env[i]);
- ((char*)lpvBuffer) += strlen(env[i]);
+ for (i = 0; i < arr->nelts; i++) {
+ if (!strncmp(elts[i].key, "HTTP_", 5)) {
+ strcpy(lpvBuffer, elts[i].key);
+ ((char*)lpvBuffer) += strlen(elts[i].key);
*(((char*)lpvBuffer)++) = ':';
- strcpy(lpvBuffer, env[i + 1]);
- ((char*)lpvBuffer) += strlen(env[i + 1]);
+ strcpy(lpvBuffer, elts[i].val);
+ ((char*)lpvBuffer) += strlen(elts[i].val);
*(((char*)lpvBuffer)++) = '\n';
}
+ }
*(((char*)lpvBuffer)++) = '\0';
*lpdwSizeofBuffer = len;
@@ -601,12 +604,13 @@
/* lf delimited, colon split, comma seperated and
* null terminated list of the raw request header
*/
- const char * const *raw = (const char* const *)
apr_table_elts(r->headers_in)->elts;
- int nelts = 2 * apr_table_elts(r->headers_in)->nelts;
+ const apr_array_header_t *arr = apr_table_elts(r->headers_in);
+ const apr_table_entry_t *elts = (const apr_table_entry_t *)arr->elts;
int i;
- for (len = 0, i = 0; i < nelts; i += 2)
- len += strlen(raw[i]) + strlen(raw[i + 1]) + 2;
+ for (len = 0, i = 0; i < arr->nelts; i++) {
+ len += strlen(elts[i].key) + strlen(elts[i].val) + 2;
+ }
if (*lpdwSizeofBuffer < len + 1) {
*lpdwSizeofBuffer = len + 1;
@@ -614,15 +618,14 @@
return FALSE;
}
- for (i = 0; i < nelts; i += 2) {
- strcpy(lpvBuffer, raw[i]);
- ((char*)lpvBuffer) += strlen(raw[i]);
+ for (i = 0; i < arr->nelts; i++) {
+ strcpy(lpvBuffer, elts[i].key);
+ ((char*)lpvBuffer) += strlen(elts[i].key);
*(((char*)lpvBuffer)++) = ':';
*(((char*)lpvBuffer)++) = ' ';
- strcpy(lpvBuffer, raw[i + 1]);
- ((char*)lpvBuffer) += strlen(raw[i + 1]);
+ strcpy(lpvBuffer, elts[i].val);
+ ((char*)lpvBuffer) += strlen(elts[i].val);
*(((char*)lpvBuffer)++) = '\n';
- i += 2;
}
*(((char*)lpvBuffer)++) = '\0';
*lpdwSizeofBuffer = len;
