List<T> readonly maken en bestanden filteren bij iteratie

[Anoniem: 530556]

Hallo Tweakers,

dit kleine hobby project loopt al een tijdje en ik heb er een hoop van opgestoken!
Mijn doel is om uiteindelijk wat acties uit te voeren op een groot (+/- 6TB) aantal geluidsbestanden.

Het is me gelukt bestanden vrij rap te identificeren op een test set van 150+ GB, MAAR nu wil ik als perfectionist alles zo hebben als ik in gedachte heb, hoop ik

Waar ik bij vast loop is:
- Hoe kan ik er voor zorgen dat alleen dubbele in deze lijst komen bij iteratie, wat moet ik overriden ?
- Hoe zorg ik er voor dat deze lijst readonly wordt, misschien een klein voorbeeld?
- Eventueel nog andere tips om dit sneller te maken op een groot aantal bestanden.

C#:

/*
var fileList = new DuplicateFileList();
fileList.Add(new DirectoryInfo(@"g:\sampling").GetFiles("*.*", SearchOption.AllDirectories));
//Console.WriteLine("Found {0} duplicate files.", fileList.Count);
foreach(Collection<FileInfo> files in fileList)
{
    if(files.Count > 1)
    {
        //Console.WriteLine("Found {0} duplicate file(s).", files[0].Name);
    }
}
Console.ReadKey();
*/

class DuplicateFileList : List<Collection<FileInfo>>
{
    const int BYTES_TO_READ = sizeof(Int64);
    
    protected Collection<long> _lengths = new Collection<long>();
    protected Collection<string> _paths = new Collection<string>();
    
    public DuplicateFileList() : base()
    {
    
    }
    
    public void Add(FileInfo file)
    {
        if(!_lengths.Contains(file.Length))
        {
            //Console.WriteLine("New entry {0}", file.Length);
            _lengths.Add(file.Length);
            var newEntry = new Collection<FileInfo>();
            newEntry.Add(file);
            Add(newEntry);
        }
        else if(!_paths.Contains(file.FullName))
        {
            _paths.Add(file.FullName);
            FileInfo[] targetFilesCopy;
            foreach(Collection<FileInfo> targetFiles in this)
            {
                targetFilesCopy = new FileInfo[targetFiles.Count];
                targetFiles.CopyTo(targetFilesCopy, 0);
                foreach(FileInfo targetFile in targetFilesCopy)
                {
                    //Console.WriteLine("Comparing {0} : {1}", targetFile.Name, file.Name);
                    if(CompareFiles(targetFile, file))
                    {
                        targetFiles.Add(file);
                    }
                }
            }
        }
    }
    
    public void Add(FileInfo[] files)
    {
        foreach(FileInfo file in files)
        {
            Add(file);
        }
    }
    
    
    
    protected bool CompareFiles(FileInfo first, FileInfo second)
    {
        if(first.Length != second.Length)
        {
            return false;
        }
        
        int iterations = (int)Math.Ceiling((double)first.Length / BYTES_TO_READ);

        using (FileStream fs1 = first.OpenRead())
        using (FileStream fs2 = second.OpenRead())
        {
            byte[] one = new byte[BYTES_TO_READ];
            byte[] two = new byte[BYTES_TO_READ];

            for (int i = 0; i < iterations; i++)
            {
                fs1.Read(one, 0, BYTES_TO_READ);
                fs2.Read(two, 0, BYTES_TO_READ);

                if (BitConverter.ToInt64(one,0) != BitConverter.ToInt64(two,0))
                    return false;
            }
        }

        return true;
    }
}

[Anoniem: 34209]

Waarom heb je sizeof(int64) is gewoon 8 bytes ?
Dan moet je wel heel vaak lezen

[ Voor 25% gewijzigd door Anoniem: 34209 op 08-11-2013 20:17 ]

[Anoniem: 530556]

The slowest possible method is to compare two files byte by byte. The fastest I've been able to come up with is a similar comparison, but instead of one byte at a time, you would use an array of bytes sized to Int64, and then compare the resulting numbers.

