Optimize pathlib.PurePath.relative_to walk up case

[heikkitoivonen]

Feature or enhancement

Proposal:

pathlib.PurePath.relative_to method has a loop, which builds parents through every iteration of the loop. This makes it slow if we end up looping more than once. We could improve performance by caching the parents when looping multiple times.

The difficult part is how to make the changes so that they do not slow down two special cases:

• path == self
• we loop exactly once

So far all my attempts to improve this either slow down one or both of the above cases, which is why I have not yet done a PR. But if we could figure out ways to not slow down the above two, then the savings would be significant.

The best I have been able to come up with (I can make a PR if this looks good enough):

No changes if path == self
break on 1st loop, walk_up=False: 1.01x slower
1 level up: 1.09x slower
2 levels up: 1.25x faster
3 levels up: 1.46x faster

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

[heikkitoivonen]

I attached my patch in case someone else wants to take a stab at it.

diff --git a/Lib/pathlib/__init__.py b/Lib/pathlib/__init__.py
index 44f967eb12d..208c4854626 100644
--- a/Lib/pathlib/__init__.py
+++ b/Lib/pathlib/__init__.py
@@ -486,9 +486,16 @@ def relative_to(self, other, *, walk_up=False):
         if not hasattr(other, 'with_segments'):
             other = self.with_segments(other)
         parts = []
+        parents = None
         for path in chain([other], other.parents):
-            if path == self or path in self.parents:
+            if path == self:
                 break
+
+            if parents is None:
+                parents = set(self.parents) if walk_up else chain(self.parents)
+
+            if path in parents:
+                 break
             elif not walk_up:
                 raise ValueError(f"{str(self)!r} is not in the subpath of {str(other)!r}")
             elif path.name == '..':

[heikkitoivonen]

Also attached my benchmark.

import pyperf
from pathlib import PurePath

P = PurePath('a/b')
P_UP_1 = PurePath('a/b/c')
P_UP_2 = PurePath('a/b/c/d')
P_UP_3 = PurePath('a/b/c/d/e')


def bench_pathlib_self():
    P.relative_to(P)

def bench_pathlib1_nowalk():
    try:
        P.relative_to(P_UP_1)
        assert False
    except ValueError:
        pass

def bench_pathlib1_walk():
    P.relative_to(P_UP_1, walk_up=True)

def bench_pathlib2_walk():
    P.relative_to(P_UP_2, walk_up=True)

def bench_pathlib3_walk():
    P.relative_to(P_UP_3, walk_up=True)

def add_benchmarks(runner):
    runner.bench_func(
        "pathlib_self",
        bench_pathlib_self
    )
    runner.bench_func(
        "pathlib1_nowalk",
        bench_pathlib1_nowalk
    )
    runner.bench_func(
        "pathlib1_walk",
        bench_pathlib1_walk
    )
    runner.bench_func(
        "pathlib2_walk",
        bench_pathlib2_walk
    )
    runner.bench_func(
        "pathlib3_walk",
        bench_pathlib3_walk
    )

if __name__ == "__main__":
    runner = pyperf.Runner()
    add_benchmarks(runner)

[picnixz]

In the future can you avoid attaching the files please and directly paste them as comments? it's a bit annoying to always download files to look at them.

[picnixz]

For the parents property, there is a really important comment:

# The value of this property should not be cached on the path object,
# as doing so would introduce a reference cycle.

I don't think we can cache the parents computation (unless you're talking about something else)

[heikkitoivonen]

I believe the comment means that we can not cache it permanently as a data member, but that we should still be able to cache it in a temporary variable in a function.

[picnixz]

I'm not entirely sure about it though so I'll ask the maintainer @barneygale. He can also decide whether the improvement is worth or not (but he may take a while to reply)

One rule we also apply to performance improvements is whether the (active) maintainer wants them or not (they usually have the final say).