doc/todo/Improving_the_efficiency_of_match__95__glob.mdwn

   1 I've been profiling my IkiWiki to try to improve speed (with many pages makes speed even more important) and I've written a patch to improve the speed of match_glob.  This matcher is a good one to improve the speed of, because it gets called so many times.
   2
   3 Here's my patch - please consider it! -- [[KathrynAndersen]]
   4
   5 > It seems to me as though changing `glob2re` to return qr/$re/, and calling
   6 > `memoize(glob2re)` next to the other memoize calls, would be a less
   7 > verbose way to do this? --[[smcv]]
   8
   9 >> I think so, yeah. Anyway, do you have any benchmark results handy,
  10 >> Kathryn?  --[[Joey]]
  11
  12 >>> See below.
  13 >>> Also, would it make more sense for glob2re to return qr/^$re$/i rather than qr/$re/?  Everything that uses glob2re seems to use
  14         $foo =~ /^$re$/i
  15 >>> rather than /$re/ so I think that would make sense.
  16 >>> -- [[KathrynAndersen]]
  17
  18 >>>> Git branch `smcv/ka-glob-cache` has Kathryn's patch. Git
  19 >>>> branch `smcv/memoize-glob2re` does as I suggested, which
  20 >>>> is less verbose than Kathryn's patch but also not as
  21 >>>> fast; I'm not sure why, tbh. --[[smcv]]
  22
  23 >>>>> I think it's because my patch focuses on match_glob while the memoize patch focuses on `glob2re`, and `glob2re` is called in `filecheck`, `meta` and `po` as well as in `match_glob` and `match_user`; thus the memoized `glob2re` is dealing with a bigger set of globs to look up, and thus could be just that little bit slower. -- [[KathrynAndersen]]
  24
  25 >>>>>> What may be going on is that glob2re is already a fairly fast
  26 >>>>>> function, so the overhead of memoizing it with the very generic
  27 >>>>>> `_memoizer` (see its source) swamps the memoization gain. Note
  28 >>>>>> that the few functions memoized with the Memoizer before were much
  29 >>>>>> more expensive, so that little overhead was acceptable then.
  30 >>>>>>
  31 >>>>>> It also may be that Kathryn's patch is slightly faster due to using
  32 >>>>>> the construct `$foo =~ $regexp` rather than `$foo =~ /$regexp/`
  33 >>>>>> (probably avoids a copy or something like that internally) --
  34 >>>>>> this despite checking both `exists` and `defined` on the hash, which
  35 >>>>>> should be reundant AFAICS.
  36 >>>>>>
  37 >>>>>> My guess is that the best of both worlds would be to move
  38 >>>>>> the byhand memoization to glob2re and have it return a compiled
  39 >>>>>> `/^/i` regexp that can be used without further modifiction in most
  40 >>>>>> cases. --[[Joey]]
  41
  42 --------------------------------------------------------------
  43 Benchmarks done with Devel::Profile on the same testbed IkiWiki setup.  I'm just showing the start of the profile output, since that's what's relevant.
  44
  45 Before:
  46 <pre>
  47 time elapsed (wall):   27.4173
  48 time running program:  22.5909  (82.40%)
  49 time profiling (est.): 4.8264  (17.60%)
  50 number of calls:       1314729
  51 number of exceptions:  65
  52
  53 %Time    Sec.     #calls   sec/call  F  name
  54 11.05    2.4969    62333   0.000040     IkiWiki::PageSpec::match_glob
  55  4.10    0.9261      679   0.001364     Text::Balanced::_match_tagged
  56  2.72    0.6139    59812   0.000010     IkiWiki::SuccessReason::merge_influences
  57 </pre>
  58
  59 After:
  60 <pre>
  61 time elapsed (wall):   26.1843
  62 time running program:  21.5673  (82.37%)
  63 time profiling (est.): 4.6170  (17.63%)
  64 number of calls:       1252433
  65 number of exceptions:  65
  66
  67 %Time    Sec.     #calls   sec/call  F  name
  68  7.66    1.6521    62333   0.000027     IkiWiki::PageSpec::match_glob
  69  4.33    0.9336      679   0.001375     Text::Balanced::_match_tagged
  70  2.81    0.6057    59812   0.000010     IkiWiki::SuccessReason::merge_influences
  71 </pre>
  72
  73 Note that the seconds per call for match_glob in the "after" case has gone down by about a third.
  74
  75 K.A.
  76
  77 --------------------------------------------------------------
  78
  79 A second set of benchmarks, done by rebuilding the docwiki at commit f942c2db05e4
  80 like so:
  81
  82     perl -Iblib/lib -d:Profile ikiwiki.in -setup docwiki.setup --no-verbose
  83
  84 The docwiki appears to use fewer glob matches than Kathryn's wiki.
  85
  86 With master:
  87
  88     time elapsed (wall):   29.6970
  89     time running program:  24.6930  (83.15%)
  90     time profiling (est.): 5.0041  (16.85%)
  91     number of calls:       1359180
  92     number of exceptions:  13
  93
  94     %Time    Sec.     #calls   sec/call  F  name
  95     13.62    3.3629     3406   0.000987     Text::Balanced::_match_tagged
  96     10.84    2.6773    79442   0.000034     IkiWiki::PageSpec::match_glob
  97      3.08    0.7598    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
  98      3.07    0.7593    29830   0.000025     IkiWiki::bestlink
  99      2.99    0.7378    10231   0.000072     IkiWiki::PageSpec::match_link
 100
 101 With my `smcv/memoize-glob2re` branch:
 102
 103     time elapsed (wall):   30.4931
 104     time running program:  25.1248  (82.39%)
 105     time profiling (est.): 5.3683  (17.61%)
 106     number of calls:       1439943
 107     number of exceptions:  13
 108
 109     %Time    Sec.     #calls   sec/call  F  name
 110     13.19    3.3146     3406   0.000973     Text::Balanced::_match_tagged
 111      8.41    2.1123    79442   0.000027     IkiWiki::PageSpec::match_glob
 112      3.97    0.9979    86905   0.000011     Memoize::_memoizer
 113      3.05    0.7654    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
 114      3.02    0.7576    29830   0.000025     IkiWiki::bestlink
 115
 116 and in a repeated run:
 117
 118      8.40    2.0905    79442   0.000026     IkiWiki::PageSpec::match_glob
 119
 120 With Kathryn's patch as seen in my `smcv/ka-glob-cache` branch:
 121
 122     time elapsed (wall):   27.7567
 123     time running program:  22.9941  (82.84%)
 124     time profiling (est.): 4.7627  (17.16%)
 125     number of calls:       1279946
 126     number of exceptions:  13
 127
 128     %Time    Sec.     #calls   sec/call  F  name
 129     14.29    3.2867     3406   0.000965     Text::Balanced::_match_tagged
 130      7.89    1.8136    79442   0.000023     IkiWiki::PageSpec::match_glob
 131      3.30    0.7577    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
 132      3.24    0.7461    29830   0.000025     IkiWiki::bestlink
 133      3.19    0.7332      143   0.005127  ?  IkiWiki::pagespec_match_list
 134
 135 and in a repeated run:
 136
 137      7.84    1.8253    79442   0.000023     IkiWiki::PageSpec::match_glob
 138
 139 --[[smcv]]
 140
 141 --------------------------------------------------------------
 142
 143
 144 <pre>
 145 diff --git a/IkiWiki.pm b/IkiWiki.pm
 146 index 08a3d78..c187b98 100644
 147 --- a/IkiWiki.pm
 148 +++ b/IkiWiki.pm
 149 @@ -2482,6 +2482,8 @@ sub derel ($$) {
 150         return $path;
 151  }
 152
 153 +my %glob_cache;
 154 +
 155  sub match_glob ($$;@) {
 156         my $page=shift;
 157         my $glob=shift;
 158 @@ -2489,8 +2491,15 @@ sub match_glob ($$;@) {
 159
 160         $glob=derel($glob, $params{location});
 161
 162 -       my $regexp=IkiWiki::glob2re($glob);
 163 -       if ($page=~/^$regexp$/i) {
 164 +       # Instead of converting the glob to a regex every time,
 165 +       # cache the compiled regex to save time.
 166 +       if (!exists $glob_cache{$glob}
 167 +           or !defined $glob_cache{$glob})
 168 +       {
 169 +           my $re=IkiWiki::glob2re($glob);
 170 +           $glob_cache{$glob} = qr/^$re$/i;
 171 +       }
 172 +       if ($page =~ $glob_cache{$glob}) {
 173                 if (! IkiWiki::isinternal($page) || $params{internal}) {
 174                         return IkiWiki::SuccessReason->new("$glob matches $page");
 175                 }
 176 </pre>
 177 --------------------------------------------------------------