{"thread":{"id":"40728","subject":"[PATCH] git-svn: improve rebase/mkdirs performance","startedAt":"2015-11-05T10:26:15Z","lastAt":"2015-11-10T01:46:58Z","messageCount":2,"participants":["Dair Grant","Eric Wong"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"272953","messageId":"1446719175-9860-1-git-send-email-dair@feralinteractive.com","threadId":"40728","inReplyTo":null,"subject":"[PATCH] git-svn: improve rebase/mkdirs performance","fromName":"Dair Grant","fromEmail":"dair@feralinteractive.com","sentAt":"2015-11-05T10:26:15Z","receivedAt":"2015-11-05T10:26:15Z","isPatch":true,"sender":{"key":"dair@feralinteractive.com","avatar":null},"body":"Processing empty_dir directives becomes extremely slow for svn\nrepositories with a large enough history.\n\nThis is due to using a single hash to store the list of empty\ndirectories, with the expensive step being purging items from\nthat hash using grep+delete.\n\nStoring directories in a hash of hashes improves the performance\nof this purge step and removes a potentially lengthy delay after\nevery rebase/mkdirs command.\n\nThe svn repository with this behaviour has 110K commits with\nunhandled.log containing 170K empty_dir directives.\n\nThis takes 10 minutes to process when using a single hash, vs\n3 seconds with a hash of hashes.\n\nSigned-off-by: Dair Grant <dair@feralinteractive.com>\n---\n perl/Git/SVN.pm | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 74 insertions(+), 8 deletions(-)\n\ndiff --git a/perl/Git/SVN.pm b/perl/Git/SVN.pm\nindex 152fb7e..ebbdd37 100644\n--- a/perl/Git/SVN.pm\n+++ b/perl/Git/SVN.pm\n@@ -1211,20 +1211,85 @@ sub do_fetch {\n sub mkemptydirs {\n \tmy ($self, $r) = @_;\n \n+\t# add/remove/collect a paths table\n+\t#\n+\t# Paths are split into a tree of nodes, stored as a hash of hashes.\n+\t#\n+\t# Each node contains a 'path' entry for the path (if any) associated with\n+\t# that node and a 'children' entry for any nodes under that location.\n+\t#\n+\t# Removing a path requires a hash lookup for each component then dropping\n+\t# that node (and anything under it), which is substantially faster than a\n+\t# grep slice into a single hash of paths for large numbers of paths.\n+\t#\n+\t# For a large (200K) number of empty_dir directives this reduces scanning\n+\t# time to 3 seconds vs 10 minutes for grep+delete on a single hash of paths.\n+\tsub add_path {\n+\t\tmy ($paths_table, $path) = @_;\n+\t\tmy $node_ref = undef;\n+\n+\t\tforeach my $x (split('/', $path)) {\n+\t\t\tif (!exists($paths_table->{$x})) {\n+\t\t\t\t$paths_table->{$x}             = {};\n+\t\t\t\t$paths_table->{$x}{\"children\"} = {};\n+\t\t\t}\n+\n+\t\t\t$node_ref    = $paths_table->{$x};\n+\t\t\t$paths_table = $paths_table->{$x}{\"children\"};\n+\t\t}\n+\n+\t\t$node_ref->{\"path\"} = $path;\n+\t}\n+\n+\tsub remove_path {\n+\t\tmy ($paths_table, $path) = @_;\n+\t\tmy $nodes_ref = undef;\n+\t\tmy $node_name = undef;\n+\n+\t\tforeach my $x (split('/', $path)) {\n+\t\t\tif (!exists($paths_table->{$x})) {\n+\t\t\t\treturn;\n+\t\t\t}\n+\n+\t\t\t$nodes_ref = $paths_table;\n+\t\t\t$node_name = $x;\n+\n+\t\t\t$paths_table = $paths_table->{$x}{\"children\"};\n+\t\t}\n+\t\n+\t\tdelete($nodes_ref->{$node_name});\n+\t}\n+\n+\tsub collect_paths {\n+\t\tmy ($paths_table, $paths_ref) = @_;\n+\n+\t\tforeach my $v (values %$paths_table) {\n+\t\t\tmy $p = $v->{\"path\"};\n+\t\t\tmy $c = $v->{\"children\"};\n+\n+\t\t\tcollect_paths($c, $paths_ref);\n+\t\t\t\n+\t\t\tif (defined($p)) {\n+\t\t\t\tpush(@$paths_ref, $p);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n \tsub scan {\n-\t\tmy ($r, $empty_dirs, $line) = @_;\n+\t\tmy ($r, $paths_table, $line) = @_;\n \t\tif (defined $r && $line =~ /^r(\\d+)$/) {\n \t\t\treturn 0 if $1 > $r;\n \t\t} elsif ($line =~ /^  \\+empty_dir: (.+)$/) {\n-\t\t\t$empty_dirs->{$1} = 1;\n+\t\t\tadd_path($paths_table, $1);\n \t\t} elsif ($line =~ /^  \\-empty_dir: (.+)$/) {\n-\t\t\tmy @d = grep {m[^\\Q$1\\E(/|$)]} (keys %$empty_dirs);\n-\t\t\tdelete @$empty_dirs{@d};\n+\t\t\tremove_path($paths_table, $1);\n \t\t}\n \t\t1; # continue\n \t};\n \n-\tmy %empty_dirs = ();\n+\tmy @empty_dirs  = ();\n+\tmy %paths_table = ();\n+\n \tmy $gz_file = \"$self->{dir}/unhandled.log.gz\";\n \tif (-f $gz_file) {\n \t\tif (!can_compress()) {\n@@ -1235,7 +1300,7 @@ sub mkemptydirs {\n \t\t\t\tdie \"Unable to open $gz_file: $!\\n\";\n \t\t\tmy $line;\n \t\t\twhile ($gz->gzreadline($line) > 0) {\n-\t\t\t\tscan($r, \\%empty_dirs, $line) or last;\n+\t\t\t\tscan($r, \\%paths_table, $line) or last;\n \t\t\t}\n \t\t\t$gz->gzclose;\n \t\t}\n@@ -1244,13 +1309,14 @@ sub mkemptydirs {\n \tif (open my $fh, '<', \"$self->{dir}/unhandled.log\") {\n \t\tbinmode $fh or croak \"binmode: $!\";\n \t\twhile (<$fh>) {\n-\t\t\tscan($r, \\%empty_dirs, $_) or last;\n+\t\t\tscan($r, \\%paths_table, $_) or last;\n \t\t}\n \t\tclose $fh;\n \t}\n \n+\tcollect_paths(\\%paths_table, \\@empty_dirs);\n \tmy $strip = qr/\\A\\Q@{[$self->path]}\\E(?:\\/|$)/;\n-\tforeach my $d (sort keys %empty_dirs) {\n+\tforeach my $d (sort @empty_dirs) {\n \t\t$d = uri_decode($d);\n \t\t$d =~ s/$strip//;\n \t\tnext unless length($d);\n-- \n2.6.2\n"},{"id":"273116","messageId":"20151110014658.GA17298@dcvr.yhbt.net","threadId":"40728","inReplyTo":"1446719175-9860-1-git-send-email-dair@feralinteractive.com","subject":"Re: [PATCH] git-svn: improve rebase/mkdirs performance","fromName":"Eric Wong","fromEmail":"normalperson@yhbt.net","sentAt":"2015-11-10T01:46:58Z","receivedAt":"2015-11-10T01:46:58Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Dair Grant <dair@feralinteractive.com> wrote:\n> This takes 10 minutes to process when using a single hash, vs\n> 3 seconds with a hash of hashes.\n> \n> Signed-off-by: Dair Grant <dair@feralinteractive.com>\n\nThanks!  I've made some minor edits, will push the following out\nto git://bogomips.org/git-svn.git for Junio to pull in a day\nor so.\n\nBtw, feel free to Cc: me on any git-(svn|Perl)-related stuff.  Likewise,\nCc: any regular contributor/maintainer on any subsystem you work on.  We\nmight not always answer, but appreciate being Cc:-ed anyways just in\ncase.\n\n-------------------------- 8< ---------------------------\nFrom: Dair Grant <dair@feralinteractive.com>\nSubject: [PATCH] git-svn: improve rebase/mkdirs performance\n\nProcessing empty_dir directives becomes extremely slow for svn\nrepositories with a large enough history.\n\nThis is due to using a single hash to store the list of empty\ndirectories, with the expensive step being purging items from\nthat hash using grep+delete.\n\nStoring directories in a hash of hashes improves the performance\nof this purge step and removes a potentially lengthy delay after\nevery rebase/mkdirs command.\n\nThe svn repository with this behaviour has 110K commits with\nunhandled.log containing 170K empty_dir directives.\n\nThis takes 10 minutes to process when using a single hash, vs\n3 seconds with a hash of hashes.\n\n[ew: wrap comments, shorten initializations, avoid unnecessary spaces]\n\nSigned-off-by: Dair Grant <dair@feralinteractive.com>\nSigned-off-by: Eric Wong <normalperson@yhbt.net>\n---\n perl/Git/SVN.pm | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 76 insertions(+), 8 deletions(-)\n\ndiff --git a/perl/Git/SVN.pm b/perl/Git/SVN.pm\nindex 152fb7e..b2c14e2 100644\n--- a/perl/Git/SVN.pm\n+++ b/perl/Git/SVN.pm\n@@ -1211,20 +1211,87 @@ sub do_fetch {\n sub mkemptydirs {\n \tmy ($self, $r) = @_;\n \n+\t# add/remove/collect a paths table\n+\t#\n+\t# Paths are split into a tree of nodes, stored as a hash of hashes.\n+\t#\n+\t# Each node contains a 'path' entry for the path (if any) associated\n+\t# with that node and a 'children' entry for any nodes under that\n+\t# location.\n+\t#\n+\t# Removing a path requires a hash lookup for each component then\n+\t# dropping that node (and anything under it), which is substantially\n+\t# faster than a grep slice into a single hash of paths for large\n+\t# numbers of paths.\n+\t#\n+\t# For a large (200K) number of empty_dir directives this reduces\n+\t# scanning time to 3 seconds vs 10 minutes for grep+delete on a single\n+\t# hash of paths.\n+\tsub add_path {\n+\t\tmy ($paths_table, $path) = @_;\n+\t\tmy $node_ref;\n+\n+\t\tforeach my $x (split('/', $path)) {\n+\t\t\tif (!exists($paths_table->{$x})) {\n+\t\t\t\t$paths_table->{$x} = { children => {} };\n+\t\t\t}\n+\n+\t\t\t$node_ref = $paths_table->{$x};\n+\t\t\t$paths_table = $paths_table->{$x}->{children};\n+\t\t}\n+\n+\t\t$node_ref->{path} = $path;\n+\t}\n+\n+\tsub remove_path {\n+\t\tmy ($paths_table, $path) = @_;\n+\t\tmy $nodes_ref;\n+\t\tmy $node_name;\n+\n+\t\tforeach my $x (split('/', $path)) {\n+\t\t\tif (!exists($paths_table->{$x})) {\n+\t\t\t\treturn;\n+\t\t\t}\n+\n+\t\t\t$nodes_ref = $paths_table;\n+\t\t\t$node_name = $x;\n+\n+\t\t\t$paths_table = $paths_table->{$x}->{children};\n+\t\t}\n+\n+\t\tdelete($nodes_ref->{$node_name});\n+\t}\n+\n+\tsub collect_paths {\n+\t\tmy ($paths_table, $paths_ref) = @_;\n+\n+\t\tforeach my $v (values %$paths_table) {\n+\t\t\tmy $p = $v->{path};\n+\t\t\tmy $c = $v->{children};\n+\n+\t\t\tcollect_paths($c, $paths_ref);\n+\n+\t\t\tif (defined($p)) {\n+\t\t\t\tpush(@$paths_ref, $p);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n \tsub scan {\n-\t\tmy ($r, $empty_dirs, $line) = @_;\n+\t\tmy ($r, $paths_table, $line) = @_;\n \t\tif (defined $r && $line =~ /^r(\\d+)$/) {\n \t\t\treturn 0 if $1 > $r;\n \t\t} elsif ($line =~ /^  \\+empty_dir: (.+)$/) {\n-\t\t\t$empty_dirs->{$1} = 1;\n+\t\t\tadd_path($paths_table, $1);\n \t\t} elsif ($line =~ /^  \\-empty_dir: (.+)$/) {\n-\t\t\tmy @d = grep {m[^\\Q$1\\E(/|$)]} (keys %$empty_dirs);\n-\t\t\tdelete @$empty_dirs{@d};\n+\t\t\tremove_path($paths_table, $1);\n \t\t}\n \t\t1; # continue\n \t};\n \n-\tmy %empty_dirs = ();\n+\tmy @empty_dirs;\n+\tmy %paths_table;\n+\n \tmy $gz_file = \"$self->{dir}/unhandled.log.gz\";\n \tif (-f $gz_file) {\n \t\tif (!can_compress()) {\n@@ -1235,7 +1302,7 @@ sub mkemptydirs {\n \t\t\t\tdie \"Unable to open $gz_file: $!\\n\";\n \t\t\tmy $line;\n \t\t\twhile ($gz->gzreadline($line) > 0) {\n-\t\t\t\tscan($r, \\%empty_dirs, $line) or last;\n+\t\t\t\tscan($r, \\%paths_table, $line) or last;\n \t\t\t}\n \t\t\t$gz->gzclose;\n \t\t}\n@@ -1244,13 +1311,14 @@ sub mkemptydirs {\n \tif (open my $fh, '<', \"$self->{dir}/unhandled.log\") {\n \t\tbinmode $fh or croak \"binmode: $!\";\n \t\twhile (<$fh>) {\n-\t\t\tscan($r, \\%empty_dirs, $_) or last;\n+\t\t\tscan($r, \\%paths_table, $_) or last;\n \t\t}\n \t\tclose $fh;\n \t}\n \n+\tcollect_paths(\\%paths_table, \\@empty_dirs);\n \tmy $strip = qr/\\A\\Q@{[$self->path]}\\E(?:\\/|$)/;\n-\tforeach my $d (sort keys %empty_dirs) {\n+\tforeach my $d (sort @empty_dirs) {\n \t\t$d = uri_decode($d);\n \t\t$d =~ s/$strip//;\n \t\tnext unless length($d);\n-- \nEW\n"}]}