Van het SO topic.

Ik ben tevreden met de snelheid, maar optimalisaties zijn altijd welkom

[RobIII]

Besef dat een Contains() elke keer (potentieel) een complete collectie itereert; daar hebben we HashSets en Dictionaries voor uitgevonden; die zijn O(1). Beide _lengths en _paths komen daar voor in aanmerking.

Ik vind 't sowieso nogal omslachtig;

C#:

var files_grouped_by_length = new DirectoryInfo(@"G:\sampling")
                .GetFiles("*.*", SearchOption.AllDirectories)
                .GroupBy(f => f.Length)     //Files grouped by filesize 
                .Where(g => g.Count() > 1); //We're only interested in groups with more than 1 file

Dit groepeert alle files op lengte; als de lengte verschilt kun je jezelf de compare immers sowieso besparen. En alle lengtes waarvan er maar 1 voorkomt zijn per definitie al uniek, dus die snoeien we er ook uit.

Ook die BitConverter.ToInt64 is nergens voor nodig; je kunt toch zeker wel gewoon twee int64's met elkaar vergelijken Ik zou die CompareFiles() eerder zo implementeren:

C#:

public bool CompareFiles(FileInfo left, FileInfo right)
{
    if (left.Length != right.Length)
        return false;

    Int64 l = 0, r = 0;         //"Buffers"
    long p = 0,                 //Position
         i = left.Length / 8,   //Iterations of "int64-sized reads"
         c = left.Length % 8;   //Rest

    using (var brl = new BinaryReader(left.OpenRead()))
    using (var brr = new BinaryReader(right.OpenRead()))
    {
        //Compare "int64 chunks" at a time
        while (l == r && p++ < i)
        {
            l = brl.ReadInt64();
            r = brr.ReadInt64();
        }

        //Compare remaining bytes (if any and the left still equalled right in the last read)
        if (l == r && c > 0)
        {
            p = 0;  //Reset position
            while (l == r && p++ < c)
            {
                l = brl.ReadByte();
                r = brr.ReadByte();
            }
        }
    }
    return l == r;
}

Het enige wat je nu nog moet doen is per group de files tegen elkaar houden om de duplicates er uit te plukken.

Wat betreft "readonly" lists; ook daar is in .Net in voorzien maar daar zie ik hier niet direct het nut van en is wel 't minst van je problemen

[ Voor 17% gewijzigd door RobIII op 08-11-2013 21:31 ]

[doskabouter]

Met natuurlijk een early exit als de lengtes ongelijk zijn

[RobIII]

doskabouter schreef op vrijdag 08 november 2013 @ 21:19:
Met natuurlijk een early exit als de lengtes ongelijk zijn

Die is aanwezig?

[doskabouter]

Niet in jouw implementatie, of ben ik echt toe aan een bril?

[RobIII]

doskabouter schreef op vrijdag 08 november 2013 @ 21:20:
Niet in jouw implementatie, of ben ik echt toe aan een bril?

Nee, je hebt gelijk; die was verloren gegaan in 't proces Staat er weer in. My bad.
Overigens, zolang je de CompareFiles() binnen dezelfde "group" gebruikt zijn de lengtes per definitie natuurlijk al hetzelfde en is die check onnodig. Maar in 't kader van reuseability is die (toch al goedkope) check natuurlijk wel netjes.

[ Voor 31% gewijzigd door RobIII op 08-11-2013 21:26 ]

[RobIII]

Als je slim bent giet je die CompareFiles() in een IEqualityComparer<FileInfo> die de GroupBy() kan gebruiken om te bepalen of files gelijk zijn (en dus bij elkaar groeperen).

C#:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var duplicates = new DirectoryInfo(@"G:\sampling")
            .GetFiles("*.*", SearchOption.AllDirectories)
            .GroupBy(f => f, new FileComparer())    //Group by file equality
            .Where(g => g.Count() > 1);             //Groups with more than 1 file
        //Voila!
    }
}

