Repository navigation
make marshal output not dependent on reference count #98819
Description
Activity
This would require two passes over the entire DAG, right? It's not just a matter of retroactively setting or clearing
FLAG_REF, since its presence or absence also affects the numbering of remaining references.Possibly this is acceptable because we'd expect PYC files to be read more than written, but it does feel like it'd double the amount of pointer chasing marshal already does.
A pre-traversal of the DAG would be one approach; the extra cost might be acceptable (not sure how visible it would be compared to compilation and I/O.) I think there are other possible approaches, too. By tracking a map of references used and their location in the buffer, we should be able to both populate reference indices and set
FLAG_REFon objects that need it after the DAG traversal as fixups. This approach might cause issues forPyMarshal_WriteObjectToFile(which flushes directly to file when the buffer fills instead of resizing the buffer), but tbh I'm not sure why that function even exists, it doesn't seem to be used AFAICT. Evenmarshal.dumpis backed byPyMarshal_WriteObjectToStringfollowed by a separate file write.A really simple (probably dumb?) idea would be to eliminate
FLAG_REFand always track everything as a possible reference target. That would definitely burn through reference indices faster, though; might lead to hitting "too many objects" too often on real-world code objects.A really simple (probably dumb?) idea would be to eliminate
FLAG_REFand always track everything as a possible reference target. That would definitely burn through reference indices faster, though; might lead to hitting "too many objects" too often on real-world code objects.I think the main downside would be that the readers need a larger table of objects to look up references.
I don't know what fraction of objects in a typical PYC file has more than one reference, but the idea is that most objects have exactly one reference, since the DAG is mostly a tree. Sharing within the tree occurs primarily when different code objects use the same constants or variable names (and attribute/argument names). There is a small amount of sharing tuples of constants or variable names, e.g. when two functions happen to use exactly the same set of constants variable names (in the same order).
There is also some spurious sharing, where an object occurs only once in the DAG but has a refcount > 1; this may happen if a constant or variable name is used in only one function in an entire module, but it's also used in a different module. And I wouldn't be surprised if the root code object always has a refcount > 1.
So possibly the extra pass would pay off.
Bug report
Currently the
marshalmodule will emit a previously-unseen object flagged as a potential reference from later objects, unless the object has a reference count of 1. Seecpython/Python/marshal.c
Line 305 in b27b57c
This is an overly-conservative heuristic -- it's easy to construct cases where an object has a reference count >1 but is not actually referenced by any other object about to be marshaled, so
FLAG_REFis set when it does not need to be.This makes marshal output unstable depending on accidents of reference counting behavior in the code calling
marshal.dumps.I ran into this because the Cinder JIT is able to reduce unnecessary increfs, and that resulted in some importlib tests failing on comparison of marshal output at
cpython/Lib/test/test_importlib/test_abc.py
Lines 870 to 871 in b27b57c
code_objectin that method is 1.This previously caused issues in distutils reproducibility, resulting in a partial fix that applies only to interned strings: #8226
It would be better if marshal would actually determine which objects have multiple parents in the DAG and deterministically use
FLAG_REFor not based on that.