diff options
Diffstat (limited to 'py/map.c')
| -rw-r--r-- | py/map.c | 35 |
1 files changed, 35 insertions, 0 deletions
@@ -40,6 +40,27 @@ #define DEBUG_printf(...) (void)0 #endif +#if MICROPY_OPT_MAP_LOOKUP_CACHE +// MP_STATE_VM(map_lookup_cache) provides a cache of index to the last known +// position of that index in any map. On a cache hit, this allows +// short-circuiting the full linear search in the case of an ordered map +// (i.e. all builtin modules and objects' locals dicts), and computation of +// the hash (and potentially some linear probing) in the case of a regular +// map. Note the same cache is shared across all maps. + +// Gets the index into the cache for this index. Shift down by two to remove +// mp_obj_t tag bits. +#define MAP_CACHE_OFFSET(index) ((((uintptr_t)(index)) >> 2) % MICROPY_OPT_MAP_LOOKUP_CACHE_SIZE) +// Gets the map cache entry for the corresponding index. +#define MAP_CACHE_ENTRY(index) (MP_STATE_VM(map_lookup_cache)[MAP_CACHE_OFFSET(index)]) +// Retrieve the mp_obj_t at the location suggested by the cache. +#define MAP_CACHE_GET(map, index) (&(map)->table[MAP_CACHE_ENTRY(index) % (map)->alloc]) +// Update the cache for this index. +#define MAP_CACHE_SET(index, pos) MAP_CACHE_ENTRY(index) = (pos) & 0xff; +#else +#define MAP_CACHE_SET(index, pos) +#endif + // This table of sizes is used to control the growth of hash tables. // The first set of sizes are chosen so the allocation fits exactly in a // 4-word GC block, and it's not so important for these small values to be @@ -136,6 +157,18 @@ mp_map_elem_t *mp_map_lookup(mp_map_t *map, mp_obj_t index, mp_map_lookup_kind_t // If the map is a fixed array then we must only be called for a lookup assert(!map->is_fixed || lookup_kind == MP_MAP_LOOKUP); + #if MICROPY_OPT_MAP_LOOKUP_CACHE + // Try the cache for lookup or add-if-not-found. + if (lookup_kind != MP_MAP_LOOKUP_REMOVE_IF_FOUND && map->alloc) { + mp_map_elem_t *slot = MAP_CACHE_GET(map, index); + // Note: Just comparing key for value equality will have false negatives, but + // these will be handled by the regular path below. + if (slot->key == index) { + return slot; + } + } + #endif + // Work out if we can compare just pointers bool compare_only_ptrs = map->all_keys_are_qstrs; if (compare_only_ptrs) { @@ -172,6 +205,7 @@ mp_map_elem_t *mp_map_lookup(mp_map_t *map, mp_obj_t index, mp_map_lookup_kind_t elem->value = value; } #endif + MAP_CACHE_SET(index, elem - map->table); return elem; } } @@ -254,6 +288,7 @@ mp_map_elem_t *mp_map_lookup(mp_map_t *map, mp_obj_t index, mp_map_lookup_kind_t } // keep slot->value so that caller can access it if needed } + MAP_CACHE_SET(index, pos); return slot; } |