Patrick Useldinger a écrit : Great idea. You have 100.000 files in an average filesystem. If you compare each couple, this gives you 100.000 * (100.000-1) / 2 combinations, so about 5.000.000.000 file comparaisons, or 10.000.000.000 file read. As example, the first file only will have to be compared do 99.999 others... Instead, the md5sum stuff reads all the files (indeed) but only once, leading to 100.000 file read. About 100.000 times more performant that your proposal. The actual file comparison is only a confirmation that the files are indeed exactly the same, and not only sharing the same md5sum by chance (very unlikely), so will be done more than probably on files that HAVE the same content. No waste of time then, because it is the first time the two involved files will be actually compared. You don't wish to flag as identical files the ones that are just sharing the same md5sum and file length, I guess ? Doing so would lead to a M$t-like system: something that works properly sometimes, and has strange behaviour in some unpredictable, unidentified circumstances, and even sometimes a non causal behaviour. Do your choice. For very small "filesystems" (~10 files), your algorithm might be more efficient, depending on the file content (your comparaison might indeed not read the file up to the end if properly implemented), but computer science learns us that an algorithm having a lower computational complexity <http://en.wikipedia.org/wiki/Computational_complexity_theory> is always the good choice in long-term. Yours, -- Brent Frère Private e-mail: Brent(a)BFrere.net Postal address: 5, rue de Mamer L-8280 Kehlen Grand-Duchy of Luxembourg European Union Mobile: +352-021/29.05.98 Fax: +352-26.30.05.96 Home: +352-307.341 URL: http://BFrere.net If you have problem with my digital signature, please install the appropriate authority certificate by browsing https://www.cacert.org/certs/root.crt.

On a more constructive level, I have written a first version of the program. It's only slightly optimised but appears to be quite fast already. It will also print stats at the end which show the potential gain as well as the number of bytes read vs. the total number of bytes in the potentially identical files (i.e. having the same length). Maybe it's clearer now what my intention was. You can find it at: http://www.homepages.lu/pu/finddups.txt (the webserver at vo would not serve finddups.py). Everybody, please feel free to try it and to give me your feedback. Of course, I would not recommend running it on a production machine yet, of course. Thanks.

Brent Frère wrote: OK, I've done it, as well as added a few optimisations - please have a look if it's OK like that. But isn't refering to the GPL enough, as I did it initially? When I run the program over my disk which has a large number of duplicates (especially on the windows partition), the head is spinning quite heavily. I've increased the size of blocks it reads to keep the movements down, but it's still impressive. Maybe calculating an MD5 would indeed speed up, i.e. have more reads but less head movement? That is provided that files are more or less sequentially on a disk. Maybe I'll make it an option, just to compare. -pu

Patrick Useldinger a écrit : To optimise the head movements, you must drop the abstraction level of the filesystem: you consider that it is implemented on a hard disk... In this case, it would be efficient to process the files in the order of physical block allocation... Not easy, and file-system dependant... Do we really need this ? To check a freshly brewed CD, I usually run this: find /media/cdrom -type f -exec tail -1c {} \; > /dev/null && eject cdrom It's incredibly efficient, even on slow CD readers, compared to a full read. But it cause also some head movements... If the CD is ejected, it is OK. -- Brent Frère Private e-mail: Brent(a)BFrere.net Postal address: 5, rue de Mamer L-8280 Kehlen Grand-Duchy of Luxembourg European Union Mobile: +352-021/29.05.98 Fax: +352-26.30.05.96 Home: +352-307.341 URL: http://BFrere.net If you have problem with my digital signature, please install the appropriate authority certificate by browsing https://www.cacert.org/certs/root.crt.

Patrick Useldinger a écrit : Shame on me: I don't know this strange language... Other implementation (less performant): http://search.cpan.org/src/ANDK/Perl-Repository-APC-1.132/eg/trimtrees.pl I think the head movement problem might be solved by first building a list of file length (the find command processes the files on a directory by directory basis, so very efficient in this case), before considering computation of md5sum for files matching in size... I like your soft. I'll try to find some time to learn basics of Python, as I had to work already on projects partially written in perl. -- Brent Frère Private e-mail: Brent(a)BFrere.net Postal address: 5, rue de Mamer L-8280 Kehlen Grand-Duchy of Luxembourg European Union Mobile: +352-021/29.05.98 Fax: +352-26.30.05.96 Home: +352-307.341 URL: http://BFrere.net If you have problem with my digital signature, please install the appropriate authority certificate by browsing https://www.cacert.org/certs/root.crt.

