[Bug libstdc++/106014] New: Overload std::distance for filesystem::recursive_directory_iterator

redi at gcc dot gnu.org gcc-bugzilla@gcc.gnu.org
Fri Jun 17 11:16:11 GMT 2022


            Bug ID: 106014
           Summary: Overload std::distance for
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
  Target Milestone: ---


A user reported that a C++ program (using GCC) to count the number of files
under a directory is 5x slower than the Rust equivalent. The reason is that
dereferencing a directory iterator has to construct a filesystem::path, which
is expensive. Avoiding the dereference improves it a lot, but it's still 2x

By defining a specialized overload of std::distance for
filesystem::recursive_iterator we can double the speed of the C++ version and
slightly beat the Rust code that uses the walkdir crate (although the jwalk
crate is still faster).

The custom overload looks like this:

--- a/libstdc++-v3/include/bits/fs_dir.h
+++ b/libstdc++-v3/include/bits/fs_dir.h
@@ -44,6 +44,10 @@ namespace std _GLIBCXX_VISIBILITY(default)

+  ptrdiff_t
+  distance(filesystem::recursive_directory_iterator,
+          filesystem::recursive_directory_iterator);
 namespace filesystem
   /** @addtogroup filesystem
@@ -545,6 +549,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
     filesystem::remove_all(const path&, error_code&);
     friend uintmax_t
     filesystem::remove_all(const path&);
+    friend ptrdiff_t
+    std::distance(recursive_directory_iterator, recursive_directory_iterator);

   /// @relates std::filesystem::recursive_directory_iterator @{

--- a/libstdc++-v3/src/c++17/fs_dir.cc
+++ b/libstdc++-v3/src/c++17/fs_dir.cc
@@ -559,3 +564,25 @@ fs::recursive_directory_iterator::__erase(error_code*

   return *this;
+std::distance(fs::recursive_directory_iterator first,
+             fs::recursive_directory_iterator last)
+  if (first == last)
+    return 0;
+  if (last == fs::recursive_directory_iterator())
+    {
+      first._M_dirs->options |= __directory_iterator_filename_only;
+      first._M_dirs->top().path.clear();
+    }
+  ptrdiff_t d = 0;
+  do
+    ++d;
+  while (++first != last);
+  return d;

(Additional changes are needed to export the symbols from the shared lib).

The libstdc++ code for actually walking directories is reasonably efficient,
all the overhead is in creating the path objects that are required for the
public API. So the trick is to avoid storing the path when we increment the
iterator, because we know that it will never be needed by std::distance. This
is only possible when using ::dirfd and ::openat to recurse into directories,
because without those we do need the path. For an OS without those POSIX
functions the custom std::distance will be no faster than the naive handwritten
loop (but no slower).

It should be worth doing for filesystem::directory_iterator too, but I haven't
benchmarked that. I think that would just require clearing the path stored in
the _Dir.

More information about the Gcc-bugs mailing list