py/qstr: Add support for sorted qstr pools.
This provides a significant performance boost for qstr_find_strn, which is
called a lot during parsing and loading of .mpy files, as well as interning
of string objects (which happens in most string methods that return new
strings).
Also adds comments to explain the "static" qstrs. These are part of the
.mpy ABI and avoid needing to duplicate string data for QSTRs known to
already be in the firmware. The static pool isn't currently sorted, but in
the future we could either split the static pool into the sorted regions,
or in the next .mpy version just sort them.
Based on initial work done by @amirgon in #6896.
This work was funded through GitHub Sponsors.
Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
diff --git a/py/qstr.h b/py/qstr.h
index 0ef861f..0c4fc46 100644
--- a/py/qstr.h
+++ b/py/qstr.h
@@ -38,9 +38,21 @@
// first entry in enum will be MP_QSTRnull=0, which indicates invalid/no qstr
enum {
#ifndef NO_QSTR
-#define QDEF(id, hash, len, str) id,
+#define QDEF0(id, hash, len, str) id,
+#define QDEF1(id, hash, len, str)
#include "genhdr/qstrdefs.generated.h"
-#undef QDEF
+#undef QDEF0
+#undef QDEF1
+ #endif
+ MP_QSTRnumber_of_static,
+ MP_QSTRstart_of_main = MP_QSTRnumber_of_static - 1, // unused but shifts the enum counter back one
+
+ #ifndef NO_QSTR
+#define QDEF0(id, hash, len, str)
+#define QDEF1(id, hash, len, str) id,
+ #include "genhdr/qstrdefs.generated.h"
+#undef QDEF0
+#undef QDEF1
#endif
MP_QSTRnumber_of, // no underscore so it can't clash with any of the above
};
@@ -66,7 +78,8 @@
typedef struct _qstr_pool_t {
const struct _qstr_pool_t *prev;
- size_t total_prev_len;
+ size_t total_prev_len : (8 * sizeof(size_t) - 1);
+ size_t is_sorted : 1;
size_t alloc;
size_t len;
qstr_hash_t *hashes;