Add depends_exact: simplified dependency tracking for dependencies on a single page

Let E be the number of dependencies per page of the form "A depends on B and
nothing else", let D be the number of other dependencies per page,
let P be the total number of pages, and let C be the number of changed
pages in a refresh.

This patch should speed up a refresh from O(E*C*P + D*C*P) to
O(C + E*P + D*C*P), assuming that hash lookups are O(1).

In practice, plugins like inline and map produce a lot of these very simple
dependencies, and my album plugin's combination of inline with a large
number of pages causes it to suffer particularly badly.

In testing on a wiki with about 7000 objects (3500 full pages, 3500
images), a full rebuild continued to take about 5:30, and a refresh
after touching about 350 pages and 350 images reduced from 5:30 to 1:30.

As with my previous optimizations, this change will result in downgrades not
working correctly until the wiki is rebuilt.

1 files changed, 17 insertions, 0 deletions

diff --git a/IkiWiki/Render.pm b/IkiWiki/Render.pm
index da2d7b4cc..121fc97e3 100644
--- a/IkiWiki/Render.pm
+++ b/IkiWiki/Render.pm
@@ -210,6 +210,7 @@ sub render ($) {
 	if (defined $type) {
 		my $page=pagename($file);
 		delete $depends{$page};
+		delete $depends_exact{$page};
 		will_render($page, htmlpage($page), 1);
 		return if $type=~/^_/;
 		
@@ -224,6 +225,7 @@ sub render ($) {
 	}
 	else {
 		delete $depends{$file};
+		delete $depends_exact{$file};
 		will_render($file, $file, 1);
 		
 		if ($config{hardlink}) {
@@ -431,6 +433,7 @@ sub refresh () {
 		# internal pages are not rendered
 		my $page=pagename($file);
 		delete $depends{$page};
+		delete $depends_exact{$page};
 		foreach my $old (@{$renderedfiles{$page}}) {
 			delete $destsources{$old};
 		}
@@ -454,10 +457,24 @@ sub refresh () {
 	if (%rendered || @del || @internal) {
 		my @changed=(keys %rendered, @del);
 
+ 		my %changedpages = map { pagename($_) => 1 } @changed;
+ 
 		# rebuild dependant pages
 		F: foreach my $f (@$files) {
 			next if $rendered{$f};
 			my $p=pagename($f);
+
+			if (exists $depends_exact{$p}) {
+				foreach my $d (keys %{$depends_exact{$p}}) {
+					if (exists $changedpages{$d}) {
+						debug(sprintf(gettext("building %s, which depends on %s"), $f, $p));
+						render($f);
+						$rendered{$f}=1;
+						next F;
+					}
+				}
+			}
+
 			if (exists $depends{$p}) {
 				foreach my $d (keys %{$depends{$p}}) {
 					my $sub=pagespec_translate($d);