Skip to content

py/qstr: Disable qstr hashing on low-flash/mem boards. #12835

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Jan 26, 2024
Merged

py/qstr: Disable qstr hashing on low-flash/mem boards. #12835

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
7ea5039
py/qstr: Add support for MICROPY_QSTR_BYTES_IN_HASH=0.
jimmo Feb 3, 2023
8486e28
stm32: Disable qstr hashing on small boards.
jimmo Oct 30, 2023
d419081
py/mpconfig: Disable qstr hashing at minimum feature level.
jimmo Oct 30, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 0 additions & 1 deletion ports/cc3200/mpconfigport.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -59,7 +59,6 @@
#else
#define MICROPY_CPYTHON_COMPAT (0)
#endif
#define MICROPY_QSTR_BYTES_IN_HASH (1)

// fatfs configuration used in ffconf.h
#define MICROPY_FATFS_ENABLE_LFN (2)
Expand Down
1 change: 0 additions & 1 deletion ports/nrf/mpconfigport.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -281,7 +281,6 @@
#define MICROPY_PY_SYS (1)
#define MICROPY_PY_SYS_PATH_ARGV_DEFAULTS (1)
#define MICROPY_PY___FILE__ (1)
#define MICROPY_QSTR_BYTES_IN_HASH (2)
#endif

#ifndef MICROPY_PY_UBLUEPY
Expand Down
1 change: 0 additions & 1 deletion ports/pic16bit/mpconfigport.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -29,7 +29,6 @@
// options to control how MicroPython is built
#define MICROPY_OBJ_REPR (MICROPY_OBJ_REPR_B)
#define MICROPY_ALLOC_PATH_MAX (64)
#define MICROPY_QSTR_BYTES_IN_HASH (1)
#define MICROPY_EMIT_X64 (0)
#define MICROPY_EMIT_THUMB (0)
#define MICROPY_EMIT_INLINE_THUMB (0)
Expand Down
1 change: 0 additions & 1 deletion ports/powerpc/mpconfigport.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -35,7 +35,6 @@

// #define MICROPY_DEBUG_VERBOSE (1)

#define MICROPY_QSTR_BYTES_IN_HASH (1)
#define MICROPY_QSTR_EXTRA_POOL mp_qstr_frozen_const_pool
#define MICROPY_ALLOC_PATH_MAX (256)
#define MICROPY_EMIT_X64 (0)
Expand Down
1 change: 0 additions & 1 deletion ports/samd/mpconfigport.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -35,7 +35,6 @@
#define MICROPY_GC_STACK_ENTRY_TYPE uint16_t
#define MICROPY_GC_ALLOC_THRESHOLD (0)
#define MICROPY_ALLOC_PATH_MAX (256)
#define MICROPY_QSTR_BYTES_IN_HASH (1)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe this should stay, to keep SAMD size down? Or maybe move it to samd/mcu/samd21/mpconfigmcu.h?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

SAMD doesn't set the feature level, so this is the default anyway.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

But the samd port has increased in size, so this change is not a no-op. We need to make a conscious decision about whether the current config for samd should be changed, or not.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Right. I missed that it's set in the samd/mcu/*/mpconfigmcu.h...

I think it makes sense then for samd21 to be 1 and samd51 to be 2. i.e. d21 is unchanged, but d51 is now moving to 2.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Updated the commit message to match.

Copy link
Contributor

@robert-hh robert-hh Oct 31, 2023 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@jimmo I made the cross-check with the SAMD ItsyBitsy M4 build. Setting #define MICROPY_QSTR_BYTES_IN_HASH (0) in mpconfigport,h reduced the flash size by 2064 bytes compared to the setting of this PR. Compared to the initial setting, the reduction is 1008 bytes. For the ItsyBitsy M0, the size decrease is 684 bytes.

Or in absolute numbers for the M4

QSTR_BYTES   Flash size
 2           260020
 1           259012  (Previous setting)
 0           257956

Copy link
Contributor