public class FileComparer : IEqualityComparer<FileInfo>
{
    public bool Equals(FileInfo left, FileInfo right)
    {
        if (left.Length != right.Length)
            return false;

        Int64 l = 0, r = 0;         //"Buffers" 
        long p = 0,                 //Position 
             i = left.Length / 8,   //Iterations of "int64-sized reads" 
             c = left.Length % 8;   //Rest 

        using (var brl = new BinaryReader(left.OpenRead()))
        using (var brr = new BinaryReader(right.OpenRead()))
        {
            //Compare "int64 chunks" at a time 
            while (l == r && p++ < i)
            {
                l = brl.ReadInt64();
                r = brr.ReadInt64();
            }

            //Compare remaining bytes (if any and the left still equalled right in the last read) 
            if (l == r && c > 0)
            {
                p = 0;  //Reset position 
                while (l == r && p++ < c)
                {
                    l = brl.ReadByte();
                    r = brr.ReadByte();
                }
            }
        }
        return l == r;
    }

    public int GetHashCode(FileInfo obj)
    {
        return unchecked((int)obj.Length);  //As a first "indicator" the filelength is used as "hashcode"
    }
}

[ Voor 7% gewijzigd door RobIII op 08-11-2013 22:13 ]

[Anoniem: 530556]

Nou moet je niet alles gaan voor doen

Ik was net zo lekker op weg. Ik laat z.s.m. even weten hoe alles er uit gaat zien

[ Voor 3% gewijzigd door Anoniem: 530556 op 08-11-2013 23:28 ]

[pedorus]

Over performance: Het lezen van een bestand is zeer waarschijnlijk het traagste. Het lijkt me sneller om blokken van tenminste 128kB in te lezen. Met memcmp kun je byte arrays snel vergelijken. Houd ook rekening met het theoretische feit dat Read() niet alles retourneert wat je op vraagt, ook al is er nog voldoende data in een bestand, waardoor je dus een loopje moet gebruiken voor vulling. (En jawel, ik heb dus het idee dat de oplossing van R3, en de antwoorden op SO nog wel verbeterd kunnen worden )

Het handigst lijkt me eerst alle bestanden groeperen op grootte (Dictionary+List). Als er dan meer dan 2 bestanden met dezelfde grootte zijn, is het waarschijnlijk handig om bij het vergelijken van de eerste 2 bestanden gelijk een hash te berekenen (zeg MurMurHash3, handig dat je al byte arrays hebt in afgeronde hoeveelheden van 16 bytes die je aan ProcessBytes() kan geven als je die public maakt). Als je dan afwijkingen tegenkomt, ga je eerst op hash vergelijken. (Wat handig is hangt ook een beetje af van de kans op ongelijke bestanden met dezelfde grootte.)

[RobIII]

pedorus schreef op zaterdag 09 november 2013 @ 00:53:
Over performance: Het lezen van een bestand is zeer waarschijnlijk het traagste. Het lijkt me sneller om blokken van tenminste 128kB in te lezen.

Dat durf ik te betwijfelen...

pedorus schreef op zaterdag 09 november 2013 @ 00:53:
Met memcmp kun je byte arrays snel vergelijken.

Je leest dan dus in blokken van 128Kb terwijl de kans zeer groot is dat je, bij files met gelijke grootte, in de eerste paar (tiental/honderden) bytes een verschil vindt en dus kunt stoppen met I/O. Ik heb dit even simpel opgelost met een BufferedStream (om me de P/invokes etc te besparen) die ik op regel 30/31 plaats van mijn voorstel en door 5 iteraties heb laten lopen op een directory met aardig wat duplicates (617 duplicates op 3381 bestanden):

C#:

//Oorspronkelijk:
using (var brl = new BinaryReader(left.OpenRead()))
using (var brr = new BinaryReader(right.OpenRead()))

00:00:02.3544427
00:00:02.2857829
00:00:02.2826566
00:00:02.2956776
00:00:02.3489316
2,3159112 sec. avg.

C#:

//4Kb per keer
using var brl = new BinaryReader(new BufferedStream(left.OpenRead(), 4 * 1024)))
using (var brr = new BinaryReader(new BufferedStream(right.OpenRead(), 4 * 1024)))

