MENU

《两周自制脚本语言》——第十二天(优化对象操作性能)

December 25, 2018 • Read: 580 • 编译原理

笔记、源码同步在github上,欢迎Star,蟹蟹~


减少内存占用

第9天的实现使用了环境来表现Stone语言中的对象。环境中不仅含有由字段名与相应的值组成的键值对,还记录了由方法名与Function对象组成的键值对。这种实现的内存利用率很低

JavaScript每个对象都能拥有不同方法的语言,这种实现方式较为合适。然而,Stone语言中同一个类的对象只能具有相同的方法。因此,语言处理器没有必要在环境中记录由方法名与Function对象组成的键值对

基于以上原因,今天的优化中,同一个类的对象将共享方法(见下图)。Stone语言将为每个方法创建一个ClassInfo对象,用于记录与方法相关的信息。用于表示Stone语言对象的stoneObject对象包含ClassInfo对象的引用,当语言处理器需要获取方法调用的相关信息时,将查找该ClassInfo对象中的内容。这样一来,Stoneobject对象仅需记录字段信息,每个单独的stoneobject对象使用的内存量也相应减少

今天的优化方法和第十一天一样,通过数组实现环境

根据上述讨论重新定义ClassInfo类与StoneObject类。为了区分今天和第九天的定义,重新定义的类的名称之前会加上Opt

代码清单12.1 OptClassInfo.java

package chap12;
import java.util.ArrayList;
import Stone.ast.ClassStmnt;
import Stone.ast.DefStmnt;
import chap11.Symbols;
import chap12.ObjOptimizer.DefStmntEx2;
import chap6.Environment;
import chap9.ClassInfo;

public class OptClassInfo extends ClassInfo {
    protected Symbols methods, fields;
    protected DefStmnt[] methodDefs;

    public OptClassInfo(ClassStmnt cs, Environment env, Symbols methods, Symbols fields) {
        super(cs, env);
        this.methods = methods;
        this.fields = fields;
        this.methodDefs = null;
    }

    public int size() {
        return fields.size();
    }

    @Override
    public OptClassInfo superClass() {
        return (OptClassInfo) superClass;
    }

    public void copyTo(Symbols f, Symbols m, ArrayList<DefStmnt> mlist) {
        f.append(fields);
        m.append(methods);
        for (DefStmnt def : methodDefs)
            mlist.add(def);
    }

    public Integer fieldIndex(String name) {
        return fields.find(name);
    }

    public Integer methodIndex(String name) {
        return methods.find(name);
    }

    public Object method(OptStoneObject self, int index) {
        DefStmnt def = methodDefs[index];
        return new OptMethod(def.parameters(), def.body(), environment(), ((DefStmntEx2) def).locals(), self);
    }

    public void setMethods(ArrayList<DefStmnt> methods) {
        methodDefs = methods.toArray(new DefStmnt[methods.size()]);
    }
}

代码清单12.2 OptStoneObject.java

package chap12;
import chap12.OptStoneObject.AccessException;

public class OptStoneObject {
    public static class AccessException extends Exception {
    }

    protected OptClassInfo classInfo;
    protected Object[] fields;

    public OptStoneObject(OptClassInfo ci, int size) {
        classInfo = ci;
        fields = new Object[size];
    }

    public OptClassInfo classInfo() {
        return classInfo;
    }

    public Object read(String name) throws AccessException {
        Integer i = classInfo.fieldIndex(name);
        if (i != null)
            return fields[i];
        else {
            i = classInfo.methodIndex(name);
            if (i != null)
                return method(i);
        }
        throw new AccessException();
    }

    public void write(String name, Object value) throws AccessException {
        Integer i = classInfo.fieldIndex(name);
        if (i == null)
            throw new AccessException();
        else
            fields[i] = value;
    }

    public Object read(int index) {
        return fields[index];
    }

    public void write(int index, Object value) {
        fields[index] = value;
    }

    public Object method(int index) {
        return classInfo.method(this, index);
    }
}

代码清单12.3 OptMethod.java

package chap12;
import Stone.ast.BlockStmnt;
import Stone.ast.ParameterList;
import chap11.ArrayEnv;
import chap11.OptFunction;
import chap6.Environment;

public class OptMethod extends OptFunction {
    OptStoneObject self;

    public OptMethod(ParameterList parameters, BlockStmnt body, Environment env, int memorySize, OptStoneObject self) {
        super(parameters, body, env, memorySize);
        this.self = self;
    }

    @Override
    public Environment makeEnv() {
        ArrayEnv e = new ArrayEnv(size, env);
        e.put(0, 0, self);
        return e;
    }
}

定义lookup方法

lookup方法能查找class语句中与由大括号括起的类定义体对应的抽象语法树,向Symbols对象添加该类种所有的方法名与字段名,同时为它们分配保存位置。lookup方法执行结束后,语言处理器将能通过Symbols对象获得方法名与字段名一览

