3dfa8e1f28a0c1a87bdfe4750ec319cc2f043286
[ikiwiki.git] / doc / todo / should_optimise_pagespecs.mdwn
1 I think there is a problem in my "dependency graph". As an example, 
2 [here](http://poivron.org/~nil/misc/ikiwiki_buggy_index) is the index 
3 ikiwiki generated for [my site](http://poivron.org/~nil/misc/ikiwiki_buggy_index)
4 (note that the site changed since this index was generated).
5
6 Some **HUGE** dependencies appear, clearly non optimal, like
7
8     depends = A| B | A | C | A | D | A | E | A | F | A | G | ....
9
10 or 
11
12     depends= A | B | C | D | A | B | C | D | A | B | C | D | ....
13
14 Couldn't isolate the cause, but some sources for this problem may be:
15
16 * related to the img module
17 * easily observable in my sire because one of my pages includes 80 resized images
18
19 Other special things in my templates and site:
20
21 * a sidebar with \[[!include pages="notes/\*" template=foo]] while notes.mdwn has 
22   a \[[!include pages="notes/*"]] and uses the sidebar; removed it, doesn't change
23 * a template (biblio.tmpl) calling the "img" plugin with a template parameter as the
24   image filename; removed it, doesn't change
25 * some strange games with tags whose page calls a "map" directive to show other tags
26   shile tags are also used in tagclouds (in the sidebar and in the main pages)
27 * ...
28
29 I observed these problems (same *kind*, I didn't check in details) on
30  
31 * ikiwiki 2.00gpa1 + v5.8.4 + Debian 3.1
32 * ikiwiki 2.3 + v5.8.8 + Ubuntu 7.04
33
34 I can think about reducung the size of my wiki source and making it available online for analysis.
35
36 -- NicolasLimare
37
38 > As long as these dependencies don't grow over time (ie, when a page is
39 > edited and nothing changed that should add a dependency), I wouldn't
40 > worry about them. There are many things that can cause non-optimal
41 > dependencies to be recorded. For one thing, if you inline something, ikiwiki
42 > creates a dependency like:
43
44 > (PageSpec) or (file1 or file2 or file3 ...)
45
46 > Where fileN are all the files that the PageSpec currently matches. (This
47 > is ncessary to detect when a currently inlined file is deleted, and know
48 > the inlining page needs an update.) Now consider what it does if you have
49 > a single page with two inline statements, that inline the same set of
50 > stuff twice:
51
52 > ((PageSpec) or (file1 or file2 or file3 ...) or (PageSpec) or (file1 or file2 or file3 ...)
53 >
54 > Clearly non-optimal, indeed.
55
56 > Ikiwiki doesn't bother to simplify complex PageSpecs
57 > because it's difficult to do, and because all they use is some disk
58 > space. Consider what ikiwiki uses these dependencies for.
59 > All it wants to know is: does the PageSpec for this page it's considering
60 > rebuilding match any of the pages that have changed? Determining this is
61 > a simple operation -- the PageSpec is converted to perl code. The perl
62 > code is run.
63
64 > So the total impact of an ugly dependency like this is:
65
66 > 1. Some extra data read/written to disk.
67 > 2. Some extra space in memory.
68 > 3. A bit more data for the PageSpec translation code to handle. But that
69 >    code is quite fast.
70 > 4. Typically one extra function call when the generated perl code is run.
71 >    Ie, when the expression on the left-hand side fails, which typically
72 >    happens after one (inexpensive) function call, it has to check
73 >    the identical expression on the right hand side.
74
75 > So this is at best a wishlist todo item, not a bug. A PageSpec simplifier
76 > (or improved `pagespec_merge()` function) could be written and improve
77 > ikiwiki's memory and disk usage, but would it actually speed it up any?
78 > We'd have to see the code to the simplifier to know.
79
80 > --[[Joey]]
81
82 [[!template id=gitbranch branch=smcv/ready/optimize-depends author="[[smcv]]"]]
83
84 >> I've been looking at optimizing ikiwiki for a site using
85 >> [[plugins/contrib/album]] (which produces a lot of pages) and it seems
86 >> that checking which pages depend on which pages does take a significant
87 >> amount of time. The optimize-depends branch in my git repository
88 >> avoids using `pagespec_merge()` for this (indeed it's no longer used
89 >> at all), and instead represents dependencies as a list of pagespecs
90 >> rather than a single pagespec. This does turn out to be faster, although
91 >> not as much as I'd like. --[[smcv]]
92
93 >>> I just wanted to note that there is a whole long discussion of dependencies and pagespecs on the [[todo/tracking_bugs_with_dependencies]] page. -- [[Will]]
94
95 >>>> Yeah, I had a look at that (as the only other mention of `pagespec_merge`).
96 >>>> I think I might have solved some of the problems mentioned there,
97 >>>> actually - `pagespec_merge` no longer needs to exist in my branch (although
98 >>>> I haven't actually deleted it), because the "or" operation is now done in
99 >>>> the Perl code, rather than by merging pagespecs and translating. --[[smcv]]
100
101 [[!template id=gitbranch branch=smcv/ready/remove-pagespec-merge author="[[smcv]]"]]
102
103 >>>>> I've now added a patch to the end of that branch that deletes
104 >>>>> `pagespec_merge` almost entirely (we do need to keep a copy around, in
105 >>>>> ikiwiki-transition, but that copy doesn't have to be optimal or support
106 >>>>> future features like [[tracking_bugs_with_dependencies]]). --[[smcv]]
107
108 ---
109
110 Some questions on your optimize-depends branch. --[[Joey]]
111
112 In saveindex it still or'd together the depends list, but the `{depends}`
113 field seems only useful for backwards compatability (ie, ikiwiki-transition
114 uses it still), and otherwise just bloats the index.
115
116 > If it's acceptable to declare that downgrading IkiWiki requires a complete
117 > rebuild, I'm happy with that. I'd prefer to keep the (simple form of the)
118 > transition done automatically during a load/save cycle, rather than
119 > requiring ikiwiki-transition to be run; we should probably say in NEWS
120 > that the performance increase won't fully apply until the next
121 > rebuild. --[[smcv]]
122
123 >> It is acceptable not to support downgrades.
124 >> I don't think we need a NEWS file update since any sort of refresh,
125 >> not just a full rebuild, will cause the indexdb to be loaded and saved,
126 >> enabling the optimisation. --[[Joey]]
127
128 >>> A refresh will load the current dependencies from `{depends}` and save
129 >>> them as-is as a one-element `{dependslist}`; only a rebuild will replace
130 >>> the single complex pagespec with a long list of simpler pagespecs.
131 >>> --[[smcv]]
132
133 Is an array the right data structure? `add_depends` has to loop through the
134 array to avoid dups, it would be better if a hash were used there. Since
135 inline (and other plugins) explicitly add all linked pages, each as a
136 separate item, the list can get rather long, and that single add_depends
137 loop has suddenly become O(N^2) to the number of pages, which is something
138 to avoid..
139
140 > I was also thinking about this (I've been playing with some stuff based on the
141 > `remove-pagespec-merge` branch).  A hash, by itself, is not optimal because
142 > the dependency list holds two things: page names and page specs.  The hash would
143 > work well for the page names, but you'll still need to iterate through the page specs.
144 > I was thinking of keeping a list and a hash.  You use the list for pagespecs
145 > and the hash for individual page names.  To make this work you need to adjust the
146 > API so it knows which you're adding.  -- [[Will]]
147
148 > I wasn't thinking about a lookup hash, just a dedup hash, FWIW.
149 > --[[Joey]]
150
151 >> I was under the impression from previous code review that you preferred
152 >> to represent unordered sets as lists, rather than hashes with dummy
153 >> values. If I was wrong, great, I'll fix that and it'll probably go
154 >> a bit faster. --[[smcv]]
155
156 >>> It depends, really. And it'd certianly make sense to benchmark such a
157 >>> change. --[[Joey]]
158
159 >>>> Benchmarked, below. --[[smcv]]
160
161 Also, since a lot of places are calling add_depends in a loop, it probably
162 makes sense to just make it accept a list of dependencies to add. It'll be
163 marginally faster, probably, and should allow for better optimisation
164 when adding a lot of depends at once.
165
166 > That'd be an API change; perhaps marginally faster, but I don't
167 > see how it would allow better optimisation if we're de-duplicating
168 > anyway? --[[smcv]]
169
170 >> Well, I was thinking that it might be sufficient to build a `%seen`
171 >> hash of dependencies inside `add_depends`, if the places that call
172 >> it lots were changed to just call it once. Of course the only way to
173 >> tell is benchmarking. --[[Joey]]
174
175 >>> It doesn't seem that it significantly affects performance either way.
176 >>> --[[smcv]]
177
178 In Render.pm, we now have a triply nested loop, which is a bit
179 scary for efficiency. It seems there should be a way to
180 rework this code so it can use the optimised `pagespec_match_list`,
181 and/or hoist some of the inner loop calculations (like the `pagename`)
182 out.
183
184 > I don't think the complexity is any greater than it was: I've just
185 > moved one level of "loop" out of the generated Perl, to be
186 > in visible code. I'll see whether some of it can be hoisted, though.
187 > --[[smcv]]
188
189 >> The call to `pagename` is the only part I can see that's clearly
190 >> run more often than before. That function is pretty inexpensive, but..
191 >> --[[Joey]]
192
193 >>> I don't see anything that can be hoisted without significant refactoring,
194 >>> actually. Beware that there are two pagename calls in the loop: one for
195 >>> `$f` (which is the page we might want to rebuild), and one for `$file`
196 >>> (which is the changed page that it might depend on). Note that I didn't
197 >>> choose those names!
198 >>>
199 >>> The three loops are over source files, their lists of dependency pagespecs,
200 >>> and files that might have changed. I see the following things we might be
201 >>> doing redundantly:
202 >>>
203 >>> * If `$file` is considered as a potential dependency for more than
204 >>>   one `$f`, we evaluate `pagename($file)` more than once. Potential fix:
205 >>>   cache them (this turns out to save about half a second on the docwiki,
206 >>>   see below).
207 >>> * If several pages depend on the same pagespec, we evaluate whether each
208 >>>   changed page matches that pagespec more than once: however, we do so
209 >>>   with a different location parameter every time, so repeated calls are,
210 >>>   in the general case, the only correct thing to do. Potential fix:
211 >>>   perhaps special-case "page x depends on page y and nothing else"
212 >>>   (i.e. globs that have no wildcards) into a separate hash? I haven't
213 >>>   done anything in this direction.
214 >>> * Any preparatory work done by pagespec_match (converting the pagespec
215 >>>   into Perl, mostly?) is done in the inner loop; switching to
216 >>>   pagespec_match_list (significant refactoring) saves more than half a
217 >>>   second on the docwiki.
218 >>>
219 >>> --[[smcv]]
220
221 Very good catch on img/meta using the wrong dependency; verified in the wild!
222 (I've cherry-picked those bug fixes.)
223
224 ----
225
226 Benchmarking results: I benchmarked by altering docwiki.setup to switch off
227 verbose, running "make clean && ./Makefile.PL && make", and timing one rebuild
228 of the docwiki followed by three refreshes. Before each refresh I used
229 `touch plugins/*.mdwn` to have something significant to refresh.
230
231 I'm assuming that "user" CPU time is the important thing here (system time was
232 relatively small in all cases, up to 0.35 seconds per run).
233
234 master at the time of rebasing: 14.20s to rebuild, 10.04/12.07/14.01s to
235 refresh. I think you can see the bug clearly here - the pagespecs are getting
236 more complicated every time!
237
238 After the initial optimization: 14.27s to rebuild, 8.26/8.33/8.26 to refresh.
239 Success!
240
241 Not pre-joining dependencies actually took about ~0.2s more; I don't know why.
242 I'm worried that duplicates will just build up (again) in less simple cases,
243 though, so 0.2s is probably a small price to pay for that not happening (it
244 might well be experimental error, for that matter).
245
246 Not saving {depends} to the index, using a hash instead of a list to
247 de-duplicate, and allowing add_depends to take an arrayref instead of a single
248 pagespec had no noticable positive or negative effect on this test.
249
250 Memoizing the results of pagename brought the rebuild time down to 14.06s
251 and the refresh time down to 7.96/7.92/7.92, a significant win.
252
253 Refactoring to use pagespec_match_list looks more risky from a code churn
254 point of view; rebuild now takes 14.35s, but refresh is only 7.30/7.29/7.28,
255 another significant win.
256
257 --[[smcv]]
258
259 [[!tag wishlist patch patch/core]]