From: Zygo Blaxell <zblaxell@waya.furryterror.org>
Date: Sat, 9 Jan 2010 01:51:45 +0000 (-0500)
Subject: Merge branch 'performance'
X-Git-Tag: dm6-0.20100514~31
X-Git-Url: http://git.hungrycats.org/cgi-bin/gitweb.cgi?p=dupemerge;a=commitdiff_plain;h=776aeabce8add0b31e16bb91b13e6cb9fcee682a;hp=-c

Merge branch 'performance'

Conflicts:
	faster-dupemerge
---

776aeabce8add0b31e16bb91b13e6cb9fcee682a
diff --combined faster-dupemerge
index 0b43a3c,6223ab0..d35f591
--- a/faster-dupemerge
+++ b/faster-dupemerge
@@@ -4,7 -4,7 +4,7 @@@ use Fcntl qw(:DEFAULT :flock)
  use File::Compare;
  use File::Temp;
  
 -# Copyright (C) 2003-2006 Zygo Blaxell <zblaxell@feedme.hungrycats.org>
 +# Copyright (C) 2003-2009 Zygo Blaxell <faster-dupemerge@mailtoo.hungrycats.org>
  
  # This program is free software; you can redistribute it and/or modify
  # it under the terms of the GNU General Public License as published by
@@@ -238,7 -238,7 +238,7 @@@ my @find_command = ('find', @directorie
  my $printf_string = '%s ' .
  	($collapse_access    ? '0 0 0 ' : '%U %G %m ') .
  	($collapse_timestamp ? '0 '     : '%T@ ') .
- 	'%i %p\0';
+ 	'%D:%i %p\0';
  
  push(@find_command, '!', '-empty') unless $collapse_zero;
  push(@find_command, '-printf', $printf_string);
@@@ -305,14 -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);
@@@ -333,9 -333,8 +333,9 @@@
  		if ($ok) {
  			print STDERR "\t\tDigest is $digest\n" if $debug;
  
 -			my $incumbent = $hash_to_inode{$digest};
 -			if (defined($incumbent)) {
 +			my $incumbent_list = ($hash_to_inode{$digest} ||= []);
 +			my $incumbent_matched = 0;
 +			for my $incumbent (@$incumbent_list) {
  				print STDERR "\t\tInodes $incumbent and $candidate have same hash\n" if $debug;
  
  				my $finished = 0;
@@@ -343,9 -342,9 +343,9 @@@
  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 $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;
  
  incumbent_file:
@@@ -412,7 -411,6 +412,7 @@@ candidate_file
  										print STDERR "$quoted_incumbent_file and $quoted_candidate_file have same hash but do not compare equal!\n" unless $skip_hashes;
  									} else {
  										$identical = 1;
 +										$incumbent_matched = 1;
  									}
  									$compare_count++;
  									$compare_bytes += $incumbent_size;
@@@ -443,6 -441,12 +443,12 @@@
  									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;
@@@ -489,9 -493,13 +495,9 @@@
  									# My random number generator chooses the incumbent's size.
  
  									if ($link_done) {
 -										# Since we're in a dry run, the filesystem doesn't change.
 -										# Our notion of what the filesystem should look like should not change either.
  										delete $inode_to_file_name{$to_inode}->{$to_file};
 -										unless ($dry_run) {
 -											$inode_to_file_name{$from_inode}->{$to_file} = undef;
 -											$hash_to_inode{$digest} = $from_inode;
 -										}
 +										$inode_to_file_name{$from_inode}->{$to_file} = undef;
 +										$hash_to_inode{$digest} = [ $from_inode ];
  
  										$hard_links++;
  										if ($to_nlink == 1) {
@@@ -519,10 -527,9 +525,10 @@@
  					}
  					$finished = 1;
  				}
 -			} else {
 +			}
 +			unless ($incumbent_matched) {
  				print STDERR "\t\tNew hash entered\n" if $debug;
 -				$hash_to_inode{$digest} = $candidate;
 +				push(@$incumbent_list, $candidate);
  			}
  		} else {
  			warn "No digests found for inode $candidate\n";
@@@ -537,7 -544,7 +543,7 @@@ end_merge
  }
  
  while (<FIND>) {
- 	my ($weak_key, $inode, $name) = m/^(\d+ \d+ \d+ \d+ -?[\d.]+) (\d+) (.+)\0$/so;
 -	my ($weak_key, $inode, $name) = m/^(\d+ \d+ \d+ \d+ -?\d+) (\d+:\d+) (.+)\0$/so;
++	my ($weak_key, $inode, $name) = m/^(\d+ \d+ \d+ \d+ -?[\d.]+) (\d+:\d+) (.+)\0$/so;
  	die "read error: $!\nLast input line was '$_'" unless defined($name);
  
  	print STDERR "weak_key=$weak_key inode=$inode name=$name\n" if $debug;