Skip to content

Commit 7ee91cf

Browse files
dpgeorgedpgeorge
committed
py: Add option to cache map lookup results in bytecode.
This is a simple optimisation inspired by JITing technology: we cache in the bytecode (using 1 byte) the offset of the last successful lookup in a map. This allows us next time round to check in that location in the hash table (mp_map_t) for the desired entry, and if it's there use that entry straight away. Otherwise fallback to a normal map lookup. Works for LOAD_NAME, LOAD_GLOBAL, LOAD_ATTR and STORE_ATTR opcodes. On a few tests it gives >90% cache hit and greatly improves speed of code. Disabled by default. Enabled for unix and stmhal ports.
1 parent b4b10fd commit 7ee91cf

File tree

7 files changed

+142
-4
lines changed

7 files changed

+142
-4
lines changed

‎py/emitbc.c‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -510,16 +510,25 @@ STATIC void emit_bc_load_deref(emit_t *emit, qstr qst, mp_uint_t local_num) {
510510
STATIC void emit_bc_load_name(emit_t *emit, qstr qst) {
511511
emit_bc_pre(emit, 1);
512512
emit_write_bytecode_byte_qstr(emit, MP_BC_LOAD_NAME, qst);
513+
if (MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE) {
514+
emit_write_bytecode_byte(emit, 0);
515+
}
513516
}
514517

515518
STATIC void emit_bc_load_global(emit_t *emit, qstr qst) {
516519
emit_bc_pre(emit, 1);
517520
emit_write_bytecode_byte_qstr(emit, MP_BC_LOAD_GLOBAL, qst);
521+
if (MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE) {
522+
emit_write_bytecode_byte(emit, 0);
523+
}
518524
}
519525

520526
STATIC void emit_bc_load_attr(emit_t *emit, qstr qst) {
521527
emit_bc_pre(emit, 0);
522528
emit_write_bytecode_byte_qstr(emit, MP_BC_LOAD_ATTR, qst);
529+
if (MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE) {
530+
emit_write_bytecode_byte(emit, 0);
531+
}
523532
}
524533

525534
STATIC void emit_bc_load_method(emit_t *emit, qstr qst) {
@@ -565,6 +574,9 @@ STATIC void emit_bc_store_global(emit_t *emit, qstr qst) {
565574
STATIC void emit_bc_store_attr(emit_t *emit, qstr qst) {
566575
emit_bc_pre(emit, -2);
567576
emit_write_bytecode_byte_qstr(emit, MP_BC_STORE_ATTR, qst);
577+
if (MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE) {
578+
emit_write_bytecode_byte(emit, 0);
579+
}
568580
}
569581

570582
STATIC void emit_bc_store_subscr(emit_t *emit) {

‎py/mpconfig.h‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -182,6 +182,13 @@
182182
#define MICROPY_OPT_COMPUTED_GOTO (0)
183183
#endif
184184

185+
// Whether to cache result of map lookups in LOAD_NAME, LOAD_GLOBAL, LOAD_ATTR,
186+
// STORE_ATTR bytecodes. Uses 1 byte extra RAM for each of these opcodes and
187+
// uses a bit of extra code ROM, but greatly improves lookup speed.
188+
#ifndef MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
189+
#define MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE (0)
190+
#endif
191+
185192
/*****************************************************************************/
186193
/* Python internal features */
187194

‎py/objtype.c‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -456,7 +456,7 @@ STATIC mp_obj_t instance_binary_op(mp_uint_t op, mp_obj_t lhs_in, mp_obj_t rhs_i
456456
}
457457
}
458458

459-
STATIC void instance_load_attr(mp_obj_t self_in, qstr attr, mp_obj_t *dest) {
459+
void mp_obj_instance_load_attr(mp_obj_t self_in, qstr attr, mp_obj_t *dest) {
460460
// logic: look in obj members then class locals (TODO check this against CPython)
461461
assert(is_instance_type(mp_obj_get_type(self_in)));
462462
mp_obj_instance_t *self = self_in;
@@ -510,7 +510,7 @@ STATIC void instance_load_attr(mp_obj_t self_in, qstr attr, mp_obj_t *dest) {
510510
}
511511
}
512512

513-
STATIC bool instance_store_attr(mp_obj_t self_in, qstr attr, mp_obj_t value) {
513+
bool mp_obj_instance_store_attr(mp_obj_t self_in, qstr attr, mp_obj_t value) {
514514
mp_obj_instance_t *self = self_in;
515515

516516
#if MICROPY_PY_BUILTINS_PROPERTY
@@ -817,8 +817,8 @@ mp_obj_t mp_obj_new_type(qstr name, mp_obj_t bases_tuple, mp_obj_t locals_dict)
817817
o->make_new = instance_make_new;
818818
o->unary_op = instance_unary_op;
819819
o->binary_op = instance_binary_op;
820-
o->load_attr = instance_load_attr;
821-
o->store_attr = instance_store_attr;
820+
o->load_attr = mp_obj_instance_load_attr;
821+
o->store_attr = mp_obj_instance_store_attr;
822822
o->subscr = instance_subscr;
823823
o->call = mp_obj_instance_call;
824824
o->getiter = instance_getiter;

‎py/objtype.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,10 @@ typedef struct _mp_obj_instance_t {
3737
// TODO maybe cache __getattr__ and __setattr__ for efficient lookup of them
3838
} mp_obj_instance_t;
3939

40+
// these need to be exposed for MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE to work
41+
void mp_obj_instance_load_attr(mp_obj_t self_in, qstr attr, mp_obj_t *dest);
42+
bool mp_obj_instance_store_attr(mp_obj_t self_in, qstr attr, mp_obj_t value);
43+
4044
// these need to be exposed so mp_obj_is_callable can work correctly
4145
bool mp_obj_instance_is_callable(mp_obj_t self_in);
4246
mp_obj_t mp_obj_instance_call(mp_obj_t self_in, mp_uint_t n_args, mp_uint_t n_kw, const mp_obj_t *args);

‎py/vm.c‎

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@
3232
#include "py/mpstate.h"
3333
#include "py/nlr.h"
3434
#include "py/emitglue.h"
35+
#include "py/objtype.h"
3536
#include "py/runtime.h"
3637
#include "py/bc0.h"
3738
#include "py/bc.h"
@@ -248,26 +249,101 @@ mp_vm_return_kind_t mp_execute_bytecode(mp_code_state *code_state, volatile mp_o
248249
goto load_check;
249250
}
250251

252+
#if !MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
251253
ENTRY(MP_BC_LOAD_NAME): {
252254
MARK_EXC_IP_SELECTIVE();
253255
DECODE_QSTR;
254256
PUSH(mp_load_name(qst));
255257
DISPATCH();
256258
}
259+
#else
260+
ENTRY(MP_BC_LOAD_NAME): {
261+
MARK_EXC_IP_SELECTIVE();
262+
DECODE_QSTR;
263+
mp_obj_t key = MP_OBJ_NEW_QSTR(qst);
264+
mp_uint_t x = *ip;
265+
if (x < MP_STATE_CTX(dict_locals)->map.alloc && MP_STATE_CTX(dict_locals)->map.table[x].key == key) {
266+
PUSH(MP_STATE_CTX(dict_locals)->map.table[x].value);
267+
} else {
268+
mp_map_elem_t *elem = mp_map_lookup(&MP_STATE_CTX(dict_locals)->map, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
269+
if (elem != NULL) {
270+
*(byte*)ip = (elem - &MP_STATE_CTX(dict_locals)->map.table[0]) & 0xff;
271+
PUSH(elem->value);
272+
} else {
273+
PUSH(mp_load_name(MP_OBJ_QSTR_VALUE(key)));
274+
}
275+
}
276+
ip++;
277+
DISPATCH();
278+
}
279+
#endif
257280

281+
#if !MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
258282
ENTRY(MP_BC_LOAD_GLOBAL): {
259283
MARK_EXC_IP_SELECTIVE();
260284
DECODE_QSTR;
261285
PUSH(mp_load_global(qst));
262286
DISPATCH();
263287
}
288+
#else
289+
ENTRY(MP_BC_LOAD_GLOBAL): {
290+
MARK_EXC_IP_SELECTIVE();
291+
DECODE_QSTR;
292+
mp_obj_t key = MP_OBJ_NEW_QSTR(qst);
293+
mp_uint_t x = *ip;
294+
if (x < MP_STATE_CTX(dict_globals)->map.alloc && MP_STATE_CTX(dict_globals)->map.table[x].key == key) {
295+
PUSH(MP_STATE_CTX(dict_globals)->map.table[x].value);
296+
} else {
297+
mp_map_elem_t *elem = mp_map_lookup(&MP_STATE_CTX(dict_globals)->map, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
298+
if (elem != NULL) {
299+
*(byte*)ip = (elem - &MP_STATE_CTX(dict_globals)->map.table[0]) & 0xff;
300+
PUSH(elem->value);
301+
} else {
302+
PUSH(mp_load_global(MP_OBJ_QSTR_VALUE(key)));
303+
}
304+
}
305+
ip++;
306+
DISPATCH();
307+
}
308+
#endif
264309

310+
#if !MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
265311
ENTRY(MP_BC_LOAD_ATTR): {
266312
MARK_EXC_IP_SELECTIVE();
267313
DECODE_QSTR;
268314
SET_TOP(mp_load_attr(TOP(), qst));
269315
DISPATCH();
270316
}
317+
#else
318+
ENTRY(MP_BC_LOAD_ATTR): {
319+
MARK_EXC_IP_SELECTIVE();
320+
DECODE_QSTR;
321+
mp_obj_t top = TOP();
322+
if (mp_obj_get_type(top)->load_attr == mp_obj_instance_load_attr) {
323+
mp_obj_instance_t *self = top;
324+
mp_uint_t x = *ip;
325+
mp_obj_t key = MP_OBJ_NEW_QSTR(qst);
326+
mp_map_elem_t *elem;
327+
if (x < self->members.alloc && self->members.table[x].key == key) {
328+
elem = &self->members.table[x];
329+
} else {
330+
elem = mp_map_lookup(&self->members, key, MP_MAP_LOOKUP);
331+
if (elem != NULL) {
332+
*(byte*)ip = elem - &self->members.table[0];
333+
} else {
334+
goto load_attr_cache_fail;
335+
}
336+
}
337+
SET_TOP(elem->value);
338+
ip++;
339+
DISPATCH();
340+
}
341+
load_attr_cache_fail:
342+
SET_TOP(mp_load_attr(top, qst));
343+
ip++;
344+
DISPATCH();
345+
}
346+
#endif
271347

272348
ENTRY(MP_BC_LOAD_METHOD): {
273349
MARK_EXC_IP_SELECTIVE();
@@ -315,13 +391,50 @@ mp_vm_return_kind_t mp_execute_bytecode(mp_code_state *code_state, volatile mp_o
315391
DISPATCH();
316392
}
317393

394+
#if !MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
318395
ENTRY(MP_BC_STORE_ATTR): {
319396
MARK_EXC_IP_SELECTIVE();
320397
DECODE_QSTR;
321398
mp_store_attr(sp[0], qst, sp[-1]);
322399
sp -= 2;
323400
DISPATCH();
324401
}
402+
#else
403+
// This caching code works with MICROPY_PY_BUILTINS_PROPERTY enabled because
404+
// if the attr exists in self->members then it can't be a property. A
405+
// consequence of this is that we can't use MP_MAP_LOOKUP_ADD_IF_NOT_FOUND
406+
// in the fast-path below, because that store could override a property.
407+
ENTRY(MP_BC_STORE_ATTR): {
408+
MARK_EXC_IP_SELECTIVE();
409+
DECODE_QSTR;
410+
mp_obj_t top = TOP();
411+
if (mp_obj_get_type(top)->store_attr == mp_obj_instance_store_attr && sp[-1] != MP_OBJ_NULL) {
412+
mp_obj_instance_t *self = top;
413+
mp_uint_t x = *ip;
414+
mp_obj_t key = MP_OBJ_NEW_QSTR(qst);
415+
mp_map_elem_t *elem;
416+
if (x < self->members.alloc && self->members.table[x].key == key) {
417+
elem = &self->members.table[x];
418+
} else {
419+
elem = mp_map_lookup(&self->members, key, MP_MAP_LOOKUP);
420+
if (elem != NULL) {
421+
*(byte*)ip = elem - &self->members.table[0];
422+
} else {
423+
goto store_attr_cache_fail;
424+
}
425+
}
426+
elem->value = sp[-1];
427+
sp -= 2;
428+
ip++;
429+
DISPATCH();
430+
}
431+
store_attr_cache_fail:
432+
mp_store_attr(sp[0], qst, sp[-1]);
433+
sp -= 2;
434+
ip++;
435+
DISPATCH();
436+
}
437+
#endif
325438

326439
ENTRY(MP_BC_STORE_SUBSCR):
327440
MARK_EXC_IP_SELECTIVE();

‎stmhal/mpconfigport.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@
4040
#define MICROPY_LONGINT_IMPL (MICROPY_LONGINT_IMPL_MPZ)
4141
#define MICROPY_FLOAT_IMPL (MICROPY_FLOAT_IMPL_FLOAT)
4242
#define MICROPY_OPT_COMPUTED_GOTO (1)
43+
#define MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE (1)
4344
/* Enable FatFS LFNs
4445
0: Disable LFN feature.
4546
1: Enable LFN with static working buffer on the BSS. Always NOT reentrant.

‎unix/mpconfigport.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,7 @@
5050
#define MICROPY_LONGINT_IMPL (MICROPY_LONGINT_IMPL_MPZ)
5151
#define MICROPY_STREAMS_NON_BLOCK (1)
5252
#define MICROPY_OPT_COMPUTED_GOTO (1)
53+
#define MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE (1)
5354
#define MICROPY_CAN_OVERRIDE_BUILTINS (1)
5455
#define MICROPY_PY_BUILTINS_STR_UNICODE (1)
5556
#define MICROPY_PY_BUILTINS_MEMORYVIEW (1)

0 commit comments

Comments
 (0)