Read("../gap/optim.g"); Read("../gap/bench.g");
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.
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:
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));
"137ns"
"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
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.
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") ]);
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" )
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
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.
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));
"340ns"
"95ns"