First draft of persistent bytecode - #1527

To test:

1. Build unix version.
2. Run uPy with script to compile as argument. This will execute it and leave behind a .mpc file.
3. Run uPy with .mpc file as argument. It will execute it.
4. Run uPy without args. Then at the REPL import the mpc file by doing import <basename-of-mpc-file>. The import system will look first for .mpc, then for .py.
5. Build stmhal port.
6. Copy .mpc file to pyboard, and execute it using import <basename>.

The most interesting changes are:

• comment near top of bc.h describes the layout of the bytecode and constant table
• vm.c has very minimal changes and looking at these changes will show you exactly how the constant table works
• emitglue.c contains the bytecode load and save functions

Lot of pretty deep code changes (I guess, stackless support would be broken), so hard to tell something, so let's again start from high-level. Given a persistent bytecode, there're 2 ways to load it:

1. If it can be mapped into address space, then it can be accessed as such, then only constant table should be created in RAM to interpret it (besides the usual things as function objects).
2. Loading from sequential-access stream.

Of these, 1) is the most interesting (allows to save RAM but keeping code in ROM). 2) actually can be implemented by loading data from stream into memory and calling 1). Of course, it can be optimized to parse stream and skipping e.g. qstr's which are already available. Seeing in the patchset above load_qstr() which calls qstr_from_strn(), I see that optimized stream loading is implemented. But what about accessing bytecode from the address space - is it supported? Perhaps optimized stream loading can be made configurable?

Another question - I guess const_table scheme allows clean path to support aggregate constant objects (including dict "templates")?

Lot of pretty deep code changes

Yes, but not much we can do about that!

I tried to separate out the changes. The first 3 patches are just refactoring and don't really change any functionality, so you can almost ignore them when trying to understand how persistent bytecode works.

I guess, stackless support would be broken

I think it works... if not then it's easy to fix.

Yes, you're correct about the 2 different ways to load code.

2. actually can be implemented by loading data from stream into memory and calling

Yes, this is exactly how it's done: https://github.com/micropython/micropython/pull/1527/files#diff-a91b6ceb641fa02899a4dd78ab82a61dR230 (that's line 230 of emitglue.c).

Seeing in the patchset above load_qstr() which calls qstr_from_strn(), I see that optimized stream loading is implemented.

When loading it goes through all needed qstrs and interns them if they don't already exist. Then the global interned string (be it existing or newly interned) is inserted into the const_table at the correct position. Thus the bytecode can index this table and get the qstr value.

But what about accessing bytecode from the address space - is it supported?

Yes, using the get_ptr method of the stream reader (see link above to line 230 of emitglue.c). You'd need to implement a ROM stream reader to get this functionality (only file reading is implemented at the moment).

Perhaps optimized stream loading can be made configurable?

Please elaborate on what you mean by "optimised stream loading"?

I guess const_table scheme allows clean path to support aggregate constant objects (including dict "templates")?

Yes, definitely.

Ah, and now the big question - do you really want to make bytecode as portable as storing external representation of objects (floats, long ints, etc.?). I guess, that's pretty big dip in efficiency (more processing, more memory).

I guess the first usecase and requirements for persistent bytecode should be saving as much as possible RAM for baremetal devices. (That of course opens a question: if bytecode is system-dependent, then how to generate it for baremetal devices...)

Ah, and now the big question - do you really want to make bytecode as portable as storing external representation of objects (floats, long ints, etc.?). I guess, that's pretty big dip in efficiency (more processing, more memory).

Yes, these are the exact architectural questions that we need to answer.

It currently loads const objects by "interpreting" them, aka unpickling. I don't think it's that big a performance hit (much more efficient than lexing, parsing and compiling). Yes it uses RAM. To save RAM you'd need to store actual "live" objects in the mpc file. Only useful if the mpc is executed from ROM.

I guess the first usecase and requirements for persistent bytecode should be saving as much as possible RAM for baremetal devices.

