erts: Use linear search for small select_val arrays

For searching a key in an array we use linear search in arrays
up to 10 elements.

Selecting on tuple arity will always use linear search.

Instead of using two different instructions we assume selecting on
different tuple arities are always few in numbers.

4 files changed, 226 insertions, 77 deletions

diff --git a/erts/emulator/beam/beam_debug.c b/erts/emulator/beam/beam_debug.c
index a3cd08834f..6bb987985d 100644
--- a/erts/emulator/beam/beam_debug.c
+++ b/erts/emulator/beam/beam_debug.c
@@ -579,9 +579,29 @@ print_op(int to, void *to_arg, int op, int size, BeamInstr* addr)
     unpacked = ap;
     ap = addr + size;
     switch (op) {
-    case op_i_select_val_rfI:
-    case op_i_select_val_xfI:
-    case op_i_select_val_yfI:
+    case op_i_select_val_lins_rfI:
+    case op_i_select_val_lins_xfI:
+    case op_i_select_val_lins_yfI:
+	{
+	    int n = ap[-1];
+	    int ix = n;
+
+	    while (ix--) {
+		erts_print(to, to_arg, "%T ", (Eterm) ap[0]);
+		ap++;
+		size++;
+	    }
+	    ix = n;
+	    while (ix--) {
+		erts_print(to, to_arg, "f(" HEXF ") ", (Eterm) ap[0]);
+		ap++;
+		size++;
+	    }
+	}
+	break;
+    case op_i_select_val_bins_rfI:
+    case op_i_select_val_bins_xfI:
+    case op_i_select_val_bins_yfI:
 	{
 	    int n = ap[-1];
 
@@ -598,13 +618,19 @@ print_op(int to, void *to_arg, int op, int size, BeamInstr* addr)
     case op_i_select_tuple_arity_yfI:
 	{
 	    int n = ap[-1];
+	    int ix = n;
 
-	    while (n > 0) {
+	    while (ix--) {
 		Uint arity = arityval(ap[0]);
-		erts_print(to, to_arg, " {%d} f(" HEXF ")", arity, ap[1]);
-		ap += 2;
-		size += 2;
-		n--;
+		erts_print(to, to_arg, "{%d} ", arity, ap[1]);
+		ap++;
+		size++;
+	    }
+	    ix = n;
+	    while (ix--) {
+		erts_print(to, to_arg, "f(" HEXF ") ", ap[0]);
+		ap++;
+		size++;
 	    }
 	}
 	break;
diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c
index e9f5fd798b..292971a387 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -2138,19 +2138,18 @@ void process_main(void)
      NextPF(0, next);
  }
 
-
  {
      Eterm select_val2;
 
- OpCase(i_select_tuple_arity2_yfAfAf):
+ OpCase(i_select_tuple_arity2_yfAAff):
      select_val2 = yb(Arg(0));
      goto do_select_tuple_arity2;
 
- OpCase(i_select_tuple_arity2_xfAfAf):
+ OpCase(i_select_tuple_arity2_xfAAff):
      select_val2 = xb(Arg(0));
      goto do_select_tuple_arity2;
 
- OpCase(i_select_tuple_arity2_rfAfAf):
+ OpCase(i_select_tuple_arity2_rfAAff):
      select_val2 = r(0);
      I--;
 
@@ -2161,22 +2160,22 @@ void process_main(void)
      select_val2 = *tuple_val(select_val2);
      goto do_select_val2;
 
- OpCase(i_select_val2_yfcfcf):
+ OpCase(i_select_val2_yfccff):
      select_val2 = yb(Arg(0));
      goto do_select_val2;
 
- OpCase(i_select_val2_xfcfcf):
+ OpCase(i_select_val2_xfccff):
      select_val2 = xb(Arg(0));
      goto do_select_val2;
 
- OpCase(i_select_val2_rfcfcf):
+ OpCase(i_select_val2_rfccff):
      select_val2 = r(0);
      I--;
 
  do_select_val2:
      if (select_val2 == Arg(2)) {
-	 I += 2;
-     } else if (select_val2 == Arg(4)) {
+	 I += 3;
+     } else if (select_val2 == Arg(3)) {
 	 I += 4;
      }
 
@@ -2203,20 +2202,50 @@ void process_main(void)
  do_select_tuple_arity:
      if (is_tuple(select_val)) {
 	 select_val = *tuple_val(select_val);
-	 goto do_binary_search;
+	 goto do_linear_search;
+     }
+     SET_I((BeamInstr *) Arg(1));
+     Goto(*I);
+
+ OpCase(i_select_val_lins_xfI):
+     select_val = xb(Arg(0));
+     goto do_linear_search;
+
+ OpCase(i_select_val_lins_yfI):
+     select_val = yb(Arg(0));
+     goto do_linear_search;
+
+ OpCase(i_select_val_lins_rfI):
+     select_val = r(0);
+     I--;
+
+ do_linear_search: {
+     BeamInstr *vs = &Arg(3);
+     int ix = 0;
+
+     for(;;) {
+	 if (vs[ix+0] >= select_val) { ix += 0; break; }
+	 if (vs[ix+1] >= select_val) { ix += 1; break; }
+	 ix += 2;
+     }
+
+     if (vs[ix] == select_val) {
+	 I += ix + Arg(2) + 2;
      }
+
      SET_I((BeamInstr *) Arg(1));
      Goto(*I);
+   }
 
- OpCase(i_select_val_xfI):
+ OpCase(i_select_val_bins_xfI):
      select_val = xb(Arg(0));
      goto do_binary_search;
 
- OpCase(i_select_val_yfI):
+ OpCase(i_select_val_bins_yfI):
      select_val = yb(Arg(0));
      goto do_binary_search;
      
- OpCase(i_select_val_rfI):
+ OpCase(i_select_val_bins_rfI):
      select_val = r(0);
      I--;
 
diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c
index 07654f6d5c..b9a6536ac6 100644
--- a/erts/emulator/beam/beam_load.c
+++ b/erts/emulator/beam/beam_load.c
@@ -3321,9 +3321,10 @@ gen_select_tuple_arity(LoaderState* stp, GenOpArg S, GenOpArg Fail,
 
 {
     GenOp* op;
+    GenOpArg *tmp;
     int arity = Size.val + 3;
     int size = Size.val / 2;
-    int i;
+    int i, j, align = 0;
 
     /*
      * Verify the validity of the list.
@@ -3338,9 +3339,37 @@ gen_select_tuple_arity(LoaderState* stp, GenOpArg S, GenOpArg Fail,
     }
 
     /*
+     * Use a special-cased instruction if there are only two values.
+     */
+    if (size == 2) {
+	NEW_GENOP(stp, op);
+	op->next = NULL;
+	op->op = genop_i_select_tuple_arity2_6;
+	GENOP_ARITY(op, arity - 1);
+	op->a[0] = S;
+	op->a[1] = Fail;
+	op->a[2].type = TAG_u;
+	op->a[2].val  = Rest[0].val;
+	op->a[3].type = TAG_u;
+	op->a[3].val  = Rest[2].val;
+	op->a[4] = Rest[1];
+	op->a[5] = Rest[3];
+
+	return op;
+    }
+
+    /*
      * Generate the generic instruction.
+     * Assumption:
+     *   Few different tuple arities to select on (fewer than 20).
+     *   Use linear scan approach.
      */
 
+    align = 1;
+
+    arity += 2*align;
+    size  += align;
+
     NEW_GENOP(stp, op);
     op->next = NULL;
     op->op = genop_i_select_tuple_arity_3;
@@ -3348,39 +3377,36 @@ gen_select_tuple_arity(LoaderState* stp, GenOpArg S, GenOpArg Fail,
     op->a[0] = S;
     op->a[1] = Fail;
     op->a[2].type = TAG_u;
-    op->a[2].val = Size.val / 2;
-    for (i = 0; i < Size.val; i += 2) {
-	op->a[i+3].type = TAG_v;
-	op->a[i+3].val = make_arityval(Rest[i].val);
-	op->a[i+4] = Rest[i+1];
-    }
+    op->a[2].val = size;
 
-    /*
-     * Sort the values to make them useful for a binary search.
-     */
+    tmp = (GenOpArg *) erts_alloc(ERTS_ALC_T_LOADER_TMP, sizeof(GenOpArg)*(arity-2*align));
 
-    qsort(op->a+3, size, 2*sizeof(GenOpArg), 
-	   (int (*)(const void *, const void *)) genopargcompare);
-#ifdef DEBUG
-    for (i = 3; i < arity-2; i += 2) {
-	ASSERT(op->a[i].val < op->a[i+2].val);
+    for (i = 3; i < arity - 2*align; i+=2) {
+	tmp[i-3].type = TAG_v;
+	tmp[i-3].val  = make_arityval(Rest[i-3].val);
+	tmp[i-2]      = Rest[i-2];
     }
-#endif
 
     /*
-     * Use a special-cased instruction if there are only two values.
+     * Sort the values to make them useful for a sentinel search
      */
-    if (size == 2) {
-	op->op = genop_i_select_tuple_arity2_6;
-	op->arity--;
-	op->a[2].type = TAG_u;
-	op->a[2].val = arityval(op->a[3].val);
-	op->a[3] = op->a[4];
-	op->a[4].type = TAG_u;
-	op->a[4].val = arityval(op->a[5].val);
-	op->a[5] = op->a[6];
+
+    qsort(tmp, size - align, 2*sizeof(GenOpArg),
+	    (int (*)(const void *, const void *)) genopargcompare);
+
+    j = 3;
+    for (i = 3; i < arity - 2*align; i += 2) {
+	op->a[j]        = tmp[i-3];
+	op->a[j + size] = tmp[i-2];
+	j++;
     }
 
+    erts_free(ERTS_ALC_T_LOADER_TMP, (void *) tmp);
+
+    op->a[j].type = TAG_u;
+    op->a[j].val  = ~((BeamInstr)0);
+    op->a[j+size] = Fail;
+
     return op;
 }
 
@@ -3602,45 +3628,109 @@ gen_select_val(LoaderState* stp, GenOpArg S, GenOpArg Fail,
 	       GenOpArg Size, GenOpArg* Rest)
 {
     GenOp* op;
+    GenOpArg *tmp;
     int arity = Size.val + 3;
     int size = Size.val / 2;
-    int i;
+    int i, j, align = 0;
+
+    if (size == 2) {
+
+	/*
+	 * Use a special-cased instruction if there are only two values.
+	 */
+
+	NEW_GENOP(stp, op);
+	op->next = NULL;
+	op->op = genop_i_select_val2_6;
+	GENOP_ARITY(op, arity - 1);
+	op->a[0] = S;
+	op->a[1] = Fail;
+	op->a[2] = Rest[0];
+	op->a[3] = Rest[2];
+	op->a[4] = Rest[1];
+	op->a[5] = Rest[3];
+
+	return op;
+
+    } else if (size > 10) {
+
+	/* binary search instruction */
+
+	NEW_GENOP(stp, op);
+	op->next = NULL;
+	op->op = genop_i_select_val_bins_3;
+	GENOP_ARITY(op, arity);
+	op->a[0] = S;
+	op->a[1] = Fail;
+	op->a[2].type = TAG_u;
+	op->a[2].val = size;
+	for (i = 3; i < arity; i++) {
+	    op->a[i] = Rest[i-3];
+	}
+
+	/*
+	 * Sort the values to make them useful for a binary search.
+	 */
+
+	qsort(op->a+3, size, 2*sizeof(GenOpArg),
+		(int (*)(const void *, const void *)) genopargcompare);
+#ifdef DEBUG
+	for (i = 3; i < arity-2; i += 2) {
+	    ASSERT(op->a[i].val < op->a[i+2].val);
+	}
+#endif
+	return op;
+    }
+
+    /* linear search instruction */
+
+    align = 1;
+
+    arity += 2*align;
+    size  += align;
 
     NEW_GENOP(stp, op);
     op->next = NULL;
-    op->op = genop_i_select_val_3;
+    op->op = genop_i_select_val_lins_3;
     GENOP_ARITY(op, arity);
     op->a[0] = S;
     op->a[1] = Fail;
     op->a[2].type = TAG_u;
     op->a[2].val = size;
-    for (i = 3; i < arity; i++) {
-	op->a[i] = Rest[i-3];
+
+    tmp = (GenOpArg *) erts_alloc(ERTS_ALC_T_LOADER_TMP, sizeof(GenOpArg)*(arity-2*align));
+
+    for (i = 3; i < arity - 2*align; i++) {
+	tmp[i-3] = Rest[i-3];
     }
 
     /*
-     * Sort the values to make them useful for a binary search.
+     * Sort the values to make them useful for a sentinel search
      */
 
-    qsort(op->a+3, size, 2*sizeof(GenOpArg), 
-	  (int (*)(const void *, const void *)) genopargcompare);
-#ifdef DEBUG
-    for (i = 3; i < arity-2; i += 2) {
-	ASSERT(op->a[i].val < op->a[i+2].val);
+    qsort(tmp, size - align, 2*sizeof(GenOpArg),
+	    (int (*)(const void *, const void *)) genopargcompare);
+
+    j = 3;
+    for (i = 3; i < arity - 2*align; i += 2) {
+	op->a[j]      = tmp[i-3];
+	op->a[j+size] = tmp[i-2];
+	j++;
     }
-#endif
 
-    /*
-     * Use a special-cased instruction if there are only two values.
-     */
-    if (size == 2) {
-	op->op = genop_i_select_val2_6;
-	op->arity--;
-	op->a[2] = op->a[3];
-	op->a[3] = op->a[4];
-	op->a[4] = op->a[5];
-	op->a[5] = op->a[6];
+    erts_free(ERTS_ALC_T_LOADER_TMP, (void *) tmp);
+
+    /* add sentinel */
+
+    op->a[j].type = TAG_u;
+    op->a[j].val  = ~((BeamInstr)0);
+    op->a[j+size] = Fail;
+
+#ifdef DEBUG
+    for (i = 0; i < size; i++) {
+	ASSERT(op->a[i+3].val <= op->a[i+4].val);
     }
+#endif
 
     return op;
 }
diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab
index 68fcc177ae..d3649080dc 100644
--- a/erts/emulator/beam/ops.tab
+++ b/erts/emulator/beam/ops.tab
@@ -166,22 +166,26 @@ is_tuple Fail=f S | select_tuple_arity S=d Fail=f Size=u Rest=* => \
 select_tuple_arity S=d Fail=f Size=u Rest=* => \
   gen_select_tuple_arity(S, Fail, Size, Rest)
 
-i_select_val r f I
-i_select_val x f I
-i_select_val y f I
+i_select_val_bins r f I
+i_select_val_bins x f I
+i_select_val_bins y f I
 
-i_select_val2 r f c f c f
-i_select_val2 x f c f c f
-i_select_val2 y f c f c f
+i_select_val_lins r f I
+i_select_val_lins x f I
+i_select_val_lins y f I
 
-i_select_tuple_arity2 r f A f A f
-i_select_tuple_arity2 x f A f A f
-i_select_tuple_arity2 y f A f A f
+i_select_val2 r f c c f f
+i_select_val2 x f c c f f
+i_select_val2 y f c c f f
 
 i_select_tuple_arity r f I
 i_select_tuple_arity x f I
 i_select_tuple_arity y f I
 
+i_select_tuple_arity2 r f A A f f
+i_select_tuple_arity2 x f A A f f
+i_select_tuple_arity2 y f A A f f
+
 i_jump_on_val_zero r f I
 i_jump_on_val_zero x f I
 i_jump_on_val_zero y f I