From db3b72c4822cf9057460d47654c35f0a5115139e Mon Sep 17 00:00:00 2001 From: joey Date: Sat, 28 Oct 2006 05:07:56 +0000 Subject: 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. --- IkiWiki/Plugin/meta.pm | 2 +- IkiWiki/Plugin/tag.pm | 2 +- IkiWiki/Render.pm | 85 ++++++++++++++++++++++++++++++-------------------- 3 files changed, 54 insertions(+), 35 deletions(-) (limited to 'IkiWiki') diff --git a/IkiWiki/Plugin/meta.pm b/IkiWiki/Plugin/meta.pm index 5bcd65837..2e5fd7e76 100644 --- a/IkiWiki/Plugin/meta.pm +++ b/IkiWiki/Plugin/meta.pm @@ -13,7 +13,7 @@ my %author; my %authorurl; sub import { #{{{ - hook(type => "preprocess", id => "meta", call => \&preprocess); + hook(type => "preprocess", id => "meta", call => \&preprocess, scan => 1); hook(type => "filter", id => "meta", call => \&filter); hook(type => "pagetemplate", id => "meta", call => \&pagetemplate); } # }}} diff --git a/IkiWiki/Plugin/tag.pm b/IkiWiki/Plugin/tag.pm index 7a1be6bec..6d22c49fd 100644 --- a/IkiWiki/Plugin/tag.pm +++ b/IkiWiki/Plugin/tag.pm @@ -10,7 +10,7 @@ my %tags; sub import { #{{{ hook(type => "getopt", id => "tag", call => \&getopt); - hook(type => "preprocess", id => "tag", call => \&preprocess); + hook(type => "preprocess", id => "tag", call => \&preprocess, scan => 1); hook(type => "pagetemplate", id => "tag", call => \&pagetemplate); } # }}} diff --git a/IkiWiki/Render.pm b/IkiWiki/Render.pm index 026b3582e..da5a5510b 100644 --- a/IkiWiki/Render.pm +++ b/IkiWiki/Render.pm @@ -7,27 +7,42 @@ use strict; use IkiWiki; use Encode; +my %backlinks; +my $backlinks_calculated=0; + +sub calculate_backlinks () { #{{{ + %backlinks=(); + foreach my $page (keys %links) { + foreach my $link (@{$links{$page}}) { + my $bestlink=bestlink($page, $link); + if (length $bestlink && $bestlink ne $page) { + $backlinks{$bestlink}{$page}=1; + } + } + } + $backlinks_calculated=1; +} #}}} + sub backlinks ($) { #{{{ my $page=shift; - my @links; - foreach my $p (keys %links) { - next if bestlink($page, $p) eq $page; + calculate_backlinks() unless $backlinks_calculated; - if (grep { length $_ && bestlink($p, $_) eq $page } @{$links{$p}}) { - my $href=abs2rel(htmlpage($p), dirname($page)); + my @links; + return unless $backlinks{$page}; + foreach my $p (keys %{$backlinks{$page}}) { + my $href=abs2rel(htmlpage($p), dirname($page)); - # Trim common dir prefixes from both pages. - my $p_trimmed=$p; - my $page_trimmed=$page; - my $dir; - 1 while (($dir)=$page_trimmed=~m!^([^/]+/)!) && - defined $dir && - $p_trimmed=~s/^\Q$dir\E// && - $page_trimmed=~s/^\Q$dir\E//; - - push @links, { url => $href, page => pagetitle($p_trimmed) }; - } + # Trim common dir prefixes from both pages. + my $p_trimmed=$p; + my $page_trimmed=$page; + my $dir; + 1 while (($dir)=$page_trimmed=~m!^([^/]+/)!) && + defined $dir && + $p_trimmed=~s/^\Q$dir\E// && + $page_trimmed=~s/^\Q$dir\E//; + + push @links, { url => $href, page => pagetitle($p_trimmed) }; } return sort { $a->{page} cmp $b->{page} } @links; @@ -128,6 +143,11 @@ sub scan ($) { #{{{ my $srcfile=srcfile($file); my $content=readfile($srcfile); my $page=pagename($file); + will_render($page, htmlpage($page), 1); + + # Always needs to be done, since filters might add links + # to the content. + $content=filter($page, $content); my @links; while ($content =~ /(? $oldpagemtime{$page} || $forcerebuild{$page}) { debug("scanning $file"); + push @changed, $file; scan($file); } } - # render any updated files - foreach my $file (@files) { - my $page=pagename($file); - - if (! exists $oldpagemtime{$page} || - mtime(srcfile($file)) > $oldpagemtime{$page} || - $forcerebuild{$page}) { - debug("rendering $file"); - render($file); - $rendered{$file}=1; - } + # render changed and new pages + foreach my $file (@changed) { + debug("rendering $file"); + render($file); + $rendered{$file}=1; } # if any files were added or removed, check to see if each page @@ -310,9 +328,8 @@ FILE: foreach my $file (@files) { } } - # Handle backlinks; if a page has added/removed links, update the - # pages it links to. Also handles rebuilding dependant pages. if (%rendered || @del) { + # rebuild dependant pages foreach my $f (@files) { next if $rendered{$f}; my $p=pagename($f); @@ -330,6 +347,8 @@ FILE: foreach my $file (@files) { } } + # handle backlinks; if a page has added/removed links, + # update the pages it links to my %linkchanged; foreach my $file (keys %rendered, @del) { my $page=pagename($file); @@ -364,7 +383,7 @@ FILE: foreach my $file (@files) { } } - # Remove no longer rendered files. + # remove no longer rendered files foreach my $src (keys %rendered) { my $page=pagename($src); foreach my $file (@{$oldrenderedfiles{$page}}) { -- cgit v1.2.3