erts: Optimize hashing in process dictionary

by limiting table sizes to powers of 2.

This will change the default size from 10 to 8.

3 files changed, 22 insertions, 4 deletions

diff --git a/erts/emulator/beam/erl_init.c b/erts/emulator/beam/erl_init.c
index d9c3b0dcf4..0a34d91a01 100644
--- a/erts/emulator/beam/erl_init.c
+++ b/erts/emulator/beam/erl_init.c
@@ -197,7 +197,7 @@ Uint32 verbose;             /* See erl_debug.h for information about verbose */
 
 int erts_atom_table_size = ATOM_LIMIT;	/* Maximum number of atoms */
 
-int erts_pd_initial_size = 10;
+int erts_pd_initial_size = 8;  /* must be power of 2 */
 
 int erts_modified_timing_level;
 
@@ -1479,7 +1479,7 @@ erl_start(int argc, char **argv)
 		VERBOSE(DEBUG_SYSTEM, ("using minimum heap size %d\n", H_MIN_SIZE));
 	    } else if (has_prefix("pds", sub_param)) {
 		arg = get_arg(sub_param+3, argv[i+1], &i);
-		if ((erts_pd_initial_size = atoi(arg)) <= 0) {
+		if (!erts_pd_set_initial_size(atoi(arg))) {
 		    erts_fprintf(stderr, "bad initial process dictionary size %s\n", arg);
 		    erts_usage();
 		}
diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c
index e497267b63..c56a722542 100644
--- a/erts/emulator/beam/erl_process_dict.c
+++ b/erts/emulator/beam/erl_process_dict.c
@@ -80,6 +80,8 @@
 #define ARRAY_GET(PDict, Index) (((PDict)->size > (Index)) ? \
 				 (PDict)->data[Index] : NIL)
 
+#define IS_POW2(X) ((X) && !((X) & ((X)-1)))
+
 /*
  * Forward decalarations
  */
@@ -138,6 +140,16 @@ static void pd_check(ProcDict *pd);
 ** External interface
 */
 
+int
+erts_pd_set_initial_size(int size)
+{
+    if (size <= 0)
+	return 0;
+
+    erts_pd_initial_size = 1 << erts_fit_in_bits_uint(size-1);
+    return 1;
+}
+
 /*
  * Called from break handler
  */
@@ -399,6 +411,7 @@ Eterm erts_pd_hash_get_with_hx(Process *p, Uint32 hx, Eterm id)
     unsigned int hval;
     ProcDict *pd = p->dictionary;
 
+    ASSERT(hx == MAKE_HASH(id));
     if (pd == NULL)
 	return am_undefined;
     hval = pd_hash_value_to_ix(pd, hx);
@@ -570,6 +583,7 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
 	/* Create it */
 	array_put(&(p->dictionary), INITIAL_SIZE - 1, NIL);
 	p->dictionary->homeSize = INITIAL_SIZE;
+	ASSERT(IS_POW2(p->dictionary->homeSize));
     }	
     hval = pd_hash_value(p->dictionary, id);
     old = ARRAY_GET(p->dictionary, hval);
@@ -954,9 +968,12 @@ static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term)
 static unsigned int pd_hash_value_to_ix(ProcDict *pdict, Uint32 hx) 
 { 
     Uint high;
-    high = hx % (pdict->homeSize*2);
+
+    ASSERT(IS_POW2(pdict->homeSize));
+
+    high = hx & (pdict->homeSize*2 - 1);
     if (high >= HASH_RANGE(pdict))
-	return hx % pdict->homeSize;
+	return hx & (pdict->homeSize - 1);
     return high;
 }
 
diff --git a/erts/emulator/beam/erl_process_dict.h b/erts/emulator/beam/erl_process_dict.h
index 9aa21b7c38..ab50d45c63 100644
--- a/erts/emulator/beam/erl_process_dict.h
+++ b/erts/emulator/beam/erl_process_dict.h
@@ -31,6 +31,7 @@ typedef struct proc_dict {
     Eterm data[1]; /* The beginning of an array of erlang terms */
 } ProcDict;
 
+int erts_pd_set_initial_size(int size);
 Uint erts_dicts_mem_size(struct process *p);
 void erts_erase_dicts(struct process *p);
 void erts_dictionary_dump(int to, void *to_arg, ProcDict *pd);