Patrick Useldinger a écrit : Sorry about that. Just my style. Not sarcastic at all. I even think we go in an interesting and constructive direction (big kiss :-) ). I even need this for a customer project (the one that is described in page 20 of the February LuxBox issue) I didn't noticed that indeed. However, my need is general, and I might have several files of EXACTLY the same size (typically, several Oracle datafiles of 2GB), so if I put in the same set files having the same size, it will be very inefficient. The trick of the first kB is a good idea in this case. I'm also interested in smaller files... I know you don't really care, but think about a storage of icons. Hundred of thousands of files smaller than 1kB. Somebody renames (stupidely) the folder name from 'icon' to 'icons'. Without this tool, my rsync will spend the night copying files in a newly created directory, even if they are already there... So that's why your tool looks interesting to me, espectially integrated with RSYNC. You have as hypothesis that the amount of files of the same size is low... What about filesystems containing huge amount of same size files ? Example: huge backups splitted in 700 MB slices, or storage of floppy images (all 1.44 MB in size) ? What's right in your thoughs is that indeed we have a very cheap info for each file, which is the size. It should be used indeed before computing the md5sum. You also take as hypothesis that you should have enough ram to store 1kB per file... I worked in embedded environments, and I think in this case as well as in PDAs or cell-phones, it should be avoided. That's why I proposed to just read the first kB and keep in memory the md5sum. But you obviously dislike md5sum... :-) Do you think the cmp command reads the files up to the end, even if they have unequal length or a difference at the beginning ??? Ok. But I wouldn't be surprised to see such things in M$ code... :-) I though about the first or last kB. Unfortunately, it exist files having the same beginning (think about zip files containing about the same content: the beginning is likely to contain the list of contained files, so is likely to be the same. Think about CD iso images: the first kB is likely to be the same... I have less examples with last kB, but CD or floppies images are highly likely to share the same content. So I think taking the kB closest to the middle of the file is a good idea, and the entire file content if the file is less than 1kB in length. Let's call the md5sum of this block the 'signature' of the file. So, my proposal is: Make a list of filesizes. Drop the one that have unique length. For each sets of equal sizes, If the set has cardinality of 2, do a performant cmp (a one that stops as soon as the files differs) Otherwise, compute the list of signatures. For each identical signatures, do a progressive multi-file compare, as you described above. If the comparaison doesn't match any other file of the set, drop the file. If the comparaison reaches the end of the files without differences, all the files of the set are identical. If there are differences, but at least two files matches in each different set, keep comparing the first set and add the second to the nearest for loop. (may be improved) roF roF Yours, -- Brent Frère Private e-mail: Brent(a)BFrere.net Postal address: 5, rue de Mamer L-8280 Kehlen Grand-Duchy of Luxembourg European Union Mobile: +352-021/29.05.98 Fax: +352-26.30.05.96 Home: +352-307.341 URL: http://BFrere.net If you have problem with my digital signature, please install the appropriate authority certificate by browsing https://www.cacert.org/certs/root.crt.

Patrick Useldinger wrote: When a filesystem is periodically _replicated_ (not actually _synchronised_ despide RSYNC name might suggest) with a previous version of it, the efficiency of RSYNC is fantastic: accelerations of up to 2000 times compared to a full stupid copy. Even if parts of a file have been changed, even if some data have been added at the end, even if some data have been added _at the beginning_ of the file, the RSYNC tool takes the existing data already available at the destination side to save unecessary bandwidth in the replication process (a kind of 'refreshment' of the files instead of plain copying). But there is a lack in RSYNC: if a file is renamed, its entire content will be retransmitted to the destination at the next RSYNC replication, and not just a file renaming, because it appears that RSYNC is not able to detect that the file is actually the same, just having a different filename. Worst even is the case of folders: if you rename a folder, all the files and subfolders will have to be fully copied during next replication, because RSYNC will not notice the change. It takes the entire tree structure as new, and will delete the old one on the target. What I wish is to be able to detect this condition, by detecting files and folders that dissepeared since last replication, and files and folders that appeared since lase replication, and so instead of deleting the files and folders no more present on the source side, try to move it or rename it the the appropriate location, before running the genuine RSYNC protocol, saving large amount of bandwidth in this case. I hope it is clear. The point here is that I don't want to have to transmit the entire file content on the network to perform the actual comparaison: the idea is to save bandwidth. So, I can consider files as identical if they share the same md5sum. I have no reason to do better: RSYNC does the job very well. If a file that appeared on the source has the same checksum as a file on the target that dissepeared on the source, I'll just rename it to the new candidate file name. If a folder, newly appeared on the source, contains lots of such files (having the same checksum has files belonging to a folder on the target side that dissepeared in the source, I'll rename the folder... You see the point ? -- Brent Frère Private e-mail: Brent(a)BFrere.net Postal address: 5, rue de Mamer L-8280 Kehlen Grand-Duchy of Luxembourg European Union Mobile: +352-021/29.05.98 Fax: +352-26.30.05.96 Home: +352-307.341 URL: http://BFrere.net This e-mail signature can be checked if you have the CaCERT certificate installed. Check http://www.CaCERT.org for details.

Patrick Useldinger a écrit : Maybe a (non patentable) idea here: what about computing the md5sum on the first KB of each file ? Roughly speaking: # find . -type f -exec *head --bytes=1k {}* | md5sum | sort > md5sum.lst \; # uniq md5sum.lst > md5sum.uniq # for each couple in `diff md5sum.lst md5sum.uniq`; do Tuning the 1k value is a question of compromise between first pass file reading (the find command) and the risk to have unecessary cmp commands in the "for" loop. The chance of having files sharing the first 1kB is low in usual situations (but maybe with some M$ obscure formats ?) and should be fast (any read on a HD implies several blocks of 512B each). It is irrelevant as long as the files have non related contents. Otherwise, you can consider re-running à find with larger 'head' size, if the amount of couples in the for is too large, or trying tail instead of head. I leave you this part of the job. If you do so, why not intergrating it into RSYNC, so that the renaming of folders will no more kill the performances of the tool ? -- Brent Frère Private e-mail: Brent(a)BFrere.net Postal address: 5, rue de Mamer L-8280 Kehlen Grand-Duchy of Luxembourg European Union Mobile: +352-021/29.05.98 Fax: +352-26.30.05.96 Home: +352-307.341 URL: http://BFrere.net If you have problem with my digital signature, please install the appropriate authority certificate by browsing https://www.cacert.org/certs/root.crt.