文档章节

两周自制脚本语言-第11天 优化变量读写性能

果汁分你一半
 果汁分你一半
发布于 01/23 20:21
字数 3250
阅读 115
收藏 0

第11天 优化变量读写性能

以变量值的读写为例,向读者介绍基于这种理念的语言处理器性能优化方式。

11.1 通过简单数组来实现环境

假如函数包含局部变量x与y,程序可以事先将x设为数组的第0个元素,将y设为第1个元素,以此类推。这样一来,语言处理器引用变量时就无需计算哈希值。也就是说,这是一个通过编号,而非名称来查找变量值的环境

为了实现这种设计,语言处理器需要在函数定义完成后遍历对应的抽象语法树节点,获取该节点使用的所有函数参数与局部变量。遍历之后程序将得到函数中用到的参数与局部变量的数量,于是确定了用于保存这些变量的数组的长度

之后,语言处理器在实际调用函数,对变量的值进行读写操作时,将会直接引用数组中的元素。变量引用无需再像之前那样通过在哈希表中查找变量名的方式实现。

确定变量的值在数组中的保存位置之后,这些信息将被记录于抽象语法树节点对象的字段中。例如,程序中出现的变量名在抽象语法树中以Name对象表示。这一Name对象将事先在字段中保存数组元素的下标,这样语言处理器在需要引用该变量时,就能知道应该引用数组中的哪一个元素。Name对象的eval方法将通过该字段来引用数组元素,获得变量的值。

不必在程序执行时通过变量名来查找变量。

如果希望在Name对象的字段中保存变量的引用,仅凭数组元素仍然不够,还需要同时记录与环境对应的作用域。环境将以嵌套结构实现闭包。为此,Environment对象需要通过outer字段串连。此外,Name对象还要记录环境所处的层数,即从最内层向外数起,当前环境在这一连串Environment对象中的排序位置。该信息保存于Name对象的nest字段中。index字段则用于记录变量的值在与nest字段指向的环境对应的数组中,具体的保存位置。

图11.1 x=2的抽象语法树与环境

下图是表示x=2的抽象语法树。在该图中,变量x的值保存于从最内层数起的第2个环境对应的数组中,因此Name对象的nest字段的值为1(如果是最内层,则值为0)。由于变量x的值保存于该数组的第3个元素中,因此index字段的值为2

file

代码清单11.1 ArrayEnv.java

为了实现一个通过数组来保存变量值的环境,需要新定义一个ArrayEnv类。提供了与NestedEnv类几乎相同的功能,实现了Environment接口。ArrayEnv类没有使用哈希表,仅通过简单的数组实现了变量值的保存。

package chap11;
import stone.StoneException;
import chap11.EnvOptimizer.EnvEx2;
import chap6.Environment;

public class ArrayEnv implements Environment {
	protected Object[] values;
	protected Environment outer;

	public ArrayEnv(int size, Environment out) {
		values = new Object[size];
		outer = out;
	}

	public Symbols symbols() {
		throw new StoneException("no symbols");
	}

	public Object get(int nest, int index) {
		if (nest == 0)
			return values[index];
		else if (outer == null)
			return null;
		else
			return ((EnvEx2) outer).get(nest - 1, index);
	}

	public void put(int nest, int index, Object value) {
		if (nest == 0)
			values[index] = value;
		else if (outer == null)
			throw new StoneException("no outer environment");
		else
			((EnvEx2) outer).put(nest - 1, index, value);
	}

	public Object get(String name) {
		error(name);
		return null;
	}

	public void put(String name, Object value) {
		error(name);
	}

	public void putNew(String name, Object value) {
		error(name);
	}

	public Environment where(String name) {
		error(name);
		return null;
	}

	public void setOuter(Environment e) {
		outer = e;
	}

	private void error(String name) {
		throw new StoneException("cannot access by name: " + name);
	}
}

11.2 用于记录全局变量的环境

