• 2007-01-04

    管窥Ruby——方法缓存

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/dreamhead-logs/4203027.html

    Charles Oliver Nutter,JRuby的开发者,最近一直致力于解决JRuby臭名昭著的性能问题,在他的一篇blog中,他谈到了动态调用的问题:
    Making Dynamic Invocation Fast: An Idea?

    谈到方法调用的时候,我曾经解释过Ruby如何实现方法的动态调用,主要在于如何找到一个方法,也就是查找和缓存两步。为什么要缓存?主要是基于性能的考虑。

    即便同样采用了缓存技术,实现也是存在差别的。下面是JRuby中查找方法的实现:
    public ICallable searchMethod(String name) {
        for (RubyModule searchModule = this; searchModule != null; searchModule = searchModule.getSuperClass()) {
            synchronized(searchModule.getMethods()) {
                ICallable method = (ICallable) searchModule.getMethods().get(name);
                if (method != null) {
                    if (searchModule != this) {
                        addCachedMethod(name, method);
                    }

                    return method;
                }
            }
        }

        return UndefinedMethod.getInstance();
    }
    (RubyModule.java)

    这段代码基本上等同于之前介绍Ruby的对应实现,也就是说,会沿着类的继承体系一路向上,去寻找对应的方法。显然,JRuby的开发者也知道前面提及的性能问题,所以,当找到对应方法时,他们也做了一个缓存:
        addCachedMethod(name, method);

    这个方法的实现如下:
    private void addCachedMethod(String name, ICallable method) {
        if (!isIncluded()) {
            getMethods().put(name, method);
            getRuntime().getCacheMap().add(method, this);
        }
    }
    (RubyModule.java)

    这段代码告诉我们,所谓缓存,实际上就是放到了这个类(或模块)的方法表中,当再次调用方法时,就可以字节从这个类(或模块)本身找到这个方法,也就是一次调用,而不必再次沿着类的继承体系向上找寻了。

    初看上去,这个实现很不错,但对比于Ruby的实现便不难发现一些问题。首先,便是缓存的实现。来看看Ruby的缓存是如何实现的:
    #define CACHE_SIZE 0x800
    #define CACHE_MASK 0x7ff
    #define EXPR1(c,m) ((((c)>>3)^(m))&CACHE_MASK)

    struct cache_entry {  /* method hash table. */
        ID mid;   /* method's id */
        ID mid0;   /* method's original id */
        VALUE klass;  /* receiver's class */
        VALUE origin;  /* where method defined  */
        NODE *method;
        int noex;
    };

    static struct cache_entry cache[CACHE_SIZE];
    (eval.c)

    用法我们已经在《管窥Ruby——方法调用》中见识过了:
    ent = cache + EXPR1(klass, mid);

    这里,klass表示一个类,它是一个VALUE,也就是long。mid表示一个方法,对应于方法名,它是ID,实际上也是long。

    通过上面的代码,我们知道,cache实际上就是一个数组,查找缓存项的方法就是计算数组的索引,索引的计算方法已经摆在上面了,这样的计算显然比在Hash表中查找来得更加简单。对比来看,我们不难发现,这是JRuby性能还有提高空间的原因之一。

    再来看看原因之二。在JRuby中,用来作为查找的键值是什么?
    searchModule.getMethods().get(name);

    没错,字符串。这里查找的容器是Hash表。我们知道,Java的Hash表中计算键值需要用到hashCode这个方法:
    public int hashCode() {
        int h = hash;
        if (h == 0) {
            int off = offset;
            char val[] = value;
            int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }
    (String.java)

    这个hashCode方法同字符串自身的长度有关,字符串越长计算的代价也就越高。显然,JDK的开发者也意识到了这个问题,所以,他们在实现的时候也采用的缓存的技术,将结果单独保存起来。不过,通过平摊成本来看,它同直接采用long相比还是有一些差距的。

    这里提到的JRuby版本是0.9.2,Charles Oliver Nutter如此积极的在解决Ruby的性能问题,相信JRuby这个低效的实现很快就会被改写。

    回到Charles Oliver Nutter的那篇blog,他在其中提到了一种巨型矩阵的方法,也就是把类和方法名作为两个维度,而把实际的方法作为对应的元素值。显然,这种做法存在巨大的缺陷,会造成巨大的空间浪费。作者也提到了这一点,所以,他提出以稀疏矩阵来解决问题。

    我不敢苟同这个实现,至少这种方式不比Ruby的实现来得更好。更何况将类和方法作为矩阵的二维,也要增加额外的转换成本。而且维护这个二维矩阵也是一件劳心费力的事情,不要忘了,动态语言的动态特性,增删方法也是允许的。再者,即便采用稀疏矩阵,查找也不见得来得更快。

    其实,这种想法本质上与Ruby的实现异曲同工,只是对比之下,显得有些笨拙。在Ruby中,通过前面提到的计算索引的方法,巧妙的将两个维度合并为一个维度。Ruby的实现更多在体现缓存的思想,而按照Charles Oliver Nutter的设想,方法表就会失去其价值,因为在这个想法中,矩阵存储了所有的方法。

    这篇blog引出了一些很有意思的评论,沿着这些路走出去,还是会有一些不同的发现。

    分享到:

    历史上的今天:

    走近SICP 2005-01-04
    引用地址: