gh-72793: C implementation of parts of copy.deepcopy #91610

eendebakpt · 2022-04-16T18:44:07Z

The original idea and implementation are from @Villemoes. The original issue has been inactive for a long time.

Benchmark on deepcopy of a dict and dataclass:

deepcopy dict: Mean +- std dev: [b] 7.28 us +- 0.27 us -> [d] 982 ns +- 24 ns: 7.41x faster
deepcopy dataclass: Mean +- std dev: [b] 6.49 us +- 0.07 us -> [d] 3.69 us +- 0.11 us: 1.76x faster

Geometric mean: 3.61x faster

Benchmark details

Test script

import pyperf
runner = pyperf.Runner()

setup="""
import copy

a={'list': [1,2,3,43], 't': (1,2,3), 'str': 'hello', 'subdict': {'a': True}}

from dataclasses import dataclass

@dataclass
class A:
    a : list
    b : str
    c : bool
    
dc=A([1,2,3], 'hello', True)
"""

runner.timeit(name=f"deepcopy dict", stmt=f"b=copy.deepcopy(a)", setup=setup)
runner.timeit(name=f"deepcopy dataclass", stmt=f"b=copy.deepcopy(dc)", setup=setup)

Fixes #72793

Pyperformance results

Pyperformance results show small speedup, although this could very well be a random fluctuation. (there are no explicit calls to deepcopy in the pyperformance tests)

2to3: Mean +- std dev: [base] 325 ms +- 5 ms -> [patch] 322 ms +- 4 ms: 1.01x faster
chaos: Mean +- std dev: [base] 87.8 ms +- 0.8 ms -> [patch] 88.3 ms +- 1.1 ms: 1.01x slower
float: Mean +- std dev: [base] 103 ms +- 2 ms -> [patch] 98.5 ms +- 2.5 ms: 1.04x faster
go: Mean +- std dev: [base] 163 ms +- 1 ms -> [patch] 165 ms +- 2 ms: 1.01x slower
json_dumps: Mean +- std dev: [base] 15.1 ms +- 0.5 ms -> [patch] 14.9 ms +- 0.1 ms: 1.01x faster
json_loads: Mean +- std dev: [base] 28.0 us +- 0.3 us -> [patch] 28.1 us +- 0.3 us: 1.01x slower
logging_format: Mean +- std dev: [base] 8.11 us +- 0.14 us -> [patch] 8.18 us +- 0.12 us: 1.01x slower
logging_silent: Mean +- std dev: [base] 133 ns +- 1 ns -> [patch] 130 ns +- 1 ns: 1.02x faster
meteor_contest: Mean +- std dev: [base] 128 ms +- 1 ms -> [patch] 126 ms +- 1 ms: 1.01x faster
nbody: Mean +- std dev: [base] 111 ms +- 2 ms -> [patch] 113 ms +- 2 ms: 1.01x slower
nqueens: Mean +- std dev: [base] 106 ms +- 1 ms -> [patch] 106 ms +- 1 ms: 1.00x slower
pathlib: Mean +- std dev: [base] 23.0 ms +- 0.4 ms -> [patch] 23.2 ms +- 0.7 ms: 1.01x slower
pickle: Mean +- std dev: [base] 10.5 us +- 0.1 us -> [patch] 10.6 us +- 0.4 us: 1.01x slower
pickle_dict: Mean +- std dev: [base] 30.9 us +- 0.2 us -> [patch] 31.3 us +- 0.3 us: 1.02x slower
pickle_list: Mean +- std dev: [base] 4.41 us +- 0.04 us -> [patch] 4.55 us +- 0.06 us: 1.03x slower
pyflate: Mean +- std dev: [base] 532 ms +- 8 ms -> [patch] 535 ms +- 4 ms: 1.01x slower
regex_compile: Mean +- std dev: [base] 163 ms +- 1 ms -> [patch] 165 ms +- 1 ms: 1.01x slower
regex_dna: Mean +- std dev: [base] 238 ms +- 2 ms -> [patch] 213 ms +- 1 ms: 1.12x faster
regex_effbot: Mean +- std dev: [base] 3.50 ms +- 0.03 ms -> [patch] 3.08 ms +- 0.03 ms: 1.14x faster
regex_v8: Mean +- std dev: [base] 29.2 ms +- 0.7 ms -> [patch] 25.8 ms +- 0.9 ms: 1.13x faster
richards: Mean +- std dev: [base] 57.4 ms +- 1.5 ms -> [patch] 58.2 ms +- 1.3 ms: 1.01x slower
scimark_fft: Mean +- std dev: [base] 447 ms +- 10 ms -> [patch] 452 ms +- 2 ms: 1.01x slower
scimark_lu: Mean +- std dev: [base] 142 ms +- 2 ms -> [patch] 145 ms +- 1 ms: 1.02x slower
scimark_sor: Mean +- std dev: [base] 155 ms +- 1 ms -> [patch] 156 ms +- 2 ms: 1.01x slower
scimark_sparse_mat_mult: Mean +- std dev: [base] 6.18 ms +- 0.11 ms -> [patch] 6.03 ms +- 0.06 ms: 1.02x faster
spectral_norm: Mean +- std dev: [base] 150 ms +- 7 ms -> [patch] 146 ms +- 3 ms: 1.02x faster
unpack_sequence: Mean +- std dev: [base] 52.6 ns +- 1.0 ns -> [patch] 52.2 ns +- 0.6 ns: 1.01x faster
unpickle_list: Mean +- std dev: [base] 5.77 us +- 0.06 us -> [patch] 5.88 us +- 0.10 us: 1.02x slower
xml_etree_parse: Mean +- std dev: [base] 176 ms +- 3 ms -> [patch] 173 ms +- 2 ms: 1.02x faster

Benchmark hidden because not significant (17): deltablue, fannkuch, hexiom, logging_simple, pickle_pure_python, pidigits, python_startup, python_startup_no_site, raytrace, scimark_monte_carlo, sqlite_synth, telco, unpickle, unpickle_pure_python, xml_etree_iterparse, xml_etree_generate, xml_etree_process

Geometric mean: 1.01x faster

Notes

eendebakpt · 2022-04-28T07:31:22Z

@pablogsal Would you be able to review this PR?

eendebakpt · 2022-05-27T20:49:20Z

@serhiy-storchaka As the latest core develop working on this file, would you be able to review this PR?

AA-Turner

I don't feel comfortable reviewing the C code, but you will need to add tests to ensure the fallback and C implementation have the same inputs/outputs/etc -- the easiest way would be to duplicate the tests and run one set for the C accelerator and one for the Python version.

A

Misc/NEWS.d/next/Core and Builtins/2022-04-16-20-21-13.gh-issue-72793.qc-BP-.rst

Lib/test/test_capi.py

eendebakpt · 2022-06-08T11:59:52Z

I don't feel comfortable reviewing the C code, but you will need to add tests to ensure the fallback and C implementation have the same inputs/outputs/etc -- the easiest way would be to duplicate the tests and run one set for the C accelerator and one for the Python version.

A

@AA-Turner The _deepcopy_fallback is only used for objects not handled by the C deepcopy method (and vice versa). therefore we cannot test both the fallback and C on the same inputs. The deepcopy is the public method (and _deepcopy_fallback is called via deepcopy), so I think we only need to test on deepcopy. If there are any tests you would like me to add, let me know.

Note: in earlier versions of the PR the fallback there was a funny try-except statement to fix a build problem. This I resolved by making _copy a builtin module.

AA-Turner · 2022-06-08T13:27:21Z

The _deepcopy_fallback is only used for objects not handled by the C deepcopy method (and vice versa). therefore we cannot test both the fallback and C on the same inputs.