ArrayEnv实现了用于记录函数的参数与局部变量的环境,但要记录全局变量,我们还需要另外设计一个不同的类,使用该类的对象来实现用于记录全局变量的环境。除了ArrayEnv类的功能,该类还需要随时记录变量的名称与变量值的保存位置(也就是数组元素的下标)之间的对应关系。它不仅能够通过编号查找变量值,还能通过变量名找到与之相应的变量值。

之前设计的Stone语言处理器可以在执行程序的同时以对话的形式添加新的语句。用户不必一次输入全部程序,从头至尾完整运行。因此,为了让之后添加的语句也能访问全局变量,我们必须始终记录变量的名称与该值保存位置的对应关系。 语言处理器必须能够通过变量名查找新添加语句中使用的变量值的保存位置。

另一方面,局部变量仅能在函数内部引用。函数在定义完成时就能确定所有引用了局部变量之处,且之后无法新增。这时,所有引用该变量的标识符都会在各自的Name对象中记录它的保存位置。由于语言处理器记录了这些信息之后便无需再了解变量名与保存位置的对应关系,因此环境不必记录变量的名称。作为用于记录局部变量的环境,ArrayEnv对象已经足够。

代码清单11.2中的ResizableArrayEnv类用于实现记录全局变量的环境。它是ArrayEnv的子类。ArrayEnv对象只能保存固定数量的变量,ResizableArrayEnv对象则能保存任意数量的变量。

由于程序新增的语句可能会引入新的全局变量,因此环境能够保存的变量数量也必须能够修改。ResizableArrayEnv类的对象含有names字段,它的值是一个Symbols对象。Symbols对象是一张哈希表,用于记录变量名与保存位置之间的对应关系。代码清单11.3是Symbols类的定义。

代码清单11.2 ResizableArrayEnv.java

package chap11;
import java.util.Arrays;
import chap6.Environment;
import chap11.EnvOptimizer.EnvEx2;

public class ResizableArrayEnv extends ArrayEnv {
	protected Symbols names;

	public ResizableArrayEnv() {
		super(10, null);
		names = new Symbols();
	}

	@Override
	public Symbols symbols() {
		return names;
	}

	@Override
	public Object get(String name) {
		Integer i = names.find(name);
		if (i == null)
			if (outer == null)
				return null;
			else
				return outer.get(name);
		else
			return values[i];
	}

	@Override
	public void put(String name, Object value) {
		Environment e = where(name);
		if (e == null)
			e = this;
		((EnvEx2) e).putNew(name, value);
	}

	@Override
	public void putNew(String name, Object value) {
		assign(names.putNew(name), value);
	}

	@Override
	public Environment where(String name) {
		if (names.find(name) != null)
			return this;
		else if (outer == null)
			return null;
		else
			return ((EnvEx2) outer).where(name);
	}

	@Override
	public void put(int nest, int index, Object value) {
		if (nest == 0)
			assign(index, value);
		else
			super.put(nest, index, value);
	}

	protected void assign(int index, Object value) {
		if (index >= values.length) {
			int newLen = values.length * 2;
			if (index >= newLen)
				newLen = index + 1;
			values = Arrays.copyOf(values, newLen);
		}
		values[index] = value;
	}
}

代码清单11.3 Symbols.java

package chap11;
import java.util.HashMap;

public class Symbols {
	public static class Location {
		public int nest, index;

		public Location(int nest, int index) {
			this.nest = nest;
			this.index = index;
		}
	}

	protected Symbols outer;
	protected HashMap<String, Integer> table;

	public Symbols() {
		this(null);
	}

	public Symbols(Symbols outer) {
		this.outer = outer;
		this.table = new HashMap<String, Integer>();
	}

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

	public void append(Symbols s) {
		table.putAll(s.table);
	}

	public Integer find(String key) {
		return table.get(key);
	}

