Support object instancing and recursion in marshal

@loewis

BPO	16475
Nosy	@loewis, @gpshead, @amauryfa, @mdickinson, @pitrou, @kristjanvalur, @tiran, @benjaminp, @ezio-melotti, @serhiy-storchaka
Files	marshalinstance.patch marshalinstance.patch marshalinstance.patch marshalinstance.patch marshalinstance.patch marshalstat.py: Quick and dirty marshal statistics tool

^{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 2014-04-04.11:47:25.028>
created_at = <Date 2012-11-15.08:54:38.446>
labels = ['interpreter-core', 'type-feature']
title = 'Support object instancing and recursion in marshal'
updated_at = <Date 2014-04-04.13:25:37.673>
user = 'https://github.com/kristjanvalur'

bugs.python.org fields:

activity = <Date 2014-04-04.13:25:37.673>
actor = 'kristjan.jonsson'
assignee = 'none'
closed = True
closed_date = <Date 2014-04-04.11:47:25.028>
closer = 'kristjan.jonsson'
components = ['Interpreter Core']
creation = <Date 2012-11-15.08:54:38.446>
creator = 'kristjan.jonsson'
dependencies = []
files = ['27987', '27988', '28047', '28048', '28052', '28055']
hgrepos = []
issue_num = 16475
keywords = ['patch']
message_count = 47.0
messages = ['175603', '175606', '175632', '175672', '175690', '175695', '175799', '175823', '175955', '175959', '175962', '175963', '175964', '175981', '175982', '175983', '175987', '175988', '175989', '175998', '176003', '176005', '176008', '176011', '176013', '176014', '176015', '176016', '176017', '176018', '176057', '184727', '184738', '184739', '184740', '184754', '184780', '184785', '184809', '184868', '184876', '185142', '185143', '185156', '185193', '185198', '185274']
nosy_count = 11.0
nosy_names = ['loewis', 'gregory.p.smith', 'amaury.forgeotdarc', 'mark.dickinson', 'pitrou', 'kristjan.jonsson', 'christian.heimes', 'benjamin.peterson', 'ezio.melotti', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue16475'
versions = ['Python 3.4']

The format used by the marshal module does not support instancing. This precludes certain data optimizations, such as sharing string constants, common tuples, even common code objects. Since the marshal format is used to write compiled code, this makes it impossible to do data optimization on code prior to writing it out.

This patch adds proper instancing support for all the supported types and increases the default version to three.

(A separate defect/regression is that interned strings are no longer preserved as was implemented in version 1 of the original 2.x branch. This also negates any interning done at compile time. That is a separate defect.)

Second patch which adds the missing internment support for strings, including unittests.

marshal is only supposed to be used to serialize code objects, not arbitrary user data. Why don't you use pickle?

This change is specifically aimed at code objects.
As it is, it is impossible to produce code objects that share common data (e.g. filename strings, common tuples, name strings, etc) that don't unserialize to separate objects.

Also, separately but related (see second patch) the effort spent in interning names when compiling, is lost when code objects are loaded back from disk.

This change is based on work done at CCP to reduce the size of compiled code in memory. Simple preprocessing of code objects prior to writing them to disk can result in important memory savings.

This change is specifically aimed at code objects.
As it is, it is impossible to produce code objects that share common
data (e.g. filename strings, common tuples, name strings, etc) that
don't unserialize to separate objects.

Shouldn't strings be interned when the code object is unmarshalled?

This change is based on work done at CCP to reduce the size of
compiled code in memory. Simple preprocessing of code objects prior
to writing them to disk can result in important memory savings.

How important?

Basically, reuse of strings (and preservation of their internment status) fell by the wayside somewhere in the 3.x transition. Strings have been reused, and interned strings re-interned, since protocol version 1 in 2.x. This patch adds that feature back, and uses that mechanism to reuse not only strings, but also any other multiply-referenced object.

It is not desirable to simply intern all strings that are read from marshaled data. Only selected strings are interned by python during compilation and we want to keep it that way. Also, 2.x reuses not only interned strings but other strings as well.

Generalizing reuse of strings to other objects is trivial, and a logical step forward. This allows optimizations to be made on code objects where common data are identified and instanced, and those code objects to be saved and reloaded with that instancing intact.

But even without such code-object optimization, the changes are significant:
The sizes of the marshaled code object of lib/test/test_marshal drops from 24093 bytes in version 2 to 17841 bytes with version 3, without any additional massaging of the module code object.

I agree that restoring the string interning behaviour would be a good thing.
However, I don't agree that supporting recursive objects and instantiation is useful. marshal is specialized for code objects, and you shouldn't find any recursive constants there.

As for the size of pyc files, who cares? Memory footprint may be useful to shrink (especially for cache efficiency reasons), but I don't see why we should try to reduce the size of on-disk bytecode. And if we do, it would probably be simpler to zlib-compress them.

When I added interning support to marshal, I specifically cared about the size of pyc. I find it sad that this support was thrown out, so I support restoring it.

I'm also skeptical about general sharing, and would like to see some specific numbers pointing out the gain of such a mechanism (compared to a version that merely preserves interned strings).

If you have string sharing, adding support for general sharing falls automatically out without any effort. There is no reason _not_ to support it, in other words.
Marshal may be primarily used for .pyc files but it is not the only usage. It is a very fast and powerful serializer for data that is not subject to the overhead or safety concerns of the general pickle protocol. This is illustrated by the following code (2.7):

case TYPE_CODE:
        if (PyEval_GetRestricted()) {
            PyErr_SetString(PyExc_RuntimeError,
                "cannot unmarshal code objects in "
                "restricted execution mode");
Obviously, this shows that marshal is still expected to work and be useful even if not for pickling code objects.

It is good to know that you care about the size of the .pyc files, Martin. But we should bear in mind that this size difference is directly reflected in the memory use of the loaded data. A reduction by 25% of the .pyc size is roughly equivalent to a 25% memory use reduction by the loaded code object.

I haven't produced data about the savings of general object reuse because it relies on my "recode" code optimizer module which is still work in progress. However, I will do some tests and let you know. Suffice to say that it is enormously frustrating to re-generate code objects with an optimization tool, sharing common or identical sub-objects and so on, and then finding that the marshal module undoes all of that.

I'll report back with additional figures.

There is no many sense to use references for TYPE_INT whose representation size not greater then a reference representation size. I doubt about references to mutable objects.

Ok, I did some tests with my recode module. The following are the sizes of the marshal data:

test2To3 ... 24748 24748 212430 212430
test3To3 ... 18420 17848 178969 174806
test4To3 ... 18425 18411 178969 178550

The columns:
a) test_marshal.py without transform
b) test_marshal.py with recode.intern() (folding common objects)
c) and d): decimal.py module (the largest one in lib)