If both functions exist and can be theoretically used, both must be tested. You can import copy._deepcopy_fallback and import _copy.deepcopy to test the functions independently. If I understand correctly, in your current patch _deepcopy_fallback is only ever called from the C layer. If so, you should make this more clear -- oftentimes the C accelerator has a pure Python fallback which implements the same method when the extension module can't be loaded.

A

tiran · 2022-06-08T16:53:42Z

Modules/Setup.bootstrap.in

@@ -25,6 +25,7 @@ _weakref _weakref.c

 # commonly used core modules
 _abc _abc.c
+_copy _copy.c


The build rule should be either added to Setup.bootstrap.in or Setup.stdlib.in rules. Is the module required to run setup.py? In case it it not required, it should not be added to the bootstrap file.

I don't think we have any documentation concerning new modules in the dev guide yet.

Modules/Setup.stdlib.in

Lib/copy.py

Modules/_copy.c

tiran · 2022-06-08T16:53:42Z

Modules/_copy.c

+    for (i = 0; i < N_DISPATCHERS; ++i) {
+        dd = &deepcopy_dispatch[i];
+        if (Py_TYPE(x) != dd->type)
+            continue;


It might be faster to replace the atomic types and dispatch types code with a _Py_hashtable_t table.

_hashopenssl.c has an example how to use the hash table API.

bedevere-bot · 2022-06-08T16:53:45Z

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

serhiy-storchaka · 2022-06-08T17:24:14Z

There are some issues with the copy module. I prefer to resolve them prior to adding the C implementation.

eendebakpt · 2022-06-08T17:54:27Z

The _deepcopy_fallback is only used for objects not handled by the C deepcopy method (and vice versa). therefore we cannot test both the fallback and C on the same inputs.

If both functions exist and can be theoretically used, both must be tested. You can import copy._deepcopy_fallback and import _copy.deepcopy to test the functions independently. If I understand correctly, in your current patch _deepcopy_fallback is only ever called from the C layer. If so, you should make this more clear -- oftentimes the C accelerator has a pure Python fallback which implements the same method when the extension module can't be loaded.

A

@tiran noted the fallback will be used by PyPy, so it must indeed be tested. I will add the required tests

tiran · 2022-06-08T18:09:12Z

We have helper code to block / force imports to test both pure and C accelerated features.

from test.support.import_helper import import_fresh_module

copy_py = import_fresh_module('copy', blocked=['_copy'])
try:
    copy_c = import_fresh_module('copy', fresh=['_copy'])
except ImportError:
    copy_c = None

eendebakpt · 2022-06-08T20:44:28Z

I addressed some of the review comments.

@serhiy-storchaka Could you indicate which issues with the copy module there are, and whether there already is a timeline on addressing them?

Lib/copy.py

Lib/test/test_capi.py

Co-authored-by: Adam Turner <9087854+AA-Turner@users.noreply.github.com>

serhiy-storchaka · 2022-06-09T04:40:22Z

@serhiy-storchaka Could you indicate which issues with the copy module there are, and whether there already is a timeline on addressing them?

See https://github.com/orgs/python/projects/9. Note that some issues are common for the pickle and copy modules. Some issues are about copying concrete classes, they can be ignored in this context. But #93627 is specially about inconsistency between implementations, it should be addressed first.

tiran

Good work so far!

If you pass PyObject *module to all functions then you can access the module state for free. PyState_FindModule is costly.
You have to provide callbacks to clear/free the module state.
We prefer a different approach to test C and Py implementations of a module.

tiran · 2022-06-09T10:58:47Z

Lib/test/test_copy_fallback.py

@@ -0,0 +1,60 @@
+"""Unit tests for the copy module without the C accelerator."""


We use a different approach to test pure Python and C accelerated code:

create a test class for C and Python implementation

remove import copy

replace copy.* with self.module....

py_copy = import_helper.import_fresh_module( 'copy', blocked=['_copy'] ) c_copy = import_helper.import_fresh_module( 'copy', fresh=['_copy'] ) class TestCopy: module = None def test_exceptions(self): self.assertIs(self.module.Error, self.module.error) self.assertTrue(issubclass(self.module.Error, Exception)) class TestCopyPy(TestCopy, unittest.TestCase): module = py_copy @unittest.skipUnless(c_copy, 'requires _copy') class TestCopyC(TestCopy, unittest.TestCase): module = c_copy

tiran · 2022-06-09T10:58:47Z

Lib/test/test_copy_fallback.py

+        # XXX: import_fresh_module() is supposed to leave sys.module cache untouched,
+        # XXX: but it does not, so we have to cleanup ourselves.


Please open a new bug report for this issue.

Modules/_copy.c

tiran · 2022-06-09T10:58:47Z

Modules/_copy.c

+static struct PyModuleDef copy_moduledef = {
+    PyModuleDef_HEAD_INIT,
+    "_copy",
+    "C implementation of deepcopy",
+    sizeof(PyObject *),
+    functions,
+    NULL,
+    NULL,
+    NULL,
+    NULL
+};


New code should use named struct initialization, e.g. .m_name = "_copy",.

Since you store a strong Python reference to a mutable object in the module state, you must provide traverse, clear, and free callbacks.

And please don't reuse the module state pointer as a PyObject *. It's a clever hack -- a bit too clever and surprising for the next person that reads the code. :)

