doc/todo/optimize_simple_dependencies.mdwn

   1 [[!template id=gitbranch branch=smcv/ready/depends-exact author="[[smcv]]"]]
   2
   3 I'm still trying to optimize ikiwiki for a site using
   4 [[plugins/contrib/album]], and checking which pages depend on which pages
   5 is still taking too long. Here's another go at fixing that, using [[Will]]'s
   6 suggestion from [[todo/should_optimise_pagespecs]]:
   7
   8 > A hash, by itself, is not optimal because
   9 > the dependency list holds two things: page names and page specs.  The hash would
  10 > work well for the page names, but you'll still need to iterate through the page specs.
  11 > I was thinking of keeping a list and a hash.  You use the list for pagespecs
  12 > and the hash for individual page names.  To make this work you need to adjust the
  13 > API so it knows which you're adding.  -- [[Will]]
  14
  15 If you have P pages and refresh after changing C of them, where an average
  16 page has E dependencies on exact page names and D other dependencies, this
  17 branch should drop the complexity of checking dependencies from
  18 O(P * (D+E) * C) to O(C + P*E + P*D*C). Pages that use inline or map have
  19 a large value for E (e.g. one per inlined page) and a small value for D (e.g.
  20 one per inline).
  21
  22 Benchmarking:
  23
  24 Test 1: a wiki with about 3500 pages and 3500 photos, and a change that
  25 touches about 350 pages and 350 photos
  26
  27 Test 2: the docwiki (about 700 objects not excluded by docwiki.setup, mostly
  28 pages), docwiki.setup modified to turn off verbose, and a change that touches
  29 the 98 pages of plugins/*.mdwn
  30
  31 In both tests I rebuilt the wiki with the target ikiwiki version, then touched
  32 the appropriate pages and refreshed.
  33
  34 Results of test 1: without this branch it took around 5:45 to rebuild and
  35 around 5:45 again to refresh (so rebuilding 10% of the pages, then deciding
  36 that most of the remaining 90% didn't need to change, took about as long as
  37 rebuilding everything). With this branch it took 5:47 to rebuild and 1:16
  38 to refresh.
  39
  40 Results of test 2: rebuilding took 14.11s without, 13.96s with; refreshing
  41 three times took 7.29/7.40/7.37s without, 6.62/6.56/6.63s with.
  42
  43 (This benchmarking was actually done with my [[plugins/contrib/album]] branch,
  44 since that's what the huge wiki needs; that branch doesn't alter core code
  45 beyond the ready/depends-exact branch point, so the results should be
  46 equally valid.)
  47
  48 --[[smcv]]