[PATCH 0/7] gitweb: Trying to improve history view speed

[PATCH 0/7] gitweb: Trying to improve history view speed

[Jakub Narebski]

This series of patches tries to improve gitweb speed somewhat.

Patch 1/7 makes possible to easily enable/disable pickaxe search
('pickaxe:' operator), by making pickaxe search a feature. 

Patch 2/7 paginates history output, which makes "history" view
for files with longer history appear much faster. Patch 7/7 fixes
omission in pagination of history output. This patch is updated
to newer mod_perl compatibile gitweb version, and corrected version
of previous patch with the same title.

Patch 3/7 makes it easy to make history output faster, if changing
the output (making output backward-incompatibile), by making it easy
to remove '--full-history' option and/or add '--remove-empty' option.

Patches 4/7, 5/7, 6/7 tries to make gitweb faster by eliminating
calls to git-rev-list, combining generating list of revision and
commit parsing into one subroutine, using one call to git-rev-list.
Unfortunately, git-rev-list is broken: 'git rev-list <commit> 
--full-history --parents -- <filename>' shows all merges in addition
to what 'git rev-list <commit> --parents -- <filename>' and 
'git rev-list <commit> --full-history -- <filename>' shows, see
"git-rev-list --full-history --parents doesn't respect path limit 
and shows all merges" thread
  Message-ID: <edmabt$3tc$1@sea.gmane.org>
  http://permalink.gmane.org/gmane.comp.version-control.git/26514
So probably those patches should be dropped or put in freezer until
git-rev-list is corrected.


Benchmark:
First column is the patch number (0 means state before first patch),
columns 2 to 4 are results of running gitweb from command line,
using /usr/bin/time -f "%e %U %s", columns 5 to 8 are taken from
ApacheBench 2.0.41-dev, run with -n 10 option, 5 and 6 for mod_cgi,
7 and 8 for mod_perl (probably not configured correctly, as it is
slower than CGI version).
 
# 1:gitweb/new~n 2:%e 3:%U 4:%s 5:ab-n10_cgi_time[ms] 6:[+/-sd] 7:ab-n10_perl_time[ms] 8:[+/-sd]
0 11.38 9.66 0 11350.681   96.8 11950.143  546.3
1 11.37 9.71 0 18150.842 4327.8 14535.352 3149.1
2 3.61  2.16 0  3719.344  261.9  3975.663  219.6
3 3.62  2.20 0  3576.822   41.2  3929.396  201.6
4 3.61  2.13 0  3620.246  188.3  3943.111  184.1
4 3.61  2.13 0  3622.156  172.6  3716.499   53.0  
#5 0/0   0/0 0/0     0/0    0/0       0/0    0/0
6 2.60  1.56 0  2809.344  369.5  2823.286  245.9
7 2.59  1.53 0  2621.073  234.2  2742.230   96.6

Shortlog:
 [PATCH 1/7] gitweb: Make pickaxe search a feature
 [PATCH 2/7] gitweb: Paginate history output
 [PATCH 3/7] gitweb: Use @hist_opts as git-rev-list parameters
             in git_history
 [PATCH 4/7] gitweb: Add parse_rev_list for later use
 [PATCH 5/7] gitweb: Use parse_rev_list in git_shortlog and git_history
 [PATCH 6/7] gitweb: Assume parsed revision list in git_shortlog_body
             and git_history_body
 [PATCH 7/7] gitweb: Set page to 0 if it is not defined, in git_history

Diffstat:
---
gitweb/gitweb.perl |  180 +++++++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 141 insertions(+), 39 deletions(-)-

P.S. Is putting diffstat in such a series of patches actually usefull?
-- 
Jakub Narebski
ShadeHawk on #git
Poland

[PATCH 1/7] gitweb: Make pickaxe search a feature

[Jakub Narebski]

As pickaxe search (selected using undocumented 'pickaxe:' operator in
search query) is resource consuming, allow to turn it on/off using
feature meachanism.

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
 gitweb/gitweb.perl |   33 +++++++++++++++++++++++++++++++--
 1 files changed, 31 insertions(+), 2 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index d6f546d..e95d16f 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -93,6 +93,11 @@ our %feature = (
 		'override' => 0,
 		#         => [content-encoding, suffix, program]
 		'default' => ['x-gzip', 'gz', 'gzip']},
