Merge branch 'sverker/dict-put-immed-opt/OTP-14976'

* sverker/dict-put-immed-opt:
  erts: Optimize erlang:put/2 for hash collision lists
  erts: Optimize erlang:put/2 for immed values
  erts: Refactor erlang:put/2

1 files changed, 82 insertions, 76 deletions

diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c
index 3c80f0e0f6..aee88841ae 100644
--- a/erts/emulator/beam/erl_process_dict.c
+++ b/erts/emulator/beam/erl_process_dict.c
@@ -79,6 +79,8 @@
 /* Array access macro */ 
 #define ARRAY_GET(PDict, Index) (ASSERT((Index) < (PDict)->arraySize), \
 				 (PDict)->data[Index])
+#define ARRAY_GET_PTR(PDict, Index) (ASSERT((Index) < (PDict)->arraySize), \
+				     &(PDict)->data[Index])
 #define ARRAY_PUT(PDict, Index, Val) (ASSERT((Index) < (PDict)->arraySize), \
                                       (PDict)->data[Index] = (Val))
 
@@ -92,7 +94,7 @@ static void pd_hash_erase_all(Process *p);
 static Eterm pd_hash_get_with_hval(Process *p, Eterm bucket, Eterm id);
 static Eterm pd_hash_get_keys(Process *p, Eterm value);
 static Eterm pd_hash_get_all_keys(Process *p, ProcDict *pd);
-static Eterm pd_hash_get_all(Process *p, ProcDict *pd);
+static Eterm pd_hash_get_all(Process *p, ProcDict *pd, int keep_dict);
 static Eterm pd_hash_put(Process *p, Eterm id, Eterm value);
 
 static void shrink(Process *p, Eterm* ret); 
@@ -281,7 +283,7 @@ BIF_RETTYPE get_0(BIF_ALIST_0)
 {
     Eterm ret;
     PD_CHECK(BIF_P->dictionary);
-    ret = pd_hash_get_all(BIF_P, BIF_P->dictionary);
+    ret = pd_hash_get_all(BIF_P, BIF_P->dictionary, 1);
     PD_CHECK(BIF_P->dictionary);
     BIF_RET(ret);
 }
