Merge branch 'egil/beam/select_val/OTP-12555'

* egil/beam/select_val/OTP-12555:
  erts: Use linear search for small select_val arrays

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 3af7c43abf..b89c8b3900 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