00:00:02.5317447
00:00:02.4693344
00:00:02.5331502
00:00:02.5495536
00:00:02.5344998
2,52597282 sec. avg.

C#:

//128Kb per keer
using (var brl = new BinaryReader(new BufferedStream(left.OpenRead(), 128 * 1024)))
using var brr = new BinaryReader(new BufferedStream(right.OpenRead(), 128 * 1024)))

00:00:03.5325261
00:00:03.7654742
00:00:03.7520843
00:00:03.7776412
00:00:03.7800445
3,72404044 sec. avg.

C#:

//1MB per keer
using (var brl = new BinaryReader(new BufferedStream(left.OpenRead(), 1024 * 1024)))
using (var brr = new BinaryReader(new BufferedStream(right.OpenRead(), 1024 * 1024)))

00:00:07.3622192
00:00:08.9732089
00:00:08.4011407
00:00:08.3767841
00:00:08.5113488
8,32736576 sec. avg.

Blokgrootte	Avg (seconden)
8 bytes	2,31591120
4KB	2,52597282
128KB	3,72404044
1MB	8,32736576

Je verknoeit een hoop tijd aan 't vullen van een (grotere) buffer. Het filesystem leest toch al in blokken van, wat, 4Kb (NTFS default) ofzo en hoe eerder je een verschil vindt hoe eerder je kunt afhaken.

pedorus schreef op zaterdag 09 november 2013 @ 00:53:
Houd ook rekening met het theoretische feit dat Read() niet alles retourneert wat je op vraagt, ook al is er nog voldoende data in een bestand, waardoor je dus een loopje moet gebruiken voor vulling.