	public Location get(String key) {
		return get(key, 0);
	}

	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 + 1);
		else
			return new Location(nest, index.intValue());
	}

	public int putNew(String key) {
		Integer i = find(key);
		if (i == null)
			return add(key);
		else
			return i;
	}

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

	protected int add(String key) {
		int i = table.size();
		table.put(key, i);
		return i;
	}
}

11.3 事先确认变量值的存放位置

接下来为抽象语法树中的类添加1ookup方法,它的作用是在函数定义时,查找函数用到的所有变量,并确定它们在环境中的保存位置。该方法还将根据需要,在抽象语法树的节点对象中记录这些保存位置。这样语言处理器就能够通过编号来查找保存在环境中的变量值

代码清单11.4是为抽象语法树的各个类添加lookup方法的修改器。这里仅对支持函数与闭包的Stone语言进行性能优化,不会涉及类的优化

lookup方法如果在遍历时发现了赋值表达式左侧的变量名,就会查找通过参数接收的Symbols对象,判断该变量名是否是第一次出现、尚未记录。如果它是首次出现的变量名,lookup方法将为它在环境中分配一个保存位置,在Symbols对象中记录由该变量名与保存位置组成的名值对。除了赋值,lookup方法还会在所有引用该变量的抽象语法树节点中记录变量值的保存位置

代码清单11.4 EnvOptimizer.java

package chap11;
import static javassist.gluonj.GluonJ.revise;
import javassist.gluonj.*;
import java.util.List;
import stone.Token;
import stone.StoneException;
import stone.ast.*;
import chap11.Symbols.Location;
import chap6.Environment;
import chap6.BasicEvaluator;
import chap7.ClosureEvaluator;

@Require(ClosureEvaluator.class)
@Reviser public class EnvOptimizer {
    @Reviser public static interface EnvEx2 extends Environment {
        Symbols symbols();
        void put(int nest, int index, Object value);
        Object get(int nest, int index);
        void putNew(String name, Object value);
        Environment where(String name);
    }
    @Reviser public static abstract class ASTreeOptEx extends ASTree {
        public void lookup(Symbols syms) {}
    }
    @Reviser public static class ASTListEx extends ASTList {
        public ASTListEx(List<ASTree> c) { super(c); }
        public void lookup(Symbols syms) {
            for (ASTree t: this)
                ((ASTreeOptEx)t).lookup(syms);
        }
    }
    @Reviser public static class DefStmntEx extends DefStmnt {
        protected int index, size;
        public DefStmntEx(List<ASTree> c) { super(c); }
        public void lookup(Symbols syms) {
            index = syms.putNew(name());
            size = FunEx.lookup(syms, parameters(), body());
        }
        public Object eval(Environment env) {
            ((EnvEx2)env).put(0, index, new OptFunction(parameters(), body(),
                                                        env, size));
            return name();
        }
    }
    @Reviser public static class FunEx extends Fun {
        protected int size = -1;
        public FunEx(List<ASTree> c) { super(c); }
        public void lookup(Symbols syms) {
            size = lookup(syms, parameters(), body());
        }
        public Object eval(Environment env) {
            return new OptFunction(parameters(), body(), env, size);
        }
        public static int lookup(Symbols syms, ParameterList params,
                                 BlockStmnt body)
        {
            Symbols newSyms = new Symbols(syms);
            ((ParamsEx)params).lookup(newSyms);
            ((ASTreeOptEx)revise(body)).lookup(newSyms);
            return newSyms.size();
        }
    }
    @Reviser public static class ParamsEx extends ParameterList {
        protected int[] offsets = null;
        public ParamsEx(List<ASTree> c) { super(c); }
        public void lookup(Symbols syms) {
            int s = size();
            offsets = new int[s];
            for (int i = 0; i < s; i++)
                offsets[i] = syms.putNew(name(i));
        }
        public void eval(Environment env, int index, Object value) {
            ((EnvEx2)env).put(0, offsets[index], value);
        }
    }
    @Reviser public static class NameEx extends Name {
        protected static final int UNKNOWN = -1;
        protected int nest, index;
        public NameEx(Token t) { super(t); index = UNKNOWN; }
        public void lookup(Symbols syms) {
            Location loc = syms.get(name());
            if (loc == null)
                throw new StoneException("undefined name: " + name(), this);
            else {
                nest = loc.nest;
                index = loc.index;
            }
        }
        public void lookupForAssign(Symbols syms) {
            Location loc = syms.put(name());
            nest = loc.nest;
            index = loc.index;
        }
        public Object eval(Environment env) {
            if (index == UNKNOWN)
                return env.get(name());
            else
                return ((EnvEx2)env).get(nest, index);
        }
        public void evalForAssign(Environment env, Object value) {
            if (index == UNKNOWN)
                env.put(name(), value);
            else
                ((EnvEx2)env).put(nest, index, value);
        }
    }
    @Reviser public static class BinaryEx2 extends BasicEvaluator.BinaryEx {
        public BinaryEx2(List<ASTree> c) { super(c); }
        public void lookup(Symbols syms) {
            ASTree left = left();
            if ("=".equals(operator())) {
                if (left instanceof Name) {
                    ((NameEx)left).lookupForAssign(syms);
                    ((ASTreeOptEx)right()).lookup(syms);
                    return;
                }
            }
            ((ASTreeOptEx)left).lookup(syms);
            ((ASTreeOptEx)right()).lookup(syms);
        }
        @Override
        protected Object computeAssign(Environment env, Object rvalue) {
            ASTree l = left();
            if (l instanceof Name) {
                ((NameEx)l).evalForAssign(env, rvalue);
                return rvalue;
            }
            else
                return super.computeAssign(env, rvalue);
        }
    }
}