@robert-hh robert-hh Oct 31, 2023 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I see, the increase of 1020 bytes for SAMD51 was caused by the change of the hash size from 1 to 2 bytes. That should not be a problem. The only device & configuration short of flash and RAM is the SAMD21 without external flash. For these, setting the QSTR hash to 0 is an advantage. I could add that to the next service PR.
Edit: A single test using pystone_lowmem.py shows a ~20% performance penalty. Not sure if that's worth the memory saving.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@robert-hh I think all those results sound expected. Thanks for checking. Just to confirm, I expect from this PR:

  • D21 boards are unchanged and should have no firmware size change.
  • D51 boards should grow by roughly 1kiB (and get a small performance boost).

For these, setting the QSTR hash to 0 is an advantage.

I don't think we should set bytes-in-hash to zero by default for anything except the "true" minimal ports/variants (where we're really trying to highlight the minimal possible configuration), or unless we're at the size limit (for example some of those stm32x0 boards). As you've noted, the performance impact is non-trivial.


// MicroPython emitters
#define MICROPY_PERSISTENT_CODE_LOAD (1)
Expand Down
2 changes: 2 additions & 0 deletions ports/stm32/boards/B_L072Z_LRWAN1/mpconfigboard.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -7,6 +7,8 @@

#define MICROPY_CONFIG_ROM_LEVEL (MICROPY_CONFIG_ROM_LEVEL_CORE_FEATURES)

#define MICROPY_QSTR_BYTES_IN_HASH (0)

#define MICROPY_HELPER_REPL (1)
#define MICROPY_KBD_EXCEPTION (1)
#define MICROPY_EMIT_THUMB (0)
Expand Down
2 changes: 2 additions & 0 deletions ports/stm32/boards/NUCLEO_F091RC/mpconfigboard.h
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,6 +1,8 @@
#define MICROPY_HW_BOARD_NAME "NUCLEO-F091RC"
#define MICROPY_HW_MCU_NAME "STM32F091RCT6"

#define MICROPY_QSTR_BYTES_IN_HASH (0)

#define MICROPY_EMIT_THUMB (0)
#define MICROPY_EMIT_INLINE_THUMB (0)
#define MICROPY_OPT_COMPUTED_GOTO (0)
Expand Down
2 changes: 2 additions & 0 deletions ports/stm32/boards/NUCLEO_L073RZ/mpconfigboard.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5,6 +5,8 @@
#define MICROPY_HW_BOARD_NAME "NUCLEO-L073RZ"
#define MICROPY_HW_MCU_NAME "STM32L073RZT6"

#define MICROPY_QSTR_BYTES_IN_HASH (0)

#define MICROPY_EMIT_THUMB (0)
#define MICROPY_EMIT_INLINE_THUMB (0)
#define MICROPY_OPT_COMPUTED_GOTO (0)
Expand Down
3 changes: 0 additions & 3 deletions ports/unix/variants/minimal/mpconfigvariant.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -64,6 +64,3 @@
// Enable just the sys and os built-in modules.
#define MICROPY_PY_SYS (1)
#define MICROPY_PY_OS (1)

// The minimum sets this to 1 to save flash.
#define MICROPY_QSTR_BYTES_IN_HASH (2)
3 changes: 2 additions & 1 deletion py/makeqstrdata.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -295,7 +295,8 @@ def compute_hash(qstr, bytes_hash):
for b in qstr:
hash = (hash * 33) ^ b
# Make sure that valid hash is never zero, zero means "hash not computed"
return (hash & ((1 << (8 * bytes_hash)) - 1)) or 1
# if bytes_hash is zero, assume a 16-bit mask (to match qstr.c)
return (hash & ((1 << (8 * (bytes_hash or 2))) - 1)) or 1


def qstr_escape(qst):
Expand Down
6 changes: 4 additions & 2 deletions py/mpconfig.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -290,10 +290,12 @@

// Number of bytes used to store qstr hash
#ifndef MICROPY_QSTR_BYTES_IN_HASH
#if MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_CORE_FEATURES
#if MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_EXTRA_FEATURES
#define MICROPY_QSTR_BYTES_IN_HASH (2)
#else
#elif MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_CORE_FEATURES
#define MICROPY_QSTR_BYTES_IN_HASH (1)
#else
#define MICROPY_QSTR_BYTES_IN_HASH (0)
#endif
#endif

