パフォーマンスチューニング いのちをだいじに
さて現在のプロファイラの結果によると pass3/find-free が実行時間の 1/4 を占める。
time% msec calls name 24 220 4606 pass3/find-free
この手続きは中間形式 IForm で表現された lambda の中にある free variables を探してリストで返すもの。
現在 C++ で書かれている。Scheme で書かれていたものをそのまま移植したので再帰。
さてこれをどうやって速くするかだな。
入力が長いと結果を append2 でためていくのはコストが高そうと予想はしているが測定はまだしていない。
コストが高かったら vector
Object findFreeRec(Object i, Object l, Object canFrees, Object labelsSeen)
{
const int CONST = 0;
const int LET = 2;
const int SEQ = 3;
const int LAMBDA = 4;
const int LOCAL_REF = 5;
const int LOCAL_ASSIGN = 6;
const int GLOBAL_REF = 7;
const int GLOBAL_ASSIGN = 8;
const int UNDEF = 9;
const int IF = 10;
const int ASM = 11;
const int DEFINE = 12;
const int CALL_CC = 13;
const int CALL = 14;
const int LABEL = 15;
const int LIST = 16;
const int LIBRARY = 17;
const int IMPORT = 18;
const int IT = 20;
const int RECEIVE = 21;
Vector* v = i.toVector();
switch(v->ref(0).toInt()) {
case CONST:
return Object::Nil;
case LET:
{
const Object letLvars = v->ref(2);
const Object letInits = v->ref(3);
const Object letBody = v->ref(4);
return Pair::append2(findFreeRecMap(l, canFrees, labelsSeen, letInits),
findFreeRec(letBody, letLvars, canFrees, labelsSeen));
}
case RECEIVE:
{
const Object receiveVals = v->ref(4);
const Object receiveBody = v->ref(5);
const Object receiveLVars = v->ref(1);
return Pair::append2(findFreeRec(receiveVals, l, canFrees, labelsSeen),
findFreeRec(receiveBody, receiveLVars, canFrees, labelsSeen));
}
case SEQ:
{
const Object seqBody = v->ref(1);
return findFreeRecMap(l, canFrees, labelsSeen, seqBody);
}
case LAMBDA:
{
const Object lambdaBody = v->ref(6);
const Object lambdaLvars = v->ref(5);
return findFreeRec(lambdaBody, lambdaLvars, canFrees, labelsSeen);
}
case LOCAL_ASSIGN:
{
const Object lvar = v->ref(1);
const Object val = v->ref(2);
if (existsInCanFrees(lvar, canFrees)) {
return Object::cons(lvar, findFreeRec(val, l, canFrees, labelsSeen));
} else {
return findFreeRec(val, l, canFrees, labelsSeen);
}
}
case LOCAL_REF:
{
const Object lvar = v->ref(1);
if (!memq(lvar, l).isFalse()) {
return Object::Nil;
} else if (existsInCanFrees(lvar, canFrees)) {
return Pair::list1(lvar);
} else {
return Object::Nil;
}
}
case GLOBAL_REF:
{
const Object sym = v->ref(2);
Object foundSym = findSymbolInCanFrees(sym, canFrees);
return !foundSym.isFalse() ? Pair::list1(foundSym) : Object::Nil;
}
case UNDEF:
return Object::Nil;
case IF:
{
const Object testF = findFreeRec(v->ref(1), l, canFrees, labelsSeen);
const Object thenF = findFreeRec(v->ref(2), l, canFrees, labelsSeen);
const Object elseF = findFreeRec(v->ref(3), l, canFrees, labelsSeen);
return Pair::append2(testF, Pair::append2(thenF, elseF));
}
case ASM:
{
const Object asmArgs = v->ref(2);
return findFreeRecMap(l, canFrees, labelsSeen, asmArgs);
}
case DEFINE:
{
const Object defineVal = v->ref(3);
return findFreeRec(defineVal, l, canFrees, labelsSeen);
}
case CALL:
{
const Object callArgs = v->ref(2);
const Object callProc = v->ref(1);
return Pair::append2(findFreeRecMap(l, canFrees, labelsSeen, callArgs),
findFreeRec(callProc, l, canFrees, labelsSeen));
}
case CALL_CC:
{
const Object callccProc = v->ref(1);
return findFreeRec(callccProc, l, canFrees, labelsSeen);
}
case GLOBAL_ASSIGN:
{
const Object globalAssignVal = v->ref(3);
return findFreeRec(globalAssignVal, l, canFrees, labelsSeen);
}
case LIST:
{
const Object listArgs = v->ref(1);
return findFreeRecMap(l, canFrees, labelsSeen, listArgs);
}
case LABEL:
{
const Object labelBody = v->ref(2);
if (!memq(i, labelsSeen).isFalse()) {
return Object::Nil;
} else {
return findFreeRec(labelBody, l, canFrees, Object::cons(i, labelsSeen));
}
}
case IMPORT:
return Object::Nil;
case LIBRARY:
return Object::Nil;
case IT:
return Object::Nil;
default:
VM_RAISE1("pass3/find-free unknown iform: ~a", v->ref(0));
break;
}
return Object::Undef;