Co-authored-by: Christian Heimes <christian@python.org>

bedevere-bot added the awaiting review label Apr 16, 2022

eendebakpt marked this pull request as draft Apr 16, 2022

eendebakpt marked this pull request as ready for review Apr 16, 2022

slimshady621 approved these changes May 2, 2022

View changes

bedevere-bot added awaiting core review and removed awaiting review labels May 2, 2022

AlexWaygood added the performance label May 4, 2022

eendebakpt mentioned this pull request May 12, 2022

Benchmark suggestion: deepcopy faster-cpython/ideas#379

Closed

eendebakpt mentioned this pull request May 13, 2022

Benchmark suggestion: deepcopy python/pyperformance#199

Closed

eendebakpt force-pushed the deepcopy_c_implementation branch from 83741a6 to 2f8e489 Compare Jun 7, 2022

eendebakpt requested review from rhettinger and markshannon as code owners Jun 7, 2022

eendebakpt force-pushed the deepcopy_c_implementation branch 2 times, most recently from af2a201 to 502c747 Compare Jun 7, 2022

AA-Turner added the extension-modules label Jun 7, 2022

AA-Turner reviewed Jun 7, 2022

View changes

Misc/NEWS.d/next/Core and Builtins/2022-04-16-20-21-13.gh-issue-72793.qc-BP-.rst Outdated Show resolved Hide resolved

Lib/test/test_capi.py Show resolved Hide resolved

eendebakpt and others added 12 commits Jun 8, 2022

add patch from https://bugs.python.org/issue28607

712cf74

add patch from https://bugs.python.org/issue28607

e190851

fix clinic; add _copy to build

0ffe82b

fix tests

357cba5

newline at end of file

3709279

rerun argument clinic

cb41a10

whitespace

e67f19a

📜🤖 Added by blurb_it.

d93d34a

fix docstring in setup.py

f684d88

make regen-stdlib-module-names

be0d187

whitespace

e5644da

add test to check the fallback is not called if not required

2d9266a

eendebakpt force-pushed the deepcopy_c_implementation branch from 2c18cb6 to c0fd5c9 Compare Jun 8, 2022

eendebakpt added 4 commits Jun 8, 2022

fix generated code

18dd609

fix clinic

103d3cf

fix build

0ef290e

add module to Setup.stdlib.in

1d6e2e9

[test] fix windows build

1dcceed

