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 files changed, 113 insertions, 0 deletions

diff --git a/py/vm.c b/py/vm.c
index 72dfb8a01..24280ee71 100644
--- a/py/vm.c
+++ b/py/vm.c
@@ -32,6 +32,7 @@
 #include "py/mpstate.h"
 #include "py/nlr.h"
 #include "py/emitglue.h"
+#include "py/objtype.h"
 #include "py/runtime.h"
 #include "py/bc0.h"
 #include "py/bc.h"
@@ -248,26 +249,101 @@ dispatch_loop:
                     goto load_check;
                 }
 
+                #if !MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
                 ENTRY(MP_BC_LOAD_NAME): {
                     MARK_EXC_IP_SELECTIVE();
                     DECODE_QSTR;
                     PUSH(mp_load_name(qst));
                     DISPATCH();
                 }
+                #else
+                ENTRY(MP_BC_LOAD_NAME): {
+                    MARK_EXC_IP_SELECTIVE();
+                    DECODE_QSTR;
+                    mp_obj_t key = MP_OBJ_NEW_QSTR(qst);
+                    mp_uint_t x = *ip;
+                    if (x < MP_STATE_CTX(dict_locals)->map.alloc && MP_STATE_CTX(dict_locals)->map.table[x].key == key) {
+                        PUSH(MP_STATE_CTX(dict_locals)->map.table[x].value);
+                    } else {
+                        mp_map_elem_t *elem = mp_map_lookup(&MP_STATE_CTX(dict_locals)->map, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
+                        if (elem != NULL) {
+                            *(byte*)ip = (elem - &MP_STATE_CTX(dict_locals)->map.table[0]) & 0xff;
+                            PUSH(elem->value);
+                        } else {
+                            PUSH(mp_load_name(MP_OBJ_QSTR_VALUE(key)));
+                        }
+                    }
+                    ip++;
+                    DISPATCH();
+                }
+                #endif
 
+                #if !MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
                 ENTRY(MP_BC_LOAD_GLOBAL): {
                     MARK_EXC_IP_SELECTIVE();
                     DECODE_QSTR;
                     PUSH(mp_load_global(qst));
                     DISPATCH();
                 }
+                #else
+                ENTRY(MP_BC_LOAD_GLOBAL): {
+                    MARK_EXC_IP_SELECTIVE();
+                    DECODE_QSTR;
+                    mp_obj_t key = MP_OBJ_NEW_QSTR(qst);
+                    mp_uint_t x = *ip;
+                    if (x < MP_STATE_CTX(dict_globals)->map.alloc && MP_STATE_CTX(dict_globals)->map.table[x].key == key) {
+                        PUSH(MP_STATE_CTX(dict_globals)->map.table[x].value);
+                    } else {
+                        mp_map_elem_t *elem = mp_map_lookup(&MP_STATE_CTX(dict_globals)->map, MP_OBJ_NEW_QSTR(qst), MP_MAP_LOOKUP);
+                        if (elem != NULL) {
+                            *(byte*)ip = (elem - &MP_STATE_CTX(dict_globals)->map.table[0]) & 0xff;
+                            PUSH(elem->value);
+                        } else {
+                            PUSH(mp_load_global(MP_OBJ_QSTR_VALUE(key)));
+                        }
+                    }
+                    ip++;
+                    DISPATCH();
+                }
+                #endif
 
+                #if !MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
                 ENTRY(MP_BC_LOAD_ATTR): {
                     MARK_EXC_IP_SELECTIVE();
                     DECODE_QSTR;
                     SET_TOP(mp_load_attr(TOP(), qst));
                     DISPATCH();
                 }
+                #else
+                ENTRY(MP_BC_LOAD_ATTR): {
+                    MARK_EXC_IP_SELECTIVE();
+                    DECODE_QSTR;
+                    mp_obj_t top = TOP();
+                    if (mp_obj_get_type(top)->load_attr == mp_obj_instance_load_attr) {
+                        mp_obj_instance_t *self = top;
+                        mp_uint_t x = *ip;
+                        mp_obj_t key = MP_OBJ_NEW_QSTR(qst);
+                        mp_map_elem_t *elem;
+                        if (x < self->members.alloc && self->members.table[x].key == key) {
+                            elem = &self->members.table[x];
+                        } else {
+                            elem = mp_map_lookup(&self->members, key, MP_MAP_LOOKUP);
+                            if (elem != NULL) {
+                                *(byte*)ip = elem - &self->members.table[0];
+                            } else {
+                                goto load_attr_cache_fail;
+                            }
+                        }
+                        SET_TOP(elem->value);
+                        ip++;
+                        DISPATCH();
+                    }
+                load_attr_cache_fail:
+                    SET_TOP(mp_load_attr(top, qst));
+                    ip++;
+                    DISPATCH();
+                }
+                #endif
 
                 ENTRY(MP_BC_LOAD_METHOD): {
                     MARK_EXC_IP_SELECTIVE();
@@ -315,6 +391,7 @@ dispatch_loop:
                     DISPATCH();
                 }
 
+                #if !MICROPY_OPT_CACHE_MAP_LOOKUP_IN_BYTECODE
                 ENTRY(MP_BC_STORE_ATTR): {
                     MARK_EXC_IP_SELECTIVE();
                     DECODE_QSTR;
@@ -322,6 +399,42 @@ dispatch_loop:
                     sp -= 2;
                     DISPATCH();
                 }
+                #else
+                // This caching code works with MICROPY_PY_BUILTINS_PROPERTY enabled because
+                // if the attr exists in self->members then it can't be a property.  A
+                // consequence of this is that we can't use MP_MAP_LOOKUP_ADD_IF_NOT_FOUND
+                // in the fast-path below, because that store could override a property.
+                ENTRY(MP_BC_STORE_ATTR): {
+                    MARK_EXC_IP_SELECTIVE();
+                    DECODE_QSTR;
+                    mp_obj_t top = TOP();
+                    if (mp_obj_get_type(top)->store_attr == mp_obj_instance_store_attr && sp[-1] != MP_OBJ_NULL) {
+                        mp_obj_instance_t *self = top;
+                        mp_uint_t x = *ip;
+                        mp_obj_t key = MP_OBJ_NEW_QSTR(qst);
+                        mp_map_elem_t *elem;
+                        if (x < self->members.alloc && self->members.table[x].key == key) {
+                            elem = &self->members.table[x];
+                        } else {
+                            elem = mp_map_lookup(&self->members, key, MP_MAP_LOOKUP);
+                            if (elem != NULL) {
+                                *(byte*)ip = elem - &self->members.table[0];
+                            } else {
+                                goto store_attr_cache_fail;
+                            }
+                        }
+                        elem->value = sp[-1];
+                        sp -= 2;
+                        ip++;
+                        DISPATCH();
+                    }
+                store_attr_cache_fail:
+                    mp_store_attr(sp[0], qst, sp[-1]);
+                    sp -= 2;
+                    ip++;
+                    DISPATCH();
+                }
+                #endif
 
                 ENTRY(MP_BC_STORE_SUBSCR):
                     MARK_EXC_IP_SELECTIVE();