Yes, we should discuss use-cases, since they'll drive the implementation. For ESA it's about being able to compile offline (don't want to have a compile error in space!). For microbit, it would be about executing from ROM (and being able to write frozen modules in Python that don't need RAM to load, or need very little RAM). For WiPy ROM=RAM so it would just be that loading pre-compiled bytecode is faster (and doesn't need RAM for the parse/compile stage which can help with reducing RAM pressure). For pyboard, I'd say it would be about writing some high-level drivers in Python (eg Accel class) and providing them as persistent bytecode, executed from ROM.

That of course opens a question: if bytecode is system-dependent, then how to generate it for baremetal devices...

Tough question. You'll notice I needed to disable bytecode lookup cache for unix port, since otherwise it generates bytecode that is incompatible with stmhal.

There's also the use-case where a very constrained system doesn't have room for the parser/compiler and just has pre-compiled bytecode in ROM.

Seeing in the patchset above load_qstr() which calls qstr_from_strn(), I see that optimized stream loading is implemented.
When loading it goes through all needed qstrs and interns them if they don't already exist. Then the global interned string (be it existing or newly interned) is inserted into the const_table at the correct position. Thus the bytecode can index this table and get the qstr value.

qstr_from_strn() unconditionally makes string content copy into the global table, so in the end, string content is duplicated in memory. Default behavior for "loading" in-memory persistent bytecode files should be pointing qstr to string content within this in-memory buffer, instead of allocating it in qstr pool.

Please elaborate on what you mean by "optimised stream loading"?

Taking the scheme above as default, there's another way to load bytecode files with stream access - load it field by field, and discard fields which are not needed as-is. For example, each code objects will be stored in RAM, while each qstr record will be checked if it already exists, if not added to global pool, and the from-file record discarded. (Similarly for constants f you really want to store their external representation - float string value can be parsed and discarded (even qstr for it doesn't need to be created, unlike if compiled from source)).

Yes, but not much we can do about that!

Sure, I'm just hinting that I'm in pretty dumb state now apparently ;-). (But I did check that a reference to out-side-the-pool qstr content is (well, should be) possible).

There's also the use-case where a very constrained system doesn't have room for the parser/compiler and just has pre-compiled bytecode in ROM.

Exactly, that's the main, "default" usecase I mentioned - no ROM, no RAM, so the all thinking is about how to shrink constant table in RAM (taking for granted that nothing else than constant table is needed at all).

For microbit, it would be about executing from ROM

Yes, per above, I kinda took for granted, that if doing persistent bytecode, then with a requirement of deepening uPy penetration to smaller systems (e.g. breaking down 64K ROM barrier, by compiling without parser/compiler). Well, thinking about it, having portable bytecode may actually have bigger real-world impact. So, we won't go as low as we could go and won't be able to write in the FAQ that we beta them all. But it will allow to actually leverage all this stuff for the benefit of ecosystem, instead of saying "hey, that's how far you can go - you just need to go there yourself, here's a map". And yep, it of course still will be great improvement, even if don't go for last 10% of efficiency in exchange of it being reusable and portable.

So, I guess you did it exactly right for how it should be done for starters ;-). (Though comments of qstr storage optimization should be still valid.)

Reason I'm not merging this yet is because it's too memory hungy.

Bytecode on a 32-bit machine has 0.16 qstrs per byte of (non-qstr) bytecode. A qstr fits in 1.92 bytes (most are encoded in 1 byte, the rest in 2 bytes). That data comes from 13mb of bytecode, compiling all Python 3.5 stdlib plus some more.

Currently (ie without this PR applied) for 1000 bytes of non-qstr bytecode you need 307 extra bytes to store the qstrs. Ie 1307 bytes of bytecode contains 307 bytes just for qstr numbers.

With this persistent bytecode patch, 1000 bytes of non-qstr bytecode will need 800 extra bytes for the qstrs, ie in 1800 bytes of bytecode there are 800 bytes for the qstrs (each qstr needs 1 byte in the bytecode pointing to the const table, then 4 bytes in the const table).

That's about a 38% increase in bytecode size. And this isn't just for loaded .mpc files, it's for all bytecode functions.

Probably the only way out is to keep the qstr ids stored directly in the bytecode. This requires modifying the bytecode chunk when loading and throws away the read-only nature of the bytecode chunk.

Hmm. If we store the qstr ids directly in the bytecode does it make sense to have them be relative?

i.e. for a given bytecode file, have some qstr base id (which maybe is even stored in RAM) from which all of the relative qstr id's in the bytecode is added to.

Hmm. If we store the qstr ids directly in the bytecode does it make sense to have them be relative?

i.e. for a given bytecode file, have some qstr base id (which maybe is even stored in RAM) from which all of the relative qstr id's in the bytecode is added to.

I don't think this would help with linking the qstrs to the global table, since you'd still need to update the qstr ids in the bytecode. It wouldn't really help with code size reduction because you'd need always to provide 2 bytes of space for the id in case it was out of range of 1 byte. And it'd add a lot of overhead: the VM would need to know the base id, and add it to the qstr id after reading it from the bytecode.

Closing because superseded by #1577.