tiran requested changes Jun 8, 2022

View changes

bedevere-bot removed the awaiting core review label Jun 8, 2022

bedevere-bot added the awaiting changes label Jun 8, 2022

address review comments

6a9e458

eendebakpt requested a review from as a code owner Jun 8, 2022

eendebakpt added 2 commits Jun 8, 2022

fix build

e661a71

regen-configure

b0bf25e

AA-Turner reviewed Jun 8, 2022

View changes

Lib/copy.py Outdated Show resolved Hide resolved

Lib/copy.py Show resolved Hide resolved

Lib/test/test_capi.py Show resolved Hide resolved

eendebakpt and others added 2 commits Jun 8, 2022

Update Lib/copy.py

830236e

Co-authored-by: Adam Turner <9087854+AA-Turner@users.noreply.github.com>

Update Lib/copy.py

b2afbea

Co-authored-by: Adam Turner <9087854+AA-Turner@users.noreply.github.com>

tiran requested changes Jun 9, 2022

View changes

eendebakpt and others added 4 commits Jun 10, 2022

Update Modules/_copy.c

d1433f5

Co-authored-by: Christian Heimes <christian@python.org>

Update Modules/_copy.c

3223387

Co-authored-by: Christian Heimes <christian@python.org>

Update Modules/_copy.c

cd25a5d

Co-authored-by: Christian Heimes <christian@python.org>

Update Modules/_copy.c

8793d88

Co-authored-by: Christian Heimes <christian@python.org>

eendebakpt marked this pull request as draft Jun 10, 2022

gh-72793: C implementation of parts of copy.deepcopy #91610

gh-72793: C implementation of parts of copy.deepcopy #91610

eendebakpt commented Apr 16, 2022 •

edited

eendebakpt commented Apr 28, 2022

eendebakpt commented May 27, 2022

AA-Turner left a comment

eendebakpt commented Jun 8, 2022

AA-Turner commented Jun 8, 2022

tiran Jun 8, 2022

tiran Jun 8, 2022

tiran Jun 8, 2022

bedevere-bot commented Jun 8, 2022

serhiy-storchaka commented Jun 8, 2022

eendebakpt commented Jun 8, 2022

tiran commented Jun 8, 2022

eendebakpt commented Jun 8, 2022

serhiy-storchaka commented Jun 9, 2022

tiran left a comment

tiran Jun 9, 2022

tiran Jun 9, 2022

tiran Jun 9, 2022

		@@ -0,0 +1,60 @@
		"""Unit tests for the copy module without the C accelerator."""

		# XXX: import_fresh_module() is supposed to leave sys.module cache untouched,
		# XXX: but it does not, so we have to cleanup ourselves.

gh-72793: C implementation of parts of copy.deepcopy #91610

Are you sure you want to change the base?

gh-72793: C implementation of parts of copy.deepcopy #91610

Conversation

eendebakpt commented Apr 16, 2022 • edited

eendebakpt commented Apr 28, 2022

eendebakpt commented May 27, 2022

AA-Turner left a comment

eendebakpt commented Jun 8, 2022

AA-Turner commented Jun 8, 2022

tiran Jun 8, 2022

Choose a reason for hiding this comment

tiran Jun 8, 2022

Choose a reason for hiding this comment

tiran Jun 8, 2022

Choose a reason for hiding this comment

bedevere-bot commented Jun 8, 2022

serhiy-storchaka commented Jun 8, 2022

eendebakpt commented Jun 8, 2022

tiran commented Jun 8, 2022

eendebakpt commented Jun 8, 2022

serhiy-storchaka commented Jun 9, 2022

tiran left a comment

tiran Jun 9, 2022

Choose a reason for hiding this comment

tiran Jun 9, 2022

Choose a reason for hiding this comment

tiran Jun 9, 2022

Choose a reason for hiding this comment

eendebakpt commented Apr 16, 2022 •

edited