Faster startup -- Experiment C -- lazy unmarshalling

[gvanrossum]

This is a placeholder for a description of Experiment C (see #32 (comment))

• borrows ideas from (Faster startup -- Experiment A #64): delay hydrating code objects until called, keep PYC file in memory
• but dehydration just calls back into marshal
• this might be less code changes compared to Experiment A, and doesn't need as many new opcodes

[gvanrossum]

• In marshal.loads(), when r_object() encounters the type code TYPE_CODE, instead of constructing a full code object, it should construct a dummy ("dehydrated") code object and skip to the end of the data for that type code.
• The dehydrated code object must be populated with just enough things so that we can construct a function object from it, and introspecting the function will function correctly.
• When we are asked to execute a dehydrated code object, we go back to marshal.loads() and load the full code object (but leave nested code objects as dummies again). This process is called hydration.
• We need one modification to the marshal format: we need to know the size of the code object so that we can skip it. This is harder than it might seem, since writing a marshal file is a one-pass process, and the size is not known until we're done writing the object.
  • A hacky approach would be to have a magic string that we hope never occurs, so we can search for it. Maybe a unique random 8-byte string would suffice. A complication is that code objects nest; we could use different strings for different levels. Another complication is that if the magic string is included anywhere in the data (e.g. in a bytes constant) this would break the format. For a quick experiment this might be acceptable.
  • Another approach would be to marshal to a temporary buffer, once done measure the buffer, and copy the buffer, prefixing it with its size as a 4-byte int. This is slow because of the extra copying (and, again, the nesting makes it worse).
  • If we can update bytes earlier in the output string, this can be with less overhead by simply reserving 4 bytes and patching in the size once done writing. For marshal.dump() (which writes to a file) this is not possible, but for marshal.dumps() it should be simple. Fortunately because of importlib, we always use marshal.dumps().

[iritkatriel]

What if marshal loads reads the data in the opposite direction than dumps writes?

[gvanrossum]

You mean reading the file backwards? We'd have to change the entire format.

[iritkatriel]

Yes.

[gvanrossum]

So we'd write the file in reverse polish notation. Unfortunately buffered I/O APIs aren't really geared to reading backwards. I think I'll do this:

• If writing to a string, use the backpatch trick
• Otherwise, code objects will be loaded eagerly

This is all academic since real PYC files always use dumps()/loads(), see the code in _bootstrap_external.py.

[gvanrossum]

The first step (prefixing the marshalled code object with its size in bytes) is complete in https://github.com/gvanrossum/cpython/tree/lazy-marshal .

[gvanrossum]

Let's see what the next step will be. In Experiment A (#64) I already wrote code for creating dehydrated code objects and deciding when to hydrate them, I could probably just copy that. But the implementation of hydration will be different, so let me focus on how to do that.

I worry most about the "refs" feature in the marshal format. Unfortunately the format is not documented except in the code, so I'll just have to refer to that. The basic idea is simple enough:

• When marshal.loads() encounters a top-level code object, it should unmarshal that code object as before. But when it encounters a code object nested inside another, it should construct a dummy code object and skip the data, using the skip size that I added in the previous step. (Conveniently, there's a 'depth' field in the RFILE struct.) The dummy code object must contain a a pointer to the bytes object from which it is reading, plus a pointer to the starting point. (Alternatively, we could make a slice of the original bytes so that the start is at index zero, but we're trying to save time here, so let's not make redundant copies.)
• The bytes object is not accessible from the RFILE; we probably have to add it -- or maybe we should add the Py_buffer struct (ownership TBD). The general approach here can be similar to what I did for Faster startup -- Experiment A #64 -- introduce a new struct containing everything that's needed and that's shared between all code objects for a given PYC file (each of which points to it), and give each code object one extra piece of data needed for hydration -- that could be the offset relative to the start of the buffer where the code object's data starts.
• The tricky bit is the 'refs' field of RFILE. This is a list of certain previously encountered values, used to save space in the marshalled data. For example, if we marshal the tuple ("abc", "abc"), the generated marshal code writes a type code with a flag bit set for the first occurrence of "abc", and instead of the second occurrence (or further) of the same value, it generates a TYPE_REF type code followed by the index of the first value in the list of shared values. (Which happens to be 1, because the tuple value itself also gets shared, even though it occurs only once. This could be improved upon, at the cost of more data analysis in marshal.dumps().)
• When the reader skips over a code object, it will potentially also skip over new values to be entered into the list of shared values. This is a problem for us, since a value shared between two code objects will be entered into the list by the first code object and referenced by the second. If the second code object is hydrated first, the referenced value will be missing! Even more disturbing, if we skip unmarshalling some reference definitions, the indexes of further reference definitions will be off.
• For a quick prototype we could probably get away with disabling the creation of reference definitions, but I need to know first that we could solve this if we had to, because the savings by not repeating identical values is potentially significant (though it isn't really for this toy example).
• To avoid the indexes from getting out of sync, we could add a second new field for marshalled code objects, after the "skip bytes" field, to indicate how many reference definitions were skipped. On unmarshalling, we could then append that many None values to the 'refs' list (fortunately, None has its own type code, TYPE_NONE, so None cannot be a valid value in the list). When rehydrating, we can patch those Nones with the corresponding correct values.
• But what to do if a reference points to a None that hasn't been patched yet? Maybe instead of None, we could put a special object in the list that means "a value needs to be patched here" which has an extra field meaning "here's where you have to start reading to get the missing value". Honestly the simplest thing to put here would perhaps be the dummy code object, since we also don't want to have to unmarshal that code object more than once (once when the first missing value is needed, once when rehydrating the code object). It shouldn't be hard to arrange that all code objects in the list of refs are such "to be rehydrated" dummy code objects, since in normal usage code objects are never shared.

Let me do some experiments here before rambling on.

[gvanrossum]

I believe I can make this work, although I need to think more about what to do when a value needed requires recursively hydrating several code objects. Honestly, the quickest way to some kind of working code is to just disable shared references. (Since so many constants are simple, having MAKE_INT and LOAD_COMMON_CONSTANT might be sufficient. See Experiment B, #64.)

[gvanrossum]

Thinking about the design for the rehydration, let's say marshal.c exports a function Hydrate(code) which takes a dehydrated code object and hydrates it. How does it do that?

• The code object must contain a pointer to a struct that tells it (a) the bytes object from which to load, and (b) where in that bytes object to start. (If that pointer is NULL the code object is already hydrated and we do nothing.)
• That pointer is put there by the initial marshal.loads() call that returned the code object in dehydrated form. The pointer must be shareable between all code objects loaded from the same bytes object.
• Who owns the struct? In the prototype, it's immortal: it's allocated by malloc() and never freed. Eventually it should become a PyObject and will be DECREF'ed when a PyCodeObject pointing to it is deallocated.
• The bytes object is not currently a part of the RFILE struct. We'll have to add it there.
• It doesn't even have to be a bytes object (it could be anything with a buffer interface, PEP 3118). But that seems overkill so I'll punt if it isn't.
• Let's call this the context struct for now.
• Note that the offset where a particular code object lives is not part of the context struct -- it is a second new field in the code object.

Okay, so now we have a bytes object and a starting point and a code object. What do we do?

• Let's assume the starting point is the index of the TYPE_CODE type-code in the bytes object. We can assert that the first byte here is TYPE_CODE.
• We construct an RFILE struct from the context struct.
• We collect all the data for the code object but instead of constructing a new code object, we somehow update the existing object in place.
• Wish we could use the replace() method on the code object, but it's probably easier (from C code) to add a _PyCode_Update() method that takes a code object and a code constructor and updates the code object in place -- it can share code with _PyCode_New() (maybe a little refactoring is needed).

For code objects containing other code objects (modules, classes, and functions containing lambdas or nested functions) as long as the outer object is not hydrated the inner objects don't exist at all (since they would live in co_consts which is NULL for a dehydrated code object). So these inner code object are created (one level deep) when the outer code object is hydrated. It is important that they all share the same context struct. (So maybe the RFILE has to have an optional pointer to the context struct.)

Idea for the context struct: Maybe marshal_loads_impl() can allocate the context struct (if applicable) and add it to the RFILE struct.

In the future, if/when we restore the 'refs' mechanism, we'll have to update this design.

[iritkatriel]

• The code object must contain a pointer to a struct that tells it (a) the bytes object from which to load, and (b) where in that bytes object to start. (If that pointer is NULL the code object is already hydrated and we do nothing.)

Why is this only for code objects and not all marshalled objects? I think the refs could be to any object.

[gvanrossum]

Why is this only for code objects and not all marshalled objects? I think the refs could be to any object.

We only leave code objects potentially dehydrated.

The refs can indeed be any object -- this is one of the problems I'm working around by disabling them for now, but we can't very well add fields for hydration support to e.g. tuples or strings.

[gvanrossum]

The prototype in the branch "works" on a very simple test. It needs tests and perf measurements, and there's coding work on memory deallocation, plus the 'refs' list (the latter is the only thing that needs deep thinking).

[gvanrossum]

Stuff to do includes:

• Search for bugs and fix them
• Avoid leaking values in _PyCode_Update()
• Properly free 'struct context' (by making it an object?)
• Unit tests
• Perf measurements
• Hydrate in more places, e.g. when accessing attributes
• Deal with function.__doc__ -- this is taken from co_consts[0] which is not defined
• And the big one: implement 'refs' list again (I need to draw some pictures)

[gvanrossum]

So here are the first perf measurements, using Irit's script from the pyco branch (with small tweaks).

                                                        load+exec   steady state
shared call locals  consts  100 funcs,   10 vars            1.153          1.091
unique call locals          100 funcs,   10 vars            1.148          0.897
shared call locals          100 funcs,   10 vars            1.092          0.990
shared call globals consts  100 funcs,   10 vars            1.084          1.015
unique call locals  consts  100 funcs,   10 vars            1.075          0.895
shared call globals         100 funcs,   10 vars            1.074          1.029
unique call globals consts  100 funcs,   10 vars            1.055          0.929
unique call globals         100 funcs,  100 vars            1.023          0.996
unique call globals consts  100 funcs,  100 vars            1.022          0.963
shared call globals consts  100 funcs,  100 vars            1.015          1.023
shared call locals          100 funcs,  100 vars            1.011          0.939
unique call locals  consts  100 funcs,  100 vars            1.004          1.026
shared call locals  consts  100 funcs,  100 vars            1.003          0.976
shared call globals         100 funcs,  100 vars            0.998          1.014
unique call locals          100 funcs,  100 vars            0.993          0.992
unique call globals         100 funcs,   10 vars            0.922          1.071
unique      globals consts  100 funcs,   10 vars            0.670          1.004
unique      globals         100 funcs,   10 vars            0.637          0.979
unique      globals consts  100 funcs,  100 vars            0.629          1.095
unique      globals         100 funcs,  100 vars            0.614          1.114
shared      globals consts  100 funcs,   10 vars            0.453          1.130
shared      globals         100 funcs,   10 vars            0.450          0.627
shared      locals          100 funcs,   10 vars            0.337          0.870
shared      locals  consts  100 funcs,   10 vars            0.321          0.833
unique      locals          100 funcs,   10 vars            0.317          0.813
unique      locals  consts  100 funcs,   10 vars            0.292          1.188
shared      globals consts  100 funcs,  100 vars            0.243          1.132
shared      globals         100 funcs,  100 vars            0.242          1.020
shared      locals  consts  100 funcs,  100 vars            0.057          0.768
shared      locals          100 funcs,  100 vars            0.056          0.863
unique      locals          100 funcs,  100 vars            0.049          0.956
unique      locals  consts  100 funcs,  100 vars            0.044          0.894