Speed up pickling of dicts in cPickle

[collinwinter]

BPO	5670
Nosy	@amauryfa, @pitrou, @avassalotti
Files	cpickle_dict.patch: Patch against trunk, r71058 pickle_batch_dict_exact_py3k-5.diff

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2009-05-25.05:44:08.252>
created_at = <Date 2009-04-02.18:53:50.140>
labels = ['extension-modules', 'performance']
title = 'Speed up pickling of dicts in cPickle'
updated_at = <Date 2009-05-25.09:35:39.370>
user = 'https://bugs.python.org/collinwinter'

bugs.python.org fields:

activity = <Date 2009-05-25.09:35:39.370>
actor = 'pitrou'
assignee = 'collinwinter'
closed = True
closed_date = <Date 2009-05-25.05:44:08.252>
closer = 'collinwinter'
components = ['Extension Modules']
creation = <Date 2009-04-02.18:53:50.140>
creator = 'collinwinter'
dependencies = []
files = ['13584', '13598']
hgrepos = []
issue_num = 5670
keywords = ['patch', 'needs review']
message_count = 20.0
messages = ['85239', '85245', '85248', '85253', '85257', '85272', '85276', '85277', '85293', '85294', '85296', '85306', '85307', '85333', '85335', '85433', '86188', '86194', '88303', '88314']
nosy_count = 5.0
nosy_names = ['collinwinter', 'amaury.forgeotdarc', 'pitrou', 'alexandre.vassalotti', 'feisan']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'commit review'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue5670'
versions = ['Python 3.1', 'Python 2.7']

[collinwinter]

The attached patch adds another version of cPickle.c's batch_dict(),
batch_dict_exact(), which is specialized for "type(x) is dict". This
provides a nice performance boost when pickling objects that use
dictionaries:

Pickle:
Min: 2.216 -> 1.858: 19.24% faster
Avg: 2.238 -> 1.889: 18.50% faster
Significant (t=106.874099, a=0.95)

Benchmark is at
http://code.google.com/p/unladen-swallow/source/browse/tests/performance/macro_pickle.py
(driver is ../perf.py; perf.py was run with "--rigorous -b pickle").

This patch passes all the tests added in bpo-5665. I would recommend
reviewing that patch first. I'll port to py3k once this is reviewed for
trunk.

[pitrou]

Without taking a very detailed look, the patch looks good.
Are there already tests for pickling of dict subclasses? Otherwise, they
should be added.

[pitrou]

By the way, could the same approach be applied to lists and sets as well?

[collinwinter]

On Thu, Apr 2, 2009 at 12:20 PM, Antoine Pitrou <report@bugs.python.org> wrote:

Antoine Pitrou <pitrou@free.fr> added the comment:

By the way, could the same approach be applied to lists and sets as well?

Certainly; see http://bugs.python.org/issue5671 for the list version.
It doesn't make as big an impact on the benchmark, though.

[pitrou]

Certainly; see http://bugs.python.org/issue5671 for the list version.
It doesn't make as big an impact on the benchmark, though.

How about splitting the benchmark in parts:

• (un)pickling lists
• (un)pickling dicts
• (un)pickling sets
  (etc.)

[collinwinter]

Antoine: pickletester.py:test_newobj_generic() appears to test dict
subclasses, though in a roundabout-ish way. I don't know of any tests
for dict subclasses in the C level sense (ie, PyDict_Check() vs
PyDict_CheckExact()). I can add more explicit tests for Python-level
dict subclasses, if you want.

[amauryfa]

The patch produces different output for an empty dict: a sequence "MARK
SETITEMS" is written, which is useless and wastes 2 bytes.

[pitrou]

Antoine: pickletester.py:test_newobj_generic() appears to test dict
subclasses, though in a roundabout-ish way. I don't know of any tests
for dict subclasses in the C level sense (ie, PyDict_Check() vs
PyDict_CheckExact()). I can add more explicit tests for Python-level
dict subclasses, if you want.

Well, Python-level dict subclasses are also C-level subclasses (in the
PyDict_Check() sense), or am I mistaken?

[avassalotti]

I ported the patch to py3k. In addition, I added a special-case when the
dict contains only one item; you probably want this special-case in the
trunk version as well.

[avassalotti]

Oops, I forgot to add the comment on top of batch_dict_exact in the
patch. Here is a better patch.

[avassalotti]

Oops again, I just remarked that the comment for batch_dict_exact refers
to batch_dict as being above, but I copied batch_dict_exact before
batch_dict. Here's a good patch (hopefully) that puts batch_dict_exact
at the right place.

[avassalotti]

Silly me, I had changed the PyDict_Size call in outer loop for Py_SIZE
and this is of course totally wrong. Here's a good patch (I am pretty
sure now! ;-) I ran the whole test suite and I saw no failures.

Collin, you can go ahead and commit both patches. Nice work!

[avassalotti]

Sigh... silly me again. There is some other junk in my last patch.

[collinwinter]

FYI, I just added a pickle_dict microbenchmark to perf.py. Using this
new microbenchmark, I see these results (perf.py -r -b pickle_dict):

pickle_dict:
Min: 2.092 -> 1.341: 56.04% faster
Avg: 2.126 -> 1.360: 56.37% faster
Significant (t=216.895643, a=0.95)

I still need to address the comment about pickling empty dicts.

[collinwinter]

Amaury, I can't reproduce the issue you're seeing with empty dicts.
Here's what I'm doing:

dhcp-172-19-19-199:trunk collinwinter$ ./python.exe 
Python 2.7a0 (trunk:71100M, Apr  3 2009, 14:40:49) 
[GCC 4.0.1 (Apple Inc. build 5490)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import cPickle, pickletools
>>> data = cPickle.dumps({}, protocol=2)
>>> pickletools.dis(data)
    0: \x80 PROTO      2
    2: }    EMPTY_DICT
    3: .    STOP
highest protocol among opcodes = 2
>>> data
'\x80\x02}.'
>>>

What are you doing to produce the MARK SETITEMS sequence?

[amauryfa]

Sorry, I was wrong. I think I noticed that the case size==1 was handled
differently, and incorrectly inferred the same for size==0.
(btw, the patch for trunk was not updated)

[feisan]

Can this patch be used or ported to 2.5.x?

[pitrou]

Sorry, it won't even be integrated in 2.6 actually. It's a new feature,
not a bug fix.

[collinwinter]

Fixed the len(d) == 1 size regression. Final performance of the patch
relative to trunk:

Using Unladen Swallow's perf.py -b pickle,pickle_dict on trunk:
pickle:
Min: 2.238 -> 1.895: 18.08% faster
Avg: 2.241 -> 1.898: 18.04% faster
Significant (t=282.066701, a=0.95)

pickle_dict:
Min: 2.163 -> 1.375: 57.36% faster
Avg: 2.168 -> 1.376: 57.50% faster
Significant (t=527.668441, a=0.95)

Performance for py3k:
pickle:
Min: 2.849 -> 2.790: 2.10% faster
Avg: 2.854 -> 2.796: 2.09% faster
Significant (t=27.624303, a=0.95)

pickle_dict:
Min: 2.121 -> 1.512: 40.27% faster
Avg: 2.128 -> 1.519: 40.13% faster
Significant (t=283.406572, a=0.95)

regrtest.py -uall test_xpickle passes all backwards-compatibility tests
for trunk, and all other tests run by regrtest.py on Linux pass.

Committed as r72909 (trunk), r72910 (py3k).

[pitrou]

Thanks!

Committed as r72909 (trunk), r72910 (py3k).

----------
resolution: accepted -> fixed
status: open -> closed