第11天 優(yōu)化變量讀寫(xiě)性能

以變量值的讀寫(xiě)為例，向讀者介紹基于這種理念的語(yǔ)言處理器性能優(yōu)化方式。

11.1 通過(guò)簡(jiǎn)單數(shù)組來(lái)實(shí)現(xiàn)環(huán)境

假如函數(shù)包含局部變量x與y，程序可以事先將x設(shè)為數(shù)組的第0個(gè)元素，將y設(shè)為第1個(gè)元素，以此類推吮螺。這樣一來(lái)，語(yǔ)言處理器引用變量時(shí)就無(wú)需計(jì)算哈希值帕翻。也就是說(shuō)鸠补，這是一個(gè)通過(guò)編號(hào)，而非名稱來(lái)查找變量值的環(huán)境

為了實(shí)現(xiàn)這種設(shè)計(jì)嘀掸，語(yǔ)言處理器需要在函數(shù)定義完成后遍歷對(duì)應(yīng)的抽象語(yǔ)法樹(shù)節(jié)點(diǎn)莫鸭，獲取該節(jié)點(diǎn)使用的所有函數(shù)參數(shù)與局部變量。遍歷之后程序?qū)⒌玫胶瘮?shù)中用到的參數(shù)與局部變量的數(shù)量横殴，于是確定了用于保存這些變量的數(shù)組的長(zhǎng)度

之后被因，語(yǔ)言處理器在實(shí)際調(diào)用函數(shù)卿拴，對(duì)變量的值進(jìn)行讀寫(xiě)操作時(shí)，將會(huì)直接引用數(shù)組中的元素梨与。變量引用無(wú)需再像之前那樣通過(guò)在哈希表中查找變量名的方式實(shí)現(xiàn)堕花。

確定變量的值在數(shù)組中的保存位置之后，這些信息將被記錄于抽象語(yǔ)法樹(shù)節(jié)點(diǎn)對(duì)象的字段中粥鞋。例如缘挽，程序中出現(xiàn)的變量名在抽象語(yǔ)法樹(shù)中以Name對(duì)象表示。這一Name對(duì)象將事先在字段中保存數(shù)組元素的下標(biāo)呻粹，這樣語(yǔ)言處理器在需要引用該變量時(shí)壕曼，就能知道應(yīng)該引用數(shù)組中的哪一個(gè)元素。Name對(duì)象的eval方法將通過(guò)該字段來(lái)引用數(shù)組元素等浊，獲得變量的值腮郊。

不必在程序執(zhí)行時(shí)通過(guò)變量名來(lái)查找變量。

如果希望在Name對(duì)象的字段中保存變量的引用筹燕，僅憑數(shù)組元素仍然不夠轧飞，還需要同時(shí)記錄與環(huán)境對(duì)應(yīng)的作用域。環(huán)境將以嵌套結(jié)構(gòu)實(shí)現(xiàn)閉包撒踪。為此过咬，Environment對(duì)象需要通過(guò)outer字段串連。此外制妄，Name對(duì)象還要記錄環(huán)境所處的層數(shù)掸绞，即從最內(nèi)層向外數(shù)起，當(dāng)前環(huán)境在這一連串Environment對(duì)象中的排序位置耕捞。該信息保存于Name對(duì)象的nest字段中衔掸。index字段則用于記錄變量的值在與nest字段指向的環(huán)境對(duì)應(yīng)的數(shù)組中，具體的保存位置砸脊。

圖11.1 x=2的抽象語(yǔ)法樹(shù)與環(huán)境

下圖是表示x=2的抽象語(yǔ)法樹(shù)。在該圖中纬霞，變量x的值保存于從最內(nèi)層數(shù)起的第2個(gè)環(huán)境對(duì)應(yīng)的數(shù)組中凌埂，因此Name對(duì)象的nest字段的值為1（如果是最內(nèi)層，則值為0）诗芜。由于變量x的值保存于該數(shù)組的第3個(gè)元素中瞳抓，因此index字段的值為2

file

代碼清單11.1 ArrayEnv.java

為了實(shí)現(xiàn)一個(gè)通過(guò)數(shù)組來(lái)保存變量值的環(huán)境，需要新定義一個(gè)ArrayEnv類伏恐。提供了與NestedEnv類幾乎相同的功能孩哑，實(shí)現(xiàn)了Environment接口。ArrayEnv類沒(méi)有使用哈希表翠桦，僅通過(guò)簡(jiǎn)單的數(shù)組實(shí)現(xiàn)了變量值的保存横蜒。

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 用于記錄全局變量的環(huán)境

ArrayEnv實(shí)現(xiàn)了用于記錄函數(shù)的參數(shù)與局部變量的環(huán)境胳蛮，但要記錄全局變量，我們還需要另外設(shè)計(jì)一個(gè)不同的類丛晌，使用該類的對(duì)象來(lái)實(shí)現(xiàn)用于記錄全局變量的環(huán)境仅炊。除了ArrayEnv類的功能，該類還需要隨時(shí)記錄變量的名稱與變量值的保存位置（也就是數(shù)組元素的下標(biāo)）之間的對(duì)應(yīng)關(guān)系澎蛛。它不僅能夠通過(guò)編號(hào)查找變量值抚垄，還能通過(guò)變量名找到與之相應(yīng)的變量值。

