Description

ionite34

opened on Mar 11, 2023

Issue body actions

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

Reacted by Barney Gale

Activity

1. ionite34

   added

   type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

   on Mar 11, 2023
2. ionite34

   changed the title [-]Pathlib.rglob performance issues in deeply nested directories compared to glob.glob(recursive=True)[/-] [+]Path.rglob performance issues in deeply nested directories compared to glob.glob(recursive=True)[/+] on Mar 11, 2023
3. AlexWaygood

   added

   performancePerformance or resource usagePerformance or resource usage

   topic-pathlib

   on Mar 12, 2023
4. barneygale commented on Mar 12, 2023

   

   barneygale

   on Mar 12, 2023

   Contributor

   More actions

   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.
5. barneygale

   added a commit that references this issue on Mar 12, 2023

   pythonGH-77609: Support following symlinks in `pathlib.Path.glob()`

   59dcdb1
6. barneygale commented on Mar 12, 2023

   

   barneygale

   on Mar 12, 2023

   Contributor

   More actions

   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

   Reacted by Ionite
7. barneygale commented on Mar 21, 2023

   

   barneygale

   on Mar 21, 2023

   Contributor

   More actions

   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!

   Reacted by Niels Lohmann
8. barneygale commented on Apr 9, 2023

   

   barneygale

   on Apr 9, 2023

   Contributor

   More actions

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

   Reacted by h-vetinari
9. barneygale

   added a commit that references this issue on May 6, 2023

   pythonGH-102613: Improve performance of `pathlib.Path.rglob()`

   e3d0923
10. barneygale commented on May 6, 2023

    

    barneygale

    on May 6, 2023

    Contributor

    More actions

    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

    Reacted by Ionite
11. barneygale

    added a commit that references this issue on May 7, 2023

    GH-102613: Improve performance of `pathlib.Path.rglob()` (GH-104244)

    c0ece3d
12. jbower-fb

    added a commit that references this issue on May 8, 2023

    pythonGH-102613: Improve performance of `pathlib.Path.rglob()` (pytho…

    f6943eb
13. carljm

    added a commit that references this issue on May 9, 2023

    Merge branch 'main' into inlinecomp2

    76077cd
14. barneygale

    added 3 commits that reference this issue on May 11, 2023

    pythonGH-102613: Fix recursion error from `pathlib.Path.glob()`

    71dc988

    GH-102613: Fix recursion error from `pathlib.Path.glob()` (GH-104373)

    cb88ae6

    pythonGH-102613: Simplify implementation of `pathlib.Path.glob()`

    7a58251
15. carljm

    added a commit that references this issue on May 16, 2023

    Merge branch 'main' into supermon

    a6dd626
16. barneygale

    added a commit that references this issue on May 18, 2023

    Merge branch 'main' into pythongh-102613-remove-selector-classes

    53dcb79
17. barneygale

    added 2 commits that reference this issue on May 29, 2023

    Merge branch 'main' into pythongh-102613-remove-selector-classes

    6da6a83

    Merge branch 'main' into pythongh-102613-remove-selector-classes

    73ed81d
18. barneygale commented on May 31, 2023

    

    barneygale

    on May 31, 2023

    Contributor

    More actions

    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! 🎉

    Reacted by Alex Waygood and Daniel Thoren

    Reacted by Hugo van Kemenade, Ahmed Kamal, bion howard and ljarosch
19. barneygale

    added a commit that references this issue on Jun 6, 2023

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

    24af451
20. barneygale commented on Jun 6, 2023

    

    barneygale

    on Jun 6, 2023

    Contributor

    More actions

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

    Reacted by Alex Waygood and Hugo van Kemenade
21. barneygale

    closed this as completedon Jun 6, 2023
22. ambv

    added a commit that references this issue on Jun 13, 2023

    pythongh-102613: Bump recursion limit to fix running test_pathlib und…

    a4ad5d6
23. barneygale

    added a commit that references this issue on Jun 13, 2023

    gh-102613: Bump recursion limit to fix running test_pathlib under Cov…

    4e80082
24. miss-islington

    added a commit that references this issue on Jun 13, 2023

    pythongh-102613: Bump recursion limit to fix running test_pathlib und…

    530af52
25. barneygale

    added a commit that references this issue on Jun 13, 2023

    [3.12] gh-102613: Bump recursion limit to fix running test_pathlib un…

    27426d8

Issue actions