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: [email protected] ReportedBy: [EMAIL PROTECTED] CC: [EMAIL PROTECTED] 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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
