M2 evaluation algorithm

[mahrud]

This is a question for @DanGrayson but if anyone else knows the answer, what's the point of these nested evaluations of semicolon separated code, when you can just use a loop like they do after the 5th nesting? https://github.com/Macaulay2/M2/blob/ec9e9ac60ed4a8e791448942202f077a88a87e15/M2/Macaulay2/d/evaluate.d#L43-L64 https://github.com/Macaulay2/M2/blob/ec9e9ac60ed4a8e791448942202f077a88a87e15/M2/Macaulay2/d/evaluate.d#L1529-L1550 I'm familiar with AST flattening, which has some benefits like reusing the stack and avoiding recursion, but this isn't that. A semicolon separated list is already flat. The while loop at the end of each of these nested sections is basically as best as one can do.

Am I missing something?

[pzinn]

I always assumed it was somehow faster?

[mahrud]

Here is the resulting c code for the v:semiCode do section in the original:

        case 109:;
	  v = ((parse_semiCode)c);
	  w = v->w;
	  n = w->len;
	  r = evaluate_eval(w->array[0]);
	  switch (r->type_) {;
	  case 16:;
            e_1 = ((parse_Error)r);
            tmp__23 = ((parse_Code)e_1);
	    return tmp__23;
	    break;
	  default:;
	    break;
	  };
	  if ((n == 2)) goto L16_;
	  r = evaluate_eval(w->array[1]);
	  switch (r->type_) {;
	  case 16:;
            e_2 = ((parse_Error)r);
            tmp__24 = ((parse_Code)e_2);
	    return tmp__24;
	    break;
	  default:;
	    break;
	  };
	  if ((n == 3)) goto L17_;
	  r = evaluate_eval(w->array[2]);
	  switch (r->type_) {;
	  case 16:;
            e_3 = ((parse_Error)r);
            tmp__25 = ((parse_Code)e_3);
	    return tmp__25;
	    break;
	  default:;
	    break;
	  };
	  if ((n == 4)) goto L18_;
	  r = evaluate_eval(w->array[3]);
	  switch (r->type_) {;
	  case 16:;
            e_4 = ((parse_Error)r);
            tmp__26 = ((parse_Code)e_4);
	    return tmp__26;
	    break;
	  default:;
	    break;
	  };
	  if ((n == 5)) goto L19_;
	  r = evaluate_eval(w->array[4]);
	  switch (r->type_) {;
	  case 16:;
            e_5 = ((parse_Error)r);
            tmp__27 = ((parse_Code)e_5);
	    return tmp__27;
	    break;
	  default:;
	    break;
	  };
	  i_2 = 5;
    L20_:;
	  if ((! (i_2 < (n - 1)))) goto L21_;
	  r = evaluate_eval(w->array[i_2]);
	  switch (r->type_) {;
	  case 16:;
            e_6 = ((parse_Error)r);
            tmp__28 = ((parse_Code)e_6);
	    return tmp__28;
	    break;
	  default:;
            i_2 = (i_2 + 1);
            break;
	  };
	  goto L20_;
    L21_:;
	  tmp__29 = w->array[i_2];
	  goto L23_;
    L19_:;
	  tmp__29 = w->array[4];
    L23_:;
	  tmp__30 = tmp__29;
	  goto L24_;
    L18_:;
	  tmp__30 = w->array[3];
    L24_:;
	  tmp__31 = tmp__30;
	  goto L25_;
    L17_:;
	  tmp__31 = w->array[2];
    L25_:;
	  tmp__32 = tmp__31;
	  goto L26_;
    L16_:;
	  tmp__32 = w->array[1];
    L26_:;
	  tmp__22 = tmp__32;
	  break;

Now if you jump directly to the while loop:

        case 109:;
	  v = ((parse_semiCode)c);
	  w = v->w;
	  n = w->len;
	  r = parse_nullE;
	  i_2 = 0;
    L16_:;
	  if ((! (i_2 < (n - 1)))) goto L17_;
	  r = evaluate_eval(w->array[i_2]);
	  switch (r->type_) {;
	  case 16:;
            e_1 = ((parse_Error)r);
            tmp__23 = ((parse_Code)e_1);
	    return tmp__23;
	    break;
	  default:;
            i_2 = (i_2 + 1);
            break;
	  };
	  goto L16_;
    L17_:;
	  tmp__22 = w->array[i_2];
	  break;

So one building block repeated ~5 times in the first one is:

	  if ((n == 2)) goto L16_;
	  r = evaluate_eval(w->array[1]);
	  switch (r->type_) {;
	  case 16:;
            e_2 = ((parse_Error)r);
            tmp__24 = ((parse_Code)e_2);
	    return tmp__24;
	    break;
	  default:;
	    break;
	  };

Whereas for the simpler version as a single block:

	  if ((! (i_2 < (n - 1)))) goto L17_;
	  r = evaluate_eval(w->array[i_2]);
	  switch (r->type_) {;
	  case 16:;
            e_1 = ((parse_Error)r);
            tmp__23 = ((parse_Code)e_1);
	    return tmp__23;
	    break;
	  default:;
            i_2 = (i_2 + 1);
            break;
	  };

I'm not a c expert, so maybe the compiler can optimize n == 2 and w->array[1] more than ! (i_2 < (n-1)) and w->array[i_2], but even if that's the case, is it worth it?

[mahrud]

I doubt this will get answered so closing.