[Gelöst] Mehrfach-Dateien erkennen C++ und std::filesystem



  • Hallo zusammen,

    ich bin mir durchaus bewusst, dass es vermutlich bessere Werkzeuge gibt, um das Ziel zu erreichen.
    Dennoch interessierte mich eine C++ Umsetzung.

    Wie würdet ihr das besser machen? Ich könnte mir vorstellen, dass man es irgendwie noch eleganter machen kann, aber ich habe halt bei Datei Ein- und Ausgabe keine Sorgen, dass die Performance irgendwie am Programmcode groß scheitern könnte (außer man macht etwas blödes mit dem Dateiinhalt).

    Den unordered_set habe ich noch hinzugefügt, weil das Arbeiten allein mit den unordered_multimap Iteratoren total ätzend war.

    /* NOTE: Somewhat deprecated / outdated comment
    How to find duplicate files:
    	1. Iterate over all files in the search space.
    	   For example: Specify a starting root path and recursively iterate all files within that given start path.
    	2. For each iterated file, record the file size and the absolute file path.
    	3. For each non-empty file sharing an equal file size and extension/type (e.g., inspect extension or inspect file contents/header),
           compute a hash digest / checksum of the files
        4. For any given files that share an equal digest, to be sure, a byte-wise comparison of the file(s) can be performed to prove duplicate data (seems redundant depending on the used hash function).
           E.g., cryptographic hash functions probably remove the need for additional binary comparison.	
    	
    How to find duplicate directories:
    */
    
    #include <algorithm>
    #include <filesystem>
    #include <fstream>
    #include <iostream>
    #include <string>
    #include <string_view>
    #include <unordered_map>
    #include <unordered_set>
    
    namespace fs = std::filesystem;
    
    constexpr std::size_t operator""_KiB(std::uintmax_t x) {
      return std::uintmax_t{1024} * x;
    }
    
    constexpr std::size_t operator""_MiB(std::uintmax_t x) {
      return 1024_KiB * x;
    }
    
    constexpr std::size_t operator""_GiB(std::uintmax_t x) {
      return 1024_MiB * x;
    }
    
    template<class Path>
    std::string read_file_raw(const Path& filePath) {
        std::string str;
        auto size = fs::file_size(filePath);
        str.resize(size);
    
        std::ifstream file{filePath, std::ios::binary};
        if (!file) {
            throw std::runtime_error{"Failed to open file for reading."};
        }
        file.read(str.data(), static_cast<std::streamsize>(size));
        return str;
    }
    
    void find_duplicate_files(const fs::path& path)
    {
    	std::unordered_set<std::uintmax_t> size_keys;
    	std::unordered_multimap<std::uintmax_t, fs::path> files_by_size;
    	
            // Group files sharing the same size
    	for (const auto& entry : fs::recursive_directory_iterator{path})
    	{
    		if (fs::is_regular_file(entry) && entry.file_size() > 0)
    		{
    			size_keys.emplace(entry.file_size());
    			files_by_size.emplace(entry.file_size(), fs::canonical(entry));
    		}
    	}
    	
    	for (const auto size : size_keys)
    	{
                    // Look for identical duplicates within groups of files with the same size
    		const auto range = files_by_size.equal_range(size);
    		if (std::distance(range.first, range.second) < 2)
    		{
    			continue;
    		}
    			
    		std::cout << "[Info] Found potential duplicates with file size " << size << " bytes:\n";
    		const bool compareSize{size < 1_GiB};  // Hier kann man sich noch etwas einfallen lassen. Z. B. nur in kleinen Mengen lesen/vergleichen und früh rausspringen oder mmap?
    		std::string lhs_content;
    		if (compareSize)
    		{
    			lhs_content = std::move(read_file_raw(range.first->second)); // I think std::move is needed to avoid copy but not 100% sure
    		}
    		const auto lhs_ext = range.first->second.extension();
    		for (auto it = range.first; it != range.second; ++it) {
    			std::cout << " -> " << it->second << '\n';
    			const auto rhs_ext = it->second.extension();
    			if (compareSize && it != range.first)
    			{
    				const auto rhs_content = read_file_raw(it->second);
    				// could try std::equal(lhs_content.cbegin(), lhs_content.cend(), rhs_content.cbegin()) or std::memcmp(lhs_content.c_str(), rhs_content.c_str()) if needed / faster.
    				if (lhs_content == rhs_content)
    				{
    					std::cout << "      [Info]      Binary identical confirmed.\n";
    				}
    			}
    			if (lhs_ext != rhs_ext) {
    				std::cout << "      [!Warning!] Unexpected file extension change.\n";
    			}
    		}
    	}
    }
    
    void print_usage() {
    	std::cout << "Usage: dupfi <root_path>\n";
    }
    
    int main(int argc, char** argv)
    try
    {
    	argc == 2 ? find_duplicate_files(argv[1])
    	          : print_usage();
    	return 0;
    }
    catch (const fs::filesystem_error& e)
    {
    	std::cerr << e.what() << '\n';
    	return e.code().value();
    }
    catch (...)
    {
    	std::cerr << "Unhandled exception. The program will terminate!\n";
    	return -1;
    }
    

    Meine andere Idee wäre noch gewesen eine std::unordered_multimap<fs::path, fs::path> bzw. std::unordered_multimap<std::string, fs::path>, wobei man jeweils nach Dateiname geht (i. d. R. hätten ja Mehrfach-Dateien auch den gleichen Dateinamen) und dann auf den absoluten Pfad verweist, und auf der Basis Duplikate findet.

    Edit: Huiuiui, https://github.com/pkolaczk/fclones (aber "leider" Rust und nicht C++)


  • Mod

    Ist denn die Grundidee überhaupt effizient? Klingt so, als wären Schritt 3b und 4 unnötig bis falsch. Dateiendungen sind Schall und Rauch, daher sollte die doch nicht für Gleichheit zählen, sonst hast du deine typische virus.pdf.exe. Und der Hashvergleich bedeutet, dass du im besten Fall bei jedem Kandidaten beide Dateien komplett durchgehen musst, und schlimmstenfalls danach nochmals beide komplett. Wohingegen das Weglassen dieses Schritts dazu führen würde, dass das komplette Durchgehen von beiden Dateien der worst-case wäre, und der best-case ein Abbrechen nach dem ersten Block. Ein Vergleich von zwei Blöcken ist sicherlich auch effizienter als irgendetwas mit diesen Blöcken zu berechnen.

    Der Nebensatz mit der cryptigraphic hash function beweist, dass der Autor keine Ahnung hat. Die Kryptografietauglichkeit eines Hash hat überhaupt absolut gar nichts damit zu tun, wie wahrscheinlich Doppelungen sind.



  • Hallo SeppJ,

    vielen Dank für die Rückmeldung, ich werde mir nochmals Gedanken machen. Der Code ist auch anders geworden. Bei anderer Endung habe ich nur eine "Warnung" ausgegeben. Ich berechne auch keine Hashes. Erstes Indiz ist die Länge, dann wird die Datei eingelesen in std::string und via operator== verglichen. Der Kommentar war leider etwas veraltet.

    @SeppJ sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Der Nebensatz mit der cryptigraphic hash function beweist, dass der Autor keine Ahnung hat. Die Kryptografietauglichkeit eines Hash hat überhaupt absolut gar nichts damit zu tun, wie wahrscheinlich Doppelungen sind.

    Das kann ich so nicht stehenlassen. Selbstverständlich ist Kollisionsresistenz bzw. das Nichtvorhandensein* von Kollisionen keine hinreichende Bedingung, sehr wohl aber eine notwendige Bedingung für kryptografische Hashfunktionen.

    *Ich möchte noch ergänzen, natürlich gibt es in der Theorie Kollisionen, da man den unbegrenzten Eingaberaum auf z. B. 256-Bit Ausgabe begrenzt, aber gemeint war "in der Praxis nicht vorhanden", da i. d. R. entdeckte Kollisionen bereits als Anreiz genommen werden, dass die Hashfunktion nicht mehr sicher sein könnte.


  • Mod

    @HarteWare sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Das kann ich so nicht stehenlassen. Selbstverständlich ist Kollisionsresistenz bzw. das Nichtvorhandensein* von Kollisionen keine hinreichende Bedingung, sehr wohl aber eine notwendige Bedingung für kryptografische Hashfunktionen.

    Das ist schon die Definition eines Hash! Deswegen nennt man es kryptographischer Hash, nicht kryptografischer Dingensbummels. Die Kryptographietauglichkeit ist ein völlige andere Zusatzeigenschaft, die eben sonst die wenigsten Hashes haben.

    Erstes Indiz ist die Länge, dann wird die Datei eingelesen in std::string und via operator== verglichen.

    Aber hoffentlich nicht alles auf einmal?



  • @SeppJ @HarteWare Ich glaube, ihr meint hier das Gleiche.

    Allgemeine Hashfunktion: Die Hash Werte sind möglichst Gleichverteilt im Abbildungsraum.

    Kryptografische Hashfunktionen: Es ist hinreichend schwer eine Kollision zu finden (Pre-image resistance, Second pre-image resistance und collsion resistance)


  • Mod

    @Schlangenmensch sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Kryptografische Hashfunktionen: Es ist hinreichend schwer eine Kollision zu finden (Pre-image resistance, Second pre-image resistance und collsion resistance)

    Das ist ein Teil, aber reicht noch nicht für kryptographische Zwecke.



  • Hat zwar nichts direkt mit der ursprünglichen Frage zu tun, aber nur als weitere Idee: ich habe bislang öfter mal fdupes benutzt, um nach doppelten Dateien zu suchen. Das ist in C, aber vielleicht ist es interessant, mal dort in den Sourcecode zu schauen und zu gucken, wie das Programm Duplikate findet?

    https://github.com/adrianlopezroche/fdupes (ich hab das den github-Link gerade erst selber ergooglet, kann also nicht sagen, ob hilfreich oder nicht)



  • @Schlangenmensch sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Kryptografische Hashfunktionen: Es ist hinreichend schwer eine Kollision zu finden (Pre-image resistance, Second pre-image resistance und collsion resistance)

    Ich verstehe schon was SeppJ meint.

    So einfach darf man nicht Hash Funktion und kryptografische Hashfunktionen in einen Topf werfen. Folgende zusätzliche Eigenschaften von kryptografischen Hashfunktionen kenne ich noch:



  • Also ich würde es vermutlich so machen:

    1. Pfade und Grössen sammeln
    2. Eindeutig einzigartige Files anhand der Grösse ermitteln und rauswerfen
    3. Von allem was übrig geblieben ist einen Hash über die ersten paar kB erstellen
    4. Eindeutig einzigartige Files anhand der Grösse + partiellem Hash ermitteln und rauswerfen

    Danach könnte man dann entweder einen Hash über den gesamten Inhalt machen.

    Oder man könnte einen weiteren partiellen Hash über einen grösseren Bereich machen und schauen was danach noch übrig geblieben ist. Dann einen nochmal grösseren Bereich usw. bis man alle verbliebenen Files vollständig gehasht hat.

    Evtl. könnte es auch Sinn machen zusätzlich zu den ersten paar kB auch die letzten paar kB zu hashen. Gibt ja ein paar File-Formate die sich in bestimmten Fällen erst sehr weit hinten unterscheiden. Z.B. ZIP Archive die sich erst in Files unterscheiden die zuletzt hinzugefügt wurden. Die könnte man dann schneller rauswerfen.

    Weiters würde es vermutlich auch Sinn machen die Inodes der Files zu ermitteln. Denn zwei Files die die selbe Inode haben (und auf dem selben Volume liegen) sind ja notwendigerweise identisch. Die sollte das Programm dann nicht vergleichen. Und ggf. auch gesondert ausweisen. Denn wenn es z.B. darum geht dass man Speicherplatz sparen will indem man Duplikate löscht, dann könnte es interessant sein dass diese "Duplikate" gar keinen Speicherplatz verschwenden. Also abgesehen von dem bisschen Platz den der Verzeichniseintrag braucht.



  • @Quiche-Lorraine @SeppJ Wahrscheinlich habe ich mich ungünstig ausgedrückt. Mir ging es darum, dass Kollisionsresitenz ein Merkmal von krypotografischen Hashfunktionen sind, aber nicht von Hashfunktionen im Allgemeinen.
    zB. die einstellige Quersumme, ist eine Hashfunktion, aber natürlich weit weg von einer kryptorafischen Hashfunktion. U.a. ist es hier sehr einfach eine Kollision zu erzeugen.



  • @Schlangenmensch sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    @Quiche-Lorraine @SeppJ Wahrscheinlich habe ich mich ungünstig ausgedrückt. Mir ging es darum, dass Kollisionsresitenz ein Merkmal von krypotografischen Hashfunktionen sind, aber nicht von Hashfunktionen im Allgemeinen.

    Resistenz gegen zufällige Kollisionen ist eine Eigenschaft jeder (guten) Hashfunktion. Natürlich nur soweit die Länge/der Wertebereich es zulässt. Was dagegen nicht für jede Hashfunktion erforderlich ist, ist Resistenz gegen Angriffe, wo man absichtlich versucht Kollisionen herbeizuführen.

    zB. die einstellige Quersumme, ist eine Hashfunktion, aber natürlich weit weg von einer kryptorafischen Hashfunktion. U.a. ist es hier sehr einfach eine Kollision zu erzeugen.

    Das ist ein unsinniges Beispiel. Das Problem ist hier nicht nur der Algorithmus, sondern bereits der Wertebereich. Den Wertebereich gross genug zu machen ist aber nicht genug. Es muss auch der Algorithmus derart sein, dass es trotz voller Kontrolle über die Inputs praktisch unmöglich ist zwei Inputs zu erzeugen die auf den selben Wert hashen.



  • @hustbaer Aber all das sind nicht zwangsläufig Eigenschaften von Hashfunktionen, sondern Eigenschaften die von speziellen Hashfunktionen für bestimmte Anwendungen gefordert werden.

    Nehmen wir die Prüfsumme für eine IBAN (Module 97-10). Die ist 2 Stellig. Da wird ein 20 stelliger Wertebereich auf 2 Stellen reduziert. Das reicht um typische Vertipper zu erkennen, ist aber weit weg von dem, was ich unter Kollisionsresitenz verstehe.



  • @Schlangenmensch
    Ich würde die IBAN Prüfsumme nicht als Hashfunktion bezeichnen.



  • Warum nicht?

    Ich habe mal geschaut, was Wikipedia schreibt. Dort findet sich u.a. der Satz "Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen". (Hervorhebung von mir)

    Der Definition dort scheint das auch nicht zu widersprechen.

    Dann kommt auf allerdings der Absatz "Kriterien" mit "Geringe Wahrscheinlichkeit von Kollisionen der Hashwerte für den Eingabewertebereich, also möglichst eine Gleichverteilung der Hashwerte auf die erwarteten Eingabewerte." Das klingt nach Wischi-Waschi und ich kann es aus der Definition dort nicht ableiten. Finde auch spannend, dass dort "Die Funktion muss schnell berechenbar sein" als Kriterium angegeben ist. Für Krypto kann man ja auch das Gegenteil wollen.

    (nun ist Wikipedia aber sicher nicht der einzige Ort, wo es Definitionen von Hash-Funktionen gibt).



  • @wob sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Warum nicht?

    Der Zweck einer Prüfsumme ist es Fehler zu erkennen.
    Der Zweck eines Hashcodes ist es Inputs gleichmässig auf Buckets zu verteilen.

    Es gibt natürlich viele Algorithmen die sich für beides gut eignen.

    Und der Zweck der IBAN Prüfsumme ist halt Fehler zu erkennen. Weiters ist sie als Hashcode nur sehr begrenzt geeignet - eigentlich nur wenn man zufällig genau 97 Buckets verwenden will. Mehr Buckets geht sowieso nicht, und bei weniger Buckets muss man eine beträchtliche Ungleichverteilung in Kauf nehmen. Von daher macht die Bezeichnung als Hashcode mMn. keinen Sinn.



  • @SeppJ sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Aber hoffentlich nicht alles auf einmal?

    Upps... daran muss man arbeiten, hatte ich schon vermutet, das ist ja katastrophal langsam (und außerdem müsste man wohl Spezialfälle für große Dateien ebenfalls betrachten).

    Das ist jetzt das Beste, was ich ohne Hashing und sonstigen Schnick-Schnack erzielen konnte, für den ad-hoc Dateivergleich:

    template<std::streamsize BufSize>
    bool is_duplicate_file(const fs::path& a_path, const fs::path& b_path)
    {
    	if (!fs::is_regular_file(a_path) || !fs::is_regular_file(b_path)) return false;
            if (fs::equivalent(a_path, b_path)) return true;
    	if (fs::file_size(a_path) != fs::file_size(b_path)) return false;
    	
    	std::ifstream a_in{ a_path, std::ios::binary };
    	std::ifstream b_in{ b_path, std::ios::binary };
    	if (!a_in || !b_in) {
    		// Exceptional case because files cannot be compared. Therefore, can neither return true nor false.
    		throw std::runtime_error("is_duplicate_file: Unable to open file(s) for reading");
    	}
    	if (a_in.peek() != b_in.peek()) return false;
    	
    	std::array<char, BufSize> a_buf{};
    	std::array<char, BufSize> b_buf{};
    	while (a_in.read(a_buf.data(), BufSize) && b_in.read(b_buf.data(), BufSize)) {
    		if (a_buf != b_buf) return false;
    	}
    	
    	if (!a_in.eof() || !b_in.eof()) {
    		// Exceptional case because if this point is reached, given file sizes are equal, eventually while-loop would exit due to eof().
    		throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
    	}
    	
    	return true;
    }
    

  • Mod

    Schaut mir fein aus 👍



  • @SeppJ Ein Bug ist mir noch reingerutscht, ich weiß auch gar nicht, ob man so einen Mist verhindern kann (o.k., mit Tests halt, oder wahrscheinlich bessere Namensgebung, z. B. sollten a und b eher bennant sein, um auf einen Pfad/Datei/... hinzudeuten, wie a_path und b_path):

    if (a != b) return false;
    // muss sein:
    if (a_buf != b_buf) return false;
    

    Edit 1: Weiterer potenzieller Bug, durch die Konstruktion der while-Schleife wird beim letzten gültigen read bereits a_in.eof() und somit wird das letzte b.read() nicht mehr erreicht, ist mir dadurch erst aufgefallen, dass die if (!a_in.eof() || !b_in.eof()) Ausnahme ausgelöst wurde.

    while (a_in.read(a_buf.data(), BufSize) && b_in.read(b_buf.data(), BufSize))
    
    // müsste evtl. sein: -- NEIN, das ist Quatsch, das ist wie while(true)
    while ((a_in.read(buf_a.data(), BufSize) || a_in.eof()) && 
           (b_in.read(buf_b.data(), BufSize) || b_in.eof()))
    {
    }
    
    // müsste evtl. sein (das ist auch nicht optimal, wenn a::fail und b nicht, aber die Dateien in Wirklichkeit gleich wären, passt es nicht):
    do {
    	a_in.read(buf_a.data(), BufSize);
    	b_in.read(buf_b.data(), BufSize);
    	if (buf_a != buf_b) return false;
    } while (a_in && b_in);
    
    // Oder so, und dann den äußeren if (!a_in.eof() || !b_in.eof()) weglassen (hässlich, aber gut?):
    do {
    	a_in.read(buf_a.data(), BufSize);
    	if (a_in.fail() || a_in.bad())
    		throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
    		
    	b_in.read(buf_b.data(), BufSize);
    	if (b_in.fail() || b_in.bad())
    		throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
    		
    	if (buf_a != buf_b) return false;
    } while (a_in && b_in);
    

  • Mod

    Argh, das hätte mir auffallen müssen. Zumal ich speziell auf das Verhalten in Fehlerfällen geachtet habe, das aber solide aussieht. Habe da wohl beim Lesen den Normalfall vernachlässigt 🙂

    PS: Was hältst du von a_in.read(…).rd-state() == b_in.read(…).rd_state() && a_in?
    PPS: Schaut so aus als hätte ein iostate keinen Vergleichsoperator 😞 . Cast zu bool dann? Deine Vorschläge finde ich jedenfalls ein bisschen schwer verständlich, bin mir gar nicht sicher, ob sie stimmen.



  • @SeppJ Meine Überlegung ist, dass das mit der while-Bedingung (und Prüfen des Rückgabewerts von read()) nicht funktioneren kann, weil eof() immer abbrechen würde. Also ich könnte damit leben:

    while (a_in && b_in) {
    	a_in.read(buf_a.data(), BufSize);
    	b_in.read(buf_b.data(), BufSize);
    	if (a_in.fail() || a_in.bad() || b_in.fail() || b_in.bad()) {
    		throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
    	}
    	if (buf_a != buf_b) return false;
    }
    

    Edit2: Ach manno: https://devdocs.io/cpp/io/ios_base/iostate

    [...]
    Note that in nearly all situations, if eofbit is set, the failbit is set as well.
    [...]
    The failbit is set by the following standard library functions:

    • basic_istream::read, if the end-of-file condition occurs on the input stream before all requested characters could be extracted.

    Es scheint eigentlich so, dass realistisch bei read() nichts schiefgehen kann, sobald die Datei erfolgreich geöffnet wurde (was nicht auch das Programm abschießen würde, z. B. Stromausfall), außer dass die Dateien EOF sind. Vielleicht ist also dieser zweite Check mit throw overkill.

    Edit3: Noch ein allgemeiner Hinweis (oder Vermutung): Die filesystem Funktionen wie file_size oder is_regular_file führen zu "syscalls" o. Ä. und unnötige Aufrufe sind unbedingt zu vermeiden / minimieren, sofern möglich. Ich hatte einen zusätzlichen file_size sowie is_regular_file aufruf und dadurch gleich mal die Performance halbiert im Vergleich zur Funktion ohne die zusätzlichen Aufrufe. Wohingegen fs::equivalent vernachlässigbar zu sein scheint. Die Verwendung von peek() bringt nicht zuverlässig etwas, sodass sich die Zeile wohl nicht lohnt.
    Wie man sieht, habe ich einiges ausprobiert:

    $ ./dupf.exe --benchmark 'D:/Pictures'
    Running [FileCompare_baseline]
      Total bytes compared   : 0
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 2481.48ms
    
    Running [FileCompare_baseline_file_size]
      Total bytes compared   : 0
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3515.58ms
    
    Running [FileCompare_baseline_is_regular_file]
      Total bytes compared   : 0
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3534.22ms
    
    Running [FileCompare_bytewise_ignoreSize]
      Total bytes compared   : 48502896
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 7210.14ms
    
    Running [FileCompare_bytewise_peek_ignoreSize]
      Total bytes compared   : 48472646
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 30264
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 7464.32ms
    
    Running [FileCompare_noHash<128ll>]
      Total bytes compared   : 48453120
      Total files compared   : 32950
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3639.78ms
    
    Running [FileCompare_noHash_2<128ll>]
      Total bytes compared   : 44416768
      Total files compared   : 32950
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 12
      Time                   : 3642.16ms
    
    Running [FileCompare_noHash_2_ignoreSize<128ll>]
      Total bytes compared   : 44759040
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 30264
      Total seekg exits      : 0
      Total duplicates found : 12
      Time                   : 10373.1ms
    
    Running [FileCompare_bytewise_size]
      Total bytes compared   : 48454500
      Total files compared   : 32950
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 4923.53ms
    
    Running [FileCompare_stdequal_ignoreSize<128ull>]
      Total bytes compared   : 52627840
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 5880.31ms
    
    Running [FileCompare_memcmp_ignoreSize<128ull>]
      Total bytes compared   : 52627840
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 5890.91ms
    
    Running [FileCompare_stdequal<128ull>]
      Total bytes compared   : 48453120
      Total files compared   : 12
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3618.82ms
    
    Running [FileCompare_memcmp<128ull>]
      Total bytes compared   : 48453120
      Total files compared   : 12
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3671.38ms
    
    Running [FileCompare_stdequal<2048ull>]
      Total bytes compared   : 48439296
      Total files compared   : 12
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3623.17ms
    
    Running [FileCompare_memcmp<2048ull>]
      Total bytes compared   : 48439296
      Total files compared   : 12
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3608.61ms
    
    Running [FileCompare_memcmp<16384ull>]
      Total bytes compared   : 48365568
      Total files compared   : 12
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3548.36ms
    
    Running [FileCompare_memcmp<65536ull>]
      Total bytes compared   : 47972352
      Total files compared   : 12
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 3545.12ms
    
    Running [FileCompare_mmap]
      Total bytes compared   : 48454488
      Total files compared   : 32950
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 12
      Time                   : 7584.03ms
    
    Running [FileCompare_peek_end]
      Total bytes compared   : 48454500
      Total files compared   : 32950
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 8355.01ms
    
    Running [FileCompare_xxHash]
      Total bytes compared   : 48454488
      Total files compared   : 32950
      Total size exits       : 32938
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 12
      Time                   : 3564.38ms
    
    Running [FileCompare_readall]
      Total bytes compared   : 7533884225
      Total files compared   : 32950
      Total size exits       : 0
      Total peek exits       : 0
      Total seekg exits      : 0
      Total duplicates found : 0
      Time                   : 13140.2ms
    

    Man sieht auch wie viele dieser "Benchmarks" hier tatsächlich fehlerbehaftet waren (weil "Total duplicates found : 0", obwohl es 12 sein müssen), wegen ähnlicher Probleme wie oben beschrieben, weil der eof() Fall beispielsweise nicht korrekt gehandhabt wird. Die Zahlen sind trotzdem einigermaßen nützlich für mich gewesen. Die oben beschriebene Funktion wird durch FileCompare_noHash_2 verwendet.



  • Ich würde hier explizit memcmp verwenden für den Vergleich. Klar, man kann hoffen dass std::array::operator == ne passende Spezialisierung hat oder der Compiler schlau genug ist die char-Vergleichs-Schleife zu nem memcmp zu optimieren. Aber man kann es auch direkt selbst hinschreiben und sich sicher sein 😉

    Weitere Optimierung wird dann ... schwierig. Weil man dann unterscheiden müsste ob die Files vom selben Datenträger kommen oder nicht. Auf dem selben Datenträger wären sehr grosse Puffer von Vorteil und abwechselnd Lesen -- speziell wenn es HDDs sind. Bei unterschiedlichen Datenträgern ist meist ne kleinere Puffergrösse besser und gleichzeitig lesen (mit async IO oder zwei Threads).

    Und dann kann man natürlich noch den Vergleich in einen eigenen Thread auslagern. Also zwei Sets an Puffern verwenden und dann gleichzeitig Lesen und Vergleichen.


    Wobei es gut sein kann dass man mit passender Puffergrösse selbst mit der einfachen Variante (single threaded, synchron) in den meisten Fällen close-to-optimal Performance schaffen wird. Jedes vernünftige OS macht ja read-ahead. Man muss nur schauen dass man den read-ahead Mechanismus nicht ohne es zu wollen deaktiviert -- was AFAIK passiert wenn man zu grosse Puffer verwendet. 64 oder 128 kB sollte "safe" sein.


Anmelden zum Antworten