The lines:

Version 2 of the protocol.
Version 3 of the protocol (object instancing and the works)
Version 4, an dummy version that only instances strings)

As expected, there is no difference between version 3 and 4 unless I employ the recode module to fold common subobjects. This brings an additional saving of some 3% bringing the total reduction up to 28% and
18% respectively.

Note that the transform is a simple recursive folding of objects. common argument lists, such as (self) are subject to this. No renaming of local variables or other stripping is performed.
So, although the "recode" module is work in progress, and not the subject of this "defect", its use shows how it is important to be able to support proper instancing in serialization protocols.

Implementation note: The trick of using a bit flag on the type to indicate a slot reservation in the instance list is one that has been in use in CCP´s own "Marshal" format, a proprietary serialization format based on marshal back in 2002 (adding many more special opcodes and other stuff)

Serhiy: There is no reason _not_ to reuse INT objects if we are doing it for other immutables to. As you note, the size of the data is the same. This will ensure that integers that are not cached can be folded into the same object, e.g. the value 123, if used in two functions, can be the same int object.

I should also point out that the marshal protocol takes care to be able to serialize lists, sets and frozensets correctly, the latter being added in version 2.4. This despite the fact that code objects don't make use of these.

The following are the sizes of the marshal data:

Can you please measure the time of unmarshalling? It would be interesting. If you can count the statistics about marshalled types (what percent of shared and non shared integers, strings, etc), it would also be very interesting.

