8000 py/qstr: Separate hash and len from string data. · iabdalkader/micropython@18b1ba0 · GitHub 10000
[go: up one dir, main page]
Skip to content

Commit 18b1ba0

Browse files
tyomitchdpgeorge
tyomitch
authored and
dpgeorge
committed
py/qstr: Separate hash and len from string data.
This allows the compiler to merge strings: e.g. "update", "difference_update" and "symmetric_difference_update" will all point to the same memory. No functional change. The size reduction depends on the number of qstrs in the build. The change this commit brings is: bare-arm: -4 -0.007% minimal x86: +150 +0.092% [incl +48(data)] unix x64: -608 -0.118% unix nanbox: -572 -0.126% [incl +32(data)] stm32: -1392 -0.352% PYBV10 cc3200: -448 -0.244% esp8266: -1208 -0.173% GENERIC esp32: -1028 -0.068% GENERIC[incl -1020(data)] nrf: -440 -0.252% pca10040 rp2: -1072 -0.217% PICO samd: -368 -0.264% ADAFRUIT_ITSYBITSY_M4_EXPRESS Performance is also improved (on bare metal at least) for the core_import_mpy_multi.py, core_import_mpy_single.py and core_qstr.py performance benchmarks. Originally at adafruit#4583 Signed-off-by: Artyom Skrobov <tyomitch@gmail.com>
1 parent e8bc4a3 commit 18b1ba0

File tree

5 files changed

+122
-94
lines changed

5 files changed

+122
-94
lines changed

‎py/makeqstrdata.py

Lines changed: 12 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -317,26 +317,24 @@ def parse_input_headers(infiles):
317317
return qcfgs, qstrs
318318

319319

320-
def make_bytes(cfg_bytes_len, cfg_bytes_hash, qstr):
321-
qbytes = bytes_cons(qstr, "utf8")
322-
qlen = len(qbytes)
323-
qhash = compute_hash(qbytes, cfg_bytes_hash)
320+
def escape_bytes(qstr, qbytes):
324321
if all(32 <= ord(c) <= 126 and c != "\\" and c != '"' for c in qstr):
325322
# qstr is all printable ASCII so render it as-is (for easier debugging)
326-
qdata = qstr
323+
return qstr
327324
else:
328325
# qstr contains non-printable codes so render entire thing as hex pairs
329-
qdata = "".join(("\\x%02x" % b) for b in qbytes)
326+
return "".join(("\\x%02x" % b) for b in qbytes)
327+
328+
329+
def make_bytes(cfg_bytes_len, cfg_bytes_hash, qstr):
330+
qbytes = bytes_cons(qstr, "utf8")
331+
qlen = len(qbytes)
332+
qhash = compute_hash(qbytes, cfg_bytes_hash)
330333
if qlen >= (1 << (8 * cfg_bytes_len)):
331334
print("qstr is too long:", qstr)
332335
assert False
333-
qlen_str = ("\\x%02x" * cfg_bytes_len) % tuple(
334-
((qlen >> (8 * i)) & 0xFF) for i in range(cfg_bytes_len)
335-
)
336-
qhash_str = ("\\x%02x" * cfg_bytes_hash) % tuple(
337-
((qhash >> (8 * i)) & 0xFF) for i in range(cfg_bytes_hash)
338-
)
339-
return '(const byte*)"%s%s" "%s"' % (qhash_str, qlen_str, qdata)
336+
qdata = escape_bytes(qstr, qbytes)
337+
return '%d, %d, "%s"' % (qhash, qlen, qdata)
340338

341339

342340
def print_qstr_data(qcfgs, qstrs):
@@ -349,10 +347,7 @@ def print_qstr_data(qcfgs, qstrs):
349347
print("")
350348

351349
# add NULL qstr with no hash or data
352-
print(
353-
'QDEF(MP_QSTRnull, (const byte*)"%s%s" "")'
354-
% ("\\x00" * cfg_bytes_hash, "\ F438 \x00" * cfg_bytes_len)
355-
)
350+
print('QDEF(MP_QSTRnull, 0, 0, "")')
356351

357352
# go through each qstr and print it out
358353
for order, ident, qstr in sorted(qstrs.values(), key=lambda x: x[0]):

