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?

M2/M2/Macaulay2/d/evaluate.d

Lines 43 to 64 in ec9e9ac

	is v:semiCode do (
	w := v.w;
	n := length(w); -- at least 2
	r := eval(w.0);
	when r is e:Error do return Code(e) else nothing;
	if n == 2 then w.1 else (
	r = eval(w.1);
	when r is e:Error do return Code(e) else nothing;
	if n == 3 then w.2 else (
	r = eval(w.2);
	when r is e:Error do return Code(e) else nothing;
	if n == 4 then w.3 else (
	r = eval(w.3);
	when r is e:Error do return Code(e) else nothing;
	if n == 5 then w.4 else (
	r = eval(w.4);
	when r is e:Error do return Code(e) else nothing;
	i := 5;
	while i < n-1 do (
	r = eval(w.i);
	when r is e:Error do return Code(e) else i = i+1);
	w.i)))))

M2/M2/Macaulay2/d/evaluate.d

Lines 1529 to 1550 in ec9e9ac

	is v:semiCode do (
	w := v.w;
	n := length(w); -- at least 2
	r := eval(w.0);
	when r is Error do r else (
	r = eval(w.1);
	when r is Error do r else (
	if n == 2 then return r;
	r = eval(w.2);
	when r is Error do r else (
	if n == 3 then return r;
	r = eval(w.3);
	when r is Error do r else (
	if n == 4 then return r;
	r = eval(w.4);
	when r is Error do r else (
	i := 5;
	while i < n do (
	r = eval(w.i);
	i = when r is Error do n else i+1;
	);
	r))))))

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?