Klopt; een Read() niet, maar een ReadInt64() leest gegarandeerd 8 bytes (Of 't doet *poef* als je 8 bytes probeert te lezen terwijl er < 8 bytes te lezen zijn vanaf de huidige positie )

pedorus schreef op zaterdag 09 november 2013 @ 00:53:
(En jawel, ik heb dus het idee dat de oplossing van R3, en de antwoorden op SO nog wel verbeterd kunnen worden )

Meten == weten. Prove it (Er zal vast nog wel wat te halen zijn, dat ben ik met je eens hoor; ik denk alleen dat mijn oplossing een redelijke trade-off voor maintainability / readability / complexity / performance is).

pedorus schreef op zaterdag 09 november 2013 @ 00:53:
Het handigst lijkt me eerst alle bestanden groeperen op grootte (Dictionary+List). Als er dan meer dan 2 bestanden met dezelfde grootte zijn

Dat doet de GroupBy() in mijn voorbeeld nu heel netjes m.b.v. de GetHashCode() (die feitelijk gewoon de filesize is behalve voor files > 2GB, in welk geval er 1 extra "if" in de Equals() gespendeerd wordt om alsnog de eigenlijke filesize (long) te comparen).

pedorus schreef op zaterdag 09 november 2013 @ 00:53:
is het waarschijnlijk handig om bij het vergelijken van de eerste 2 bestanden gelijk een hash te berekenen

Het berekenen van een hash is in dit geval pure nodeloze overhead. Een hash trek je overigens ook altijd over een complete file; hier geldt ook weer dat je potentieel al na een paar bytes lezen had kunnen afhaken wegens inequality.

Alleen in geval van extreme directories met extreem veel files e.d. waardoor 't hele zakie niet meer in memory zou passen, of wanneer je dit soort acties meer dan eens (per X interval) nodig hebt, zal het zéker de moeite waard zijn hashes te berekenen en te persisten/cachen. Dan hoef je alleen maar voor nieuwe files een hash te berekenen en die tegen bestaande hashes te houden (en moet.je dus wel kunnen garanderen dat persisted/cached hashes "in sync" blijven met de files).

[edit]
Overigens; dit geeft Drkevlar's implementatie (uit de TS) van CompareFiles() als ik die in mijn IEqualityComparer<FileInfo> mikker:

00:00:01.9624807
00:00:01.8935245
00:00:01.8838745
00:00:01.8810616
00:00:01.9820400
1,92295128 sec. avg.

Die is dus nog sneller Geen idee waar dat in zit maar ik vermoed dat de BinaryReader wat smerigs doet onder de motorkap ofzo. Ik zou gaan moeten profilen om daar meer zinnigs over te kunnen zeggen maar daar heb ik nu de puf niet meer voor. Maar eerlijk is eerlijk en meten == weten: somehow is dat sneller

[ Voor 25% gewijzigd door RobIII op 09-11-2013 02:50 ]

[pedorus]

Dat die sneller is kan komen omdat je die later hebt gedraaid (cache optimalisaties/defragmentatie) en omdat die incorrect aanneemt dat Read() altijd voldoende bytes teruggeeft en een schilletje minder nodig heeft...

Het kan sowieso zijn dat de bestandencollectie grotendeels in de file cache past als je genoeg geheugen hebt. Dat betekend dat je niet hard disk gebruik test. Solid state kan bijvoorbeeld ook flink uitmaken, ik vermoed geen stolid state bij 6TB aan data.

Die voorbeelden hierboven zijn gewoon niet correct natuurlijk. Je verdoet tijd aan dubbele buffering (openread() heeft al een 4kB buffer ingebouwd), maar compenseert niet met memcmp... Verder hangt het er sterk vanaf hoe die bestanden ontstaan zijn. Als de kans groot is op verschillen in het begin, dan is een kleinere buffer natuurlijk handiger. Waarschijnlijk is het inderdaad beter om altijd eerst maar 4kB te checken, als die overeenkomen check je de rest. Als de kans groot is op geen verschillen, dan is een grotere buffer handiger. Als de kans groot is op vrij veel bestanden van dezelfde grootte, dan is het handig om het aantal vergelijkingen te kunnen beperken met een hash.

Als ik zelf test bij het vergelijken van 2 grote bestanden, dan is het enige verschil dat ik zie de hoeveelheid cpu-gebruik eigenlijk, memcmp is een stuk efficiënter dan de CompareFiles uit de TS. Verwerkingstijden zijn nogal variabel en niet consistent afwijkend (in orde 55-70 sec.). Ik denk dat er op een normale pc nog meer dan genoeg cpu tijd over is om ook 'gratis' een hash te berekenen over de eerste 4kB en eventueel over alles.

C#:

        [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
        static extern int memcmp(byte[] b1, byte[] b2, long count);

        private static bool ReadFully(Stream f, byte[] buf, int count)
        {
            int offset = 0;
            while (count > 0)
            {
                int read = f.Read(buf, offset, count);
                if (read <= 0)
                    return false;
                offset += read;
                count -= read;
            }
            return true;
        }

        public static bool CompareFiles(FileInfo first, FileInfo second)
        {
            if (first.Length != second.Length)
            {
                return false;
            }

            using (FileStream fs1 = first.OpenRead())
            using (FileStream fs2 = second.OpenRead())
            {
                byte[] one = new byte[1 << 17];
                byte[] two = new byte[1 << 17];

                int read = fs1.Read(one, 0, 4096);
                if (!(ReadFully(fs2, two, read) && (memcmp(one, two, read) == 0)))
                    return false;

                while ((read = fs1.Read(one, 0, one.Length)) > 0)
                {
                    if (!(ReadFully(fs2, two, read) && (memcmp(one, two, read) == 0)))
                        return false;
                }

                return true;
            }
        }

Edit: toch zie ik bij vaker draaien op de achtergrond wel verschil. Weet niet in hoeverre dit door memcmp of de block size komt, denk beiden uit eerste tests (dus wellicht helpt async io ook), maar meeste aan block size:

memcmp: 64419
TS: 78974
memcmp: 66038
TS: 78481
memcmp: 67580
TS: 79486
memcmp: 65098
TS: 78777
memcmp: 66006
TS: 80604
memcmp: 67397
TS: 78576
memcmp: 65725
TS: 71263
memcmp: 64581
TS: 73727
memcmp: 66945
TS: 78090
memcmp: 68332
TS: 81489

Testjes met memcmp vervangen door managed for-loopje:

memcmp: 67083
memcmp: 67881
memcmp: 65755
memcmp: 68926
memcmp: 68550

En met 1 << 20 en echte memcmp:

memcmp: 55457
memcmp: 58495
memcmp: 59310
memcmp: 58352
memcmp: 57002
memcmp: 58587

1 << 22 (4 MB):

memcmp: 41609
memcmp: 49371
memcmp: 50314
memcmp: 48040
memcmp: 50829
memcmp: 50936

[ Voor 12% gewijzigd door pedorus op 09-11-2013 15:02 ]

[RobIII]

pedorus schreef op zaterdag 09 november 2013 @ 10:15:
Dat die sneller is kan komen omdat je die later hebt gedraaid (cache optimalisaties/defragmentatie) en omdat die incorrect aanneemt dat Read() altijd voldoende bytes teruggeeft en een schilletje minder nodig heeft...

Uiteraard heb ik die tests een aantal keren "kris kras" door elkaar gedraaid en consistente uitslagen gehad. Dat schilletje minder ben ik met je eens, maar ik schrik er wel een beetje van hoeveel dat schilletje dan opeens scheelt...

pedorus schreef op zaterdag 09 november 2013 @ 10:15:
Als de kans groot is op verschillen in het begin

Wat, IMHO, zo zal zijn bij wave-files... Vooral bij files als sourcecode (waar ik bijvoorbeeld op getest hebt door verschillende branches (=lekker veel duplicates) te comparen) heb je al gauw dat er complete meuk als "author: foo, date: bar" etc. boven staat en dat de eerste paar regels of KB al snel gelijkend zijn. Dat zal bij (raw) wavefiles en zaken zonder enorme "fileheaders" (boilerplate) minder snel zo zijn (althans; dat is ook maar een educated guess).

pedorus schreef op zaterdag 09 november 2013 @ 10:15:
dan is een kleinere buffer natuurlijk handiger. Waarschijnlijk is het inderdaad beter om altijd eerst maar 4kB te checken, als die overeenkomen check je de rest. Als de kans groot is op geen verschillen, dan is een grotere buffer handiger.

In de regel is een grote(re) buffer bij I/O wel beter voor de prestaties idd.

pedorus schreef op zaterdag 09 november 2013 @ 10:15:
Als de kans groot is op vrij veel bestanden van dezelfde grootte, dan is het handig om het aantal vergelijkingen te kunnen beperken met een hash.

Alleen moet je voor die hash per definitie altijd 't hele bestand doorbuffelen; dat levert zeker winst op wanneer je de hashes ergens opslaat voor een volgende keer (en zorgt dat de hashes "in sync" blijven met de bestanden) maar in dit specifieke (uitgaande van eenmalige actie) geval is 't alleen nutteloos. Overigens heb je bij "triplicates" en meer wel kans dat je nodeloos een bestand meer dan eens doorbuffelt en dan scheelt een hash ook. En, inderdaad, de beperkende factor is toch gewoon I/O en dus reken je zo'n hash (min-of-meer) gratis uit.

[ Voor 12% gewijzigd door RobIII op 09-11-2013 21:38 ]

[Johnsel]

Eerste x bytes overslaan, waarbij x de lengte van de fileheader is. (Rekening houden met ID3 tags enzo)

[RobIII]

Johnsel schreef op zaterdag 09 november 2013 @ 23:30:
Eerste x bytes overslaan, waarbij x de lengte van de fileheader is. (Rekening houden met ID3 tags enzo)

Ook in fileheaders kunnen verschillen zitten (en ID3 tags e.d. zitten aan 't eind van een file en bij wavefiles e.d. is er amper sprake van fileheaders). De paar bytes die je skipt zijn de moeite niet waard en ook nog eens erg file-type afhankelijk (en kunnen, as said, ook verschillen bevatten).

[ Voor 15% gewijzigd door RobIII op 10-11-2013 16:37 ]