GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — GH-102613: Fast recursive globbing in `pathlib.Path.glob()` by barneygale · Pull Request #104512 · python/cpython

Conversation

@barneygale

@barneygale barneygale commented May 15, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

This PR introduces a 'walk-and-match' strategy for handling glob patterns that include a non-terminal ** wildcard, such as **/*.py. For this example, the previous implementation recursively walked directories using os.scandir() when it expanded the ** component, and then scanned those same directories again when expanded the *.py component. This is wasteful.

In the new implementation, any components following a ** wildcard are used to build a re.Pattern object, which is used to filter the results of the recursive walk. A pattern like **/*.py uses half the number of os.scandir() calls; a pattern like **/*/*.py a third, etc.

This new algorithm does not apply if either:

  1. The follow_symlinks argument is set to None (its default), or
  2. The pattern contains .. components.

In these cases we fall back to the old implementation.

This PR also replaces selector classes with selector functions. These generators directly yield results rather calling through to their successors. A new internal Path._glob() method takes care to chain these generators together, which simplifies the lazy algorithm and slightly improves performance. It should also be easier to understand and maintain.

Performance for the original #102613 repro case, with 400 nested a/ directories, and matching treatment of symlinks and hidden files:

$ ../python -m timeit -s 'import glob' 'print(glob.glob("**/*", recursive=True, include_hidden=True))'
5 loops, best of 5: 66.2 msec per loop
$ ../python -m timeit -s 'from pathlib import Path' 'print(list(Path(".").rglob("**/*", follow_symlinks=True)))'
10 loops, best of 5: 22.7 msec per loop  # before this PR
10 loops, best of 5: 16.5 msec per loop  # after this PR

These results were from an SSD. The improvement will be greater for slow storage (e.g. network-mounted volumes).

  • Issue: Path.rglob performance issues in deeply nested directories compared to glob.glob(recursive=True) #102613

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

AlexWaygood reacted with rocket emoji
All reactions
  • 🚀 1 reaction
@barneygale
pythonGH-102613: Simplify implementation of pathlib.Path.glob()
7a58251
This commit replaces selector classes with selector functions. These
generators directly yield results rather calling through to their
successor. A new internal `Path._glob()` takes care to chain these
generators together, which simplifies the lazy algorithm and slightly
improves performance.
@barneygale barneygale added performance Performance or resource usage topic-pathlib labels May 15, 2023
@bedevere-bot bedevere-bot added the awaiting core review label May 15, 2023
@bedevere-bot bedevere-bot mentioned this pull request May 15, 2023
Path.rglob performance issues in deeply nested directories compared to glob.glob(recursive=True) #102613
Closed
barneygale added 2 commits May 15, 2023 19:37
@barneygale
Speed up matching *
d5b1836
@barneygale
Add comments, docstrings.
d5c86c6
@barneygale barneygale mentioned this pull request May 17, 2023
GH-77609: Add follow_symlinks argument to pathlib.Path.glob() #102616
Merged
barneygale added 2 commits May 18, 2023 19:06
@barneygale
Merge branch 'main' into pythongh-102613-remove-selector-classes
53dcb79
@barneygale
Merge branch 'main' into pythongh-102613-remove-selector-classes
6da6a83
@barneygale
barneygale marked this pull request as draft May 30, 2023 17:39
@bedevere-bot bedevere-bot removed the awaiting core review label May 30, 2023
barneygale added 3 commits May 30, 2023 23:20
@barneygale
Merge branch 'main' into pythongh-102613-remove-selector-classes
73ed81d
@barneygale
Add support for matching files recursively.
4005619
@barneygale
Implement walk-and-match algorithm.
9401d36
@barneygale barneygale changed the title GH-102613: Simplify implementation of pathlib.Path.glob() GH-102613: Fast recursive globbing in pathlib.Path.glob() May 31, 2023
barneygale added 3 commits May 31, 2023 20:56
@barneygale
Fix up docs, news blurb.
b217587
@barneygale
Fix comment
de7e857
@barneygale
Fix handling of newlines in filenames.
d1023c7
@barneygale
barneygale marked this pull request as ready for review May 31, 2023 20:36
@bedevere-bot bedevere-bot added the awaiting core review label May 31, 2023
@barneygale

barneygale commented May 31, 2023

Copy link
Copy Markdown
Contributor Author

@zooba here's the promised walk-and-match implementation!

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

zooba
zooba reviewed Jun 1, 2023
View reviewed changes

@zooba zooba left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This seems fine, there's potentially a few simplifications, but it looks like a great improvement over the existing code.

Do we need any new tests to specifically trigger anything that behaves differently?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

barneygale reacted with thumbs up emoji
All reactions
  • 👍 1 reaction
Comment thread Lib/pathlib.py Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Lib/pathlib.py Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Lib/pathlib.py Resolved

Uh oh!

There was an error while loading. Please reload this page.

barneygale added 5 commits June 1, 2023 18:12
@barneygale
Speed up recursive selection
ad33eec
@barneygale
Exclude self from walk-and-match matching.
064efdb
@barneygale
Optimize walk-and-match logic.
14c6a58
@barneygale
Consume adjacent '**' segments before considering use of matching.
04720bd
@barneygale
Add some more tests for complex patterns.
9c6b44f
@barneygale

barneygale commented Jun 1, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor Author

Thanks for the review! I've added a few more tests exercising .. and ** segments.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@barneygale
Drop test case that doesn't work on Windows.
4cfb836
`..` components are resolved lexically, rather than after symlinks.
@barneygale
barneygale requested a review from zooba June 6, 2023 18:25
zooba
zooba approved these changes Jun 6, 2023
View reviewed changes
@bedevere-bot bedevere-bot added awaiting merge and removed awaiting core review labels Jun 6, 2023
@barneygale
barneygale merged commit 24af451 into python:main Jun 6, 2023
@bedevere-bot bedevere-bot removed the awaiting merge label Jun 6, 2023
@barneygale barneygale mentioned this pull request Feb 6, 2024
Speed up pathlib.Path.glob() by removing redundant regex matching #115060
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@zooba zooba zooba approved these changes

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

performance Performance or resource usage topic-pathlib

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

3 participants

@barneygale @zooba @bedevere-bot
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.