‎py/mpstate.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -202,7 +202,7 @@ typedef struct _mp_state_vm_t {
202202

203203
// pointer and sizes to store interned string data
204204
// (qstr_last_chunk can be root pointer but is also stored in qstr pool)
205-
byte *qstr_last_chunk;
205+
char *qstr_last_chunk;
206206
size_t qstr_last_alloc;
207207
size_t qstr_last_used;
208208

‎py/qstr.c

Lines changed: 68 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,6 @@
3535

3636
// NOTE: we are using linear arrays to store and search for qstr's (unique strings, interned strings)
3737
// ultimately we will replace this with a static hash table of some kind
38-
// also probably need to include the length in the string data, to allow null bytes in the string
3938

4039
#if MICROPY_DEBUG_VERBOSE // print debugging info
4140
#define DEBUG_printf DEBUG_printf
@@ -44,34 +43,9 @@
4443
#endif
4544

4645
// A qstr is an index into the qstr pool.
47-
// The data for a qstr contains (hash, length, data):
48-
// - hash (configurable number of bytes)
49-
// - length (configurable number of bytes)
50-
// - data ("length" number of bytes)
51-
// - \0 terminated (so they can be printed using printf)
52-
53-
#if MICROPY_QSTR_BYTES_IN_HASH == 1
54-
#define Q_HASH_MASK (0xff)
55-
#define Q_GET_HASH(q) ((mp_uint_t)(q)[0])
56-
#define Q_SET_HASH(q, hash) do { (q)[0] = (hash); } while (0)
57-
#elif MICROPY_QSTR_BYTES_IN_HASH == 2
58-
#define Q_HASH_MASK (0xffff)
59-
#define Q_GET_HASH(q) ((mp_uint_t)(q)[0] | ((mp_uint_t)(q)[1] << 8))
60-
#define Q_SET_HASH(q, hash) do { (q)[0] = (hash); (q)[1] = (hash) >> 8; } while (0)
61-
#else
62-
#error unimplemented qstr hash decoding
63-
#endif
64-
#define Q_GET_ALLOC(q) (MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + Q_GET_LENGTH(q) + 1)
65-
#define Q_GET_DATA(q) ((q) + MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN)
66-
#if MICROPY_QSTR_BYTES_IN_LEN == 1
67-
#define Q_GET_LENGTH(q) ((q)[MICROPY_QSTR_BYTES_IN_HASH])
68-
#define Q_SET_LENGTH(q, len) do { (q)[MICROPY_QSTR_BYTES_IN_HASH] = (len); } while (0)
69-
#elif MICROPY_QSTR_BYTES_IN_LEN == 2
70-
#define Q_GET_LENGTH(q) ((q)[MICROPY_QSTR_BYTES_IN_HASH] | ((q)[MICROPY_QSTR_BYTES_IN_HASH + 1] << 8))
71-
#define Q_SET_LENGTH(q, len) do { (q)[MICROPY_QSTR_BYTES_IN_HASH] = (len); (q)[MICROPY_QSTR_BYTES_IN_HASH + 1] = (len) >> 8; } while (0)
72-
#else
73-
#error unimplemented qstr length decoding
74-
#endif
46+
// The data for a qstr is \0 terminated (so they can be printed using printf)
47+
48+
#define Q_HASH_MASK ((1 << (8 * MICROPY_QSTR_BYTES_IN_HASH)) - 1)
7549

7650
#if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
7751
#define QSTR_ENTER() mp_thread_mutex_lock(&MP_STATE_VM(qstr_mutex), 1)
@@ -100,14 +74,32 @@ mp_uint_t qstr_compute_hash(const byte *data, size_t len) {
10074
return hash;
10175
}
10276

77+
const qstr_hash_t mp_qstr_const_hashes[] = {
78+
#ifndef NO_QSTR
79+
#define QDEF(id, hash, len, str) hash,
80+
#include "genhdr/qstrdefs.generated.h"
81+
#undef QDEF
82+
#endif
83+
};
84+
85+
const qstr_len_t mp_qstr_const_lengths[] = {
86+
#ifndef NO_QSTR
87+
#define QDEF(id, hash, len, str) len,
88+
#include "genhdr/qstrdefs.generated.h"
89+
#undef QDEF
90+
#endif
91+
};
92+
10393
const qstr_pool_t mp_qstr_const_pool = {
10494
NULL, // no previous pool
10595
0, // no previous pool
10696
MICROPY_ALLOC_QSTR_ENTRIES_INIT,
10797
MP_QSTRnumber_of, // corresponds to number of strings in array just below
98+
(qstr_hash_t *)mp_qstr_const_hashes,
99+
(qstr_len_t *)mp_qstr_const_lengths,
108100
{
109101
#ifndef NO_QSTR
110-
#define QDEF(id, str) str,
102+
#define QDEF(id, hash, len, str) str,
111103
#include "genhdr/qstrdefs.generated.h"
112104
#undef QDEF
113105
#endif
@@ -130,19 +122,21 @@ void qstr_init(void) {
130122
#endif
131123
}
132124

133-
STATIC const byte *find_qstr(qstr q) {
125+
STATIC qstr_pool_t *find_qstr(qstr *q) {
134126
// search pool for this qstr
135127
// total_prev_len==0 in the final pool, so the loop will always terminate
136128
qstr_pool_t *pool = MP_STATE_VM(last_pool);
137-
while (q < pool->total_prev_len) {
129+
while (*q < pool->total_prev_len) {
138130
pool = pool->prev;
139131
}
140-
return pool->qstrs[q - pool->total_prev_len];
132+
*q -= pool->total_prev_len;
133+
assert(*q < pool->len);
134+
return pool;
141135
}
142136

143137
// qstr_mutex must be taken while in this function
144-
STATIC qstr qstr_add(const byte *q_ptr) {
145-
DEBUG_printf("QSTR: add hash=%d len=%d data=%.*s\n", Q_GET_HASH(q_ptr), Q_GET_LENGTH(q_ptr), Q_GET_LENGTH(q_ptr), Q_GET_DATA(q_ptr));
138+
STATIC qstr qstr_add(mp_uint_t hash, mp_uint_t len, const char *q_ptr) {
139+
DEBUG_printf("QSTR: add hash=%d len=%d data=%.*s\n", hash, len, len, q_ptr);
146140

147141
// make sure we have room in the pool for a new qstr
148142
if (MP_STATE_VM(last_pool)->len >= MP_STATE_VM(last_pool)->alloc) {
@@ -151,7 +145,9 @@ STATIC qstr qstr_add(const byte *q_ptr) {
151145
// Put a lower bound on the allocation size in case the extra qstr pool has few entries
152 57AE 146
new_alloc = MAX(MICROPY_ALLOC_QSTR_ENTRIES_INIT, new_alloc);
153147
#endif
154-
qstr_pool_t *pool = m_new_obj_var_maybe(qstr_pool_t, const char *, new_alloc);
148+
mp_uint_t pool_size = sizeof(qstr_pool_t)
149+
+ (sizeof(const char *) + sizeof(qstr_hash_t) + sizeof(qstr_len_t)) * new_alloc;
150+
qstr_pool_t *pool = (qstr_pool_t *)m_malloc_maybe(pool_size);
155151
if (pool == NULL) {
156152
// Keep qstr_last_chunk consistent with qstr_pool_t: qstr_last_chunk is not scanned
157153
// at garbage collection since it's reachable from a qstr_pool_t. And the caller of
@@ -162,6 +158,8 @@ STATIC qstr qstr_add(const byte *q_ptr) {
162158
QSTR_EXIT();
163159
m_malloc_fail(new_alloc);
164160
}
161+
pool->hashes = (qstr_hash_t *)(pool->qstrs + new_alloc);
162+
pool->lengths = (qstr_len_t *)(pool->hashes + new_alloc);
165163
pool->prev = MP_STATE_VM(last_pool);
166164
pool->total_prev_len = MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len;
167165
pool->alloc = new_alloc;
@@ -171,10 +169,14 @@ STATIC qstr qstr_add(const byte *q_ptr) {
171169
}
172170

173171
// add the new qstr
174-
MP_STATE_VM(last_pool)->qstrs[MP_STATE_VM(last_pool)->len++] = q_ptr;
172+
mp_uint_t at = MP_STATE_VM(last_pool)->len;
173+
MP_STATE_VM(last_pool)->hashes[at] = hash;
174+
MP_STATE_VM(last_pool)->lengths[at] = len;
175+
MP_STATE_VM(last_pool)->qstrs[at] = q_ptr;
176+
MP_STATE_VM(last_pool)->len++;
175177

176178
// return id for the newly-added qstr
177-
return MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len - 1;
179+
return MP_STATE_VM(last_pool)->total_prev_len + at;
178180
}
179181

180182
qstr qstr_find_strn(const char *str, size_t str_len) {
@@ -183,9 +185,10 @@ qstr qstr_find_strn(const char *str, size_t str_len) {
183185

184186
// search pools for the data
185187
for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL; pool = pool->prev) {
186-
for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
187-
if (Q_GET_HASH(*q) == str_hash && Q_GET_LENGTH(*q) == str_len && memcmp(Q_GET_DATA(*q), str, str_len) == 0) {
188-
return pool->total_prev_len + (q - pool->qstrs);
188+
for (mp_uint_t at = 0, top = pool->len; at < top; at++) {
189+
if (pool->hashes[at] == str_hash && pool->lengths[at] == str_len
190+
&& memcmp(pool->qstrs[at], str, str_len) == 0) {
191+
return pool->total_prev_len + at;
189192
}
190193
}
191194
}
@@ -211,14 +214,14 @@ qstr qstr_from_strn(const char *str, size_t len) {
211214
}
212215

213216
// compute number of bytes needed to intern this string
214-
size_t n_bytes = MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len + 1;
217+
size_t n_bytes = len + 1;
215218

216219
if (MP_STATE_VM(qstr_last_chunk) != NULL && MP_STATE_VM(qstr_last_used) + n_bytes > MP_STATE_VM(qstr_last_alloc)) {
217220
// not enough room at end of previously interned string so try to grow
218-
byte *new_p = m_renew_maybe(byte, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_alloc) + n_bytes, false);
221+
char *new_p = m_renew_maybe(char, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_alloc) + n_bytes, false);
219222
if (new_p == NULL) {
220223
// could not grow existing memory; shrink it to fit previous
221-
(void)m_renew_maybe(byte, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_used), false);
224+
(void)m_renew_maybe(char, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_used), false);
222225
MP_STATE_VM(qstr_last_chunk) = NULL;
223226
} else {
224227
// could grow existing memory
@@ -232,10 +235,10 @@ qstr qstr_from_strn(const char *str, size_t len) {
232235
if (al < MICROPY_ALLOC_QSTR_CHUNK_INIT) {
233236
al = MICROPY_ALLOC_QSTR_CHUNK_INIT;
234237
}
235-
MP_STATE_VM(qstr_last_chunk) = m_new_maybe(byte, al);
238+
MP_STATE_VM(qstr_last_chunk) = m_new_maybe(char, al);
236239
if (MP_STATE_VM(qstr_last_chunk) == NULL) {
237240
// failed to allocate a large chunk so try with exact size
238-
MP_STATE_VM(qstr_last_chunk) = m_new_maybe(byte, n_bytes);
241+
MP_STATE_VM(qstr_last_chunk) = m_new_maybe(char, n_bytes);
239242
if (MP_STATE_VM(qstr_last_chunk) == NULL) {
240243
QSTR_EXIT();
241244
m_malloc_fail(n_bytes);
@@ -247,40 +250,38 @@ qstr qstr_from_strn(const char *str, size_t len) {
247250
}
248251

249252
// allocate memory from the chunk for this new interned string's data
250-
byte *q_ptr = MP_STATE_VM(qstr_last_chunk) + MP_STATE_VM(qstr_last_used);
253+
char *q_ptr = MP_STATE_VM(qstr_last_chunk) + MP_STATE_VM(qstr_last_used);
251254
MP_STATE_VM(qstr_last_used) += n_bytes;
252255

253256
// store the interned strings' data
254257
mp_uint_t hash = qstr_compute_hash((const byte *)str, len);
255-
Q_SET_HASH(q_ptr, hash);
256-
Q_SET_LENGTH(q_ptr, len);
257-
memcpy(q_ptr + MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN, str, len);
258-
q_ptr[MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len] = '\0';
259-
q = qstr_add(q_ptr);
258+
memcpy(q_ptr, str, len);
259+
q_ptr[len] = '\0';
260+
q = qstr_add(hash, len, q_ptr);
260261
}
261262
QSTR_EXIT();
262263
return q;
263264
}
264265

265266
mp_uint_t qstr_hash(qstr q) {
266-
const byte *qd = find_qstr(q);
267-
return Q_GET_HASH(qd);
267+
qstr_pool_t *pool = find_qstr(&q);
268+
return pool->hashes[q];
268269
}
269270

270271
size_t qstr_len(qstr q) {
271-
const byte *qd = find_qstr(q);
272-
return Q_GET_LENGTH(qd);
272+
qstr_pool_t *pool = find_qstr(&q);
273+
return pool->lengths[q];
273274
}
274275

275276
const char *qstr_str(qstr q) {
276-
const byte *qd = find_qstr(q);
277-
return (const char *)Q_GET_DATA(qd);
277+
qstr_pool_t *pool = find_qstr(&q);
278+
return pool->qstrs[q];
278279
}
279280

280281
const byte *qstr_data(qstr q, size_t *len) {
281-
const byte *qd = find_qstr(q);
282-
*len = Q_GET_LENGTH(qd);
283-
return Q_GET_DATA(qd);
282+
qstr_pool_t *pool = find_qstr(&q);
283+
*len = pool->lengths[q];
284+
return (byte *)pool->qstrs[q];
284285
}
285286

286287
void qstr_pool_info(size_t *n_pool, size_t *n_qstr, size_t *n_str_data_bytes, size_t *n_total_bytes) {
@@ -292,13 +293,14 @@ void qstr_pool_info(size_t *n_pool, size_t *n_qstr, size_t *n_str_data_bytes, si
292293
for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
293294
*n_pool += 1;
294295
*n_qstr += pool->len;
295-
for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
296-
*n_str_data_bytes += Q_GET_ALLOC(*q);
296+
for (qstr_len_t *l = pool->lengths, *l_top = pool->lengths + pool->len; l < l_top; l++) {
297+
*n_str_data_bytes += *l + 1;
297298
}
298299
#if MICROPY_ENABLE_GC
299300
*n_total_bytes += gc_nbytes(pool); // this counts actual bytes used in heap
300301
#else
301-
*n_total_bytes += sizeof(qstr_pool_t) + sizeof(qstr) * pool->alloc;
302+
*n_total_bytes += sizeof(qstr_pool_t)
303+
+ (sizeof(const char *) + sizeof(qstr_hash_t) + sizeof(qstr_len_t)) * pool->alloc;
302304
#endif
303305
}
304306
*n_total_bytes += *n_str_data_bytes;
@@ -309,8 +311,8 @@ void qstr_pool_info(size_t *n_pool, size_t *n_qstr, size_t *n_str_data_bytes, si
309311
void qstr_dump_data(void) {
310312
QSTR_ENTER();
311313
for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
312-
for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
313-
mp_printf(&mp_plat_print, "Q(%s)\n", Q_GET_DATA(*q));
314+
for (const char **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
315+
mp_printf(&mp_plat_print, "Q(%s)\n", *q);
314316
}
315317
}
316318
QSTR_EXIT();

‎py/qstr.h

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,7 @@
3838
// first entry in enum will be MP_QSTRnull=0, which indicates invalid/no qstr
3939
enum {
4040
#ifndef NO_QSTR
41-
#define QDEF(id, FD83 str) id,
41+
#define QDEF(id, hash, len, str) id,
4242
#include "genhdr/qstrdefs.generated.h"
4343
#undef QDEF
4444
#endif
@@ -47,12 +47,30 @@ enum {
4747

4848
typedef size_t qstr;
4949

50+
#if MICROPY_QSTR_BYTES_IN_HASH == 1
51+
typedef uint8_t qstr_hash_t;
52+
#elif MICROPY_QSTR_BYTES_IN_HASH == 2
53+
typedef uint16_t qstr_hash_t;
54+
#else
55+
#error unimplemented qstr hash decoding
56+
#endif
57+
58+
#if MICROPY_QSTR_BYTES_IN_LEN == 1
59+
typedef uint8_t qstr_len_t;
60+
#elif MICROPY_QSTR_BYTES_IN_LEN == 2
61+
typedef uint16_t qstr_len_t;
62+
#else
63+
#error unimplemented qstr length decoding
64+
#endif
65+
5066
typedef struct _qstr_pool_t {
5167
struct _qstr_pool_t *prev;
5268
size_t total_prev_len;
5369
size_t alloc;
5470
size_t len;
55-
const byte *qstrs[];
71+
qstr_hash_t *hashes;
72+
qstr_len_t *lengths;
73+
const char *qstrs[];
5674
} qstr_pool_t;
5775

5876
#define QSTR_TOTAL() (MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len)

0 commit comments

Comments
 (0)
0