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 Is an array the right data structure? `add_depends` has to loop through the
 117 array to avoid dups, it would be better if a hash were used there. Since
 118 inline (and other plugins) explicitly add all linked pages, each as a
 119 separate item, the list can get rather long, and that single add_depends
 120 loop has suddenly become O(N^2) to the number of pages, which is something
 121 to avoid..
 122
 123 Also, since a lot of places are calling add_depends in a loop, it probably
 124 makes sense to just make it accept a list of dependencies to add. It'll be
 125 marginally faster, probably, and should allow for better optimisation
 126 when adding a lot of depends at once.
 127
 128 In Render.pm, we now have a triply nested loop, which is a bit
 129 scary for efficiency. It seems there should be a way to
 130 rework this code so it can use the optimised `pagespec_match_list`,
 131 and/or hoist some of the inner loop calculations (like the `pagename`)
 132 out.
 133
 134 Very good catch on img/meta using the wrong dependency; verified in the wild!
 135 (I've cherry-picked those bug fixes.)
 136
 137 [[!tag wishlist patch patch/core]]