Efficient storage of code object debug information

[markshannon]

Discussed in #324

^{Originally posted by markshannon March 18, 2022}
Code objects include a lot of information, much of it only used for tracing and debugging of various sorts.
It would be good if that information used less space when we aren't using it.

Classifying the fields of a code object we have (ignoring computed attributes and int fields):

Needed for normal execution:

• co_code : The bytecode
• co_consts: Constants
• co_names: Names of attributes and global variables.
• co_exceptiontable: The exception handler table.
• co_localsplusnames: Parameter names.

Debug info, all bytes objects:

• co_localspluskinds: Describes the "kind" of locals, used for signatures and locals()
• co_linetable: Line information
• co_endlinetable: Ditto, for fancy traceback printing
• co_columntable: More stuff for fancy traceback printing

Currently this information uses about 8 bytes per instruction, in large part due to having column table entries for each cache entry.

A single table

I would like to replace the four debug objects with a single bytes object with the following format:
[0] 0 if compact, 1 if expanded.
[1 - 3] len(co_localspluskinds) (16 million max local variables seems sufficient)
[4 - 4+len] co_localspluskinds
[...] Location info in compact or expanded form.

The expanded form should be an easily searchable table; one fixed-width entry per instruction.

• Offset of instruction start (including preceding EXTENDED_ARGs)
• Instruction length (including EXTENDED_ARGs prefix and inline cache)
• Resumption point (where we currently have RESUME). 1 bit
• Line start, for tracing line events. 1 bit.
• Start line
• Start column
• End line
• End column

I think we can impose some reasonable limits on the size of the fields, even in the expanded form.

E.g. We know the instruction length cannot exceed 10 or so, so we can fit it into 4 bits. It might make sense, then, to limit the start offset to 28 bits and fit both into 32 bits.

Then we can fit the whole entry into 96 bits:

• Offset start and length: 32 bits
• Start line (30 bits), resumption and line-start flags: 32 bits:
• Start column(8 bits), End line delta (16 bits), End column (8 bits). (or 10/12/10 bits?)

This should save memory, as most tables would remain in their compact form, and it saves 3 pointers and 3 bytes object headers per code object.
It should also speed up tracing and debugging, as once expanded, the table is quickly searchable.

[gvanrossum]

I take it len(co_localspluskinds) should presumably be expressed in a fixed endianness. IIUC little-endian prevails in code objects and PYC files.

[gvanrossum]

I take it that the entries must be fixed-width so that the mapping from instruction offset/pointer to table entry can be computed relatively efficiently (e.g. using bisection)? And that that is what you refer to as "searchable"?

Two EXTENDED_ARG ops plus an opcode is 6 bytes, add 8 bytes of cache and you get to 14. And I'm not sure we never need three EXTENDED_ARG ops. But assuming this is always an even number we can drop the low bit. Or we can steal a few more bits from the offset -- 28 bits still feels very generous (some 50 million lines of "x = 1" :-).

[markshannon]

See #324 for the latest design.

The latest design doesn't include the co_localspluskinds table, just to keep things simpler for 3.11

Entries aren't fixed width, but can be searched backwards. The current linetable works that way, and has amortized O(1) performance by tracking the current line number and offset.

[gvanrossum]

Ah, sorry. I misinterpreted "Discussed in #324" for a link to earlier discussion. :-)

[markshannon]

python/cpython#91666