There is no reason _not_ to reuse INT objects if we are doing it for other immutables to.

There is at least one reason. This increases size of the refs table.

I should also point out that the marshal protocol takes care to be
able to serialize lists, sets and frozensets correctly, the latter
being added in version 2.4. This despite the fact that code objects
don't make use of these.

Code objects do use frozensets:

>>> def f(x):
...     return x in {1,2,3,4,5,6}
... 
>>> dis.dis(f)
  2           0 LOAD_FAST                0 (x) 
              3 LOAD_CONST               7 (frozenset({1, 2, 3, 4, 5, 6})) 
              6 COMPARE_OP               6 (in) 
              9 RETURN_VALUE

I don't think marshal supports any type that isn't (or hasn't been)
used in code objects.

Obviously, this shows that marshal is still expected to work and be
useful even if not for pickling code objects.

The module officially intended for general-purpose serialization is
pickle; if you use marshal for such a purpose, you're on your own.
If you think pickle is not good enough, your improvements are welcome.

As expected, there is no difference between version 3 and 4 unless
I employ the recode module to fold common subobjects. This brings
an additional saving of some 3% bringing the total reduction up to
28% and 18% respectively.

3% doesn't sound like a worthwhile improvement at all.

The trick of using a bit flag on the type to indicate a slot
reservation in the instance list is one that has been in use in
CCP´s own "Marshal" format, a proprietary serialization format
based on marshal back in 2002 (adding many more special opcodes
and other stuff)

Why don't you release your "proprietary marshal" on pypi? You would
get feedback and a sense of whether people are interested in your
approach.

I should add comments explaining this to the file.

I'm getting two failures after this:
======================================================================
ERROR: testRaising (test.test_exceptions.ExceptionTests)
----------------------------------------------------------------------

Traceback (most recent call last):
  File "/home/wolf/dev/py/py3k/Lib/test/test_exceptions.py", line 51, in testRaising
    marshal.loads(b'')
ValueError: bad marshal data (unknown type code)

and

======================================================================
ERROR: test_no_marshal (test.test_importlib.source.test_file_loader.SourceLoaderBadBytecodeTest)
----------------------------------------------------------------------

Traceback (most recent call last):
  File "/home/wolf/dev/py/py3k/Lib/test/test_importlib/source/util.py", line 23, in wrapper
    to_return = fxn(*args, **kwargs)
  File "/home/wolf/dev/py/py3k/Lib/test/test_importlib/source/test_file_loader.py", line 364, in test_no_marshal
    self._test_no_marshal()
  File "/home/wolf/dev/py/py3k/Lib/test/test_importlib/source/test_file_loader.py", line 265, in _test_no_marshal
    self.import_(file_path, '_temp')
  File "/home/wolf/dev/py/py3k/Lib/test/test_importlib/source/test_file_loader.py", line 194, in import_
    module = loader.load_module(module_name)
  File "<frozen importlib._bootstrap>", line 572, in _check_name_wrapper
  File "<frozen importlib._bootstrap>", line 1032, in load_module
  File "<frozen importlib._bootstrap>", line 1013, in load_module
  File "<frozen importlib._bootstrap>", line 548, in module_for_loader_wrapper
  File "<frozen importlib._bootstrap>", line 869, in _load_module
  File "<frozen importlib._bootstrap>", line 990, in get_code
  File "<frozen importlib._bootstrap>", line 668, in _compile_bytecode
ValueError: bad marshal data (unknown type code)

======================================================================
ERROR: test_no_marshal (test.test_importlib.source.test_file_loader.SourcelessLoaderBadBytecodeTest)
----------------------------------------------------------------------

Traceback (most recent call last):
  File "/home/wolf/dev/py/py3k/Lib/test/test_importlib/source/test_file_loader.py", line 470, in test_no_marshal
    self._test_no_marshal(del_source=True)
  File "/home/wolf/dev/py/py3k/Lib/test/test_importlib/source/test_file_loader.py", line 265, in _test_no_marshal
    self.import_(file_path, '_temp')
  File "/home/wolf/dev/py/py3k/Lib/test/test_importlib/source/test_file_loader.py", line 194, in import_
    module = loader.load_module(module_name)
  File "<frozen importlib._bootstrap>", line 1099, in load_module
  File "<frozen importlib._bootstrap>", line 548, in module_for_loader_wrapper
  File "<frozen importlib._bootstrap>", line 869, in _load_module
  File "<frozen importlib._bootstrap>", line 1105, in get_code
  File "<frozen importlib._bootstrap>", line 668, in _compile_bytecode
ValueError: bad marshal data (unknown type code)

Indeed, would be nice to fix the test failures.

Besides, it would be extra nice if you could run the test suite *before* pushing your changes. Otherwise you're wasting everyone else's time.

This should not have happened and it was indeed all tested. I'll investigate why these errors are happening.

New changeset f4c21179690b by Kristján Valur Jónsson in branch 'default':
Issue bpo-16475: Simplify the interface to r_ref_allocate and improve comments.
http://hg.python.org/cpython/rev/f4c21179690b

New changeset 42bf74b90626 by Kristján Valur Jónsson in branch 'default':
Issue bpo-16475 : Correctly handle the EOF when reading marshal streams.
http://hg.python.org/cpython/rev/42bf74b90626

FTR the two failures I saw earlier are now gone.

Yes, they were fixed with #42bf74b90626 which also added unittests in test_marshal.py to make sure invalid EOFs are always caught.

Sorry, what does "instancing" mean?
And does this change bring interesting features?
And is there an impact on regular .pyc files?

Sorry, what does "instancing" mean?

He means "keeping track of instance identities", so that objects
that were shared before marshal continue to be shared after loading.

And does this change bring interesting features?

"interesting" to whom?

And is there an impact on regular .pyc files?

Definitely. It may now contain 't' (interned) codes again, and it may contain 'r' (reference) codes. The size of the pyc files may decrease.

The size of the pyc files may decrease

This is very good news! Indeed, I noticed decimal.cpython-34.pyc going from 212k to 178k. 17% less!
This is worth an entry in whatsnew/3.4.rst IMO.

Thanks, Martin, for clarifying this.
Glad you are seeing improvements Amaury. In fact, large modules can get additional improvements by identifying identical generated constructs from the compiler, like tuples and strings. The compiler isn't very good at this to begin with. I should probably work some more on my "recode" module and make it public.

I am unsure about how whatsnew is handled these days. Is it incrementally updated or managed by someone?

I am unsure about how whatsnew is handled these days.
Is it incrementally updated or managed by someone?

It's better to add at least a stub to the whatsnew, even if someone will eventually go through it before the release.

New changeset 84e73ace3d7e by Kristjan Valur Jonsson in branch 'default':
Issue bpo-16475: Add a whatsnew entry for 3.4
http://hg.python.org/cpython/rev/84e73ace3d7e

Navigation Menu

Repository navigation

Support object instancing and recursion in marshal #60679

21 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Support object instancing and recursion in marshal #60679

Description

Activity

kristjanvalur commented on Nov 15, 2012

kristjanvalur commented on Nov 15, 2012

pitrou commented on Nov 15, 2012

kristjanvalur commented on Nov 16, 2012

pitrou commented on Nov 16, 2012

kristjanvalur commented on Nov 16, 2012

pitrou commented on Nov 17, 2012

loewis commented on Nov 17, 2012

kristjanvalur commented on Nov 19, 2012

serhiy-storchaka commented on Nov 19, 2012

kristjanvalur commented on Nov 19, 2012

serhiy-storchaka commented on Nov 19, 2012

pitrou commented on Nov 19, 2012

21 remaining items

kristjanvalur commented on Mar 20, 2013

ezio-melotti commented on Mar 20, 2013

pitrou commented on Mar 20, 2013

kristjanvalur commented on Mar 20, 2013

python-dev commented on Mar 20, 2013

ezio-melotti commented on Mar 21, 2013

kristjanvalur commented on Mar 21, 2013

amauryfa commented on Mar 24, 2013

loewis commented on Mar 24, 2013

amauryfa commented on Mar 24, 2013

kristjanvalur commented on Mar 25, 2013

ezio-melotti commented on Mar 25, 2013

python-dev commented on Mar 26, 2013

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions