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, 20 insertions, 3 deletions

diff --git a/IkiWiki.pm b/IkiWiki.pm
index 5563a03af..f6a985556 100644
--- a/IkiWiki.pm
+++ b/IkiWiki.pm
@@ -14,14 +14,14 @@ use open qw{:utf8 :std};
 use vars qw{%config %links %oldlinks %pagemtime %pagectime %pagecase
 	    %pagestate %wikistate %renderedfiles %oldrenderedfiles
 	    %pagesources %destsources %depends %hooks %forcerebuild
-	    %loaded_plugins};
+	    %loaded_plugins %depends_exact};
 
 use Exporter q{import};
 our @EXPORT = qw(hook debug error template htmlpage add_depends pagespec_match
                  pagespec_match_list bestlink htmllink readfile writefile
 		 pagetype srcfile pagename displaytime will_render gettext urlto
 		 targetpage add_underlay pagetitle titlepage linkpage
-		 newpagefile inject add_link
+		 newpagefile inject add_link add_depends_exact
                  %config %links %pagestate %wikistate %renderedfiles
                  %pagesources %destsources);
 our $VERSION = 3.00; # plugin interface version, next is ikiwiki version
@@ -1475,7 +1475,8 @@ sub loadindex () {
 	%oldrenderedfiles=%pagectime=();
 	if (! $config{rebuild}) {
 		%pagesources=%pagemtime=%oldlinks=%links=%depends=
-		%destsources=%renderedfiles=%pagecase=%pagestate=();
+		%destsources=%renderedfiles=%pagecase=%pagestate=
+		%depends_exact=();
 	}
 	my $in;
 	if (! open ($in, "<", "$config{wikistatedir}/indexdb")) {
@@ -1515,6 +1516,11 @@ sub loadindex () {
 				$links{$page}=$d->{links};
 				$oldlinks{$page}=[@{$d->{links}}];
 			}
+			if (exists $d->{depends_exact}) {
+				$depends_exact{$page}={
+					map { $_ => 1 } @{$d->{depends_exact}}
+				};
+			}
 			if (exists $d->{dependslist}) {
 				$depends{$page}={
 					map { $_ => 1 } @{$d->{dependslist}}
@@ -1570,6 +1576,10 @@ sub saveindex () {
 			$index{page}{$src}{dependslist} = [ keys %{$depends{$page}} ];
 		}
 
+		if (exists $depends_exact{$page}) {
+			$index{page}{$src}{depends_exact} = [ keys %{$depends_exact{$page}} ];
+		}
+
 		if (exists $pagestate{$page}) {
 			foreach my $id (@hookids) {
 				foreach my $key (keys %{$pagestate{$page}{$id}}) {
@@ -1744,6 +1754,13 @@ sub add_depends ($$) {
 	return 1;
 }
 
+sub add_depends_exact ($$) {
+	my $page = shift;
+	my $dep = shift;
+
+	$depends_exact{$page}{$dep} = 1;
+}
+
 sub file_pruned ($$) {
 	require File::Spec;
 	my $file=File::Spec->canonpath(shift);