Skip to content

GH-114847: Speed up posixpath.realpath()#114848

Merged
barneygale merged 23 commits intopython:mainfrom
barneygale:gh-114847
Apr 5, 2024
Merged

GH-114847: Speed up posixpath.realpath()#114848
barneygale merged 23 commits intopython:mainfrom
barneygale:gh-114847

Conversation

@barneygale
Copy link
Contributor

@barneygale barneygale commented Feb 1, 2024 •
edited
Loading

Apply the following optimizations to posixpath.realpath():

  • Remove use of recursion
  • Construct child paths directly rather than using join()
  • Use os.getcwd[b]() rather than abspath()
  • Use startswith(sep) rather than isabs()
  • Use slicing rather than split()
$ ./python -m timeit -s "from os.path import realpath" "realpath('.')"
100000 loops, best of 5: 2.74 usec per loop  # before
200000 loops, best of 5: 1.53 usec per loop  # after
# --> 1.79x faster

$ ./python -m timeit -s "from os.path import realpath" "realpath('..')"
100000 loops, best of 5: 2.9  usec per loop  # before
200000 loops, best of 5: 1.71 usec per loop  # after
# --> 1.7x faster

$ ./python -m timeit -s "from os.path import realpath" "realpath('../..')"
 50000 loops, best of 5: 4.1  usec per loop  # before
200000 loops, best of 5: 1.99 usec per loop  # after
# --> 2.06x faster

$ ./python -m timeit -s "from os.path import realpath" "realpath('Lib/test')"
50000 loops, best of 5: 8.06 usec per loop  # before
50000 loops, best of 5: 6.19 usec per loop  # after
# --> 1.3x faster

$ ./python -m timeit -s "from os.path import realpath" "realpath('Lib/test/nonexistent/..')"
20000 loops, best of 5: 12.6 usec per loop  # before
50000 loops, best of 5:  9.4 usec per loop  # after
# --> 1.34x faster

$ ./python -m timeit -s "from os.path import realpath" "realpath('/home/barney')"
50000 loops, best of 5: 6.41 usec per loop  # before
50000 loops, best of 5: 4.62 usec per loop  # after
# --> 1.39x faster

@barneygale
pythonGH-114847: Speed up posixpath.realpath()
0a4f60a 
Apply the following optimizations to `posixpath.realpath()`:

- Remove use of recursion
- Directly construct child paths rather than using `join()`
- Use `os.getcwd[b]()` rather than `abspath()`
- Use `startswith(sep)` rather than `isabs()`
@barneygale barneygale added the performance Performance or resource usage label Feb 1, 2024
@bedevere-app bedevere-app bot mentioned this pull request Feb 1, 2024
Closed
@barneygale
Copy link
Contributor Author

barneygale commented Apr 1, 2024

I've added a few wordy comments because:

  1. When I first read the code, it took me some time to really understand what seen is doing
  2. Applying tail call optimisation (this PR) further obscures the purpose of seen

Hopefully it's a bit easier for the next person to grok with the comments in place.

gpshead
gpshead reviewed Apr 1, 2024
View reviewed changes
Copy link
Member

@gpshead gpshead left a comment

Choose a reason for hiding this comment

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

I like that this gets rid of recursion.

encukou
encukou reviewed Apr 2, 2024
View reviewed changes
@barneygale
Copy link
Contributor Author

barneygale commented Apr 3, 2024

Given that symlinks are rare, perhaps I've actually slowed things down by checking in seen prior to running lstat(). I'll see if reverting that change is faster.

@encukou
Copy link
Member

encukou commented Apr 4, 2024

The introduction of a querying flag that's reset once changes behaviour, since rest can return back into an existing path.

Given a directory and a link to it:

$ mkdir a_dir
$ ln -s a_dir a_link

with Python 3.12 I get:

>>> os.path.realpath('foo/../a_link')
'/tmp/links/a_dir'

With this PR:

>>> os.path.realpath('foo/../a_link')
'/tmp/links/a_link'

The previous behaviour matches coreutils:

$ realpath -m foo/../a_link
/tmp/links/a_dir

@encukou
Copy link
Member

encukou commented Apr 5, 2024

Thanks. I see the other use of querying -- a symlink loop -- retains previous behaviour (which is tested), even though it doesn't match coreutils' realpath -m :/

$ mkdir a_dir
$ ln -s a_dir a_link
$ ln -s loop1 loop2
$ ln -s loop2 loop1
$ realpath -m loop1/../a_link/
/tmp/links/a_dir

>>> os.path.realpath('foo/../loop1/../a_link/')
'/tmp/links/a_link'

Guess that's one bug we need to let live.

encukou
encukou approved these changes Apr 5, 2024
View reviewed changes
Copy link
Member

@encukou encukou left a comment

Choose a reason for hiding this comment

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

LGTM, thank you!

@barneygale @encukou
Update Lib/posixpath.py
eed739a 
Co-authored-by: Petr Viktorin <encukou@gmail.com>
@barneygale
Copy link
Contributor Author

barneygale commented Apr 5, 2024

Thank you for the reviews!

@barneygale barneygale enabled auto-merge (squash) April 5, 2024 12:06
@barneygale barneygale merged commit abfa16b into python:main Apr 5, 2024
@barneygale
Copy link
Contributor Author

barneygale commented Apr 6, 2024

Thanks. I see the other use of querying -- a symlink loop -- retains previous behaviour (which is tested), even though it doesn't match coreutils' realpath -m :/

(For posterity:) I opened an issue about this: #117546

@barneygale barneygale mentioned this pull request Apr 10, 2024
Closed
diegorusso pushed a commit to diegorusso/cpython that referenced this pull request Apr 17, 2024
@barneygale @encukou @diegorusso
pythonGH-114847: Speed up posixpath.realpath() (python#114848)
c20c138 
Apply the following optimizations to `posixpath.realpath()`:

- Remove use of recursion
- Construct child paths directly rather than using `join()`
- Use `os.getcwd[b]()` rather than `abspath()`
- Use `startswith(sep)` rather than `isabs()`
- Use slicing rather than `split()`

Co-authored-by: Petr Viktorin <encukou@gmail.com>
@jwilk jwilk mentioned this pull request Jan 7, 2025
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@gpshead gpshead gpshead left review comments

@encukou encukou encukou approved these changes

Assignees

No one assigned

Labels

performance Performance or resource usage

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@barneygale @encukou @gpshead