dupemerge: maybe improve seek performance by sorting perl hashes

[dupemerge] / faster-dupemerge

diff --git a/faster-dupemerge b/faster-dupemerge
index 6371fd037747c419cde6efce2c2a33e8b6788d6a..6223ab0adc2d7cacb4dee7e7c4f4e71a2aa3a1d4 100755 (executable)
--- a/faster-dupemerge
+++ b/faster-dupemerge
@@ -305,14 +305,14 @@ sub merge_files {
        }
 
        print STDERR "Merging...\n" if $debug;
-       foreach my $candidate (@candidate_list) {
+       foreach my $candidate (sort @candidate_list) {
                print STDERR "\tDigesting candidate $candidate\n" if $debug;
                my $ok = 0;
                my $digest;
 
 hash_file:
 
-               foreach my $filename (keys(%{$inode_to_file_name{$candidate}})) {
+               foreach my $filename (sort keys(%{$inode_to_file_name{$candidate}})) {
                        print STDERR "\t\tDigesting file $filename\n" if $debug;
                        if ((-l $filename) || ! -f _) {
                                warn "Bogon file " . tick_quote($filename);
@@ -342,8 +342,8 @@ hash_file:
 link_start:
 
                                until ($finished) {
-                                       my @incumbent_names = keys(%{$inode_to_file_name{$incumbent}});
-                                       my @candidate_names = keys(%{$inode_to_file_name{$candidate}});
+                                       my @incumbent_names = sort keys(%{$inode_to_file_name{$incumbent}});
+                                       my @candidate_names = sort keys(%{$inode_to_file_name{$candidate}});
                                        print STDERR "\t\tLinks to $incumbent:",   join("\n\t\t\t", '', @incumbent_names),   "\n" if $debug;
                                        print STDERR "\t\tLinks to $candidate:", join("\n\t\t\t", '', @candidate_names), "\n" if $debug;
 
@@ -441,6 +441,12 @@ candidate_file:
                                                                        my $link_done = 0;
 
                                                                        my ($from_file, $to_file, $from_inode, $to_inode, $from_nlink, $to_nlink);
+
+                                                                       # If the candidate has more links than incumbent, replace incumbent with candidate.
+                                                                       # If the incumbent has more links than candidate, replace candidate with incumbent.
+                                                                       # If the link counts are equal, we saw incumbent first, so keep the incumbent.
+                                                                       # "We saw incumbent first" is significant because we explicitly sort the inodes.
+                                                                       # Thank Johannes Niess for this idea.
                                                                        if ($candidate_nlink > $incumbent_nlink) {
                                                                                $from_file = $candidate_file;
                                                                                $to_file = $incumbent_file;