doc/recentchanges/change_d6ff694ff7a6a4700ccbbd5819907eac73cf065a._change

   1 [[!meta author="""smcv"""]]
   2
   3 [[!meta authorurl="""http://ikiwiki.info/ikiwiki.cgi?page=users%2Fsmcv&amp;do=goto"""]]
   4
   5 [[!meta title="""change to todo/Improving_the_efficiency_of_match__95__glob on ikiwiki"""]]
   6
   7 [[!meta permalink="http://ikiwiki.info/recentchanges/#change-d6ff694ff7a6a4700ccbbd5819907eac73cf065a"]]
   8
   9 <div id="change-d6ff694ff7a6a4700ccbbd5819907eac73cf065a" class="metadata">
  10 <span class="desc"><br />Changed pages:</span>
  11 <span class="pagelinks">
  12
  13 <a href="http://git.ikiwiki.info/?p=ikiwiki;a=blobdiff;f=doc/todo/Improving_the_efficiency_of_match__95__glob.mdwn;h=de3cf48d3aae963943dfeb3aaffb2edd6f472ef8;hp=0fc059ad7d169c2e35f3ea869bdc2f69be649857;hb=d6ff694ff7a6a4700ccbbd5819907eac73cf065a;hpb=a4cb86d73327e7850eeb524ef387b17ac5e1614d" title="diff" rel="nofollow">[[diff|wikiicons/diff.png]]</a><a href="http://ikiwiki.info/ikiwiki.cgi?page=todo%2FImproving_the_efficiency_of_match__95__glob&amp;do=goto" rel="nofollow">todo/Improving the efficiency of match&#95;glob</a>
  14
  15
  16 </span>
  17 <span class="desc"><br />Changed by:</span>
  18 <span class="committer">
  19
  20 <a href="http://ikiwiki.info/ikiwiki.cgi?page=users%2Fsmcv&amp;do=goto" rel="nofollow">smcv</a>
  21
  22 </span>
  23 <span class="desc"><br />Commit type:</span>
  24 <span class="committype">git</span>
  25 <span class="desc"><br />Date:</span>
  26 <span class="changedate"><span class="relativedate" title="Sat, 20 Nov 2010 00:22:56 +0000">00:22:56 11/20/10</span></span>
  27 <span class="desc"><br /></span>
  28 </div>
  29
  30 <span class="revert">
  31 <a href="http://ikiwiki.info/ikiwiki.cgi?rev=d6ff694ff7a6a4700ccbbd5819907eac73cf065a&amp;do=revert" title="revert" rel="nofollow">[[revert|wikiicons/revert.png]]</a>
  32 </span>
  33
  34 <div class="changelog">
  35
  36
  37 branch ready for merge, I think<br />
  38
  39
  40 </div>
  41
  42 <div class="diff">
  43 <pre>
  44 diff --git a/doc/todo/Improving_the_efficiency_of_match__95__glob.mdwn b/doc/todo/Improving_the_efficiency_of_match__95__glob.mdwn
  45 index 0fc059a..de3cf48 100644
  46 --- a/doc/todo/Improving_the_efficiency_of_match__95__glob.mdwn
  47 +++ b/doc/todo/Improving_the_efficiency_of_match__95__glob.mdwn
  48 @@ -1,3 +1,7 @@
  49 +&#91;&#91;!template id=gitbranch branch=smcv/ready/glob-cache
  50 +  author=&quot;&#91;&#91;KathrynAndersen&#93;&#93;, &#91;&#91;smcv&#93;&#93;&quot;&#93;&#93;
  51 +&#91;&#91;!tag patch&#93;&#93;
  52 +
  53  I&#39;ve been profiling my IkiWiki to try to improve speed (with many pages makes speed even more important) and I&#39;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.
  54
  55  Here&#39;s my patch - please consider it! -- &#91;&#91;KathrynAndersen&#93;&#93;
  56 @@ -39,7 +43,92 @@ Here&#39;s my patch - please consider it! -- &#91;&#91;KathrynAndersen&#93;&#93;
  57  &gt;&gt;&gt;&gt;&gt;&gt; `/^/i` regexp that can be used without further modifiction in most
  58  &gt;&gt;&gt;&gt;&gt;&gt; cases. --&#91;&#91;Joey&#93;&#93;
  59
  60 +&gt;&gt;&gt;&gt;&gt;&gt;&gt; Done, see `smcv/ready/glob-cache`.
  61 +&gt;&gt;&gt;&gt;&gt;&gt;&gt; Kathryn&#39;s patch is a significant improvement; my first patch on top of
  62 +&gt;&gt;&gt;&gt;&gt;&gt;&gt; that is a trivial cleanup that speeds it up a little, and the other two
  63 +&gt;&gt;&gt;&gt;&gt;&gt;&gt; patches (using precompiled regexes) have surprisingly little effect
  64 +&gt;&gt;&gt;&gt;&gt;&gt;&gt; (they don&#39;t slow it down either though, so either omit them or merge
  65 +&gt;&gt;&gt;&gt;&gt;&gt;&gt; them, whichever). Detailed benchmark results --&#91;&#91;smcv&#93;&#93;
  66 +
  67  --------------------------------------------------------------
  68 +
  69 +&#91;&#91;!toggle id=&quot;smcv-benchmark&quot; text=&quot;current benchmarks&quot;&#93;&#93;
  70 +
  71 +&#91;&#91;!toggleable id=&quot;smcv-benchmark&quot; text=&quot;&quot;&quot;
  72 +master at time of branch:
  73 +
  74 +    time elapsed (wall):   29.6348
  75 +    time running program:  24.9212  (84.09%)
  76 +    time profiling (est.): 4.7136  (15.91%)
  77 +    number of calls:       1360181
  78 +    number of exceptions:  13
  79 +
  80 +    %Time    Sec.     #calls   sec/call  F  name
  81 +    13.24    3.2986     3408   0.000968     Text::Balanced::_match_tagged
  82 +    10.94    2.7253    79514   0.000034     IkiWiki::PageSpec::match_glob
  83 +     3.19    0.7952    59454   0.000013     &lt;anon&gt;:IkiWiki/Plugin/inline.pm:223
  84 +
  85 +`Improve the speed of match_glob`:
  86 +
  87 +    time elapsed (wall):   27.9755
  88 +    time running program:  23.5293  (84.11%)
  89 +    time profiling (est.): 4.4461  (15.89%)
  90 +    number of calls:       1280875
  91 +    number of exceptions:  13
  92 +
  93 +    %Time    Sec.     #calls   sec/call  F  name
  94 +    14.56    3.4257     3408   0.001005     Text::Balanced::_match_tagged
  95 +     7.82    1.8403    79514   0.000023     IkiWiki::PageSpec::match_glob
  96 +     3.27    0.7698    59454   0.000013     &lt;anon&gt;:IkiWiki/Plugin/inline.pm:223
  97 +
  98 +`match_glob: streamline glob cache slightly`:
  99 +
 100 +    time elapsed (wall):   27.5753
 101 +    time running program:  23.1714  (84.03%)
 102 +    time profiling (est.): 4.4039  (15.97%)
 103 +    number of calls:       1280875
 104 +    number of exceptions:  13
 105 +
 106 +    %Time    Sec.     #calls   sec/call  F  name
 107 +    14.09    3.2637     3408   0.000958     Text::Balanced::_match_tagged
 108 +     7.74    1.7926    79514   0.000023     IkiWiki::PageSpec::match_glob
 109 +     3.30    0.7646    59454   0.000013     &lt;anon&gt;:IkiWiki/Plugin/inline.pm:223
 110 +
 111 +`glob2re: return a precompiled, anchored case-insensitiv...`:
 112 +
 113 +    time elapsed (wall):   27.5656
 114 +    time running program:  23.1464  (83.97%)
 115 +    time profiling (est.): 4.4192  (16.03%)
 116 +    number of calls:       1282189
 117 +    number of exceptions:  13
 118 +
 119 +    %Time    Sec.     #calls   sec/call  F  name
 120 +    14.21    3.2891     3408   0.000965     Text::Balanced::_match_tagged
 121 +     7.72    1.7872    79514   0.000022     IkiWiki::PageSpec::match_glob
 122 +     3.32    0.7678    59454   0.000013     &lt;anon&gt;:IkiWiki/Plugin/inline.pm:223
 123 +
 124 +`make use of precompiled regex objects`:
 125 +
 126 +    time elapsed (wall):   27.5357
 127 +    time running program:  23.1289  (84.00%)
 128 +    time profiling (est.): 4.4068  (16.00%)
 129 +    number of calls:       1281981
 130 +    number of exceptions:  13
 131 +
 132 +    %Time    Sec.     #calls   sec/call  F  name
 133 +    14.17    3.2776     3408   0.000962     Text::Balanced::_match_tagged
 134 +     7.70    1.7814    79514   0.000022     IkiWiki::PageSpec::match_glob
 135 +     3.35    0.7756    59454   0.000013     &lt;anon&gt;:IkiWiki/Plugin/inline.pm:223
 136 +
 137 +&quot;&quot;&quot;&#93;&#93;
 138 +
 139 +--&#91;&#91;smcv&#93;&#93;
 140 +
 141 +--------------------------------------------------------------
 142 +
 143 +&#91;&#91;!toggle id=&quot;ka-benchmarks&quot; text=&quot;Kathryn&#39;s benchmarks&quot;&#93;&#93;
 144 +
 145 +&#91;&#91;!toggleable id=&quot;ka-benchmarks&quot; text=&quot;&quot;&quot;
 146  Benchmarks done with Devel::Profile on the same testbed IkiWiki setup.  I&#39;m just showing the start of the profile output, since that&#39;s what&#39;s relevant.
 147
 148  Before:
 149 @@ -73,73 +162,13 @@ number of exceptions:  65
 150  Note that the seconds per call for match_glob in the &quot;after&quot; case has gone down by about a third.
 151
 152  K.A.
 153 +&quot;&quot;&quot;&#93;&#93;
 154
 155  --------------------------------------------------------------
 156
 157 -A second set of benchmarks, done by rebuilding the docwiki at commit f942c2db05e4
 158 -like so:
 159 -
 160 -    perl -Iblib/lib -d:Profile ikiwiki.in -setup docwiki.setup --no-verbose
 161 -
 162 -The docwiki appears to use fewer glob matches than Kathryn&#39;s wiki.
 163 -
 164 -With master:
 165 -
 166 -    time elapsed (wall):   29.6970
 167 -    time running program:  24.6930  (83.15%)
 168 -    time profiling (est.): 5.0041  (16.85%)
 169 -    number of calls:       1359180
 170 -    number of exceptions:  13
 171 -
 172 -    %Time    Sec.     #calls   sec/call  F  name
 173 -    13.62    3.3629     3406   0.000987     Text::Balanced::_match_tagged
 174 -    10.84    2.6773    79442   0.000034     IkiWiki::PageSpec::match_glob
 175 -     3.08    0.7598    59454   0.000013     &lt;anon&gt;:IkiWiki/Plugin/inline.pm:223
 176 -     3.07    0.7593    29830   0.000025     IkiWiki::bestlink
 177 -     2.99    0.7378    10231   0.000072     IkiWiki::PageSpec::match_link
 178 -
 179 -With my `smcv/memoize-glob2re` branch:
 180 -
 181 -    time elapsed (wall):   30.4931
 182 -    time running program:  25.1248  (82.39%)
 183 -    time profiling (est.): 5.3683  (17.61%)
 184 -    number of calls:       1439943
 185 -    number of exceptions:  13
 186 -
 187 -    %Time    Sec.     #calls   sec/call  F  name
 188 -    13.19    3.3146     3406   0.000973     Text::Balanced::_match_tagged
 189 -     8.41    2.1123    79442   0.000027     IkiWiki::PageSpec::match_glob
 190 -     3.97    0.9979    86905   0.000011     Memoize::_memoizer
 191 -     3.05    0.7654    59454   0.000013     &lt;anon&gt;:IkiWiki/Plugin/inline.pm:223
 192 -     3.02    0.7576    29830   0.000025     IkiWiki::bestlink
 193 -
 194 -and in a repeated run:
 195 -
 196 -     8.40    2.0905    79442   0.000026     IkiWiki::PageSpec::match_glob
 197 -
 198 -With Kathryn&#39;s patch as seen in my `smcv/ka-glob-cache` branch:
 199 -
 200 -    time elapsed (wall):   27.7567
 201 -    time running program:  22.9941  (82.84%)
 202 -    time profiling (est.): 4.7627  (17.16%)
 203 -    number of calls:       1279946
 204 -    number of exceptions:  13
 205 -
 206 -    %Time    Sec.     #calls   sec/call  F  name
 207 -    14.29    3.2867     3406   0.000965     Text::Balanced::_match_tagged
 208 -     7.89    1.8136    79442   0.000023     IkiWiki::PageSpec::match_glob
 209 -     3.30    0.7577    59454   0.000013     &lt;anon&gt;:IkiWiki/Plugin/inline.pm:223
 210 -     3.24    0.7461    29830   0.000025     IkiWiki::bestlink
 211 -     3.19    0.7332      143   0.005127  ?  IkiWiki::pagespec_match_list
 212 -
 213 -and in a repeated run:
 214 -
 215 -     7.84    1.8253    79442   0.000023     IkiWiki::PageSpec::match_glob
 216 -
 217 ---&#91;&#91;smcv&#93;&#93;
 218 -
 219 ---------------------------------------------------------------
 220 +&#91;&#91;!toggle id=&quot;ka-patch&quot; text=&quot;Kathryn&#39;s original patch&quot;&#93;&#93;
 221
 222 +&#91;&#91;!toggleable id=&quot;ka-patch&quot; text=&quot;&quot;&quot;
 223
 224  &lt;pre&gt;
 225  diff --git a/IkiWiki.pm b/IkiWiki.pm
 226 @@ -174,4 +203,5 @@ index 08a3d78..c187b98 100644
 227                         return IkiWiki::SuccessReason-&gt;new(&quot;$glob matches $page&quot;);
 228                 }
 229  &lt;/pre&gt;
 230 +&quot;&quot;&quot;&#93;&#93;
 231  --------------------------------------------------------------
 232
 233 </pre>
 234 </div>
 235
 236 <!-- d6ff694ff7a6a4700ccbbd5819907eac73cf065a -->