doc/todo/optimize_simple_dependencies.mdwn

   1 I'm still trying to optimize ikiwiki for a site using
   2 [[plugins/contrib/album]], and checking which pages depend on which pages
   3 is still taking too long. Here's another go at fixing that, using [[Will]]'s
   4 suggestion from [[todo/should_optimise_pagespecs]]:
   5
   6 > A hash, by itself, is not optimal because
   7 > the dependency list holds two things: page names and page specs.  The hash would
   8 > work well for the page names, but you'll still need to iterate through the page specs.
   9 > I was thinking of keeping a list and a hash.  You use the list for pagespecs
  10 > and the hash for individual page names.  To make this work you need to adjust the
  11 > API so it knows which you're adding.  -- [[Will]]
  12
  13 If you have P pages and refresh after changing C of them, where an average
  14 page has E dependencies on exact page names and D other dependencies, this
  15 branch should drop the complexity of checking dependencies from
  16 O(P * (D+E) * C) to O(C + P*E + P*D*C). Pages that use inline or map have
  17 a large value for E (e.g. one per inlined page) and a small value for D (e.g.
  18 one per inline).
  19
  20 Benchmarking:
  21
  22 Test 1: a wiki with about 3500 pages and 3500 photos, and a change that
  23 touches about 350 pages and 350 photos
  24
  25 Test 2: the docwiki (about 700 objects not excluded by docwiki.setup, mostly
  26 pages), docwiki.setup modified to turn off verbose, and a change that touches
  27 the 98 pages of plugins/*.mdwn
  28
  29 In both tests I rebuilt the wiki with the target ikiwiki version, then touched
  30 the appropriate pages and refreshed.
  31
  32 Results of test 1: without this branch it took around 5:45 to rebuild and
  33 around 5:45 again to refresh (so rebuilding 10% of the pages, then deciding
  34 that most of the remaining 90% didn't need to change, took about as long as
  35 rebuilding everything). With this branch it took 5:47 to rebuild and 1:16
  36 to refresh.
  37
  38 Results of test 2: rebuilding took 14.11s without, 13.96s with; refreshing
  39 three times took 7.29/7.40/7.37s without, 6.62/6.56/6.63s with.
  40
  41 (This benchmarking was actually done with my [[plugins/contrib/album]] branch,
  42 since that's what the huge wiki needs; that branch doesn't alter core code
  43 beyond the ready/depends-exact branch point, so the results should be
  44 equally valid.)
  45
  46 --[[smcv]]
  47
  48 > Now [[merged|done]] --[[smcv]]
  49
  50 ----
  51
  52 > We discussed this on irc; I had some worries that things may have been
  53 > switched to `add_depends_exact` that were not pure page names. My current
  54 > feeling is it's all safe, but who knows. It's easy to miss something.
  55 > Which makes me think this is not a good interface.
  56 >
  57 > Why not, instead, make `add_depends` smart. If it's passed something
  58 > that is clearly a raw page name, it can add it to the exact depends hash.
  59 > Else, add it to the pagespec hash. You can tell if it's a pure page name
  60 > by matching on `$config{wiki_file_regexp}`.
  61
  62 >> Good thinking. Done in commit 68ce514a 'Auto-detect "simple dependencies"',
  63 >> with a related bugfix in e8b43825 "Force %depends_exact to lower case".
  64 >>
  65 >> Performance impact: Test 2 above takes 0.2s longer to rebuild (probably
  66 >> from all the calls to lc, which are, however, necessary for correctness)
  67 >> and has indistinguishable performance for a refresh.
  68 >>
  69 >> Test 1 took about 6 minutes to rebuild and 1:25 to refresh; those are
  70 >> pessimistic figures, since I've added 90 more photos and 90 more pages
  71 >> (both to the wiki as a whole, and the number touched before refreshing)
  72 >> since testing the previous version of this branch. --[[smcv]]
  73
  74 > Also I think there may be little optimisation value left in
  75 > 7227c2debfeef94b35f7d81f42900aa01820caa3, since the "regular" dependency
  76 > lists will be much shorter.
  77
  78 >> You're probably right, but IMO it's not worth reverting it - a set (hash with
  79 >> dummy values) is still the right data structure. --[[smcv]]
  80
  81 > Sounds like inline pagenames has an already exstant bug WRT
  82 > pages moving, which this should not make worse. Would be good to verify.
  83
  84 >> If you mean the standard "add a better match for a link-like construct" bug
  85 >> that also affects sidebar, then yes, it does have the bug, but I'm pretty
  86 >> sure this branch doesn't make it any worse. I could solve this at the cost
  87 >> of making pagenames less useful for interactive use, by making it not
  88 >> respect [[ikiwiki/subpage/LinkingRules]], but instead always interpret
  89 >> its paths as relative to the top of the wiki - that's actually all that
  90 >> [[plugins/contrib/album]] needs. --[[smcv]]
  91
  92 > Re coding, it would be nice if `refresh()` could avoid duplicating
  93 > the debug message, etc in the two cases. --[[Joey]]
  94
  95 >> Fixed in commit f805d566 "Avoid duplicating debug message..." --[[smcv]]