opt_accumulators.mx

一个内存数据库的源代码这是服务器端还有客户端

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f opt_accumulators
@- Accumulator Evaluations
Bulk arithmetic calculations are pretty expensive,
because new @sc{bat}s are created for each expression. 
This memory hunger can be reduced
by detecting opportunities for accummulator processing, i.e.
where a (temporary) variable is overwritten.
For example, consider the program snippet
@example
	t3:= batcalc.*(64,t2);
	t4:= batcalc,+(t1,t3);
	optimizer.accumulators();
@end example
If variable t2 is a temporary variable and not used any further in
the program block, we can re-use its storage space
and propagate its alias through the remainder of the code.
@example
	batcalc.*(t2,64,t2);
	t4:= batcalc.+(t2,t1,t2);
@end example
The implementation is straight forward. It only deals with the
arithmetic operations available in @sc{batcalc} right now.
This set will be gradually be extended.
The key decision is to determine whether we may overwrite
any of the arguments. This is hard to detect at compile
time, e.g. the argument may be the result of a binding operation
or represent a view over a persistent BAT.
Therefore, the compiler injects the call @sc{algebra.reuse()},
which avoids overwriting persistent BATs by taking a copy.
@{
@mal
pattern optimizer.accumulators():str
address OPTaccumulators;
pattern optimizer.accumulators(mod:str, fcn:str):str
address OPTaccumulators
comment "Replace calculations with accumulator model";
@h
#ifndef _OPT_ACCUMULATORS_
#define _OPT_ACCUMULATORS_
#include "opt_prelude.h"
#include "opt_support.h"
#include "mal_interpreter.h"

/* #define DEBUG_OPT_OPTIMIZER     show partial result */

#endif

@c
#include "mal_config.h"
#include "opt_accumulators.h"
#include "mal_builder.h"

static int
OPTaccumulatorsImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
	int i,j, a=0, b, valid, limit;
	InstrPtr p,q;
	Client cntxt = MCgetClient();
	Module scope = cntxt->nspace;
	int actions = 0;
	char *available;
	int *alias;
	InstrPtr *old;

	(void) pci;
	(void) stk;		/* to fool compilers */
	setLifespan(mb);
	alias= (int*) alloca(sizeof(int)*mb->vtop);
	for(j=0;j< mb->vtop; j++)
		alias[j]=j;
	available= (char*) alloca(sizeof(int)*mb->vtop);
	memset(available,0, sizeof(int)* mb->vtop);
	old= mb->stmt;
	limit= mb->stop;
	newMalBlkStmt(mb,mb->stop);
@-
Check for errors encountered sofar. If encountered
the replacement is aborted.
@= patchInstruction
	typeChecker(scope, mb, p, TRUE);
	if (mb->errors || p->typechk == TYPE_UNKNOWN) {
		/* reset instruction */
		mb->errors= 0;
		cntxt->errbuf[0]=0;
		freeInstruction(p);
		p=q;
	} else  {
		freeInstruction(q);
		if(available[a]==0){
			q= newFcnCall(mb,"algebra","reuse");
			getArg(q,0)= getArg(p,1);
			pushArgument(mb,q,a);
			available[getArg(q,0)]=1;
		} else {
			alias[getArg(p,1)]= a;
			getArg(p,1)=a;
			getArg(p,0)=a;
		}
		actions++;
	}
#ifdef DEBUG_OPT_OPTIMIZER
	printInstruction(GDKout, mb, p, LIST_MAL_ALL);
#endif
@c
	for (i = 0; i < limit; i++) {
		VarPtr v=0;
		p = old[i];

		for(j= p->retc; j<p->argc; j++)
		if( alias[getArg(p,j)] )
			getArg(p,j)= alias[getArg(p,j)];

		if( getModuleId(p) != batcalcRef ) {
			pushInstruction(mb,p);
			continue;
		}

		if (p->retc==1  && p->argc == 3) {
			/* binary/unary operation, check first argument */
			b = getArg(p, 0);
			
			valid= 0;
			if( available[getArg(p,1)] && getEndLifespan(mb,getArg(p,1))<=i){
				v = getVar(mb, a = getArg(p, 1));
				valid=  v->type == getVarType(mb,b);
			}
			if(!valid && available[getArg(p,2)] && getEndLifespan(mb,getArg(p,2))<=i){
				v = getVar(mb, a = getArg(p, 2));
				valid=  v->type == getVarType(mb,b);
			} 
			if(!valid && getEndLifespan(mb,getArg(p,1))<=i){
				v = getVar(mb, a = getArg(p, 1));
				valid=  v->type == getVarType(mb,b);
			} 
			if( !valid && getEndLifespan(mb,getArg(p,2)) <= i){
				v = getVar(mb, a = getArg(p, 2));
				valid=v->type == getVarType(mb,b);
			} 

			if( getLastUpdate(mb,b) != i || !valid || !isaBatType(v->type)) {
				pushInstruction(mb,p);
				continue;
			}
#ifdef DEBUG_OPT_OPTIMIZER
			stream_printf(GDKout, "Found accumulation candidate ");
			stream_printf(GDKout, "%d: %d(%d,%d) valid=%d isaBat=%d \n", 
				i, b,a,getArg(p,2), valid, isaBatType(v->type));
			printInstruction(GDKout, mb, p, LIST_MAL_ALL);
#endif
@-
Beware, we may only use temporary BATs as accumulators, otherwise
we can corrupt the database. 
It is safe to limit the candidates re-useable variables to those
produced by the batcalc operations. 
If the target is not yet available as a temporary variable, make
sure it becomes one.
@c

			q= copyInstruction(p);
			pushArgument(mb, p, getArg(p,2));
			setArg(p,2,getArg(p,1));
			setArg(p,1,getArg(p,0));
			@:patchInstruction@
	} else if (p->retc==1 && p->argc == 2) {
			/* unary operation, check first argument  and return type */
			v = getVar(mb, a = getArg(p, 1));
			b = getArg(p, 0);
			if( getLastUpdate(mb,b) != i || getEndLifespan(mb,a) > i ||
				!isaBatType(v->type) || v->type!= getVarType(mb,b) ) {
				pushInstruction(mb,p);
				continue;
			}
			
#ifdef DEBUG_OPT_OPTIMIZER
			stream_printf(GDKout, "Found unary accumulation candidate\n");
			printInstruction(GDKout, mb, p, LIST_MAL_ALL);
#endif
			q= copyInstruction(p);
			pushArgument(mb, p, a);
			setArg(p,1,getArg(p,0));
			@:patchInstruction@
		} 
		pushInstruction(mb,p);
	}
	GDKfree(old);
	return actions;
}

@include optimizerWrapper.mx
@h
@:exportOptimizer(accumulators)@
@c
@:wrapOptimizer(accumulators,OPT_CHECK_ALL)@
@}