11.4 修正eval方法并最终完成性能优化

代码清单11.4中的修改器将覆盖一些类的eval方法。如上所述,经过这些修改,eval方法将根据由lookup方法记录的保存位置,从环境中获取变量的值或对其进行更新

ParameterList类、Name类与BinaryExpr类的eval方法修改较为简单。Defstmnt类与Fun类的eval在修改后返回的将不再是Function类的对象,而是一个由代码清单11.5定义的OptFunction对象。OptFunction类是Function类的子类,OptFunction对象同样用于表示函数。两者的区别在于,OptFunction类将通过ArrayEnv对象来实现函数的执行环境

至此,所有修改都已完成。代码清单11.6与代码清单11.7分别是用于执行修改后的语言处理器的解释器,以及该解释器的启动程序

代码清单11.5 OptFunction.java

package chap11;
import stone.ast.BlockStmnt;
import stone.ast.ParameterList;
import chap6.Environment;
import chap7.Function;

public class OptFunction extends Function {
	protected int size;

	public OptFunction(ParameterList parameters, BlockStmnt body, Environment env, int memorySize) {
		super(parameters, body, env);
		size = memorySize;
	}

	@Override
	public Environment makeEnv() {
		return new ArrayEnv(size, env);
	}
}

代码清单11.6 EnvOptInterpreter.java

package chap11;
import chap6.BasicEvaluator;
import chap6.Environment;
import chap8.Natives;
import stone.BasicParser;
import stone.ClosureParser;
import stone.CodeDialog;
import stone.Lexer;
import stone.ParseException;
import stone.Token;
import stone.ast.ASTree;
import stone.ast.NullStmnt;

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

	public static void run(BasicParser bp, Environment env) throws ParseException {
		Lexer lexer = new Lexer(new CodeDialog());
		while (lexer.peek(0) != Token.EOF) {
			ASTree t = bp.parse(lexer);
			if (!(t instanceof NullStmnt)) {
				((EnvOptimizer.ASTreeOptEx) t).lookup(((EnvOptimizer.EnvEx2) env).symbols());
				Object r = ((BasicEvaluator.ASTreeEx) t).eval(env);
				System.out.println("=> " + r);
			}
		}
	}
}

代码清单11.7 EnvOptRunner.java

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