Expand Down
52 changes: 46 additions & 6 deletions py/qstr.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -42,7 +42,11 @@
// A qstr is an index into the qstr pool.
// The data for a qstr is \0 terminated (so they can be printed using printf)

#if MICROPY_QSTR_BYTES_IN_HASH
#define Q_HASH_MASK ((1 << (8 * MICROPY_QSTR_BYTES_IN_HASH)) - 1)
#else
#define Q_HASH_MASK (0xffff)
#endif

#if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
#define QSTR_ENTER() mp_thread_mutex_lock(&MP_STATE_VM(qstr_mutex), 1)
Expand Down Expand Up @@ -77,6 +81,7 @@ size_t qstr_compute_hash(const byte *data, size_t len) {
// future .mpy version we could re-order them and make it sorted). It also
// contains additional qstrs that must have IDs <256, see operator_qstr_list
// in makeqstrdata.py.
#if MICROPY_QSTR_BYTES_IN_HASH
const qstr_hash_t mp_qstr_const_hashes_static[] = {
#ifndef NO_QSTR
#define QDEF0(id, hash, len, str) hash,
Expand All @@ -86,6 +91,7 @@ const qstr_hash_t mp_qstr_const_hashes_static[] = {
#undef QDEF1
#endif
};
#endif

const qstr_len_t mp_qstr_const_lengths_static[] = {
#ifndef NO_QSTR
Expand All @@ -103,7 +109,9 @@ const qstr_pool_t mp_qstr_const_pool_static = {
false, // is_sorted
MICROPY_ALLOC_QSTR_ENTRIES_INIT,
MP_QSTRnumber_of_static, // corresponds to number of strings in array just below
#if MICROPY_QSTR_BYTES_IN_HASH
(qstr_hash_t *)mp_qstr_const_hashes_static,
#endif
(qstr_len_t *)mp_qstr_const_lengths_static,
{
#ifndef NO_QSTR
Expand All @@ -118,6 +126,7 @@ const qstr_pool_t mp_qstr_const_pool_static = {

// The next pool is the remainder of the qstrs defined in the firmware. This
// is sorted.
#if MICROPY_QSTR_BYTES_IN_HASH
const qstr_hash_t mp_qstr_const_hashes[] = {
#ifndef NO_QSTR
#define QDEF0(id, hash, len, str)
Expand All @@ -127,6 +136,7 @@ const qstr_hash_t mp_qstr_const_hashes[] = {
#undef QDEF1
#endif
};
#endif

const qstr_len_t mp_qstr_const_lengths[] = {
#ifndef NO_QSTR
Expand All @@ -144,7 +154,9 @@ const qstr_pool_t mp_qstr_const_pool = {
true, // is_sorted
MICROPY_ALLOC_QSTR_ENTRIES_INIT,
MP_QSTRnumber_of - MP_QSTRnumber_of_static, // corresponds to number of strings in array just below
#if MICROPY_QSTR_BYTES_IN_HASH
(qstr_hash_t *)mp_qstr_const_hashes,
#endif
(qstr_len_t *)mp_qstr_const_lengths,
{
#ifndef NO_QSTR
Expand Down Expand Up @@ -188,8 +200,13 @@ STATIC const qstr_pool_t *find_qstr(qstr *q) {
}

// qstr_mutex must be taken while in this function
STATIC qstr qstr_add(mp_uint_t hash, mp_uint_t len, const char *q_ptr) {
STATIC qstr qstr_add(mp_uint_t len, const char *q_ptr) {
#if MICROPY_QSTR_BYTES_IN_HASH
mp_uint_t hash = qstr_compute_hash((const byte *)q_ptr, len);
DEBUG_printf("QSTR: add hash=%d len=%d data=%.*s\n", hash, len, len, q_ptr);
#else
DEBUG_printf("QSTR: add len=%d data=%.*s\n", len, len, q_ptr);
#endif

// make sure we have room in the pool for a new qstr
if (MP_STATE_VM(last_pool)->len >= MP_STATE_VM(last_pool)->alloc) {
Expand All @@ -199,7 +216,11 @@ STATIC qstr qstr_add(mp_uint_t hash, mp_uint_t len, const char *q_ptr) {
new_alloc = MAX(MICROPY_ALLOC_QSTR_ENTRIES_INIT, new_alloc);
#endif
mp_uint_t pool_size = sizeof(qstr_pool_t)
+ (sizeof(const char *) + sizeof(qstr_hash_t) + sizeof(qstr_len_t)) * new_alloc;
+ (sizeof(const char *)
#if MICROPY_QSTR_BYTES_IN_HASH
+ sizeof(qstr_hash_t)
#endif
+ sizeof(qstr_len_t)) * new_alloc;
qstr_pool_t *pool = (qstr_pool_t *)m_malloc_maybe(pool_size);
if (pool == NULL) {
// Keep qstr_last_chunk consistent with qstr_pool_t: qstr_last_chunk is not scanned
Expand All @@ -211,8 +232,12 @@ STATIC qstr qstr_add(mp_uint_t hash, mp_uint_t len, const char *q_ptr) {
QSTR_EXIT();
m_malloc_fail(new_alloc);
}
#if MICROPY_QSTR_BYTES_IN_HASH
pool->hashes = (qstr_hash_t *)(pool->qstrs + new_alloc);
pool->lengths = (qstr_len_t *)(pool->hashes + new_alloc);
#else
pool->lengths = (qstr_len_t *)(pool->qstrs + new_alloc);
#endif
pool->prev = MP_STATE_VM(last_pool);
pool->total_prev_len = MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len;
pool->alloc = new_alloc;
Expand All @@ -223,7 +248,9 @@ STATIC qstr qstr_add(mp_uint_t hash, mp_uint_t len, const char *q_ptr) {

// add the new qstr
mp_uint_t at = MP_STATE_VM(last_pool)->len;
#if MICROPY_QSTR_BYTES_IN_HASH
MP_STATE_VM(last_pool)->hashes[at] = hash;
#endif
MP_STATE_VM(last_pool)->lengths[at] = len;
MP_STATE_VM(last_pool)->qstrs[at] = q_ptr;
MP_STATE_VM(last_pool)->len++;
Expand All @@ -238,8 +265,10 @@ qstr qstr_find_strn(const char *str, size_t str_len) {
return MP_QSTR_;
}

#if MICROPY_QSTR_BYTES_IN_HASH
// work out hash of str
size_t str_hash = qstr_compute_hash((const byte *)str, str_len);
#endif

// search pools for the data
for (const qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL; pool = pool->prev) {
Expand All @@ -261,7 +290,11 @@ qstr qstr_find_strn(const char *str, size_t str_len) {

// sequential search for the remaining strings
for (mp_uint_t at = low; at < high + 1; at++) {
if (pool->hashes[at] == str_hash && pool->lengths[at] == str_len
if (
#if MICROPY_QSTR_BYTES_IN_HASH
pool->hashes[at] == str_hash &&
#endif
pool->lengths[at] == str_len
&& memcmp(pool->qstrs[at], str, str_len) == 0) {
return pool->total_prev_len + at;
}
Expand Down Expand Up @@ -329,18 +362,21 @@ qstr qstr_from_strn(const char *str, size_t len) {
MP_STATE_VM(qstr_last_used) += n_bytes;

// store the interned strings' data
size_t hash = qstr_compute_hash((const byte *)str, len);
memcpy(q_ptr, str, len);
q_ptr[len] = '\0';
q = qstr_add(hash, len, q_ptr);
q = qstr_add(len, q_ptr);
}
QSTR_EXIT();
return q;
}

mp_uint_t qstr_hash(qstr q) {
const qstr_pool_t *pool = find_qstr(&q);
#if MICROPY_QSTR_BYTES_IN_HASH
return pool->hashes[q];
#else
return qstr_compute_hash((byte *)pool->qstrs[q], pool->lengths[q]);
#endif
}

size_t qstr_len(qstr q) {
Expand Down Expand Up @@ -375,7 +411,11 @@ void qstr_pool_info(size_t *n_pool, size_t *n_qstr, size_t *n_str_data_bytes, si
*n_total_bytes += gc_nbytes(pool); // this counts actual bytes used in heap
#else
*n_total_bytes += sizeof(qstr_pool_t)
+ (sizeof(const char *) + sizeof(qstr_hash_t) + sizeof(qstr_len_t)) * pool->alloc;
+ (sizeof(const char *)
#if MICROPY_QSTR_BYTES_IN_HASH
+ sizeof(qstr_hash_t)
#endif
+ sizeof(qstr_len_t)) * pool->alloc;
#endif
}
*n_total_bytes += *n_str_data_bytes;
Expand Down
7 changes: 6 additions & 1 deletion py/qstr.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -60,7 +60,9 @@ enum {
typedef size_t qstr;
typedef uint16_t qstr_short_t;

#if MICROPY_QSTR_BYTES_IN_HASH == 1
#if MICROPY_QSTR_BYTES_IN_HASH == 0
// No qstr_hash_t type needed.
#elif MICROPY_QSTR_BYTES_IN_HASH == 1
typedef uint8_t qstr_hash_t;
#elif MICROPY_QSTR_BYTES_IN_HASH == 2
typedef uint16_t qstr_hash_t;
Expand All @@ -82,7 +84,9 @@ typedef struct _qstr_pool_t {
size_t is_sorted : 1;
size_t alloc;
size_t len;
#if MICROPY_QSTR_BYTES_IN_HASH
qstr_hash_t *hashes;
#endif
qstr_len_t *lengths;
const char *qstrs[];
} qstr_pool_t;
Expand All @@ -92,6 +96,7 @@ typedef struct _qstr_pool_t {
void qstr_init(void);

size_t qstr_compute_hash(const byte *data, size_t len);

qstr qstr_find_strn(const char *str, size_t str_len); // returns MP_QSTRnull if not found

qstr qstr_from_str(const char *str);
Expand Down
27 changes: 12 additions & 15 deletions tools/mpy-tool.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1473,21 +1473,20 @@ def freeze_mpy(firmware_qstr_idents, compiled_modules):
raw_code_count = 0
raw_code_content = 0

print()
print("const qstr_hash_t mp_qstr_frozen_const_hashes[] = {")
qstr_size = {"metadata": 0, "data": 0}
for _, _, _, qbytes in new:
qhash = qstrutil.compute_hash(qbytes, config.MICROPY_QSTR_BYTES_IN_HASH)
print(" %d," % qhash)
print("};")
if config.MICROPY_QSTR_BYTES_IN_HASH:
print()
print("const qstr_hash_t mp_qstr_frozen_const_hashes[] = {")
for _, _, _, qbytes in new:
qhash = qstrutil.compute_hash(qbytes, config.MICROPY_QSTR_BYTES_IN_HASH)
print(" %d," % qhash)
qstr_content += config.MICROPY_QSTR_BYTES_IN_HASH
print("};")
print()
print("const qstr_len_t mp_qstr_frozen_const_lengths[] = {")
for _, _, _, qbytes in new:
print(" %d," % len(qbytes))
qstr_size["metadata"] += (
config.MICROPY_QSTR_BYTES_IN_LEN + config.MICROPY_QSTR_BYTES_IN_HASH
)
qstr_size["data"] += len(qbytes)
qstr_content += config.MICROPY_QSTR_BYTES_IN_LEN
qstr_content += len(qbytes) + 1 # include NUL
print("};")
print()
print("extern const qstr_pool_t mp_qstr_const_pool;")
Expand All @@ -1497,14 +1496,12 @@ def freeze_mpy(firmware_qstr_idents, compiled_modules):
print(" true, // is_sorted")
print(" %u, // allocated entries" % qstr_pool_alloc)
print(" %u, // used entries" % len(new))
print(" (qstr_hash_t *)mp_qstr_frozen_const_hashes,")
if config.MICROPY_QSTR_BYTES_IN_HASH:
print(" (qstr_hash_t *)mp_qstr_frozen_const_hashes,")
print(" (qstr_len_t *)mp_qstr_frozen_const_lengths,")
print(" {")
for _, _, qstr, qbytes in new:
print(' "%s",' % qstrutil.escape_bytes(qstr, qbytes))
qstr_content += (
config.MICROPY_QSTR_BYTES_IN_LEN + config.MICROPY_QSTR_BYTES_IN_HASH + len(qbytes) + 1
)
print(" },")
print("};")

Expand Down