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

[hustbaer]

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.

[HarteWare]

@hustbaer Danke für die zusätzlichen Hinweise.
Um das Thema im Rahmen zu halten war mein Ziel, ein einfach gestricktes "standard C++", single-threaded Programm ohne (explizit) OS-spezifische Funktionen zu verwenden, auch um einfach std::filesystem mal auszuloten aber auch überhaupt kennenzulernen. Das wird nicht "perfekt" sein bei weitem. Allein dieses "inode"-Thema habe ich bei anderer SW auch schon gesehen, und darauf hat man mit std::filesystem gar keinen Zugriff. D. h. ich habe eine einfache is_duplicate Funktion, das werde ich demnächst noch mit dem Rest verknüpfen und dann lass ich's erstmal gut sein.

Ich hab ja von dem Ganzen nicht so viel Ahnung, aber ich interpretiere das so, dass GCC die schlaue memcmp Optimierung durchführt, man kann also eigentlich immer getrost std::equal verwenden (und std::array::operator== verwendet (hier) auch std::equal):

// [gcc/libstdc++-v3/include/std/array]
// ...
  // Array comparisons.
  template<typename _Tp, std::size_t _Nm>
  [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
  inline bool operator==(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
    { return std::equal(__one.begin(), __one.end(), __two.begin()); }
// ..

// [gcc/libstdc++-v3/include/bits/stl_algobase.h]
  template<bool _BoolType>
    struct __equal
    {
      template<typename _II1, typename _II2>
	_GLIBCXX20_CONSTEXPR
	static bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
	{
	  for (; __first1 != __last1; ++__first1, (void) ++__first2)
	    if (!(*__first1 == *__first2))
	      return false;
	  return true;
	}
    };

  template<>
    struct __equal<true>
    {
      template<typename _Tp>
	_GLIBCXX20_CONSTEXPR
	static bool equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
	{
	  if (const size_t __len = (__last1 - __first1))
	    return !std::__memcmp(__first1, __first2, __len);
	  return true;
	}
    };
// ...
  template<typename _II1, typename _II2>
    _GLIBCXX20_CONSTEXPR
    inline bool __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
    {
      typedef typename iterator_traits<_II1>::value_type _ValueType1;
      const bool __simple = ((__is_integer<_ValueType1>::__value
			      || __is_pointer<_ValueType1>::__value)
			     && __memcmpable<_II1, _II2>::__value);
      return std::__equal<__simple>::equal(__first1, __last1, __first2);
    }

  template<typename _II1, typename _II2>
    _GLIBCXX20_CONSTEXPR
    inline bool __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
    {
      return std::__equal_aux1(std::__niter_base(__first1), std::__niter_base(__last1), std::__niter_base(__first2));
    }
// ...
  template<typename _II1, typename _II2>
    _GLIBCXX20_CONSTEXPR
    inline bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
      __glibcxx_function_requires(_EqualOpConcept<
	    typename iterator_traits<_II1>::value_type,
	    typename iterator_traits<_II2>::value_type>)
      __glibcxx_requires_can_increment_range(__first1, __last1, __first2);

      return std::__equal_aux(__first1, __last1, __first2);
    }

Aber ich sehe den Punkt, man kann ja auch einfach <cstring> und std::memcmp verwenden, warum nicht, ja.

[HarteWare]

Hier jetzt ein aktualisiertes Beispielprogramm:

#include <array>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <unordered_map>
#include <vector>

namespace fs = std::filesystem;
static constexpr std::streamsize BufSize{ 4096 };

template<std::streamsize BufSize>
bool is_duplicate_file(const fs::directory_entry& file_a, const fs::directory_entry& file_b) {
    if (!file_a.is_regular_file() || !file_b.is_regular_file()) {
        return false;
    }
    if (fs::equivalent(file_a, file_b)) {
        return true;
    }
    if (file_a.file_size() != file_b.file_size()) {
        return false;
    }

    std::ifstream a_in{ file_a.path(), std::ios::binary };
    std::ifstream b_in{ file_b.path(), std::ios::binary };
    if (!a_in || !b_in) {
        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> buf_a{};
    std::array<char, BufSize> buf_b{};
    while (a_in && b_in) {
        a_in.read(buf_a.data(), BufSize);
        b_in.read(buf_b.data(), BufSize);
        /* Seems superfluous since what can fail besides hitting EOF on ifstream::read().
        if (a_in.fail() && !a_in.eof() || a_in.bad() || b_in.fail() && !b_in.eof() || b_in.bad()) {
            throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
        }
        */
        if (std::memcmp(buf_a.data(), buf_b.data(), BufSize))
            return false;
    }
    return true;    
}

auto build_file_index(const fs::path& start_path) {
    std::unordered_multimap<std::uintmax_t, fs::directory_entry> files_by_size;
    for (const auto& entry : fs::recursive_directory_iterator{ start_path }) {
        if (entry.is_regular_file()) {
            files_by_size.emplace(entry.file_size(), entry);
        }
    }
    return files_by_size;
}

auto find_duplicate_files(const auto& files) {
    std::unordered_map<fs::path, std::vector<fs::path>> dupes;
    for (auto entry = files.begin(); entry != files.end(); ) {
        auto range{ files.equal_range(entry->first) };
        int idx_i{};
        std::vector<bool> matched(std::distance(range.first, range.second), false);  // std::unordered_map<fs::path, bool> works, too!
        for (auto i = range.first; i != range.second; ++i, ++idx_i) {
            int idx_j{ idx_i + 1 };
            for (auto j = std::next(i); j != range.second; ++j, ++idx_j) {
                if (!matched[idx_i] && !matched[idx_j] && is_duplicate_file<BufSize>(i->second, j->second)) {
                    dupes[i->second.path()].emplace_back(j->second.path());
                    matched[idx_j] = true;
                }
            }
        }
        entry = range.second;
    }
    return dupes;
}

void print_dupes(const auto& dupes) {
    for (const auto& a : dupes) {
        std::cout << "\nReference: " << a.first << '\n';
        for (const auto& b : a.second) {
            std::cout << "Duplicate: " << b << '\n';
        }
    }
    std::cout << "\nFound a total of " << dupes.size() << " duplicate groups.\n\n";
}

int main(int argc, char* argv[])
try {
    if (argc != 2) {
        std::cout << "Program expects one argument: <Starting path>\n";
        return 1;
    }
    
    fs::path start_path{ argv[1] };
    if (!fs::exists(start_path)) {
        std::cout << "Provided argument is not an existing path.\n";
        return 2;
    }
    
    print_dupes(
        find_duplicate_files(
            build_file_index(start_path)));
}
catch (const fs::filesystem_error& e) {
    std::cerr << e.what() << '\n';
    return e.code().value();
}
catch (const std::runtime_error& e) {
    std::cerr << e.what() << '\n';
    return -2;
}
catch (...) {
    std::cerr << "Unhandled exception!\n";
    return -1;
}

Edit 1: Ich hatte beim Programmieren auch an std::unordered_map<fs::path, bool> gedacht, was sich performance-technisch nicht viel schenkt mit std::vector<bool>. Inzwischen wurde ich darauf hingewiesen, dass man auch einfach std::unordered_set<fs::path> verwenden könnte - auch von der Performance her ähnlich, aber wahrscheinlich eleganter als dieser Pfusch mit den Indizes.
Die Idee war klar, wenn z. B. Dateien A, B, C mit Größe X geprüft werden, und ich habe bereits erkannt, dass Datei B mit A identisch sind, dann brauche ich gar nicht erst versuchen, Datei B auch noch mit C zu vergleichen (das wäre sinnlos, wenn B==C, dann wäre C bereits gegen A gefunden worden).

Edit 2:
Jetzt so:

auto find_duplicate_files(const auto& files) {
    std::unordered_map<fs::path, std::vector<fs::path>> duplicates;
    std::unordered_set<fs::path> matched;
    for (auto left = files.begin(); left != files.end(); ) {
        auto range = files.equal_range(left->first);
        left = range.second;
        for (auto ref_it = range.first; ref_it != range.second; ++ref_it) {
            if (matched.contains(ref_it->second.path())) {
                continue;
            }
            for (auto file_it = std::next(ref_it); file_it != range.second; ++file_it) {
                if (!matched.contains(file_it->second.path()) && is_duplicate_file<BufSize>(ref_it->second, file_it->second)) {
                    matched.emplace(file_it->second.path());
                    duplicates[ref_it->second.path()].emplace_back(file_it->second.path());
                }
            }
        }
    }
    return duplicates;
}