public class EnvOptRunner {
	public static void main(String[] args) throws Throwable {
		Loader.run(EnvOptInterpreter.class, args, EnvOptimizer.class, NativeEvaluator.class);
	}
}

接下来可以通过第八天代码清单8.6中的计算斐波那契的程序来比较优化前后的执行时间,最终结果计算速度至少提升了70%

© 著作权归作者所有

果汁分你一半
粉丝 0
博文 21
码字总数 22514
作品 0
泰安
私信 提问
加载中

评论(0)

演示Eclipse插件实现代码提示和补全

续上文重拾《 两周自制脚本语言 》- Eclipse插件实现语法高亮, 但仅达到了演示Eclipse本身功能的程度, 与石头语言并无直接联系. 源码库相同, 仍在同一插件. 演示效果如下: 悬浮窗显示的是当前...

中文编程
2019/05/11
0
0
重拾《 两周自制脚本语言 》- 中文关键字与原生函数

续前文重拾《 两周自制脚本语言 》- 支持中文标识符, 将当前的关键字改为中文. 基本是将语法分析器中的原本英文关键字改为中文. 如改while->每当 · program-in-chinese/stone@32c79b4: 下面...

中文编程
2019/05/09
0
0
转行了,现转让几本经典的java书籍,九成新

妈的,扣扣空间图片不能引用,有这12本 https://user.qzone.qq.com/164142021/infocenter(扣扣空间地址,可以进扣扣空间里的书籍相册) 《正则表达式必知必会》、《jQuery实战(第三版)》、...

cjb123
2018/01/17
6.1K
64
重拾《 两周自制脚本语言 》- Eclipse插件实现语法高亮

源码库: program-in-chinese/stone-editor-eclipse 参考: FAQ How do I write an editor for my own language? Deliver support for new languages in Eclipse IDE faster with Generic Edit......

中文编程
2019/05/10
0
0
《两周自制脚本语言》读后感

  粗略读完了本书,说实话比我想象的好。之前在学校就把基础部分(1-10章)过了一遍,回家之后比较懒,但终于看完了,代码也很好,可惜很多自己都没亲手敲。从消化程度来说,打算回学校之前...

戎码半生
2017/02/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【03】Python科学计算:Pandas

上一章中,我们讲了 Python 的一个重要的第三方库 NumPy,今天我来给你介绍 Python 的另一个工具 Pandas。 在数据分析工作中,Pandas 的使用频率是很高的,一方面是因为 Pandas 提供的基础数...

郑加威
17分钟前
49
0
java 类变量, 实例变量,局部变量的区别

Java语言支持的变量类型有: 类变量:独立于方法之外的变量,用 static 修饰。(类的静态成员变量) 实例变量:独立于方法之外的变量,不过没有 static 修饰。(类的成员变量) 局部变量:类...

fairy1674
19分钟前
36
0
mbti性格测试哪种类型是企业所喜欢的?

1、完全看岗位需求 不同的岗位对性格的匹配是不一样的。比如一个保洁,你要求他具有领导者性格,完全不合适呀,只需要他忠诚,做事细致,为人诚实,就是完美!而有些职位,比如部门经理,需要...

蛤蟆丸子
27分钟前
39
0
开源多商户商城系统(b2b2c),开源多店铺系统,开源多商户分销系统

对于单商户开源商城系统,国外市场很多,国内的大多数都是营销手段,搞一个开源版本,一个付费版本,然后,开源的成了烂尾工程,一致维护收费的版本,对于开源版本的单商户,可以看一下fecma...

FecShop
28分钟前
57
0
什么时候使用PHP常量“ PHP_EOL”?

什么时候使用PHP_EOL是个好主意? 我有时会在PHP的代码示例中看到这一点。 这样可以处理DOS / Mac / Unix终端问题吗? #1楼 如果要输出多行,可以使用error_log()。 我发现许多调试语句在W...

技术盛宴
28分钟前
37
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部