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.

diff --git a/IkiWiki.pm b/IkiWiki.pm
index 5563a03af7d028a88c184d8f2ac227284c475f52..f6a985556bec162c46eb6fdea84abd9ea6c7e67f 100644 (file)
--- 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
 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
 
 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
                  %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=
        %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")) {
        }
        my $in;
        if (! open ($in, "<", "$config{wikistatedir}/indexdb")) {


@@ -1515,6 +1516,11 @@ sub loadindex () {
                                $links{$page}=$d->{links};
                                $oldlinks{$page}=[@{$d->{links}}];
                        }
                                $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}}
                        if (exists $d->{dependslist}) {
                                $depends{$page}={
                                        map { $_ => 1 } @{$d->{dependslist}}


@@ -1570,6 +1576,10 @@ sub saveindex () {
                        $index{page}{$src}{dependslist} = [ keys %{$depends{$page}} ];
                }
 
                        $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}}) {
                if (exists $pagestate{$page}) {
                        foreach my $id (@hookids) {
                                foreach my $key (keys %{$pagestate{$page}{$id}}) {


@@ -1744,6 +1754,13 @@ sub add_depends ($$) {
        return 1;
 }
 
        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);
 sub file_pruned ($$) {
        require File::Spec;
        my $file=File::Spec->canonpath(shift);

diff --git a/IkiWiki/Render.pm b/IkiWiki/Render.pm
index da2d7b4ccc1adc480c2acc20f6b5d167a8fc7ff2..121fc97e374533dbf5cb91f46059ff6926394e0e 100644 (file)
--- a/IkiWiki/Render.pm
+++ b/IkiWiki/Render.pm
@@ -210,6 +210,7 @@ sub render ($) {
        if (defined $type) {
                my $page=pagename($file);
                delete $depends{$page};
        if (defined $type) {
                my $page=pagename($file);
                delete $depends{$page};

+               delete $depends_exact{$page};

                will_render($page, htmlpage($page), 1);
                return if $type=~/^_/;
                
                will_render($page, htmlpage($page), 1);
                return if $type=~/^_/;
                


@@ -224,6 +225,7 @@ sub render ($) {
        }
        else {
                delete $depends{$file};
        }
        else {
                delete $depends{$file};

+               delete $depends_exact{$file};

                will_render($file, $file, 1);
                
                if ($config{hardlink}) {
                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};
                # internal pages are not rendered
                my $page=pagename($file);
                delete $depends{$page};

+               delete $depends_exact{$page};

                foreach my $old (@{$renderedfiles{$page}}) {
                        delete $destsources{$old};
                }
                foreach my $old (@{$renderedfiles{$page}}) {
                        delete $destsources{$old};
                }


@@ -454,10 +457,24 @@ sub refresh () {
        if (%rendered || @del || @internal) {
                my @changed=(keys %rendered, @del);
 
        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);
                # 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);
                        if (exists $depends{$p}) {
                                foreach my $d (keys %{$depends{$p}}) {
                                        my $sub=pagespec_translate($d);