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.)