Support object instancing and recursion in marshal

[kristjanvalur]

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']

[kristjanvalur]

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.)

[kristjanvalur]

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

[pitrou]

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

[kristjanvalur]

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.

[pitrou]

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?

[kristjanvalur]

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.

[pitrou]

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.

[loewis]

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).

[kristjanvalur]

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.

[serhiy-storchaka]

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.

[kristjanvalur]

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:

1. Version 2 of the protocol.
2. Version 3 of the protocol (object instancing and the works)
3. 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.

[serhiy-storchaka]

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.

[pitrou]

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.