下图是lookup方法在查找大括号括起的类定义体时使用的Symbo1s对象。这4个对象通过outer字段连接,分别记录了不同类型的名称。除了最后一个,这些对象都属于Symbo1s类的子类

代码清单12.4是图中第一个出现的SymbolThis对象的定义。它用于记录在类定义体中有效的局部变量的名称。然而,与函数不同,类定义体中新增的名称并非局部变量,而是字段名称,因此该作用域内的有效局部变量就只有一个this。SymbolThis对象仅会记录this的信息

下面这两个MemberSymbols对象分别用于记录字段名与方法名。代码清单12.5是它们的定义。如果lookup方法在类定义中遇到了用于定义方法的def语句,就会直接将该方法名称添加至第二个Membersymbols对象中

代码清单12.4 SymbolThis.java

package chap12;
import Stone.StoneException;
import chap11.Symbols;

public class SymbolThis extends Symbols {
    public static final String NAME = "this";

    public SymbolThis(Symbols outer) {
        super(outer);
        add(NAME);
    }

    @Override
    public int putNew(String key) {
        throw new StoneException("fatal");
    }

    @Override
    public Location put(String key) {
        Location loc = outer.put(key);
        if (loc.nest >= 0)
            loc.nest++;
        return loc;
    }
}

代码清单12.5 MemberSymbols.java

package chap12;
import chap11.Symbols;

public class MemberSymbols extends Symbols {
    public static int METHOD = -1;
    public static int FIELD = -2;
    protected int type;

    public MemberSymbols(Symbols outer, int type) {
        super(outer);
        this.type = type;
    }

    @Override
    public Location get(String key, int nest) {
        Integer index = table.get(key);
        if (index == null)
            if (outer == null)
                return null;
            else
                return outer.get(key, nest);
        else
            return new Location(type, index.intValue());
    }

    @Override
    public Location put(String key) {
        Location loc = get(key, 0);
        if (loc == null)
            return new Location(type, add(key));
        else
            return loc;
    }
}

整合所有修改并执行

代码清单12.6 ObjOptimizer.java

package chap12;
import java.util.ArrayList;
import java.util.List;
import static javassist.gluonj.GluonJ.revise;
import javassist.gluonj.*;
import Stone.*;
import Stone.ast.*;
import chap6.Environment;
import chap6.BasicEvaluator;
import chap6.BasicEvaluator.ASTreeEx;
import chap7.FuncEvaluator.PrimaryEx;
import chap11.ArrayEnv;
import chap11.EnvOptimizer;
import chap11.Symbols;
import chap11.EnvOptimizer.ASTreeOptEx;
import chap11.EnvOptimizer.EnvEx2;
import chap11.EnvOptimizer.ParamsEx;
import chap12.OptStoneObject.AccessException;

@Require(EnvOptimizer.class)
@Reviser
public class ObjOptimizer {
    @Reviser
    public static class ClassStmntEx extends ClassStmnt {
        public ClassStmntEx(List<ASTree> c) {
            super(c);
        }

        public void lookup(Symbols syms) {
        }

        public Object eval(Environment env) {
            Symbols methodNames = new MemberSymbols(((EnvEx2) env).symbols(), MemberSymbols.METHOD);
            Symbols fieldNames = new MemberSymbols(methodNames, MemberSymbols.FIELD);
            OptClassInfo ci = new OptClassInfo(this, env, methodNames, fieldNames);
            ((EnvEx2) env).put(name(), ci);
            ArrayList<DefStmnt> methods = new ArrayList<DefStmnt>();
            if (ci.superClass() != null)
                ci.superClass().copyTo(fieldNames, methodNames, methods);
            Symbols newSyms = new SymbolThis(fieldNames);
            ((ClassBodyEx) body()).lookup(newSyms, methodNames, fieldNames, methods);
            ci.setMethods(methods);
            return name();
        }
    }

    @Reviser
    public static class ClassBodyEx extends ClassBody {
        public ClassBodyEx(List<ASTree> c) {
            super(c);
        }

        public Object eval(Environment env) {
            for (ASTree t : this)
                if (!(t instanceof DefStmnt))
                    ((ASTreeEx) t).eval(env);
            return null;
        }

        public void lookup(Symbols syms, Symbols methodNames, Symbols fieldNames, ArrayList<DefStmnt> methods) {
            for (ASTree t : this) {
                if (t instanceof DefStmnt) {
                    DefStmnt def = (DefStmnt) t;
                    int oldSize = methodNames.size();
                    int i = methodNames.putNew(def.name());
                    if (i >= oldSize)
                        methods.add(def);
                    else
                        methods.set(i, def);
                    ((DefStmntEx2) def).lookupAsMethod(fieldNames);
                } else
                    ((ASTreeOptEx) t).lookup(syms);
            }
        }
    }

