copy.deepcopy memo lookup fails when __deepcopy__ returns None

[tonghuaroot]

Bug description

copy.deepcopy uses None as the memo-miss sentinel (memo.get(d, None)), so when an object's __deepcopy__ returns None, the memo hit is indistinguishable from a miss. The object gets deep-copied again on every subsequent reference instead of once.

This was introduced by gh-132657 / PR #138429 which replaced the old _nil = [] sentinel with None for free-threading performance.

import copy

call_count = 0

class C:
 def __deepcopy__(self, memo):
 global call_count
 call_count += 1
 memo[id(self)] = None
 return None

obj = C()
copy.deepcopy([obj, obj, obj])
print(call_count) # 3, expected 1

CPython versions tested on

main

Operating systems tested on

macOS

Linked PRs

• gh-154594: Fix copy.deepcopy() re-copying objects whose __deepcopy__ returns None #154819
• gh-154594: Fix deepcopy memo lookup when __deepcopy__ returns None #154595

[picnixz]

cc @eendebakpt

[picnixz]

I would say that returning None for __deepcopy__ only makes sense if you're... deepcopying a None.

[eendebakpt]

I see the point, but I am not sure we need to fix this.

• As was already noted, returning None for the deepcopy an object that is not None is a bit weird
• The reproducer makes changes to the memo. The documentation for deepcopy states that the memo should be treated as an opaque object.
• The issue is not a bug, but a missed optimization opportunity.

On the other hand, changing None to a private sentinel (as done in the pr) is not a big change.

[pochmann]

Alternative to the PR's sentinel, how about changing

 y = memo.get(d, None)
 if y is not None:
 return y

to this?

 if d is in memo:
 return memo[d]

In a little test I wrote, that was ~8 ns slower if the object already is in memo, but ~20 ns faster if the object isn't in memo yet. So quite possibly it's faster on average.

Also, I find it clearer. It's less code, it's direct instead of doubly-negated, and it doesn't leave y lying around for the reader to wonder whether/how that matters (like the current code does in non-return cases).

[eendebakpt]

I like the idea from @pochmann. It needs some careful benchmarking and perhaps some analysis of how often the hits and misses occur. @tonghuaroot Would you be interested?