In [2]:
Read("../gap/optim.g"); Read("../gap/bench.g");

GAP Level Reflection

This newly added feature of GAP allows GAP programs to examine and modify the code of executable GAP function objects within the workspace. This will provide a platform for optimisation, automatic parallelisation and Cython-like partial static typing.

A Small Optimisation

It is natural in GAP to write Int(x/y) for integer division, but this is actually quite inefficient. If x is not divisible by y then a rational number object will be made on the heap and reduced to lowest terms before being rounded to the nearest integer below. The QuoInt function exists to avoid this, but is unnatural and underused.

We demonstrate the difference with a simple benchmark:

In [6]:
foo := function(n) local i,x; for i in [1..n] do 
    x := Int(i/3); 
    od; end;;
bar :=  function(n) local i,x; for i in [1..n] do 
    x := QuoInt(i,3); 
    od; end;;
ns2string(timer(foo)); ns2string(timer(bar));
Out[6]:
"137ns"
Out[6]:
"23ns"

We show how SyntaxTree could be used to automatically fix this in the workspace.

f below is a test function. The second comment is a pragma -- a comment which is retained in the function object, which could be used to direct optimisation.

Note that the pragma appears in the syntax tree, unlike the regular comment

In [10]:
f := function(x) 
    # normal comment
    #% optimise here 
    return Int((x+1)/3) + Int((x^2)/11);
end;;
Display(SyntaxTree(f));
EXPR_FUNC(name := f, nams := [ "x" ], variadic := false, narg := 1, nloc := 0,\
 stats := STAT_SEQ_STAT2(
              statements := [
                STAT_PRAGMA(value := % optimise here ), STAT_RETURN_OBJ(
                  obj := EXPR_SUM(
                    right := EXPR_FUNCCALL_1ARGS(
                      args := [
                        EXPR_QUO(
                          right := EXPR_INT(value := 11), left := EXPR_POW(
                            right := EXPR_INT(
                              value := 2), left := EXPR_REF_LVAR(lvar := 1)))
                          ], funcref := EXPR_REF_GVAR(gvar := Int)
                           ), left := EXPR_FUNCCALL_1ARGS(
                          args := [
                            EXPR_QUO(
                              right := EXPR_INT(value := 3), left := EXPR_SUM(
                                right := EXPR_INT(
                                  value := 1), left := EXPR_REF_LVAR(
                                  lvar := 1)))
                              ], funcref := EXPR_REF_GVAR(gvar := Int))))]))
                        

Now to produce an improved version of f, we define a pattern including placeholders "$1" and "$2" and a replacement.

Both are essentially just fragments of syntax tree. Nicer pattern editing tools and in development.

In [ ]:
pattern := rec(type := "EXPR_FUNCCALL_1ARGS", 
    funcref := rec(type := "EXPR_REF_GVAR", gvar := "Int"),
    args := [rec(type := "EXPR_QUO", left := "$1", right := rec(type := "EXPR_INT", value := "$2"))]);
replace := rec(type := "EXPR_FUNCCALL_2ARGS",
    funcref := rec(type := "EXPR_REF_GVAR", gvar := "QuoInt"),
    args := ["$1",rec(type := "EXPR_INT", value := "$2") ]);
Out[ ]:
rec( args := [ rec( left := "$1", right := rec( type := "EXPR_INT", value := "$2" ), type := "EXPR_QUO" ) ], funcref := rec( gvar := "Int", type := "EXPR_REF_GVAR" ), type := "EXPR_FUNCCALL_1ARGS" )
Out[ ]:
rec( args := [ "$1", rec( type := "EXPR_INT", value := "$2" ) ], funcref := rec( gvar := "QuoInt", type := "EXPR_REF_GVAR" ), type := "EXPR_FUNCCALL_2ARGS" )

We can use these to rewrite f

In [22]:
g := RewriteFunc(f, pattern, replace);;
Display(g);
function ( x )
                            #% optimise here 
                            return QuoInt( x + 1, 3 ) + QuoInt( x ^ 2, 11 );
                        end
                        

We compare the performance.

In [18]:
ns2string(timer( function(n) local i; for  i in [1..n] do f(i); od; end));
ns2string(timer( function(n) local i; for  i in [1..n] do g(i); od; end));
Out[18]:
"340ns"
Out[18]:
"95ns"