X-Git-Url: http://git.vanrenterghem.biz/git.ikiwiki.info.git/blobdiff_plain/49bf877701d89d613dcf5c2d85bd08876a636dba..f8cbf79735bc4588ba6fde12f3855a51efeb7ae8:/doc/todo/optimisations.mdwn

diff --git a/doc/todo/optimisations.mdwn b/doc/todo/optimisations.mdwn
index 13a270b8f..40ffaf548 100644
--- a/doc/todo/optimisations.mdwn
+++ b/doc/todo/optimisations.mdwn
@@ -1,21 +1,11 @@
+Ikiwiki has already been optimised a lot, however..
+
 * Don't render blog archive pages unless a page is added/removed. Just
   changing a page doesn't affect the archives as they show only the title.
 
 * 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.