之前設(shè)計(jì)的Stone語(yǔ)言處理器可以在執(zhí)行程序的同時(shí)以對(duì)話的形式添加新的語(yǔ)句谋逻。用戶不必一次輸入全部程序呆馁，從頭至尾完整運(yùn)行。因此毁兆，為了讓之后添加的語(yǔ)句也能訪問(wèn)全局變量浙滤，我們必須始終記錄變量的名稱與該值保存位置的對(duì)應(yīng)關(guān)系。
語(yǔ)言處理器必須能夠通過(guò)變量名查找新添加語(yǔ)句中使用的變量值的保存位置荧恍。

另一方面瓷叫，局部變量?jī)H能在函數(shù)內(nèi)部引用。函數(shù)在定義完成時(shí)就能確定所有引用了局部變量之處送巡，且之后無(wú)法新增摹菠。這時(shí)，所有引用該變量的標(biāo)識(shí)符都會(huì)在各自的Name對(duì)象中記錄它的保存位置骗爆。由于語(yǔ)言處理器記錄了這些信息之后便無(wú)需再了解變量名與保存位置的對(duì)應(yīng)關(guān)系次氨，因此環(huán)境不必記錄變量的名稱。作為用于記錄局部變量的環(huán)境摘投，ArrayEnv對(duì)象已經(jīng)足夠煮寡。

代碼清單11.2中的ResizableArrayEnv類用于實(shí)現(xiàn)記錄全局變量的環(huán)境。它是ArrayEnv的子類犀呼。ArrayEnv對(duì)象只能保存固定數(shù)量的變量幸撕，ResizableArrayEnv對(duì)象則能保存任意數(shù)量的變量。

由于程序新增的語(yǔ)句可能會(huì)引入新的全局變量外臂，因此環(huán)境能夠保存的變量數(shù)量也必須能夠修改坐儿。ResizableArrayEnv類的對(duì)象含有names字段，它的值是一個(gè)Symbols對(duì)象宋光。Symbols對(duì)象是一張哈希表貌矿，用于記錄變量名與保存位置之間的對(duì)應(yīng)關(guān)系。代碼清單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 事先確認(rèn)變量值的存放位置

接下來(lái)為抽象語(yǔ)法樹(shù)中的類添加1ookup方法逛漫，它的作用是在函數(shù)定義時(shí)，查找函數(shù)用到的所有變量赘艳，并確定它們?cè)诃h(huán)境中的保存位置酌毡。該方法還將根據(jù)需要克握，在抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)對(duì)象中記錄這些保存位置。這樣語(yǔ)言處理器就能夠通過(guò)編號(hào)來(lái)查找保存在環(huán)境中的變量值

代碼清單11.4是為抽象語(yǔ)法樹(shù)的各個(gè)類添加lookup方法的修改器阔馋。這里僅對(duì)支持函數(shù)與閉包的Stone語(yǔ)言進(jìn)行性能優(yōu)化玛荞，不會(huì)涉及類的優(yōu)化

lookup方法如果在遍歷時(shí)發(fā)現(xiàn)了賦值表達(dá)式左側(cè)的變量名，就會(huì)查找通過(guò)參數(shù)接收的Symbols對(duì)象呕寝，判斷該變量名是否是第一次出現(xiàn)勋眯、尚未記錄。如果它是首次出現(xiàn)的變量名下梢，lookup方法將為它在環(huán)境中分配一個(gè)保存位置客蹋，在Symbols對(duì)象中記錄由該變量名與保存位置組成的名值對(duì)。除了賦值孽江，lookup方法還會(huì)在所有引用該變量的抽象語(yǔ)法樹(shù)節(jié)點(diǎn)中記錄變量值的保存位置

代碼清單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方法并最終完成性能優(yōu)化

代碼清單11.4中的修改器將覆蓋一些類的eval方法讶坯。如上所述，經(jīng)過(guò)這些修改岗屏，eval方法將根據(jù)由lookup方法記錄的保存位置辆琅，從環(huán)境中獲取變量的值或?qū)ζ溥M(jìn)行更新

ParameterList類、Name類與BinaryExpr類的eval方法修改較為簡(jiǎn)單这刷。Defstmnt類與Fun類的eval在修改后返回的將不再是Function類的對(duì)象婉烟，而是一個(gè)由代碼清單11.5定義的OptFunction對(duì)象。OptFunction類是Function類的子類暇屋，OptFunction對(duì)象同樣用于表示函數(shù)似袁。兩者的區(qū)別在于，OptFunction類將通過(guò)ArrayEnv對(duì)象來(lái)實(shí)現(xiàn)函數(shù)的執(zhí)行環(huán)境

至此咐刨，所有修改都已完成昙衅。代碼清單11.6與代碼清單11.7分別是用于執(zhí)行修改后的語(yǔ)言處理器的解釋器，以及該解釋器的啟動(dòng)程序

代碼清單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);
    }
}

接下來(lái)可以通過(guò)第八天代碼清單8.6中的計(jì)算斐波那契的程序來(lái)比較優(yōu)化前后的執(zhí)行時(shí)間定鸟，最終結(jié)果計(jì)算速度至少提升了70%