Path.rglob performance issues in deeply nested directories compared to glob.glob(recursive=True)

[ionite34]

Bug report

Pathlib.rglob can be orders of magnitudes slower than glob.glob(recursive=True)

With a 1000-deep nested directory, glob.glob and Path.glob both took under 1 second. Path.rglob took close to 1.5 minutes.

import glob
import os
from pathlib import Path

x = ""
for _ in range(1000):
    x += "a/"
    os.mkdir(x)
    
# ~ 0.5s
print(glob.glob("**/*", recursive=True))

# ~ 87s
print(list(Path(".").rglob("**/*")))

Linked PRs

• GH-102613: Improve performance of pathlib.Path.rglob() #104244
• GH-102613: Fix recursion error from pathlib.Path.glob() #104373
• GH-102613: Fast recursive globbing in pathlib.Path.glob() #104512
• gh-102613: Bump recursion limit to fix running test_pathlib under Coverage #105744
• [3.12] gh-102613: Bump recursion limit to fix running test_pathlib under Coverage (GH-105744) #105749

[barneygale]

At a depth of 400, on my system, 50% of the time is spent in PurePath.__hash__(), which is called because _RecursiveWildcardSelector uses a set to de-duplicate. We could drop the set if we handle symlinks uniformly - see #77609.

[barneygale]

I believe that the following PRs will need to land before we can properly address this issue:

• gh-89727: Fix pathlib.Path.walk RecursionError on deep trees #100282
• GH-73435: Implement recursive wildcards in pathlib.PurePath.match() #101398
• GH-101362: Omit path anchor from pathlib.PurePath()._parts #102476
• GH-81079: Add case_sensitive argument to pathlib.Path.glob() #102710

[barneygale]

It occurs to me that we only need to de-duplicate results if two or more ** tokens appear in the pattern. So we can improve the situation even without making symlink handling more consistent. I'll implement this soon, just need #102710 to land first I think.

Nevermind, I'm wrong :]

Nevernevermind, I was right!

[barneygale]

My plan here is:

1. Address Support recursive wildcards in pathlib.PurePath.match() #73435
   • PR available: GH-73435: Implement recursive wildcards in pathlib.PurePath.match() #101398
2. Address Add parameter @case_sensitive to glob and rglob in pathlib #81079
   • PR available: GH-81079: Add case_sensitive argument to pathlib.Path.glob() #102710
3. Implement glob() using walk() to avoid hitting recursion errors (this issue.)
4. Address pathlib.Path.glob does not follow symlinks #77609
5. Address pathlib strips trailing slash #65238
6. Implement **/ tokens using a "walk-and-filter" strategy (this issue.)

[barneygale]

Update to my previous plan:

1. Address Add parameter @case_sensitive to glob and rglob in pathlib #81079
   • PR: GH-81079: Add case_sensitive argument to pathlib.Path.glob() #102710
2. De-duplicate paths only when necessary (this issue.)
   • PR: GH-102613: Improve performance of pathlib.Path.rglob() #104244
3. Address pathlib.Path.glob causes OSError encountering symlinks to long filenames #87695
   • PR: GH-87695: Fix OSError from pathlib.Path.glob() #104292
4. Address [pathlib] Option so that OSError does not block glob in pathlib library #90208
   • PR: GH-90208: Suppress OSError exceptions from pathlib.Path.glob() #104141
5. Use walk() to implement recursive tokens (this issue.)
   • PR: GH-102613: Fix recursion error from pathlib.Path.glob() #104373
6. Address Add case_sensitive argument to pathlib.PurePath.match() #104484
   • PR: gh-104484: Add parameter @case_sensitive to pathlib.PurePath.match() function #104565
7. Address pathlib.Path.glob does not follow symlinks #77609
   • PR: GH-77609: Add follow_symlinks argument to pathlib.Path.glob() #102616
8. Address Support recursive wildcards in pathlib.PurePath.match() #73435
   • PR: GH-73435: Implement recursive wildcards in pathlib.PurePath.match() #101398
9. Use match() to implement symlink-following recursive tokens with subsequent segments (this issue.)
   • PR: GH-102613: Fast recursive globbing in pathlib.Path.glob() #104512

[barneygale]

Final PR available:

• GH-102613: Fast recursive globbing in pathlib.Path.glob() #104512

As a result of these changes, for the particular repro case in the original post with 1000 nested a/ directories, pathlib is now about 25x faster than glob.glob(), rather than 150x slower! 🎉

[barneygale]

Tis fixed! Most changes made it into 3.12, but a couple are 3.13-only.