git.oblomov.eu Git - ikiwiki/blob - doc/todo/Improving_the_efficiency_of_match__95__glob.mdwn

   1 [[!template id=gitbranch branch=smcv/ready/glob-cache
   2   author="[[KathrynAndersen]], [[smcv]]"]]
   3 [[!tag patch]]
   4
   5 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.
   6
   7 Here's my patch - please consider it! -- [[KathrynAndersen]]
   8
   9 > It seems to me as though changing `glob2re` to return qr/$re/, and calling
  10 > `memoize(glob2re)` next to the other memoize calls, would be a less
  11 > verbose way to do this? --[[smcv]]
  12
  13 >> I think so, yeah. Anyway, do you have any benchmark results handy,
  14 >> Kathryn?  --[[Joey]]
  15
  16 >>> See below.
  17 >>> Also, would it make more sense for glob2re to return qr/^$re$/i rather than qr/$re/?  Everything that uses glob2re seems to use
  18         $foo =~ /^$re$/i
  19 >>> rather than /$re/ so I think that would make sense.
  20 >>> -- [[KathrynAndersen]]
  21
  22 >>>> Git branch `smcv/ka-glob-cache` has Kathryn's patch. Git
  23 >>>> branch `smcv/memoize-glob2re` does as I suggested, which
  24 >>>> is less verbose than Kathryn's patch but also not as
  25 >>>> fast; I'm not sure why, tbh. --[[smcv]]
  26
  27 >>>>> 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]]
  28
  29 >>>>>> What may be going on is that glob2re is already a fairly fast
  30 >>>>>> function, so the overhead of memoizing it with the very generic
  31 >>>>>> `_memoizer` (see its source) swamps the memoization gain. Note
  32 >>>>>> that the few functions memoized with the Memoizer before were much
  33 >>>>>> more expensive, so that little overhead was acceptable then.
  34 >>>>>>
  35 >>>>>> It also may be that Kathryn's patch is slightly faster due to using
  36 >>>>>> the construct `$foo =~ $regexp` rather than `$foo =~ /$regexp/`
  37 >>>>>> (probably avoids a copy or something like that internally) --
  38 >>>>>> this despite checking both `exists` and `defined` on the hash, which
  39 >>>>>> should be reundant AFAICS.
  40 >>>>>>
  41 >>>>>> My guess is that the best of both worlds would be to move
  42 >>>>>> the byhand memoization to glob2re and have it return a compiled
  43 >>>>>> `/^/i` regexp that can be used without further modifiction in most
  44 >>>>>> cases. --[[Joey]]
  45
  46 >>>>>>> Done, see `smcv/ready/glob-cache`.
  47 >>>>>>> Kathryn's patch is a significant improvement; my first patch on top of
  48 >>>>>>> that is a trivial cleanup that speeds it up a little, and the other two
  49 >>>>>>> patches (using precompiled regexes) have surprisingly little effect
  50 >>>>>>> (they don't slow it down either though, so either omit them or merge
  51 >>>>>>> them, whichever). Detailed benchmark results --[[smcv]]
  52
  53 --------------------------------------------------------------
  54
  55 [[!toggle id="smcv-benchmark" text="current benchmarks"]]
  56
  57 [[!toggleable id="smcv-benchmark" text="""
  58 master at time of branch:
  59
  60     time elapsed (wall):   29.6348
  61     time running program:  24.9212  (84.09%)
  62     time profiling (est.): 4.7136  (15.91%)
  63     number of calls:       1360181
  64     number of exceptions:  13
  65
  66     %Time    Sec.     #calls   sec/call  F  name
  67     13.24    3.2986     3408   0.000968     Text::Balanced::_match_tagged
  68     10.94    2.7253    79514   0.000034     IkiWiki::PageSpec::match_glob
  69      3.19    0.7952    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
  70
  71 `Improve the speed of match_glob`:
  72
  73     time elapsed (wall):   27.9755
  74     time running program:  23.5293  (84.11%)
  75     time profiling (est.): 4.4461  (15.89%)
  76     number of calls:       1280875
  77     number of exceptions:  13
  78
  79     %Time    Sec.     #calls   sec/call  F  name
  80     14.56    3.4257     3408   0.001005     Text::Balanced::_match_tagged
  81      7.82    1.8403    79514   0.000023     IkiWiki::PageSpec::match_glob
  82      3.27    0.7698    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
  83
  84 `match_glob: streamline glob cache slightly`:
  85
  86     time elapsed (wall):   27.5753
  87     time running program:  23.1714  (84.03%)
  88     time profiling (est.): 4.4039  (15.97%)
  89     number of calls:       1280875
  90     number of exceptions:  13
  91
  92     %Time    Sec.     #calls   sec/call  F  name
  93     14.09    3.2637     3408   0.000958     Text::Balanced::_match_tagged
  94      7.74    1.7926    79514   0.000023     IkiWiki::PageSpec::match_glob
  95      3.30    0.7646    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
  96
  97 `glob2re: return a precompiled, anchored case-insensitiv...`:
  98
  99     time elapsed (wall):   27.5656
 100     time running program:  23.1464  (83.97%)
 101     time profiling (est.): 4.4192  (16.03%)
 102     number of calls:       1282189
 103     number of exceptions:  13
 104
 105     %Time    Sec.     #calls   sec/call  F  name
 106     14.21    3.2891     3408   0.000965     Text::Balanced::_match_tagged
 107      7.72    1.7872    79514   0.000022     IkiWiki::PageSpec::match_glob
 108      3.32    0.7678    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
 109
 110 `make use of precompiled regex objects`:
 111
 112     time elapsed (wall):   27.5357
 113     time running program:  23.1289  (84.00%)
 114     time profiling (est.): 4.4068  (16.00%)
 115     number of calls:       1281981
 116     number of exceptions:  13
 117
 118     %Time    Sec.     #calls   sec/call  F  name
 119     14.17    3.2776     3408   0.000962     Text::Balanced::_match_tagged
 120      7.70    1.7814    79514   0.000022     IkiWiki::PageSpec::match_glob
 121      3.35    0.7756    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
 122
 123 """]]
 124
 125 --[[smcv]]
 126
 127 --------------------------------------------------------------
 128
 129 [[!toggle id="ka-benchmarks" text="Kathryn's benchmarks"]]
 130
 131 [[!toggleable id="ka-benchmarks" text="""
 132 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.
 133
 134 Before:
 135 <pre>
 136 time elapsed (wall):   27.4173
 137 time running program:  22.5909  (82.40%)
 138 time profiling (est.): 4.8264  (17.60%)
 139 number of calls:       1314729
 140 number of exceptions:  65
 141
 142 %Time    Sec.     #calls   sec/call  F  name
 143 11.05    2.4969    62333   0.000040     IkiWiki::PageSpec::match_glob
 144  4.10    0.9261      679   0.001364     Text::Balanced::_match_tagged
 145  2.72    0.6139    59812   0.000010     IkiWiki::SuccessReason::merge_influences
 146 </pre>
 147
 148 After:
 149 <pre>
 150 time elapsed (wall):   26.1843
 151 time running program:  21.5673  (82.37%)
 152 time profiling (est.): 4.6170  (17.63%)
 153 number of calls:       1252433
 154 number of exceptions:  65
 155
 156 %Time    Sec.     #calls   sec/call  F  name
 157  7.66    1.6521    62333   0.000027     IkiWiki::PageSpec::match_glob
 158  4.33    0.9336      679   0.001375     Text::Balanced::_match_tagged
 159  2.81    0.6057    59812   0.000010     IkiWiki::SuccessReason::merge_influences
 160 </pre>
 161
 162 Note that the seconds per call for match_glob in the "after" case has gone down by about a third.
 163
 164 K.A.
 165 """]]
 166
 167 --------------------------------------------------------------
 168
 169 [[!toggle id="ka-patch" text="Kathryn's original patch"]]
 170
 171 [[!toggleable id="ka-patch" text="""
 172
 173 <pre>
 174 diff --git a/IkiWiki.pm b/IkiWiki.pm
 175 index 08a3d78..c187b98 100644
 176 --- a/IkiWiki.pm
 177 +++ b/IkiWiki.pm
 178 @@ -2482,6 +2482,8 @@ sub derel ($$) {
 179         return $path;
 180  }
 181
 182 +my %glob_cache;
 183 +
 184  sub match_glob ($$;@) {
 185         my $page=shift;
 186         my $glob=shift;
 187 @@ -2489,8 +2491,15 @@ sub match_glob ($$;@) {
 188
 189         $glob=derel($glob, $params{location});
 190
 191 -       my $regexp=IkiWiki::glob2re($glob);
 192 -       if ($page=~/^$regexp$/i) {
 193 +       # Instead of converting the glob to a regex every time,
 194 +       # cache the compiled regex to save time.
 195 +       if (!exists $glob_cache{$glob}
 196 +           or !defined $glob_cache{$glob})
 197 +       {
 198 +           my $re=IkiWiki::glob2re($glob);
 199 +           $glob_cache{$glob} = qr/^$re$/i;
 200 +       }
 201 +       if ($page =~ $glob_cache{$glob}) {
 202                 if (! IkiWiki::isinternal($page) || $params{internal}) {
 203                         return IkiWiki::SuccessReason->new("$glob matches $page");
 204                 }
 205 </pre>
 206 """]]
 207 --------------------------------------------------------------