summaryrefslogtreecommitdiff
path: root/doc/todo
diff options
context:
space:
mode:
authorjoey <joey@0fa5a96a-9a0e-0410-b3b2-a0fd24251071>2006-10-28 05:07:56 +0000
committerjoey <joey@0fa5a96a-9a0e-0410-b3b2-a0fd24251071>2006-10-28 05:07:56 +0000
commitdb3b72c4822cf9057460d47654c35f0a5115139e (patch)
tree723244c830c22679398ee87bba7a2dbc5f5d8264 /doc/todo
parent49bf877701d89d613dcf5c2d85bd08876a636dba (diff)
instead of over and over. Typical speedup is ~4x. Max possible speedup:
8x. * Add "scan" parameter to hook(), which is used to make the hook be called during the scanning pass, as well as the render pass. The meta and tag plugins need to use the new scan parameter, so will any others that modify %links. * Now that links are calculated in a separate pass, it can also precalculate backlinks in one pass, which is O(N^2) instead of the previous code that was O(N^3). A very nice speedup for wikis with lots (thousands) of pages.
Diffstat (limited to 'doc/todo')
-rw-r--r--doc/todo/optimisations.mdwn18
1 files changed, 3 insertions, 15 deletions
diff --git a/doc/todo/optimisations.mdwn b/doc/todo/optimisations.mdwn
index 13a270b8f..0eb830cd0 100644
--- a/doc/todo/optimisations.mdwn
+++ b/doc/todo/optimisations.mdwn
@@ -4,18 +4,6 @@
* Look at splitting up CGI.pm. But note that too much splitting can slow
perl down.
-* The backlinks code turns out to scale badly to wikis with thousands of
- pages. The code is O(N^2)! It's called for each page, and it loops
- through all the pages to find backlinks.
-
- Need to find a way to calculate and cache all the backlinks in one pass,
- which could be done in at worst O(N), and possibly less (if they're
- stored in the index, it could be constant time). But to do this, there
- would need to be a way to invalidate or update the cache in these
- situations:
-
- - A page is added. Note that this can change a backlink to point to
- the new page instead of the page it pointed to before.
- - A page is deleted. This can also change backlinks that pointed to that
- page.
- - A page is modified. Links added/removed.
+* The backlinks calculation code is still O(N^2) on the number of pages.
+ If backlinks info were stored in the index file, it would go down to
+ constant time for iterative builds, though still N^2 for rebuilds.