You are viewing a plain text version of this content. The canonical link for it is here.
Posted to bugs@httpd.apache.org by bu...@apache.org on 2004/06/17 17:39:08 UTC
DO NOT REPLY [Bug 29645] New: -
Performance improvement by using sorted arrays
DO NOT REPLY TO THIS EMAIL, BUT PLEASE POST YOUR BUG
RELATED COMMENTS THROUGH THE WEB INTERFACE AVAILABLE AT
<http://issues.apache.org/bugzilla/show_bug.cgi?id=29645>.
ANY REPLY MADE TO THIS MESSAGE WILL NOT BE COLLECTED AND
INSERTED IN THE BUG DATABASE.
http://issues.apache.org/bugzilla/show_bug.cgi?id=29645
Performance improvement by using sorted arrays
Summary: Performance improvement by using sorted arrays
Product: Apache httpd-1.3
Version: HEAD
Platform: Other
OS/Version: Other
Status: NEW
Severity: Enhancement
Priority: Other
Component: Other mods
AssignedTo: bugs@httpd.apache.org
ReportedBy: burgoyne@keenuh.com
CC: burgoyne@keenuh.com
When doing some performance analisys for a client, an issue found was that they
had a huge number of redirects (over 1000) that was slowing down every request
with string compares. Due to ionternal political issues and the fact that this
was considered common business, it was realistically impossible to get them to
discontinue adding to their configuration in this manner.
I therefore made changes into mod_alias on Apache 1.3.26 to use a sorted list
instead of a linear list which resulted in significant performance gains. I
would like to release these changes back into the main stream of apache.
Following is the diff file for my changes for 1.3.26. Please note is also
requires implementation of bug 29640 which is used to sort the array. That
truly belonged back in the core and not in mod_alias.
73d72
< char *fake;
74a74
> char *fake;
83,84d82
< array_header *redirects_regexp;
< int sorted;
89d86
< int sorted;
94,109d90
<
<
< int
< compare_alias(void *first, void *second)
< {
< alias_entry *first_alias = (alias_entry *) first;
< alias_entry *second_alias = (alias_entry *) second;
< if (strcmp(first_alias->fake, second_alias->fake) < 0) {
< return 0;
< }
< return 1;
< }
<
<
<
<
117,124d97
< a->redirects_regexp = ap_make_array(p, 20, sizeof(alias_entry));
< a->sorted = 0;
<
< /*char *srm_confname;
< char *access_confname;
< char *server_admin;
< char *server_hostname;*/
<
133d105
< a->sorted = 0;
145,151d116
< a->redirects_regexp = ap_append_arrays(p, overrides->redirects_regexp,
base->redirects_regexp);
<
< if (base->sorted || overrides->sorted) {
< ap_array_sort(a->redirects, &compare_alias);
< a->sorted = 1;
< }
<
161,166d125
<
< if (base->sorted || overrides->sorted) {
< ap_array_sort(a->redirects, &compare_alias);
< a->sorted = 1;
< }
<
254d212
< {
256,257d213
< dirconf->sorted = 0;
< }
259,268c215
< {
< if (use_regex)
< {
< new = ap_push_array(serverconf->redirects_regexp);
< } else
< {
< new = ap_push_array(serverconf->redirects);
< serverconf->sorted = 0;
< }
< }
---
> new = ap_push_array(serverconf->redirects);
274d220
<
290,312d235
<
<
<
<
< static const char *sortAlias(cmd_parms *cmd, void *dummy, int to_sort)
< {
< server_rec *s = cmd->server;
< alias_server_conf *conf = (alias_server_conf *)
< ap_get_module_config(s->module_config,
< &alias_module);
<
<
< if (!to_sort || conf->sorted) {
< return NULL;
< } else {
< ap_array_sort(conf->redirects, &compare_alias);
< conf->sorted = 1;
< }
< return NULL;
< }
<
<
<
315,316d237
< {"RedirectSort", sortAlias, NULL, RSRC_CONF, FLAG,
< "Sorts the list"},
378,380c299
<
< int
< could_alias_match(char *real_URL, char *fake_URL)
---
> static char *try_alias_list(request_rec *r, array_header *aliases, int doesc,
int *status)
382,406d300
< int count = 0;
<
< if (alias_matches(real_URL, fake_URL)) {
< return 1;
< }
<
< while (real_URL[count] == fake_URL[count]) {
<
< if (count && real_URL[count] == '/') {
< return 1;
< }
< count++;
<
< if (count > strlen(real_URL) || count > strlen(fake_URL)) {
< return 0;
< }
< }
<
< return 0;
< }
<
<
< static char *try_alias_list(request_rec *r, array_header *aliases, int doesc,
< int *status, int sorted)
< {
410,415c304
< int i = 0;
< int to_continue = 1;
< alias_entry *p;
< int start = 0;
< int current = 0;
< int end = aliases->nelts;
---
> int i;
416a306,308
> for (i = 0; i < aliases->nelts; ++i) {
> alias_entry *p = &entries[i];
> int l;
418,448d309
< if (end == 0) {
< return NULL;
< }
<
< while (to_continue) {
<
< int l;
<
< if (sorted) {
<
< int old_current = current;
< if (end == start) {
< current = start;
< to_continue = 0;
< } else {
< current = (start + end) / 2;
< }
<
< if (old_current == current && end - start == 1)
< {
< to_continue = 0;
< }
< p = &entries[current];
<
< } else {
< p = &entries[i++];
< if (i == end) {
< to_continue = 0;
< }
< }
<
450c311
< if (!ap_regexec(p->regexp, r->uri, p->regexp->re_nsub + 1, regm,
0)) {
---
> if (!ap_regexec(p->regexp, r->uri, p->regexp->re_nsub + 1, regm,
0)) {
467c328,331
< if (l > 0 && sorted) {
---
> if (l > 0) {
> if (doesc) {
> char *escurl;
> escurl = ap_os_escape_path(r->pool, r->uri + l, 1);
469,470c333,338
< int lower_boundary = current - 1;
< int upper_boundary = current + 1;
---
> found = ap_pstrcat(r->pool, p->real, escurl, NULL);
> }
> else
> found = ap_pstrcat(r->pool, p->real, r->uri + l, NULL);
> }
> }
472,522d339
< while (could_alias_match(r->uri,
< (&entries[lower_boundary])->fake) > 0) {
< lower_boundary--;
< }
<
< lower_boundary++;
< while (could_alias_match(r->uri,
< (&entries[upper_boundary])->fake) > 0) {
< upper_boundary++;
< }
<
< upper_boundary--;
<
< if (upper_boundary != lower_boundary) {
<
< int longest_length = 0;
< int best_match = 0;
< while (lower_boundary != upper_boundary + 1) {
<
< int current_length;
< current_length = strlen((&entries[lower_boundary])
< ->fake);
< if (current_length > longest_length &&
< alias_matches(r->uri,
< (&entries[lower_boundary])->fake)) {
< longest_length = current_length;
< best_match = lower_boundary;
< l = alias_matches(r->uri,
< (&entries[lower_boundary])-
>fake);
< }
< lower_boundary++;
< }
<
< p = &entries[best_match];
<
< }
< }
<
< if (l > 0) {
<
< if (doesc) {
< char *escurl;
< escurl = ap_os_escape_path(r->pool, r->uri + l, 1);
<
< found = ap_pstrcat(r->pool, p->real, escurl, NULL);
< }
< else
< found = ap_pstrcat(r->pool, p->real, r->uri + l, NULL);
< }
< }
<
524d340
<
534,542d349
<
< if (sorted)
< {
< if (strcmp(r->uri, p->fake) > 0) {
< start = current;
< } else {
< end = current;
< }
< }
559,561c366
<
< if ((ret = try_alias_list(r, serverconf->redirects, 1, &status,
serverconf->sorted)) != NULL) {
<
---
> if ((ret = try_alias_list(r, serverconf->redirects, 1, &status)) != NULL)
{
570d374
<
576c380
< if ((ret = try_alias_list(r, serverconf->aliases, 0, &status, 0)) !=
NULL) {
---
> if ((ret = try_alias_list(r, serverconf->aliases, 0, &status)) != NULL) {
594c398
< if ((ret = try_alias_list(r, dirconf->redirects, 1, &status, 0)) != NULL)
{
---
> if ((ret = try_alias_list(r, dirconf->redirects, 1, &status)) != NULL) {
---------------------------------------------------------------------
To unsubscribe, e-mail: bugs-unsubscribe@httpd.apache.org
For additional commands, e-mail: bugs-help@httpd.apache.org