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