@@ -329,7 +331,7 @@ BIF_RETTYPE erase_0(BIF_ALIST_0)
 {
     Eterm ret;
     PD_CHECK(BIF_P->dictionary);
-    ret = pd_hash_get_all(BIF_P, BIF_P->dictionary);
+    ret = pd_hash_get_all(BIF_P, BIF_P->dictionary, 0);
     pd_hash_erase_all(BIF_P);
     PD_CHECK(BIF_P->dictionary);
     BIF_RET(ret);
@@ -541,29 +543,46 @@ static Eterm pd_hash_get_keys(Process *p, Eterm value)
 	
 
 static Eterm
-pd_hash_get_all(Process *p, ProcDict *pd)
+pd_hash_get_all(Process *p, ProcDict *pd, int keep_dict)
 {
     Eterm* hp;
+    Eterm* tp;
     Eterm res = NIL;
     Eterm tmp, tmp2;
     unsigned int i;
     unsigned int num;
+    Uint need;
 
     if (pd == NULL) {
 	return res;
     }
     num = HASH_RANGE(pd);
-    hp = HAlloc(p, pd->numElements * 2);
-    
+
+    /*
+     * If this is not erase/0, then must copy all key-value tuples
+     * as they may be mutated by put/2.
+     */
+    need = pd->numElements * (keep_dict ? 2+3 : 2);
+    hp = HAlloc(p, need);
+
     for (i = 0; i < num; ++i) {
 	tmp = ARRAY_GET(pd, i);
 	if (is_boxed(tmp)) {
-	    ASSERT(is_tuple(tmp));
+            if (keep_dict) {
+                tp = tuple_val(tmp);
+                tmp = TUPLE2(hp, tp[1], tp[2]);
+                hp += 3;
+            }
 	    res = CONS(hp, tmp, res);
 	    hp += 2;
 	} else if (is_list(tmp)) {
 	    while (tmp != NIL) {
 		tmp2 = TCAR(tmp);
+                if (keep_dict) {
+                    tp = tuple_val(tmp2);
+                    tmp2 = TUPLE2(hp, tp[1], tp[2]);
+                    hp += 3;
+                }
 		res = CONS(hp, tmp2, res);
 		hp += 2;
 		tmp = TCDR(tmp);
@@ -577,11 +596,14 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
 { 
     unsigned int hval;
     Eterm *hp;
+    Eterm *tp;
+    Eterm *bucket;
     Eterm tpl;
     Eterm old;
+    Eterm old_val = am_undefined;
     Eterm tmp;
     int needed;
-    int i = 0;
+    int new_key = 1;
 #ifdef DEBUG
     Eterm *hp_limit;
 #endif
@@ -595,7 +617,8 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
         p->dictionary->numElements = 0;
     }	
     hval = pd_hash_value(p->dictionary, id);
-    old = ARRAY_GET(p->dictionary, hval);
+    bucket = ARRAY_GET_PTR(p->dictionary, hval);
+    old = *bucket;
 
     /*
      * Calculate the number of heap words needed and garbage
@@ -603,32 +626,49 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
      */
     needed = 3;			/* {Key,Value} tuple */
     if (is_boxed(old)) {
-	/*
-	 * We don't want to compare keys twice, so we'll always
-	 * reserve the space for two CONS cells.
-	 */
-	needed += 2+2;
+        ASSERT(is_tuple(old));
+        tp = tuple_val(old);
+        if (EQ(tp[1], id)) {
+            old_val = tp[2];
+            if (is_immed(value)) {
+                tp[2] = value;     /* DESTRUCTIVE HEAP ASSIGNMENT */
+                return old_val;
+            }
+            new_key = 0;
+        }
+        else {
+            needed += 2+2;
+        }
     } else if (is_list(old)) {
-	i = 0;
-	for (tmp = old; tmp != NIL && !EQ(tuple_val(TCAR(tmp))[1], id); tmp = TCDR(tmp)) {
-	    ++i;
-	}
-	if (is_nil(tmp)) {
-	    i = -1;
-	    needed += 2;
-	} else {
-	    needed += 2*(i+1);
+        Eterm* prev_cdr = bucket;
+
+        needed += 2;
+	for (tmp = old; tmp != NIL; prev_cdr = &TCDR(tmp), tmp = *prev_cdr) {
+            tp = tuple_val(TCAR(tmp));
+            if (EQ(tp[1], id)) {
+                old_val = tp[2];
+                if (is_immed(value)) {
+                    tp[2] = value;     /* DESTRUCTIVE HEAP ASSIGNMENT */
+                    return old_val;
+                }
+                new_key = 0;
+                /* Unlink old {Key,Value} from list */
+                *prev_cdr = TCDR(tmp);  /* maybe DESTRUCTIVE HEAP ASSIGNMENT */
+                break;
+            }
 	}
     }
     if (HeapWordsLeft(p) < needed) {
 	Eterm root[3];
 	root[0] = id;
 	root[1] = value;
-	root[2] = old;
+        root[2] = old_val;
 	erts_garbage_collect(p, needed, root, 3);
 	id = root[0];
 	value = root[1];
-	old = root[2];
+        old_val = root[2];
+        ASSERT(bucket == ARRAY_GET_PTR(p->dictionary, hval));
+        old = *bucket;
     }
 #ifdef DEBUG
     hp_limit = p->htop + needed;
@@ -644,66 +684,29 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
      * Update the dictionary.
      */
     if (is_nil(old)) {
-	ARRAY_PUT(p->dictionary, hval, tpl);
-	++(p->dictionary->numElements);
+	*bucket = tpl;
     } else if (is_boxed(old)) {
 	ASSERT(is_tuple(old));
-	if (EQ(tuple_val(old)[1],id)) {
-	    ARRAY_PUT(p->dictionary, hval, tpl);
-	    return tuple_val(old)[2];
+	if (!new_key) {
+            ASSERT(EQ(tuple_val(old)[1],id));
+	    *bucket = tpl;
+	    return old_val;
 	} else {
 	    hp = HeapOnlyAlloc(p, 4);
 	    tmp = CONS(hp, old, NIL);
 	    hp += 2;
-	    ++(p->dictionary->numElements);
-	    ARRAY_PUT(p->dictionary, hval, CONS(hp, tpl, tmp));
+	    *bucket = CONS(hp, tpl, tmp);
 	    hp += 2;
 	    ASSERT(hp <= hp_limit);
 	}
     } else if (is_list(old)) {
-	if (i == -1) {
-	    /*
-	     * New key. Simply prepend the tuple to the beginning of the list.
-	     */
-	    hp = HeapOnlyAlloc(p, 2);
-	    ARRAY_PUT(p->dictionary, hval, CONS(hp, tpl, old));
-	    hp += 2;
-	    ASSERT(hp <= hp_limit);
-	    ++(p->dictionary->numElements);
-	} else {
-	    /*
-	     * i = Number of CDRs to skip to reach the changed element in the list.
-	     *
-	     * Replace old value in list. To avoid pointers from the old generation
-	     * to the new, we must rebuild the list from the beginning up to and
-	     * including the changed element.
-	     */
-	    Eterm nlist;
-	    int j;
-
-	    hp = HeapOnlyAlloc(p, (i+1)*2);
-	    
-	    /* Find the list element to change. */
-	    for (j = 0, nlist = old; j < i; j++, nlist = TCDR(nlist)) {
-		;
-	    }
-	    ASSERT(EQ(tuple_val(TCAR(nlist))[1], id));
-	    nlist = TCDR(nlist); /* Unchanged part of list. */
-
-	    /* Rebuild list before the updated element. */
-	    for (tmp = old; i-- > 0; tmp = TCDR(tmp)) {
-		nlist = CONS(hp, TCAR(tmp), nlist);
-		hp += 2;
-	    }
-	    ASSERT(EQ(tuple_val(TCAR(tmp))[1], id));
-
-	    /* Put the updated element first in the new list. */
-	    nlist = CONS(hp, tpl, nlist);
-	    hp += 2;
-	    ASSERT(hp <= hp_limit);
-	    ARRAY_PUT(p->dictionary, hval, nlist);
-	    return tuple_val(TCAR(tmp))[2];
-	}
+        /*
+	 * Simply prepend the tuple to the beginning of the list.
+	 */
+	hp = HeapOnlyAlloc(p, 2);
+        *bucket = CONS(hp, tpl, *bucket);
+	hp += 2;
+	ASSERT(hp <= hp_limit);
     } else {
 #ifdef DEBUG
 	erts_fprintf(stderr,
@@ -714,10 +717,13 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
 
 	erts_exit(ERTS_ERROR_EXIT, "Damaged process dictionary found during put/2.");
     }
+
+    p->dictionary->numElements += new_key;
+
     if (HASH_RANGE(p->dictionary) <= p->dictionary->numElements) {
 	grow(p);
     }
-    return am_undefined;
+    return old_val;
 }
 
 /*