[PATCH] mod_include parser optimization

[Brian Pane <bp...@pacbell.net>]

This patch optimizes away some pointer arithmetic in the
inner loop of the BNDM string-search algorithm in mod_include.

The optimization takes advantage of two invariants in the
original code:
  * Every time the variable 'skip' is set, skip==p-pi
  * The only use of skip as an rvalue is in the expression "pi += skip".

--Brian


Index: modules/filters/mod_include.c
===================================================================
RCS file: /home/cvspublic/httpd-2.0/modules/filters/mod_include.c,v
retrieving revision 1.154
diff -u -r1.154 mod_include.c
--- modules/filters/mod_include.c    2001/11/15 05:05:20    1.154
+++ modules/filters/mod_include.c    2001/11/18 10:13:57
@@ -255,7 +255,7 @@
 static apr_size_t bndm(const char *n, apr_size_t nl, const char *h,
                        apr_size_t hl, bndm_t *t)
 {
-    apr_size_t skip;
+    const char *skip;
     const char *he, *p, *pi;
     unsigned int *T, x, d;
 
@@ -268,18 +268,19 @@
     p = pi + nl; /* compare window right to left. point to the first 
char */
 
     while (p < he) {
-        skip = nl;
+        skip = p;
         d = x;
         do {
             d = (d >> 1) & T[(unsigned char) *p--];
             if ((d & 1)) {
                 if (p != pi)
-                    skip = p - pi;
+                    skip = p;
                 else
                     return p - h + 1;
             }
         } while (d > 1);
-        p = (pi += skip) + nl;
+        pi = skip;
+        p = pi + nl;
     }
 
     return hl;

Re: [PATCH] mod_include parser optimization

[Greg Ames <gr...@remulak.net>]

Brian Pane wrote:
> 
> This patch optimizes away some pointer arithmetic in the
> inner loop of the BNDM string-search algorithm in mod_include.
> 
> The optimization takes advantage of two invariants in the
> original code:
>   * Every time the variable 'skip' is set, skip==p-pi
>   * The only use of skip as an rvalue is in the expression "pi += skip".

Looks good in theory.  I haven't tested it.

Greg