    @Reviser
    public static class DefStmntEx2 extends EnvOptimizer.DefStmntEx {
        public DefStmntEx2(List<ASTree> c) {
            super(c);
        }

        public int locals() {
            return size;
        }

        public void lookupAsMethod(Symbols syms) {
            Symbols newSyms = new Symbols(syms);
            newSyms.putNew(SymbolThis.NAME);
            ((ParamsEx) parameters()).lookup(newSyms);
            ((ASTreeOptEx) revise(body())).lookup(newSyms);
            size = newSyms.size();
        }
    }

    @Reviser
    public static class DotEx extends Dot {
        public DotEx(List<ASTree> c) {
            super(c);
        }

        public Object eval(Environment env, Object value) {
            String member = name();
            if (value instanceof OptClassInfo) {
                if ("new".equals(member)) {
                    OptClassInfo ci = (OptClassInfo) value;
                    ArrayEnv newEnv = new ArrayEnv(1, ci.environment());
                    OptStoneObject so = new OptStoneObject(ci, ci.size());
                    newEnv.put(0, 0, so);
                    initObject(ci, so, newEnv);
                    return so;
                }
            } else if (value instanceof OptStoneObject) {
                try {
                    return ((OptStoneObject) value).read(member);
                } catch (AccessException e) {
                }
            }
            throw new StoneException("bad member access: " + member, this);
        }

        protected void initObject(OptClassInfo ci, OptStoneObject obj, Environment env) {
            if (ci.superClass() != null)
                initObject(ci.superClass(), obj, env);
            ((ClassBodyEx) ci.body()).eval(env);
        }
    }

    @Reviser
    public static class NameEx2 extends EnvOptimizer.NameEx {
        public NameEx2(Token t) {
            super(t);
        }

        @Override
        public Object eval(Environment env) {
            if (index == UNKNOWN)
                return env.get(name());
            else if (nest == MemberSymbols.FIELD)
                return getThis(env).read(index);
            else if (nest == MemberSymbols.METHOD)
                return getThis(env).method(index);
            else
                return ((EnvEx2) env).get(nest, index);
        }

        @Override
        public void evalForAssign(Environment env, Object value) {
            if (index == UNKNOWN)
                env.put(name(), value);
            else if (nest == MemberSymbols.FIELD)
                getThis(env).write(index, value);
            else if (nest == MemberSymbols.METHOD)
                throw new StoneException("cannot update a method: " + name(), this);
            else
                ((EnvEx2) env).put(nest, index, value);
        }

        protected OptStoneObject getThis(Environment env) {
            return (OptStoneObject) ((EnvEx2) env).get(0, 0);
        }
    }

    @Reviser
    public static class AssignEx extends BasicEvaluator.BinaryEx {
        public AssignEx(List<ASTree> c) {
            super(c);
        }

        @Override
        protected Object computeAssign(Environment env, Object rvalue) {
            ASTree le = left();
            if (le instanceof PrimaryExpr) {
                PrimaryEx p = (PrimaryEx) le;
                if (p.hasPostfix(0) && p.postfix(0) instanceof Dot) {
                    Object t = ((PrimaryEx) le).evalSubExpr(env, 1);
                    if (t instanceof OptStoneObject)
                        return setField((OptStoneObject) t, (Dot) p.postfix(0), rvalue);
                }
            }
            return super.computeAssign(env, rvalue);
        }

        protected Object setField(OptStoneObject obj, Dot expr, Object rvalue) {
            String name = expr.name();
            try {
                obj.write(name, rvalue);
                return rvalue;
            } catch (AccessException e) {
                throw new StoneException("bad member access: " + name, this);
            }
        }
    }
}

代码清单12.7 ObjOptInterpreter.java

package chap12;
import Stone.ClassParser;
import Stone.ParseException;
import chap11.EnvOptInterpreter;
import chap11.ResizableArrayEnv;
import chap8.Natives;

public class ObjOptInterpreter extends EnvOptInterpreter {
    public static void main(String[] args) throws ParseException {
        run(new ClassParser(),
            new Natives().environment(new ResizableArrayEnv()));
    }
}

代码清单12.8 ObjOptRunner.java

package chap12;
import javassist.gluonj.util.Loader;
import chap8.NativeEvaluator;

public class ObjOptRunner {
    public static void main(String[] args) throws Throwable {
        Loader.run(ObjOptInterpreter.class, args, ObjOptimizer.class, NativeEvaluator.class);
    }
}

内联缓存

如果要对非this对象进行方法调用或字段引用,今天介绍的1ookup方法将不再有效,执行速度无法得到提升。这样一来,语言处理器在调用函数或引用字段时,就不得不通过名称来查找环境,从哈希表中获取对应的值,使执行速度大幅下降

为了缓解这一问题,我们将使用一种名为内联缓存(inline cache)的方法。首先,我们假设程序需要引用某个对象的字段。正如之前所讲,只有在实际执行后语言处理器才能确定该对象的类型。不过,根据经验可知,同一位置出现的对象通常是同一种类型。即使是采用面向对象思想写成的程序也是如此。我们能够利用这一规律优化处理器的性能。语言处理器可以在执行程序的同时查找字段的保存位置,并将该结果与对象所属的类型结对保存。之后,如果再次执行同一段程序,语言处理器将首先判断对象的类型,如果与之前相同,则直接使用上次的查找结果,减少了因查找保存位置造成的性能下降

代码清单12.9中的InlineCache修改器实现了内联缓存机制。它将覆盖Dot类的eval方法与BinaryExpr类的setField方法。此外,它还会为每个类添加用于实现缓存功能的classInfo字段与index字段(其中,Dot类还会额外新增一个isField字段)

Dot类的eval方法用于读取字段的值,或充当方法调用表达式。setField方法用于处理赋值表达式左侧是某个对象的字段时的情况。这里的setField方法正是代码清单12.6中由AssignEx修改器定义的setField方法。这两个方法都会将由修改器添加的classInfo字段的值,与当前正被执行方法调用或字段引用的对象类型进行比较。如果相同,则再次利用上一次保存的值

经过InlineCache修改器的修改后,解释器将支持内联缓存功能。解释器本身的程序与代码清单12.7中的相同,不过,应用了修改器的解释器需要通过代码清单12.10中的启动程序运行。它与代码清单12.10及更早的代码清单12.8中的启动程序大同小异,唯一的区别在于启动程序中的run方法将接收不同类型的修改器

代码清单12.9 InlineCache.java

package chap12;
import java.util.List;
import Stone.StoneException;
import Stone.ast.ASTree;
import Stone.ast.Dot;
import chap6.Environment;
import javassist.gluonj.*;

@Require(ObjOptimizer.class)
@Reviser
public class InlineCache {
    @Reviser
    public static class DotEx2 extends ObjOptimizer.DotEx {
        protected OptClassInfo classInfo = null;
        protected boolean isField;
        protected int index;

        public DotEx2(List<ASTree> c) {
            super(c);
        }

        @Override
        public Object eval(Environment env, Object value) {
            if (value instanceof OptStoneObject) {
                OptStoneObject target = (OptStoneObject) value;
                if (target.classInfo() != classInfo)
                    updateCache(target);
                if (isField)
                    return target.read(index);
                else
                    return target.method(index);
            } else
                return super.eval(env, value);
        }

        protected void updateCache(OptStoneObject target) {
            String member = name();
            classInfo = target.classInfo();
            Integer i = classInfo.fieldIndex(member);
            if (i != null) {
                isField = true;
                index = i;
                return;
            }
            i = classInfo.methodIndex(member);
            if (i != null) {
                isField = false;
                index = i;
                return;
            }
            throw new StoneException("bad member access: " + member, this);
        }
    }

    @Reviser
    public static class AssignEx2 extends ObjOptimizer.AssignEx {
        protected OptClassInfo classInfo = null;
        protected int index;

        public AssignEx2(List<ASTree> c) {
            super(c);
        }

        @Override
        protected Object setField(OptStoneObject obj, Dot expr, Object rvalue) {
            if (obj.classInfo() != classInfo) {
                String member = expr.name();
                classInfo = obj.classInfo();
                Integer i = classInfo.fieldIndex(member);
                if (i == null)
                    throw new StoneException("bad member access: " + member, this);
                index = i;
            }
            obj.write(index, rvalue);
            return rvalue;
        }
    }
}

代码清单12.10 InlineRunner.java

package chap12;
import javassist.gluonj.util.Loader;
import chap8.NativeEvaluator;

public class InlineRunner {
    public static void main(String[] args) throws Throwable {
        Loader.run(ObjOptInterpreter.class, args, InlineCache.class, NativeEvaluator.class);
    }
}

代码清单12.11 测试斐波那契数的计算时间(面向对象版本)

class Fib {
    fib0 = 0
    fib1 = 1
    def fib (n) {
        if n == 0 {
            fib0
        } else {
            if n == 1 {
                this.fib1
            } else {
                fib(n - 1) + this.fib(n - 2)
            }
        }
    }
}
t = currentTime()
f = Fib.new
f.fib 33
print currentTime() - t + " msec"

运行效果如下:

可以看到优化后执行所需的时间约6秒,第九天没优化的执行所需时间约8秒

第十二天的思维导图

Archives Tip
QR Code for this page
Tipping QR Code