Speedup posixpath.abspath() for relative paths

[nineteendo]

Feature or enhancement

Proposal:

When normalising a relative path, we don't need to process the cwd as it's already normalised, which could get expensive if it's long:

< _Py_normpath_and_size(wchar_t *path, Py_ssize_t size, Py_ssize_t *normsize)
---
> _Py_normpath_and_size(wchar_t *path, Py_ssize_t size, Py_ssize_t start, Py_ssize_t *normsize)
2397a2398,2402
>         return path;
>     }
>     // Start beyond end of path
>     if (start >= size) {
>         *normsize = size;
2457a2463,2467
>     // Skip past cwd
>     if (path + start > p1) {
>         p1 = p2 = path + start;
>         lastC = *(p1-1);
>     }
2525c2535
<     return _Py_normpath_and_size(path, size, &norm_length);
---
>     return _Py_normpath_and_size(path, size, 0, &norm_length);

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

Linked PRs

• gh-117587: Add C implementation of os.path.abspath #117855

[erlend-aasland]

posixpath.abspath is an 8 line implementation. We strive to keep the code base readable and maintainable. Do the added complexity and code duplication justify the speedup¹?

Footnotes

1. moreover, a benchmark should be provided ↩

[nineteendo]

Do the added complexity and code duplication justify the speedup

No, because it's a Python implementation, it's WAY slower than the old code using posix._path_normpath().

But, comparing it with the Python implementation of normpath() shows that this approach can work. We should either add cwd support to posix._path_normpath(), or write a separate posix._path_abspath(). @barneygale, is this something you could achieve?

[barneygale]

I don't have time to pursue it, but this may achieve what you're describing:

diff --git a/Lib/posixpath.py b/Lib/posixpath.py
index 0e8bb5ab10..54d325fe28 100644
--- a/Lib/posixpath.py
+++ b/Lib/posixpath.py
@@ -386,20 +386,13 @@ def normpath(path):
 
 def abspath(path):
     """Return an absolute path."""
-    path = os.fspath(path)
-    if isinstance(path, bytes):
-        if not path.startswith(b'/'):
-            path = join(os.getcwdb(), path)
-    else:
-        if not path.startswith('/'):
-            path = join(os.getcwd(), path)
-    return normpath(path)
+    return realpath(path, querying=False)
 
 
 # Return a canonical path (i.e. the absolute location of a file on the
 # filesystem).
 
-def realpath(filename, *, strict=False):
+def realpath(filename, *, strict=False, querying=True):
     """Return the canonical path of the specified filename, eliminating any
 symbolic links encountered in the path."""
     filename = os.fspath(filename)
@@ -433,7 +426,7 @@ def realpath(filename, *, strict=False):
     # Whether we're calling lstat() and readlink() to resolve symlinks. If we
     # encounter an OSError for a symlink loop in non-strict mode, this is
     # switched off.
-    querying = True
+    #querying = True
 
     while rest:
         name = rest.pop()

You'll need to add a little private helper function to avoid exposing a new querying argument without consensus.

[nineteendo]

That's even slower:

absolute
50000 loops, best of 5: 8.05 usec per loop # after
10000 loops, best of 5: 20.2 usec per loop # after realpath
# -> 2.51x slower
relative
10000 loops, best of 5: 23.6 usec per loop # after
10000 loops, best of 5: 35.1 usec per loop # after realpath
# -> 1.49x slower

We really need a C implementation for this idea.

[barneygale]

We really need a C implementation for this idea.

Are you planning to write this implementation? If not I'll close this issue - the bug tracker isn't the right place for unproven optimization targets.

[nineteendo]

Are you planning to write this implementation?

I sadly can not, I don't understand how the C implementation works.

If not I'll close this issue - the bug tracker isn't the right place for unproven optimization targets.

OK, here's a more extreme benchmark to prove this would work:

python -m timeit -s "import os, test; os.chdir('/Users/wannes' + '/a' * 505)" "test.abspath1('')" && python -m timeit -s "import os, test; os.chdir('/Users/wannes' + '/a' * 505)" "test.abspath2('')"
5000 loops, best of 5: 82.4 usec per loop # before
5000 loops, best of 5: 77.5 usec per loop # after
# -> 4.9 usec faster (most time is spent retrieving the cwd)

Let's break down the time loss:

python -m timeit -s "import os; os.chdir('/Users/wannes' + '/a' * 505)" "os.getcwd()" && python -m timeit -s "import os.path" "os.path.normpath('/Users/wannes' + '/a' * 505)"
5000 loops, best of 5: 76.8 usec per loop # time spent retrieving the cwd
100000 loops, best of 5: 2.56 usec per loop # time spent normalising the cwd

Two observations:

1. os.getcwd() is really slow in this case, is there anything we can do about that?
2. os.path.normpath() is doing roughly 2.56 micro seconds useless work, it could be done in a couple nano seconds by skipping past the cwd.

[barneygale]

Theoretical speedups are not a good use of the issue tracker. Without a patch to discuss there's nothing more to do here.

[nineteendo]

OK, here's my suggested patch, add a parameter start to _Py_normpath_and_size() and skip that many characters:

cpython/Python/fileutils.c

Lines 2414 to 2415 in 733e56e

	// Skip leading '.\'
	if (p1[0] == L'.' && IS_SEP(&p1[1])) {

+    // Skip start
+    if (start > 0) {
+        path += start;
+        p1 = p2 = minP2 = path;
+        lastC = *(path - 1);
+    }
     // Skip leading '.\'
-    if (p1[0] == L'.' && IS_SEP(&p1[1])) { 
+    else if (p1[0] == L'.' && IS_SEP(&p1[1])) {

I would love to try this, but I have not the slightest clue how to add arguments to this function and its callers.

[nineteendo]

@eryksun, could you help me with this?

[eryksun]

The implementation of the new start parameter in _Py_normpath_and_size() should still process the beginning of the path to set up minp2 to protect the drive/share and root. Keep in mind that it could be normalizing a path with an arbitrary number of sequential ".." components, which should be able to consume the path up to the root. The start parameter should only affect the initial p1 and p2 pointers and lastC. It shouldn't increment path. That's the return value that points to the beginning of the normalized path.

I wouldn't expose start as a new parameter of os.path.normpath(). I'd implement _path_abspath() in "Modules/posixmodule.c". Special case an empty string or single "." to return the working directory. Otherwise, on Windows, call _Py_normpath_and_size() with start as 0, followed by _PyOS_getfullpathname(). On POSIX, if the path starts with "/", call _Py_normpath_and_size() with start as 0. Otherwise join it with the working directory and call _Py_normpath_and_size() with start as the index of the first character of the input path.

The PR may as well fix _path_normpath() at the same time, to support an empty path string without requiring the or "." hack in the Python wrapper.

Like the normpath() wrapper, the abspath() wrapper would support a bytes path via os.fsdecode() and os.fsencode().

[nineteendo]

The implementation of the new start parameter in _Py_normpath_and_size() should still process the beginning of the path to set up minp2 to protect the drive/share and root. Keep in mind that it could be normalizing a path with an arbitrary number of sequential ".." components, which should be able to consume the path up to the root. The start parameter should only affect the initial p1 and p2 pointers and lastC. It shouldn't increment path. That's the return value that points to the beginning of the normalized path.

Sorry for my misunderstanding of the code, in the Python implementation everything is way clearer. Could something like this work?

cpython/Python/fileutils.c

Lines 2458 to 2459 in 733e56e

	/* if pEnd is specified, check that. Else, check for null terminator */
	for (; !IS_END(p1); ++p1) {

+    if (path + start > p1) {
+        p1 = p2 = path + start;
+        lastC = *(p1-1);
+    }
     /* if pEnd is specified, check that. Else, check for null terminator */
     for (; !IS_END(p1); ++p1) {

I'd implement _path_abspath() in "Modules/posixmodule.c". Special case an empty string or single "." to return the working directory.

In the long run, it should be implemented as a separate function, but first I want to try if this idea works.

[eryksun]

Add a Py_ssize_t start parameter, i.e. _Py_normpath_and_size(wchar_t *path, Py_ssize_t size, Py_ssize_t start, Py_ssize_t *normsize). Update the function declaration in "Include/internal/pycore_fileutils.h". Update the two call sites -- one in "Modules/posixmodule.c" and one in "Python/fileutils.c" -- to pass start as 0.

I'd copy os__path_normpath_impl as os__path_abspath_impl. It will just implement normpath() at first. Add a start: Py_ssize_t=0 parameter to its clinic input definition, and run Argument Clinic. Update the _Py_normpath_and_size() call to pass start instead of 0. Add OS__PATH_ABSPATH_METHODDEF to the posix_methods array. Rebuild Python. Now you'll have posix._path_abspath(path, start=0) to play with. When you're satisfied that the idea is working (i.e. all tests pass), revisit os__path_abspath_impl() to implement it in C. Remove the start: Py_ssize_t=0 parameter from the clinic input, and run Argument Clinic. Implement _path_abspath() for just POSIX at first, which you can test. Worry about the Windows implementation later, which should be easier anyway.

[nineteendo]

The idea is working, but I don't know what to do now:

/*[clinic input]
os._path_abspath

    path: object
    start: Py_ssize_t=0

Make path absolute.
[clinic start generated code]*/

static PyObject *
os__path_abspath_impl(PyObject *module, PyObject *path, Py_ssize_t start)
/*[clinic end generated code: output=69e536dbe18ecf3a input=29df0995bc21a9cf]*/
{
    if (!PyUnicode_Check(path)) {
        PyErr_Format(PyExc_TypeError, "expected 'str', not '%.200s'",
            Py_TYPE(path)->tp_name);
        return NULL;
    }
    Py_ssize_t len;
    wchar_t *buffer = PyUnicode_AsWideCharString(path, &len);
    if (!buffer) {
        return NULL;
    }
    Py_ssize_t abs_len;
    wchar_t *abs_path = _Py_normpath_and_size(buffer, len, start, &abs_len);
    PyObject *result = PyUnicode_FromWideChar(abs_path, abs_len);
    PyMem_Free(buffer);
    return result;
}

[eryksun]

The idea is working, but I don't know what to do now:

Work on getting posixpath.abspath() to work with the new builtin function, with all tests passing. If the performance is good enough, you could just rename the new builtin as _path_normpath_with_start(). Otherwise, implement it all in _path_abspath().

[erlend-aasland]

Reading through the posts in the issue, it is not clear to me if there is significant core dev support for this idea. It would surprise me if abspath() was used for hot code. The diff of the linked PR is considerable. Does the added complexity outweigh the cost of improving the performance of an API like abspath()?

@barneygale and @serhiy-storchaka: thoughts?

[barneygale]

I reckon it unlikely that abspath() is a performance bottleneck in anyone's code.

It's a slightly dangerous function too - it calls normpath() which can change the meaning of a path like symlink/... It would be a shame to double down on that behaviour by implementing it in C. OTOH I can't see any reasonable path towards fixing abspath().

[nineteendo]

The diff of the linked PR is considerable.

Note that I also extended the capabilities of _Py_normpath_and_size(). We could expose the start and explicit_curdir parameters, but I want to discuss that later:

• You can use start to faster normalise a path after joining with an already normalised path:

  result = join(path1, path2)
  result = normpath(result, start=len(result) - len(path2))

• And explicit_curdir helps to avoid ambiguity: ./C:foo has a vastly different meaning than C:foo.

And @eryksun asked specifically to implement abspath() in C.

I reckon it unlikely that abspath() is a performance bottleneck in anyone's code.

I just don't like the fact that we're normalising the cwd which is already normalised. Otherwise I definitely wouldn't have implemented it in C (there are other functions which we would benefit more of). And making it faster certainly doesn't hurt, right? I think it's even faster now that I got rid of the Python wrapper.

[eryksun]

And @eryksun asked specifically to implement abspath() in C.

We've implemented enough of the implementation in C in terms of normpath() and splitroot() that it becomes feasible. But if you want to expose a private _path_normpath_ex() that supports start and explicit_curdir, we could make use of that instead, and continue to implement abspath() itself in Python. (I'm not satisfied with the direction you've been pushed into with the implementation of the function in C, and backing off on that saves me the time of trying to implement a rewrite that would make everyone happy.)

[erlend-aasland]

When adding new code, we try hard to weigh a lot of different factors: performance, usefulness, maintainability, readability, code complexity, the number of lines added or subtracted, and backwards compatibility, to name a few. We also try to understand any opposition to a change; "why is my PR/issue being criticised or rejected?"

I do not think this change is worth it. Performance optimisations are nice, but only if the benefits outweigh the added cost. Adding a C implementation of existing Python code needs a really good reason. C code has a lot more maintenance overhead than Python code. If the added C code is already in a state where it needs refactoring, you're directly adding technical dept.

Moreover, there has been talk about rewriting C code in Python when the interpreter has become fast enough¹. This should also be taken into account when considering to add C code.

Footnotes

1. https://github.com/faster-cpython/ideas/issues/91 ↩

[erlend-aasland]

I'll leave it for Barney to decide if this issue should be kept open or if it should be closed.

[barneygale]

Sorry @nineteendo, I don't think the C implementation is worth it on balance, for the same reasons as Erlend gave.

[eryksun]

@barneygale, what about implementing _path_normpath_ex() that supports start and explicit_curdir? Supporting explicit_curdir is important for Windows to avoid problems with DOS device names (e.g. "./con") and named streams on single-letter filenames (e.g. "/C:spam"). Supporting start is an improvement for POSIX to avoid having to re-normalize the already-normalized current directory.

[nineteendo]

Hmm, start is not a great API as it doesn't work well for bytes. normpath('foo', 'C:/bar') would be better, but would be difficult to implement on Windows. I'll make a new pull request just to implement explicit_curdir.

[erlend-aasland]

I'll make a new pull request just to implement explicit_curdir.

No; please do not pollute the already too long list of open PRs. Discuss any possible change in an actionable issue first. If you need to open an experimental PR, do so on your own fork. The CPython repo is not the place for experimentation.

[nineteendo]

Discuss any possible change in an actionable issue first.

I have already done that: #119826