aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2015-03-25 11:57:44 +0100
committerBjörn Gustavsson <[email protected]>2015-04-13 12:37:55 +0200
commit5f1e301dfec48fccbf865a8b54af5908bebb77c4 (patch)
tree2daaf298e0f80bed9de14bce6cf9bcce4dc8e2b3
parent5b8872c37f63b35e13464109e986ef3727588040 (diff)
downloadotp-5f1e301dfec48fccbf865a8b54af5908bebb77c4.tar.gz
otp-5f1e301dfec48fccbf865a8b54af5908bebb77c4.tar.bz2
otp-5f1e301dfec48fccbf865a8b54af5908bebb77c4.zip
Teach the loader to pre-compute the hash value for single-key lookups
Let the loader pre-compute the hash value when a single, literal key is matched as in: #{<<"some_key">>:=V} = Map In my measurements, this optimization resulted in a 30 percent speedup for short binary keys. Unfortunately, this optimizization makes no difference for small maps with less than 32 keys, since the hash value is not used. Still, there are the following use cases: * A map used instead of a record with more than 32 entries. I have seen some applications with huge records. * Lookup in JSON dictionaries represented as maps. The hash value will only be used when the map is a hash map (currently, that means at least 32 entries).
-rw-r--r--erts/emulator/beam/beam_emu.c46
-rw-r--r--erts/emulator/beam/beam_load.c42
-rw-r--r--erts/emulator/beam/ops.tab26
3 files changed, 95 insertions, 19 deletions
diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c
index 4e64dce95c..5f49032e23 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -710,6 +710,15 @@ void** beam_ops;
Dst = _res; \
} while (0)
+#define GetMapElementHash(Src, Key, Hx, Dst, Fail) \
+ do { \
+ Eterm _res = get_map_element_hash(Src, Key, Hx); \
+ if (is_non_value(_res)) { \
+ Fail; \
+ } \
+ Dst = _res; \
+ } while (0)
+
#define IsFunction(X, Action) \
do { \
if ( !(is_any_fun(X)) ) { \
@@ -959,6 +968,7 @@ static Eterm update_map_assoc(Process* p, Eterm* reg,
static Eterm update_map_exact(Process* p, Eterm* reg,
Eterm map, BeamInstr* I) NOINLINE;
static Eterm get_map_element(Eterm map, Eterm key);
+static Eterm get_map_element_hash(Eterm map, Eterm key, Uint32 hx);
/*
* Functions not directly called by process_main(). OK to inline.
@@ -6441,6 +6451,42 @@ static Eterm get_map_element(Eterm map, Eterm key)
return vs ? *vs : THE_NON_VALUE;
}
+static Eterm get_map_element_hash(Eterm map, Eterm key, Uint32 hx)
+{
+ const Eterm *vs;
+
+ if (is_flatmap(map)) {
+ flatmap_t *mp;
+ Eterm *ks;
+ Uint i;
+ Uint n;
+
+ mp = (flatmap_t *)flatmap_val(map);
+ ks = flatmap_get_keys(mp);
+ vs = flatmap_get_values(mp);
+ n = flatmap_get_size(mp);
+ if (is_immed(key)) {
+ for (i = 0; i < n; i++) {
+ if (ks[i] == key) {
+ return vs[i];
+ }
+ }
+ } else {
+ for (i = 0; i < n; i++) {
+ if (EQ(ks[i], key)) {
+ return vs[i];
+ }
+ }
+ }
+ return THE_NON_VALUE;
+ }
+
+ ASSERT(is_hashmap(map));
+ ASSERT(hx == hashmap_make_hash(key));
+ vs = erts_hashmap_get(hx, key, map);
+ return vs ? *vs : THE_NON_VALUE;
+}
+
#define GET_TERM(term, dest) \
do { \
Eterm src = (Eterm)(term); \
diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c
index 1a6c6c16ad..ee319d0a78 100644
--- a/erts/emulator/beam/beam_load.c
+++ b/erts/emulator/beam/beam_load.c
@@ -4161,9 +4161,30 @@ map_key_sort(LoaderState* stp, GenOpArg Size, GenOpArg* Rest)
return 1;
}
+static int
+hash_genop_arg(LoaderState* stp, GenOpArg Key, Uint32* hx)
+{
+ switch (Key.type) {
+ case TAG_a:
+ *hx = hashmap_make_hash(Key.val);
+ return 1;
+ case TAG_i:
+ *hx = hashmap_make_hash(make_small(Key.val));
+ return 1;
+ case TAG_n:
+ *hx = hashmap_make_hash(NIL);
+ return 1;
+ case TAG_q:
+ *hx = hashmap_make_hash(stp->literals[Key.val].term);
+ return 1;
+ default:
+ return 0;
+ }
+}
+
/*
* Replace a get_map_elements with one key to an instruction with one
- * element
+ * element.
*/
static GenOp*
@@ -4171,18 +4192,29 @@ gen_get_map_element(LoaderState* stp, GenOpArg Fail, GenOpArg Src,
GenOpArg Size, GenOpArg* Rest)
{
GenOp* op;
+ GenOpArg Key;
+ Uint32 hx = 0;
ASSERT(Size.type == TAG_u);
NEW_GENOP(stp, op);
op->next = NULL;
- op->op = genop_get_map_element_4;
- op->arity = 4;
-
op->a[0] = Fail;
op->a[1] = Src;
op->a[2] = Rest[0];
- op->a[3] = Rest[1];
+
+ Key = Rest[0];
+ if (hash_genop_arg(stp, Key, &hx)) {
+ op->arity = 5;
+ op->op = genop_i_get_map_element_hash_5;
+ op->a[3].type = TAG_u;
+ op->a[3].val = (BeamInstr) hx;
+ op->a[4] = Rest[1];
+ } else {
+ op->arity = 4;
+ op->op = genop_i_get_map_element_4;
+ op->a[3] = Rest[1];
+ }
return op;
}
diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab
index 23f5b75b7a..456f879ab5 100644
--- a/erts/emulator/beam/ops.tab
+++ b/erts/emulator/beam/ops.tab
@@ -1512,8 +1512,6 @@ has_map_fields Fail Src Size Rest=* => \
## Transform get_map_elements(s) #{ K1 := V1, K2 := V2 }
-get_map_element/4
-
get_map_elements Fail Src=rxy Size=u==2 Rest=* => \
gen_get_map_element(Fail, Src, Size, Rest)
get_map_elements Fail Src Size Rest=* | map_key_sort(Size, Rest) => \
@@ -1521,21 +1519,21 @@ get_map_elements Fail Src Size Rest=* | map_key_sort(Size, Rest) => \
i_get_map_elements f s I
-get_map_element Fail Src=rxy Key=cx Dst => i_get_map_element Fail Src Key Dst
-get_map_element Fail Src=rxy Key=ry Dst => \
+i_get_map_element Fail Src=rxy Key=ry Dst => \
move Key x | i_get_map_element Fail Src x Dst
-get_map_element Fail Src Key Dst => jump Fail
+
+%macro: i_get_map_element_hash GetMapElementHash -fail_action
+i_get_map_element_hash f r c I r
+i_get_map_element_hash f x c I r
+i_get_map_element_hash f y c I r
+i_get_map_element_hash f r c I x
+i_get_map_element_hash f x c I x
+i_get_map_element_hash f y c I x
+i_get_map_element_hash f r c I y
+i_get_map_element_hash f x c I y
+i_get_map_element_hash f y c I y
%macro: i_get_map_element GetMapElement -fail_action
-i_get_map_element f r c r
-i_get_map_element f x c r
-i_get_map_element f y c r
-i_get_map_element f r c x
-i_get_map_element f x c x
-i_get_map_element f y c x
-i_get_map_element f r c y
-i_get_map_element f x c y
-i_get_map_element f y c y
i_get_map_element f r x r
i_get_map_element f x x r
i_get_map_element f y x r