+
+	'pickaxe' => {
+		'sub' => \&feature_pickaxe,
+		'override' => 0,
+		'default' => [0]},
 );
 
 sub gitweb_check_feature {
@@ -146,6 +151,24 @@ sub feature_snapshot {
 	return ($ctype, $suffix, $command);
 }
 
+# To enable system wide have in $GITWEB_CONFIG
+# $feature{'pickaxe'}{'default'} = [1];
+# To have project specific config enable override in $GITWEB_CONFIG
+# $feature{'pickaxe'}{'override'} = 1;
+# and in project config gitweb.pickaxe = 0|1;
+
+sub feature_pickaxe {
+	my ($val) = git_get_project_config('pickaxe', '--bool');
+
+	if ($val eq 'true') {
+		return (1);
+	} elsif ($val eq 'false') {
+		return (0);
+	}
+
+	return ($_[0]);
+}
+
 # rename detection options for git-diff and git-diff-tree
 # - default is '-M', with the cost proportional to
 #   (number of removed files) * (number of new files).
@@ -3131,8 +3154,7 @@ sub git_search {
 	if (!%co) {
 		die_error(undef, "Unknown commit object");
 	}
-	# pickaxe may take all resources of your box and run for several minutes
-	# with every query - so decide by yourself how public you make this feature :)
+
 	my $commit_search = 1;
 	my $author_search = 0;
 	my $committer_search = 0;
@@ -3144,6 +3166,13 @@ sub git_search {
 	} elsif ($searchtext =~ s/^pickaxe\\://i) {
 		$commit_search = 0;
 		$pickaxe_search = 1;
+
+		# pickaxe may take all resources of your box and run for several minutes
+		# with every query - so decide by yourself how public you make this feature
+		my ($have_pickaxe) = gitweb_check_feature('pickaxe');
+		if (!$have_pickaxe) {
+			die_error('403 Permission denied', "Permission denied");
+		}
 	}
 	git_header_html();
 	git_print_page_nav('','', $hash,$co{'tree'},$hash);
-- 
1.4.2

[PATCH 2/7] gitweb: Paginate history output

[Jakub Narebski]

git_history output is now divided into pages, like git_shortlog,
git_tags and git_heads output. As whole git-rev-list output is now
read into array before writing anything, it allows for better
signaling of errors.

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
 gitweb/gitweb.perl |   61 +++++++++++++++++++++++++++++++++++++++++++---------
 1 files changed, 51 insertions(+), 10 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index e95d16f..4c76032 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -1936,12 +1936,15 @@ sub git_shortlog_body {
 
 sub git_history_body {
 	# Warning: assumes constant type (blob or tree) during history
-	my ($fd, $refs, $hash_base, $ftype, $extra) = @_;
+	my ($revlist, $from, $to, $refs, $hash_base, $ftype, $extra) = @_;
+
+	$from = 0 unless defined $from;
+	$to = $#{$revlist} unless (defined $to && $to <= $#{$revlist});
 
 	print "<table class=\"history\" cellspacing=\"0\">\n";
 	my $alternate = 0;
-	while (my $line = <$fd>) {
-		if ($line !~ m/^([0-9a-fA-F]{40})/) {
+	for (my $i = $from; $i <= $to; $i++) {
+		if ($revlist->[$i] !~ m/^([0-9a-fA-F]{40})/) {
 			next;
 		}
 
@@ -3122,24 +3125,62 @@ sub git_history {
 	if (!%co) {
 		die_error(undef, "Unknown commit object");
 	}
+
 	my $refs = git_get_references();
-	git_header_html();
-	git_print_page_nav('','', $hash_base,$co{'tree'},$hash_base);
-	git_print_header_div('commit', esc_html($co{'title'}), $hash_base);
+	my $limit = sprintf("--max-count=%i", (100 * ($page+1)));
+
 	if (!defined $hash && defined $file_name) {
 		$hash = git_get_hash_by_path($hash_base, $file_name);
 	}
 	if (defined $hash) {
 		$ftype = git_get_type($hash);
 	}
-	git_print_page_path($file_name, $ftype, $hash_base);
 
 	open my $fd, "-|",
-		git_cmd(), "rev-list", "--full-history", $hash_base, "--", $file_name;
+		git_cmd(), "rev-list", $limit, "--full-history", $hash_base, "--", $file_name
+			or die_error(undef, "Open git-rev-list-failed");
+	my @revlist = map { chomp; $_ } <$fd>;
+	close $fd
+		or die_error(undef, "Reading git-rev-list failed");
 
-	git_history_body($fd, $refs, $hash_base, $ftype);
+	my $paging_nav = '';
+	if ($page > 0) {
+		$paging_nav .=
+			$cgi->a({-href => href(action=>"history", hash=>$hash, hash_base=>$hash_base,
+			                       file_name=>$file_name)},
+			        "first");
+		$paging_nav .= " &sdot; " .
+			$cgi->a({-href => href(action=>"history", hash=>$hash, hash_base=>$hash_base,
+			                       file_name=>$file_name, page=>$page-1),
+			         -accesskey => "p", -title => "Alt-p"}, "prev");
+	} else {
+		$paging_nav .= "first";
+		$paging_nav .= " &sdot; prev";
+	}
+	if ($#revlist >= (100 * ($page+1)-1)) {
+		$paging_nav .= " &sdot; " .
+			$cgi->a({-href => href(action=>"history", hash=>$hash, hash_base=>$hash_base,
+			                       file_name=>$file_name, page=>$page+1),
+			         -accesskey => "n", -title => "Alt-n"}, "next");
+	} else {
+		$paging_nav .= " &sdot; next";
+	}
+	my $next_link = '';
+	if ($#revlist >= (100 * ($page+1)-1)) {
+		$next_link =
+			$cgi->a({-href => href(action=>"history", hash=>$hash, hash_base=>$hash_base,
+			                       file_name=>$file_name, page=>$page+1),
+			         -title => "Alt-n"}, "next");
+	}
+
+	git_header_html();
+	git_print_page_nav('history','', $hash_base,$co{'tree'},$hash_base, $paging_nav);
+	git_print_header_div('commit', esc_html($co{'title'}), $hash_base);
+	git_print_page_path($file_name, $ftype, $hash_base);
+
+	git_history_body(\@revlist, ($page * 100), $#revlist,
+	                 $refs, $hash_base, $ftype, $next_link);
 
-	close $fd;
 	git_footer_html();
 }
 
-- 
1.4.2

[PATCH 3/7] gitweb: Use @hist_opts as git-rev-list parameters in git_history

[Jakub Narebski]

Add new global configuration variable @hist_opts, which holds
additional, history specific options (parameters) to git-rev-list
called in git_history subroutine.  Default value is '--full-history',
as it was.

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
 gitweb/gitweb.perl |   18 ++++++++++++++++--
 1 files changed, 16 insertions(+), 2 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 4c76032..2191853 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -176,9 +176,23 @@ # - more costly is '-C' (or '-C', '-M'),
 #   (number of changed files + number of removed files) * (number of new files)
 # - even more costly is '-C', '--find-copies-harder' with cost
 #   (number of files in the original tree) * (number of new files)
-# - one might want to include '-B' option, e.g. '-B', '-M'
+# - one might want to include '-B' option, e.g. have it ('-B', '-M'),
+#   or for example '-l<num>' together with '-M' and perhaps '-C'
 our @diff_opts = ('-M'); # taken from git_commit
 
+# options fo git-rev-list used in git_history
+# - default is '--full-history', which is slowest but works with merges,
+#   and was done to not change the output from previous version when
+#   path limiting was done by piping revisions to git-diff-tree --stdin
+# - less costly is (), i.e. without '--full-history', which of course
+#   changes output and provides _simplified_ history of a file
+# - for files which appeared late in the history less costly is
+#   --full-history, --remove-empty, although it changes output in
+#   the rare case when name vanished the appeared thorough the history;
+#   it improves performance of course only the last page of history
+# - least costly, but changing output, is having --remove-mepty only
+our @hist_opts = ('--full-history');
+
 our $GITWEB_CONFIG = $ENV{'GITWEB_CONFIG'} || "++GITWEB_CONFIG++";
 do $GITWEB_CONFIG if -e $GITWEB_CONFIG;
 
@@ -3137,7 +3151,7 @@ sub git_history {
 	}
 
 	open my $fd, "-|",
-		git_cmd(), "rev-list", $limit, "--full-history", $hash_base, "--", $file_name
+		git_cmd(), "rev-list", $limit, @hist_opts, $hash_base, "--", $file_name
 			or die_error(undef, "Open git-rev-list-failed");
 	my @revlist = map { chomp; $_ } <$fd>;
 	close $fd
-- 
1.4.2

[PATCH 4/7] gitweb: Add parse_rev_list for later use

[Jakub Narebski]

Add parse_rev_list to generate _parsed_ list of revisions, combining
getting the list of revisions, and parsing of individual revisions
into one subroutine.  It is to avoid code like below

	open my $fd, "-|", git_cmd(), "rev-list", $limit, $hash
		or die_error(undef, "Open git-rev-list failed");
	my @revlist = map { chomp; $_ } <$fd>;

	...

	foreach my $commit (@revlist) {
		my %co = parse_commit($commit);

where parse_commit subroutine calls git-rev-list with '--max-count=1'
to parse individual commit.  Using parse_rev_list will avoid
unnecessary forks.

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
 gitweb/gitweb.perl |   29 +++++++++++++++++++++++++++++
 1 files changed, 29 insertions(+), 0 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 2191853..8aeca52 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -1125,6 +1125,35 @@ sub git_get_refs_list {
 	return \@reflist;
 }
 
+# To use only one invocation of git-rev-list, instead of getting
+# the list of revisions and then using git-rev-list per revision
+# to parse individual commits.
+#
+# parse_rev_list parameters are passed to git-rev-list, so they should
+# include at least starting revision; just in case we default to HEAD
+sub parse_rev_list {
+	my @rev_opts = @_;
+	my @revlist;
+
+	@rev_opts = ("HEAD") unless @rev_opts;
+
+	local $/ = "\0";
+	open my $fd, "-|", git_cmd(), "rev-list", "--header", "--parents", @rev_opts
+		or return \@revlist;
+
+	while (my $revinfo = <$fd>) {
+		chomp $revinfo;
+		my @commit_lines = split '\n', $revinfo;
+		my %co = parse_commit(undef, \@commit_lines);
+
+		push @revlist, \%co;
+	}
+
+	close $fd;
+
+	return wantarray ? @revlist : \@revlist;
+}
+
 ## ----------------------------------------------------------------------
 ## filesystem-related functions
 
-- 
1.4.2

[PATCH 5/7] gitweb: Use parse_rev_list in git_shortlog and git_history

[Jakub Narebski]

Use parse_rev_list in git_shortlog and git_history, and modify
git_shortlog_body and git_history_body to accept parse_rev_list
output; in the future we can remove support for older unparsed
revision list from git_shortlog_body and git_history_body.

Other places when we can use parse_rev_list are git_log and git_rss.

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
 gitweb/gitweb.perl |   23 ++++++++++-------------
 1 files changed, 10 insertions(+), 13 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 8aeca52..e665d94 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -1946,7 +1946,7 @@ sub git_shortlog_body {
 		my $commit = $revlist->[$i];
 		#my $ref = defined $refs ? format_ref_marker($refs, $commit) : '';
 		my $ref = format_ref_marker($refs, $commit);
-		my %co = parse_commit($commit);
+		my %co = ref $commit ? %$commit : parse_commit($commit);
 		if ($alternate) {
 			print "<tr class=\"dark\">\n";
 		} else {
@@ -1987,12 +1987,13 @@ sub git_history_body {
 	print "<table class=\"history\" cellspacing=\"0\">\n";
 	my $alternate = 0;
 	for (my $i = $from; $i <= $to; $i++) {
-		if ($revlist->[$i] !~ m/^([0-9a-fA-F]{40})/) {
+		if (ref($revlist->[$i]) ne "HASH" &&
+		    $revlist->[$i] !~ m/^([0-9a-fA-F]{40})/) {
 			next;
 		}
 
 		my $commit = $1;
-		my %co = parse_commit($commit);
+		my %co = ref $commit ? %$commit : parse_commit($commit);
 		if (!%co) {
 			next;
 		}
@@ -3179,12 +3180,9 @@ sub git_history {
 		$ftype = git_get_type($hash);
 	}
 
-	open my $fd, "-|",
-		git_cmd(), "rev-list", $limit, @hist_opts, $hash_base, "--", $file_name
-			or die_error(undef, "Open git-rev-list-failed");
-	my @revlist = map { chomp; $_ } <$fd>;
-	close $fd
-		or die_error(undef, "Reading git-rev-list failed");
+	my @revlist = parse_rev_list($limit, @hist_opts, $hash_base, "--", $file_name)
+		or die_error(undef, "Parsing git-rev-list failed");
+
 
 	my $paging_nav = '';
 	if ($page > 0) {
@@ -3387,10 +3385,9 @@ sub git_shortlog {
 	my $refs = git_get_references();
 
 	my $limit = sprintf("--max-count=%i", (100 * ($page+1)));
-	open my $fd, "-|", git_cmd(), "rev-list", $limit, $hash
-		or die_error(undef, "Open git-rev-list failed");
-	my @revlist = map { chomp; $_ } <$fd>;
-	close $fd;
+	my @revlist = parse_rev_list($limit, $hash)
+		or die_error(undef, "Parsing git-rev-list failed");
+
 
 	my $paging_nav = format_paging_nav('shortlog', $hash, $head, $page, $#revlist);
 	my $next_link = '';
-- 
1.4.2

[PATCH 6/7] gitweb: Assume parsed revision list in git_shortlog_body and git_history_body

[Jakub Narebski]

Assume that git_shortlog and git_history uses parse_rev_list
subroutine, and git_shortlog_body and git_history_body gets parsed
revision list as a parameter.

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
 gitweb/gitweb.perl |   35 ++++++++++++-----------------------
 1 files changed, 12 insertions(+), 23 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index e665d94..be4db08 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -1943,21 +1943,19 @@ sub git_shortlog_body {
 	print "<table class=\"shortlog\" cellspacing=\"0\">\n";
 	my $alternate = 0;
 	for (my $i = $from; $i <= $to; $i++) {
-		my $commit = $revlist->[$i];
-		#my $ref = defined $refs ? format_ref_marker($refs, $commit) : '';
+		my $co = $revlist->[$i];
+		my $commit = $co->{'id'};
 		my $ref = format_ref_marker($refs, $commit);
-		my %co = ref $commit ? %$commit : parse_commit($commit);
 		if ($alternate) {
 			print "<tr class=\"dark\">\n";
 		} else {
 			print "<tr class=\"light\">\n";
 		}
 		$alternate ^= 1;
-		# git_summary() used print "<td><i>$co{'age_string'}</i></td>\n" .
-		print "<td title=\"$co{'age_string_age'}\"><i>$co{'age_string_date'}</i></td>\n" .
-		      "<td><i>" . esc_html(chop_str($co{'author_name'}, 10)) . "</i></td>\n" .
+		print "<td title=\"$co->{'age_string_age'}\"><i>$co->{'age_string_date'}</i></td>\n" .
+		      "<td><i>" . esc_html(chop_str($co->{'author_name'}, 10)) . "</i></td>\n" .
 		      "<td>";
-		print format_subject_html($co{'title'}, $co{'title_short'},
+		print format_subject_html($co->{'title'}, $co->{'title_short'},
 		                          href(action=>"commit", hash=>$commit), $ref);
 		print "</td>\n" .
 		      "<td class=\"link\">" .
@@ -1987,17 +1985,8 @@ sub git_history_body {
 	print "<table class=\"history\" cellspacing=\"0\">\n";
 	my $alternate = 0;
 	for (my $i = $from; $i <= $to; $i++) {
-		if (ref($revlist->[$i]) ne "HASH" &&
-		    $revlist->[$i] !~ m/^([0-9a-fA-F]{40})/) {
-			next;
-		}
-
-		my $commit = $1;
-		my %co = ref $commit ? %$commit : parse_commit($commit);
-		if (!%co) {
-			next;
-		}
-
+		my $co = $revlist->[$i];
+		my $commit = $co->{'id'};
 		my $ref = format_ref_marker($refs, $commit);
 
 		if ($alternate) {
@@ -2006,12 +1995,12 @@ sub git_history_body {
 			print "<tr class=\"light\">\n";
 		}
 		$alternate ^= 1;
-		print "<td title=\"$co{'age_string_age'}\"><i>$co{'age_string_date'}</i></td>\n" .
-		      # shortlog uses      chop_str($co{'author_name'}, 10)
-		      "<td><i>" . esc_html(chop_str($co{'author_name'}, 15, 3)) . "</i></td>\n" .
+		print "<td title=\"$co->{'age_string_age'}\"><i>$co->{'age_string_date'}</i></td>\n" .
+		      # shortlog uses      chop_str($co->{'author_name'}, 10)
+		      "<td><i>" . esc_html(chop_str($co->{'author_name'}, 15, 3)) . "</i></td>\n" .
 		      "<td>";
-		# originally git_history used chop_str($co{'title'}, 50)
-		print format_subject_html($co{'title'}, $co{'title_short'},
+		# originally git_history used chop_str($co->{'title'}, 50)
+		print format_subject_html($co->{'title'}, $co->{'title_short'},
 		                          href(action=>"commit", hash=>$commit), $ref);
 		print "</td>\n" .
 		      "<td class=\"link\">" .
-- 
1.4.2

[PATCH 7/7] gitweb: Set page to 0 if it is not defined, in git_history

[Jakub Narebski]

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
 gitweb/gitweb.perl |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index be4db08..edded74 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -3153,6 +3153,9 @@ sub git_history {
 	if (!defined $hash_base) {
 		$hash_base = git_get_head_hash($project);
 	}
+	if (!defined $page) {
+		$page = 0;
+	}
 	my $ftype;
 	my %co = parse_commit($hash_base);
 	if (!%co) {
-- 
1.4.2

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Linus Torvalds]

On Wed, 6 Sep 2006, Jakub Narebski wrote:
>
> Unfortunately, git-rev-list is broken: 'git rev-list <commit> 
> --full-history --parents -- <filename>' shows all merges in addition
> to what 'git rev-list <commit> --parents -- <filename>' and 
> 'git rev-list <commit> --full-history -- <filename>' shows, see
> "git-rev-list --full-history --parents doesn't respect path limit 
> and shows all merges" thread

If you ask for "--full-history" and "--parents", then pretty much by 
_definition_ you need every single merge, because otherwise your history 
wouldn't be fully connected.

Without that, things like "gitk" and "qgit" wouldn't work.

> So probably those patches should be dropped or put in freezer until
> git-rev-list is corrected.

git-rev-list _is_ correct, and if you want something else, you need to 
either use a different set of flags (like _only_ using "--full-history") 
or ask for a totally new flag (like "--most-history").

So the rule is:

 - using "--full-history" + "--parents" means that you want (surprise 
   surprise) full history with parenthood, which means that you get all 
   the connecting merges too. And since you asked for the _full_ history, 
   that means EVERY SINGLE MERGE.

 - using _just_ "--parents" means that you want a connected history with 
   parenthood information, but since you didn't ask for the _full_ 
   history, it will optimize away the merges that didn't change the file, 
   and only follow the changed side. You still get merges, but now you get 
   only those merges where both (all) sides actually mattered.

 - using _just_ "--full-history" (without asking for parenthood) means 
   that you're not asking for a connected history (since you're not asking 
   for parents), and as such, it will only show individual _commits_ that 
   change the file. That does potentially include merges, but again, it 
   only includes merges that actually _changed_ something.

In other words, "--parents" means a lot more than just "show what the 
parents" were. In particular, it means (and always has meant, apart from 
bugs) that we show the _rewritten_ parents after we've done history 
munging, and that we always output enough commits to actually make sense 
of that history from the result.

So what you are asking for is pretty nonsensical. You ask for parenthood 
info, but then you seem to not want to actually connect the dots. So why 
do you ask for parents in the first place? If you don't want to connect 
the commits to their parents, you shouldn't ask for it.

		Linus

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Jakub Narebski]

Linus Torvalds wrote:

> So the rule is:
> 
>  - using "--full-history" + "--parents" means that you want (surprise 
>    surprise) full history with parenthood, which means that you get all 
>    the connecting merges too. And since you asked for the _full_ history, 
>    that means EVERY SINGLE MERGE.

I just don't quite understand where <pathspec> filtering takes place 
in this case.

Every single merge is for parents to be connected, or what?
 
> So what you are asking for is pretty nonsensical. You ask for parenthood 
> info, but then you seem to not want to actually connect the dots. So why 
> do you ask for parents in the first place? If you don't want to connect 
> the commits to their parents, you shouldn't ask for it.

When I though about it, git_history needs not parents of a commit; from
parsed commit it needs only date, author and title/summary (and of course
commit sha1), so we can skip '--parents' option to git-rev-list, and have
nice _history of a file_, using only one call to git-rev-list to make it.

This means that parse_rev_list has to be changes, and that '--parents'
option must be specified explicitely as argument to parse_rev_list.

Besides [primitive] benchmarking shows that there we gain only a little:
1.53s user+sys vs 2.13s user+sys when run from command line, 
2.8s mean vs 3.6s mean when tested using ApacheBench...
that is _after_ paginating history output.
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Linus Torvalds]

On Wed, 6 Sep 2006, Jakub Narebski wrote:

> Linus Torvalds wrote:
> 
> > So the rule is:
> > 
> >  - using "--full-history" + "--parents" means that you want (surprise 
> >    surprise) full history with parenthood, which means that you get all 
> >    the connecting merges too. And since you asked for the _full_ history, 
> >    that means EVERY SINGLE MERGE.
> 
> I just don't quite understand where <pathspec> filtering takes place 
> in this case.

Well, since you asked for full history, by definition it doesn't take 
place for merges, since you'll be wanting to follow both sides of the 
merge (to see the full history) regardless of whether the parents of that 
merge seem interesting or not.

> Every single merge is for parents to be connected, or what?

Well, "--parents" on its own means that we want a connected graph. It's 
just that if you don't ask for full history, then the connected graph 
result is obviously much smaller.

Think "graphical visualizer", and you'll see what's going on. Do a

	gitk git.c
	gitk --full-history git.c

and see the difference, and you'll understand (gitk already asks for 
"--parents" on its own).

Basically, "--full-history" means that we traverse every parent of a 
merge, whether it looks interesting or not.

> When I though about it, git_history needs not parents of a commit; from
> parsed commit it needs only date, author and title/summary (and of course
> commit sha1), so we can skip '--parents' option to git-rev-list, and have
> nice _history of a file_, using only one call to git-rev-list to make it.

Yes. Once you get rid of "--parents", git-rev-list should indeed do 
exactly what you want (because it no longer tries to keep things 
connected, and thus happily drops uninteresting merges).

Of course, there could well be a bug _there_, since "--full-history" isn't 
used very much (but "git whatchanged" uses it, so it should have gotten 
_some_ testing).

			Linus

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Jakub Narebski]

Linus Torvalds wrote:

>> Every single merge is for parents to be connected, or what?
> 
> Well, "--parents" on its own means that we want a connected graph. It's 
> just that if you don't ask for full history, then the connected graph 
> result is obviously much smaller.

Well, I just didn't realize that --parents gives parents in _simplified_
history, unless --full-history is used. Hence my confusion.

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Linus Torvalds]

On Wed, 6 Sep 2006, Jakub Narebski wrote:
> 
> Well, I just didn't realize that --parents gives parents in _simplified_
> history, unless --full-history is used. Hence my confusion.

Right. That's really the main reason for "--parents" existing in the first 
place. I added it exactly so that "gitk" would work with pathname 
limiting.

If you don't want the simplified history parents, you might as well just 
parse the parents information directly from the commit data yourself 
(although with grafting, there's arguably _some_ reason to have 
git-rev-list do it for you regardless of simplification).

			Linus

[PATCH 8/8] gitweb: Remove --parents from call to git-rev-list in parse_rev_list

[Jakub Narebski]

This option is removed by default, because with --full-history option
(which is by default used in git_history) --parents means full history
with parenthood, which means that we get all the connecting merges
too.  And since we asked for the _full_ history, that means EVERY
SINGLE MERGE.  Even those that do not change given file (or
directory).

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
Benchmarks (7 means patch before, 8 means this patch):
# 1:gitweb/new~n 2:%e 3:%U 4:%s 5:ab-n10_cgi_time[ms] 6:[+/-sd] 7:ab-n10_perl_time[ms] 8:[+/-sd]
7 2.59  1.53 0  2621.073  234.2  2742.230   96.6
8 2.89  1.80 0  3081.722  246.6  3306.196  367.2
8 2.95  1.81 0  2952.253  155.9  3175.441  128.0

 gitweb/gitweb.perl |    9 ++++++++-
 1 files changed, 8 insertions(+), 1 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index edded74..68ddbe6 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -1131,6 +1131,13 @@ # to parse individual commits.
 #
 # parse_rev_list parameters are passed to git-rev-list, so they should
 # include at least starting revision; just in case we default to HEAD
+#
+# if you want in parsed info to have full equivalent of first generating
+# list of interesting revisions, then calling parse_commit on each of revs,
+# i.e. if you want to have full parent info which includes grafts,
+# you have to include '--parents' in the parse_rev_list parameters;
+# it is excluded by default as it changes notion which revs are interesting
+# e.g. '--full-history' with '--parents' include EVERY SINGLE MERGE.
 sub parse_rev_list {
 	my @rev_opts = @_;
 	my @revlist;
@@ -1138,7 +1145,7 @@ sub parse_rev_list {
 	@rev_opts = ("HEAD") unless @rev_opts;
 
 	local $/ = "\0";
-	open my $fd, "-|", git_cmd(), "rev-list", "--header", "--parents", @rev_opts
+	open my $fd, "-|", git_cmd(), "rev-list", "--header", @rev_opts
 		or return \@revlist;
 
 	while (my $revinfo = <$fd>) {
-- 
1.4.2

Re: [PATCH 8/8] gitweb: Remove --parents from call to git-rev-list in parse_rev_list

[Linus Torvalds]

On Wed, 6 Sep 2006, Jakub Narebski wrote:
>
> Benchmarks (7 means patch before, 8 means this patch):

Btw, you should possibly look at cold-cache numbers, and numbers for 
projects that aren't fully packed. They can often be _dramatically_ 
different.

That said, the dramatic change would probably be if there were some way to 
avoid using "--full-history" (rather than "--parents", which doesn't add 
_that_ much overhead), since that "follow all parents" behaviour of 
full-history is usually what really makes a big deal.

But I guess for gitweb, you do want to use --full-history in this case ;(

			Linus

Re: [PATCH 8/8] gitweb: Remove --parents from call to git-rev-list in parse_rev_list

[Jakub Narebski]

Linus Torvalds wrote:

> On Wed, 6 Sep 2006, Jakub Narebski wrote:
>>
>> Benchmarks (7 means patch before, 8 means this patch):
> 
> Btw, you should possibly look at cold-cache numbers, and numbers for 
> projects that aren't fully packed. They can often be _dramatically_ 
> different.

By the way I forgot that the case 8 is for the repository with 1 commit
more, although that shouldn't matter much for paginated output. Still, it
is one commit more unpacked. Benchmark for 7 was also for partially packed
repository.
 
> That said, the dramatic change would probably be if there were some way to 
> avoid using "--full-history" (rather than "--parents", which doesn't add 
> _that_ much overhead), since that "follow all parents" behaviour of 
> full-history is usually what really makes a big deal.
> 
> But I guess for gitweb, you do want to use --full-history in this case ;(

It is now easy with patch 3/7 "Use @hist_opts as git-rev-list parameters in
git_history" to remove '--full-history' from git-rev-list parameters in
git_history subroutine. Or add '--remove-empty' which matters only for the
last page of file/directory history output.

I had some simple benchmark that shown that the earlier version with
filtering via piping git-rev-list to git-diff-tree --stdin -- <filename>
was slightly faster than git-rev-list --full-history -- <filename>
(current version). If I remember correctly of course. And this version can
be easily extended to include renames (but not file to directory changes).

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 8/8] gitweb: Remove --parents from call to git-rev-list in parse_rev_list

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> Linus Torvalds wrote:
>
>> But I guess for gitweb, you do want to use --full-history in this case ;(
>
> It is now easy with patch 3/7 "Use @hist_opts as git-rev-list parameters in
> git_history" to remove '--full-history' from git-rev-list parameters in
> git_history subroutine.

Well, generating not-so-useful output fast is, eh, not-so-useful
anyway, so being able to add or not add to the set of options on
a whim is not so much of value.  The real value lies in deciding
if it is needed (and I think --full-history is needed for gitweb)
and if so coming up with a way to get the same result with
cheaper operations.

Re: [PATCH 8/8] gitweb: Remove --parents from call to git-rev-list in parse_rev_list

[Jakub Narebski]

Jakub Narebski wrote:

> Benchmarks (7 means patch before, 8 means this patch):
> # 1:gitweb/new~n 2:%e 3:%U 4:%s 5:ab-n10_cgi_time[ms] 6:[+/-sd] 7:ab-n10_perl_time[ms] 8:[+/-sd]
> 7 2.59  1.53 0  2621.073  234.2  2742.230   96.6
> 8 2.89  1.80 0  3081.722  246.6  3306.196  367.2
> 8 2.95  1.81 0  2952.253  155.9  3175.441  128.0

Corrected benchmark (on the same state of repository) are

7 2.67  1.60 0  2694.654  275.2  2866.028  168.4
8 2.84  1.86 0  2892.864  263.0  3135.065   68.1

where the benchmarking commands are
$ /usr/bin/time -f "%e %U %s" \
  GATEWAY_INTERFACE="CGI/1.1" HTTP_ACCEPT="*/*" REQUEST_METHOD="GET" \
  QUERY_STRING="p=git.git;a=history;f=gitweb/gitweb.perl" \
  GITWEB_CONFIG="~/git/gitweb/gitweb_config.perl \
  perl -- ~/git/gitweb/gitweb.perl
$ ab -n 10 "http://localhost/cgi-bin/gitweb/gitweb.cgi?p=git.git;a=history;f=gitweb/gitweb.perl"
$ ab -n 10 "http://localhost/perl/gitweb/gitweb.cgi?p=git.git;a=history;f=gitweb/gitweb.perl"

and we get version 7 using
$ git checkout HEAD^ -- gitweb/gitweb.perl
and updating gitweb.cgi in correct place.

So actually removing '--parents' option did make gitweb _slower_ (sic!),
if only slightly.
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> gitweb/gitweb.perl |  180 +++++++++++++++++++++++++++++++++++++++++-----------
>  1 files changed, 141 insertions(+), 39 deletions(-)-
>
> P.S. Is putting diffstat in such a series of patches actually usefull?

Very much -- it shows me that you are not damaging the core but
only touching gitweb.

Re: [PATCH 1/7] gitweb: Make pickaxe search a feature

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> As pickaxe search (selected using undocumented 'pickaxe:' operator in
> search query) is resource consuming, allow to turn it on/off using
> feature meachanism.
>
> Signed-off-by: Jakub Narebski <jnareb@gmail.com>

I do not have a problem against making it configurable.

> +	'pickaxe' => {
> +		'sub' => \&feature_pickaxe,
> +		'override' => 0,
> +		'default' => [0]},
>  );

The patch suggests that it is turned off by default right now; I
have not checked it myself, but is that the case?

Re: [PATCH 1/7] gitweb: Make pickaxe search a feature

[Jakub Narebski]

Junio C Hamano wrote:

> Jakub Narebski <jnareb@gmail.com> writes:
> 
>> As pickaxe search (selected using undocumented 'pickaxe:' operator in
>> search query) is resource consuming, allow to turn it on/off using
>> feature meachanism.
> 
> I do not have a problem against making it configurable.
> 
>> +    'pickaxe' => {
>> +            'sub' => \&feature_pickaxe,
>> +            'override' => 0,
>> +            'default' => [0]},
>>  );
> 
> The patch suggests that it is turned off by default right now; I
> have not checked it myself, but is that the case?

No, it is not. Currently it is turned on, _but_ undocumented.

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 8/8] gitweb: Remove --parents from call to git-rev-list in parse_rev_list

[Jakub Narebski]

By the way, I didn't do benchmarking for _later_ pages. Perhaps gain from
using only one git-rev-list invocation are outweighted for the unnecessary
output and parsing of skipped revisions.

So perhaps this part of series (patches 4, 5, 6, 8) should be skipped for
now... at least until new benchmarks. Unless someone wants to use
git-rev-list for generating list of revisions, and parse_rev_list onlky for
revisions which would be on page; alternatively change the 'p' page
parameter to 'j' jump_to (= <hash>). 
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 1/7] gitweb: Make pickaxe search a feature

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> Junio C Hamano wrote:
>
>> Jakub Narebski <jnareb@gmail.com> writes:
>> 
>>> As pickaxe search (selected using undocumented 'pickaxe:' operator in
>>> search query) is resource consuming, allow to turn it on/off using
>>> feature meachanism.
>> 
>> I do not have a problem against making it configurable.
>> 
>>> +    'pickaxe' => {
>>> +            'sub' => \&feature_pickaxe,
>>> +            'override' => 0,
>>> +            'default' => [0]},
>>>  );
>> 
>> The patch suggests that it is turned off by default right now; I
>> have not checked it myself, but is that the case?
>
> No, it is not. Currently it is turned on, _but_ undocumented.

Then it would be nice to make it documented and keep the default
perhaps?

Re: [PATCH 1/7] gitweb: Make pickaxe search a feature

[Jakub Narebski]

Junio C Hamano wrote:

> Jakub Narebski <jnareb@gmail.com> writes:
> 
>> Junio C Hamano wrote:

>>> The patch suggests that it is turned off by default right now; I
>>> have not checked it myself, but is that the case?
>>
>> No, it is not. Currently it is turned on, _but_ undocumented.
> 
> Then it would be nice to make it documented and keep the default
> perhaps?
 
Keep the default is easy (although I thought that we can turn off expensive
pickaxe because it was undocumented and I suppose not many people used
that). Should I send corrected patch (i.e. making pickaxe search a feature,
but default on and perhaps overridable), or should I send correcting patch
(i.e. make pickaxe search turned on by default patch)?

Documenting gitweb search operators (author:, committer:, pickaxe:) is not:
where to put the documentation?
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Jakub Narebski]

<opublikowany i wysłany>

Jakub Narebski wrote:

> Shortlog:
>  [PATCH 1/7] gitweb: Make pickaxe search a feature
>  [PATCH 2/7] gitweb: Paginate history output
>  [PATCH 3/7] gitweb: Use @hist_opts as git-rev-list parameters
>              in git_history
>  [PATCH 4/7] gitweb: Add parse_rev_list for later use
>  [PATCH 5/7] gitweb: Use parse_rev_list in git_shortlog and git_history
>  [PATCH 6/7] gitweb: Assume parsed revision list in git_shortlog_body
>              and git_history_body
>  [PATCH 7/7] gitweb: Set page to 0 if it is not defined, in git_history

Should I resend corrected patch 1 (Make pickaxe search a feature; but
default to on), and patches 2 and 7 as one patch (Paginate history output)?

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> Jakub Narebski wrote:
>
>> Shortlog:
>>  [PATCH 1/7] gitweb: Make pickaxe search a feature
>>  [PATCH 2/7] gitweb: Paginate history output
>>  [PATCH 3/7] gitweb: Use @hist_opts as git-rev-list parameters
>>              in git_history
>>  [PATCH 4/7] gitweb: Add parse_rev_list for later use
>>  [PATCH 5/7] gitweb: Use parse_rev_list in git_shortlog and git_history
>>  [PATCH 6/7] gitweb: Assume parsed revision list in git_shortlog_body
>>              and git_history_body
>>  [PATCH 7/7] gitweb: Set page to 0 if it is not defined, in git_history
>
> Should I resend corrected patch 1 (Make pickaxe search a feature; but
> default to on), and patches 2 and 7 as one patch (Paginate history output)?

I looked at and understood 1 and 2+7, although I cannot claim I
looked at 2+7 deeply enough; cursory look told me they should be
Ok.  So is 3, but I suspect gitweb without --full-history might
surprise some users.

I do not know about 4, 5 and 6.  I didn't look at them at all
the first time you sent them out, since I got an impression that
you did not understand how git-rev-list was supposed to work
when you did them.

Now Linus explained it to you, I suspect they would probably
need to be rethought?

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Jakub Narebski]

Junio C Hamano wrote:

> Jakub Narebski <jnareb@gmail.com> writes:
> 
>> Jakub Narebski wrote:
>>
>>> Shortlog:
>>>  [PATCH 1/7] gitweb: Make pickaxe search a feature
>>>  [PATCH 2/7] gitweb: Paginate history output
>>>  [PATCH 3/7] gitweb: Use @hist_opts as git-rev-list parameters
>>>              in git_history
>>>  [PATCH 4/7] gitweb: Add parse_rev_list for later use
>>>  [PATCH 5/7] gitweb: Use parse_rev_list in git_shortlog and git_history
>>>  [PATCH 6/7] gitweb: Assume parsed revision list in git_shortlog_body
>>>              and git_history_body
>>>  [PATCH 7/7] gitweb: Set page to 0 if it is not defined, in git_history

> I do not know about 4, 5 and 6.  I didn't look at them at all
> the first time you sent them out, since I got an impression that
> you did not understand how git-rev-list was supposed to work
> when you did them.
> 
> Now Linus explained it to you, I suspect they would probably
> need to be rethought?

Well, first they don't offer that much of speed improvement even for the
first page of output. And probably would be slower than current
implementation for the next-to-last, or the last page. So yes, patches 4-6
are to be rethought, if not dropped at all.   

By the way, what do you all do with the "failed experiments", to have them
saved somewhere, but to not make trouble for normal operations?
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 0/7] gitweb: Trying to improve history view speed

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> By the way, what do you all do with the "failed experiments", to have them
> saved somewhere, but to not make trouble for normal operations?

I usually keep them under .git/refs/tags/hold/.  Yesterday (as I
said in another thread) I dropped the 64-bit packfile index
topic I had in jc/pack-toc topic from "pu" by:

	git tag hold/jc/pack-toc jc/pack-toc
	git branch -D jc/pack-toc

to shelve it and kill it.

In theory, I should occasionally come back to them and see if
they are worth keeping, but in practice they just keep piling up
X-<.  I should find time to clean them up.