Let's do preprocessor crimes to ROM tables

[jepler]

Note: the proof of concept uses "boost preprocessor" but does not require any C++ features.

It's been noted in private communication that there is a LOT of space that could be saved in the storage of ROM tables and generally speaking all tables with strictly qstr keys. This is because (rom) qstrs are 16 bit quantities, while all table entries are pointer sized.

A different organization, in which keys are separate from values, would allow keys to be stored as 2 bytes and objects as pointer sized. It might also allow the keys of a static dictionary to be ROM while values could be RAM (i.e., the mutable entries in sys dictionary) with less support code.

For the sys module of the unix standard build on a 32-bit platform this would save about 52 bytes of code space. Of course, some code space would be required for operating on tables with the new organization.

A stumbling block to trying different table organization has been the textual representation of tables in source code, such as

static const mp_rom_map_elem_t mp_module_array_globals_table[] = {
    { MP_ROM_QSTR(MP_QSTR___name__), MP_ROM_QSTR(MP_QSTR_array) },
    { MP_ROM_QSTR(MP_QSTR_array), MP_ROM_PTR(&mp_type_array) },
};

So, let's do preprocessor crimes! The 'leading' library for this is part of Boost, and the preprocessor part can be used with pure C programs.

We just have to change the table definition like so (yes, the punctuation is a bit weird but it's what preprocessor needs):

static const ROM_TABLE(mp_module_array_globals_table,
 ((MP_QSTR___name__, MP_ROM_QSTR, MP_QSTR_array)))
 ((MP_QSTR_array, MP_ROM_PTR, &mp_type_array))); 

This uses the boost preprocessor library to produce a table that's compatible with the current layout (when ROM_TABLE is ROM_TABLE_MERGED). But, you can also flip a switch and use ROM_TABLE_SEPARATE which produces something more like

static const struct {
  qstr_short_t keys[2], mp_rom_obj_t values[2],
} mp_module_array_globals_table =
    {
        {
            MP_QSTR___name__,
            MP_QSTR_array,
        },
        {
            MP_ROM_QSTR(MP_QSTR_array),
            MP_ROM_PTR(&mp_type_array),
        },
};

.. or whatever it turns out is desirable in terms of table layout (you'd need two separate objects to enable immutable keys but mutable values, for example)

Here's how the sausage is made (early draft; see link below to current version in repo):

#pragma once

#include <boost/preprocessor/seq/for_each.hpp>
#include <boost/preprocessor/tuple/elem.hpp>

// standard layout
#define TABLE_ENTRY(r, x, element) { BOOST_PP_TUPLE_ELEM(0, element), BOOST_PP_TUPLE_ELEM(1, element) },
#define ROM_TABLE_MERGED(name, contents) mp_rom_map_elem_t name[] = { \
    BOOST_PP_SEQ_FOR_EACH(TABLE_ENTRY, _, contents) \
}

// hypothetical future layout
#define TABLE_KEY(r, x, element) BOOST_PP_TUPLE_ELEM(0, element),
#define TABLE_VALUE(r, x, element) BOOST_PP_TUPLE_ELEM(1, element),
#define ROM_TABLE_SEPARATE(name, contents) \
    struct { \
        qstr_short_t keys[BOOST_PP_SEQ_SIZE(contents)], \
        mp_rom_obj_t values[BOOST_PP_SEQ_SIZE(contents)], \
    } name = { \
        { BOOST_PP_SEQ_FOR_EACH(TABLE_KEY, _, contents) }, \
        { BOOST_PP_SEQ_FOR_EACH(TABLE_VALUE, _, contents) }, \
}

// use standard layout for now
#define ROM_TABLE ROM_TABLE_MERGED

[jepler]

lib/preprocessor weighs about 14 megs checked out + 5 megs of git objects.

It might not work on esoteric or low quality C compilers (I'm particularly imagining that the pic16bit compiler that nobody can test with might be in that category) even though it aims to be conformant with the C/C++ standard for the preprocessor.

[jepler]

One surprise: /* comments */ can't appear inside a ROM_TABLE but // comments can. 🤔

This was actually due to boost preprocessor having issues with commas in tuple elements.

[jepler]

A barrier to splitting all tables: how do you make mp_map_init_fixed_table work?

mp_map_lookup and MICROPY_OPT_MAP_LOOKUP_CACHE depend on map slots too.

map.c generally just needs a whole different implementation for split tables.

Adding a non-qstr key to a dict will do a memory allocation, when it didn't before.

[jepler]

Non working WIP code at https://github.com/micropython/micropython/compare/master..jepler:circuitpython:split-dict?expand=1, I'm setting this aside for now.

[jonnor]

Interesting! What are the possible gains if applied to all the modules included in one of the standard microcontroller builds? Say for RP2040

[jepler]

A quick check of RPI-pico firmware showed 6752 bytes of ROM tables (total of symbols ending _dict_table and _globals_table). This would save 1/4 of ROM table size or 1688 bytes. That's about 0.5% of the current size of the firmware.