]> sipb.mit.edu Git - ikiwiki.git/blob - doc/todo/Improving_the_efficiency_of_match__95__glob.mdwn
branches imported into git; benchmark results
[ikiwiki.git] / 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 --------------------------------------------------------------
24 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.
25
26 Before:
27 <pre>
28 time elapsed (wall):   27.4173
29 time running program:  22.5909  (82.40%)
30 time profiling (est.): 4.8264  (17.60%)
31 number of calls:       1314729
32 number of exceptions:  65
33
34 %Time    Sec.     #calls   sec/call  F  name
35 11.05    2.4969    62333   0.000040     IkiWiki::PageSpec::match_glob
36  4.10    0.9261      679   0.001364     Text::Balanced::_match_tagged
37  2.72    0.6139    59812   0.000010     IkiWiki::SuccessReason::merge_influences
38 </pre>
39
40 After:
41 <pre>
42 time elapsed (wall):   26.1843
43 time running program:  21.5673  (82.37%)
44 time profiling (est.): 4.6170  (17.63%)
45 number of calls:       1252433
46 number of exceptions:  65
47
48 %Time    Sec.     #calls   sec/call  F  name
49  7.66    1.6521    62333   0.000027     IkiWiki::PageSpec::match_glob
50  4.33    0.9336      679   0.001375     Text::Balanced::_match_tagged
51  2.81    0.6057    59812   0.000010     IkiWiki::SuccessReason::merge_influences
52 </pre>
53
54 Note that the seconds per call for match_glob in the "after" case has gone down by about a third.
55
56 K.A.
57
58 --------------------------------------------------------------
59
60 A second set of benchmarks, done by rebuilding the docwiki at commit f942c2db05e4
61 like so:
62
63     perl -Iblib/lib -d:Profile ikiwiki.in -setup docwiki.setup --no-verbose
64
65 The docwiki appears to use fewer glob matches than Kathryn's wiki.
66
67 With master:
68
69     time elapsed (wall):   29.6970
70     time running program:  24.6930  (83.15%)
71     time profiling (est.): 5.0041  (16.85%)
72     number of calls:       1359180
73     number of exceptions:  13
74
75     %Time    Sec.     #calls   sec/call  F  name
76     13.62    3.3629     3406   0.000987     Text::Balanced::_match_tagged
77     10.84    2.6773    79442   0.000034     IkiWiki::PageSpec::match_glob
78      3.08    0.7598    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
79      3.07    0.7593    29830   0.000025     IkiWiki::bestlink
80      2.99    0.7378    10231   0.000072     IkiWiki::PageSpec::match_link
81
82 With my `smcv/memoize-glob2re` branch:
83
84     time elapsed (wall):   30.4931
85     time running program:  25.1248  (82.39%)
86     time profiling (est.): 5.3683  (17.61%)
87     number of calls:       1439943
88     number of exceptions:  13
89
90     %Time    Sec.     #calls   sec/call  F  name
91     13.19    3.3146     3406   0.000973     Text::Balanced::_match_tagged
92      8.41    2.1123    79442   0.000027     IkiWiki::PageSpec::match_glob
93      3.97    0.9979    86905   0.000011     Memoize::_memoizer
94      3.05    0.7654    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
95      3.02    0.7576    29830   0.000025     IkiWiki::bestlink
96
97 and in a repeated run:
98
99      8.40    2.0905    79442   0.000026     IkiWiki::PageSpec::match_glob
100
101 With Kathryn's patch as seen in my `smcv/ka-glob-cache` branch:
102
103     time elapsed (wall):   27.7567
104     time running program:  22.9941  (82.84%)
105     time profiling (est.): 4.7627  (17.16%)
106     number of calls:       1279946
107     number of exceptions:  13
108
109     %Time    Sec.     #calls   sec/call  F  name
110     14.29    3.2867     3406   0.000965     Text::Balanced::_match_tagged
111      7.89    1.8136    79442   0.000023     IkiWiki::PageSpec::match_glob
112      3.30    0.7577    59454   0.000013     <anon>:IkiWiki/Plugin/inline.pm:223
113      3.24    0.7461    29830   0.000025     IkiWiki::bestlink
114      3.19    0.7332      143   0.005127  ?  IkiWiki::pagespec_match_list
115
116 and in a repeated run:
117
118      7.84    1.8253    79442   0.000023     IkiWiki::PageSpec::match_glob
119
120 --[[smcv]]
121
122 --------------------------------------------------------------
123
124
125 <pre>
126 diff --git a/IkiWiki.pm b/IkiWiki.pm
127 index 08a3d78..c187b98 100644
128 --- a/IkiWiki.pm
129 +++ b/IkiWiki.pm
130 @@ -2482,6 +2482,8 @@ sub derel ($$) {
131         return $path;
132  }
133  
134 +my %glob_cache;
135 +
136  sub match_glob ($$;@) {
137         my $page=shift;
138         my $glob=shift;
139 @@ -2489,8 +2491,15 @@ sub match_glob ($$;@) {
140         
141         $glob=derel($glob, $params{location});
142  
143 -       my $regexp=IkiWiki::glob2re($glob);
144 -       if ($page=~/^$regexp$/i) {
145 +       # Instead of converting the glob to a regex every time,
146 +       # cache the compiled regex to save time.
147 +       if (!exists $glob_cache{$glob}
148 +           or !defined $glob_cache{$glob})
149 +       {
150 +           my $re=IkiWiki::glob2re($glob);
151 +           $glob_cache{$glob} = qr/^$re$/i;
152 +       }
153 +       if ($page =~ $glob_cache{$glob}) {
154                 if (! IkiWiki::isinternal($page) || $params{internal}) {
155                         return IkiWiki::SuccessReason->new("$glob matches $page");
156                 }
157 </pre>
158 --------------------------------------------------------------