梦想风暴

这几天在写多线程程序。

有了一定的开发经验之后，写程序主要是查找API用法的过程。对于多线程来说，主要就是线程创建、同步互斥这些基本API的用法。互斥主要是用锁，我查了一下用Mutex做锁的方法，基本上是看一下用法就知道怎么用了。不过，写代码的时候，突然发现一个很别扭的地方，我不知道自己的锁该锁在哪里了。想来想去，原来是我找到那几篇教程的误导。

通常多线程教程中，给人的例子会给出一个线程的函数，然后在其中给出锁的用法，比如：
void threadFunc(void* param) {
    lock(&my_lock);
    ...
    unlock(&my_lock);
}

这段代码给人传递的信息是用锁来锁住这段代码，而事实上，锁的真正目标并非代码，而是数据。

想想那些来自操作系统课程的例子，比如取钱的例子。甭管怎么取，总之，银行不愿意亏，所以，它要保护的是你的账户。至于你究竟是通过ATM取款还是网上银行，它根本不关心。由此可见，锁的目标是内容，而非行为。

当然，锁住数据之后，一般会有一系列的操作，所以，这越发像保护代码了。但事实上，不是。在这点上，Java做得比较不错，它把锁绑在了对象上，也就是相当于跟到了数据上，synchronized的时候，锁住的就是数据。

在程序设计中，代码只是用不同的方式在处理数据，最为核心的还是数据。所以，别管戏法如何变，盯住数据，我们就可以在暴风骤雨中岿然不动了。

又一次谈到了数据，之前是《管窥OS——进程透明化》和《有状态的程序》。

YARV，Yet Another Ruby VM，又一个Ruby VM。

其实，我觉得它的名字算不上准确，因为原来Ruby算不上拥有VM。当然，按照作者的本意，这个名字不会长久的存在下去，因为项目如果成功，它就会成为Ruby的一部分，不成功的话，没人会记住它。事实上，它正一步步走向成功，因为现在它已经被合并到Ruby的主干代码中。

我不想苦苦等待YARV随着发行版来到我们身边，于是我选择提前体验YARV。到Ruby的网站上，下载Nightly Snaphot版本，我们就可以拥有最新的Ruby版本，当然，这样做的代价是这个版本可能不如正式的发布版那样稳定。事实上，我自己在编译的时候就遇到了一些小问题，幸好，简单修改一下便万事大吉。

关于如何编译Ruby，我已经在之前的blog上讨论过，这里就不再赘述。

下面是我用来体会YARV的一段代码：
def fibonacci(n)
    if n == 1 or n == 0
        n
    else
        fibonacci(n - 1) + fibonacci(n - 2)
    end
end

start_time = Time.new.to_f
puts start_time
puts fibonacci(30)
end_time = Time.now.to_f
puts start_time
puts end_time - start_time

首先，我用Ruby 1.8.5-p12运行这个版本，我最关心的运行时间大概是：
2.60199999809265

同样一段代码用加入YARV的Ruby来跑：
0.401999950408936

大幅度提高，看来YARV果然不负众望。如果希望继续体会YARV，现在Ruby的代码中还多了一个benchmark目录，里面全是一些耗时的运算。

既然YARV号称虚拟机，自然要有自己的指令集。JRuby正在开发的代码之中，已经开始提供对YARV指令的支持，Ola Bini在自己的blog上写过几篇与之相关的blog：
Executing YARV (in JRuby)
YARV tail call optimization in JRuby

在《管窥Ruby——类层次结构》中，我们已经见识过Ruby是如何实现包含一个模块的，不过，那里的侧重点不同，我们忽略了很多东西。

让我们回顾一下那段代码：
void
rb_include_module(klass, module)
    VALUE klass, module;
{
    VALUE p, c;
    int changed = 0;

    rb_frozen_class_p(klass);
    if (!OBJ_TAINTED(klass)) {
        rb_secure(4);
    }
  
    if (NIL_P(module)) return;
    if (klass == module) return;

    if (TYPE(module) != T_MODULE) {
        Check_Type(module, T_MODULE);
    }

    OBJ_INFECT(klass, module);
    c = klass;
    while (module) {
        int superclass_seen = Qfalse;

        if (RCLASS(klass)->m_tbl == RCLASS(module)->m_tbl)
            rb_raise(rb_eArgError, "cyclic include detected");
        /* ignore if the module included already in superclasses */
        for (p = RCLASS(klass)->super; p; p = RCLASS(p)->super) {
            switch (BUILTIN_TYPE(p)) {
                case T_ICLASS:
                    if (RCLASS(p)->m_tbl == RCLASS(module)->m_tbl) {
                        if (!superclass_seen) {
                            c = p; /* move insertion point */
                        }
                       goto skip;
                    }
                    break;
                case T_CLASS:
                    superclass_seen = Qtrue;
                    break;
            }
        }
        c = RCLASS(c)->super = include_class_new(module, RCLASS(c)->super);
        changed = 1;
    skip:
        module = RCLASS(module)->super;
    }
    if (changed) rb_clear_cache();
}
(class.c)

经过这段代码的处理，会生成一个包含类（include class），它会加到原来的体系中，就像下面这个样子：
    super class
           |
    include class
           |
        klass

包含类的iv_table和m_table就指向了模块的iv_table和m_table，通过这种方法，模块内的内容就可以在类中访问到了。

我们注意到，这段代码并不像这里说得那么简单，至少还有两个循环在那里。先来看看外面的while循环，简化之：
while (module) {
    ...
    module = RCLASS(module)->super;
}

这段代码告诉我们，我们是沿着模块的继承体系一路向上的……

慢着，模块的继承体系？模块也有继承吗？至少在Ruby的层次上不记得有这种说法。事实上，在Ruby的层次上确实没有，你不会去让一个模块继承另一个模块。那么模块的继承体系从何谈起呢？

我们知道，不仅是类可以包含模块，模块也可以包含模块。调用的当然也是这里的代码，由此可见，这个函数的第一个参数（klass）命名并不像看上那么完美。如果模块包含类模块，走这段代码，其结果就是这个样子：
     include module
             |
        module

所以，虽然在Ruby的层次上模块没有继承，但是在C的层次上，它也是可以有超类的。回到原来的路上，沿着模块的继承体系一路向上，就可以把一个模块所包含的所有模块都加入这个类的继承体系之中。

再来看看内部的for循环，简化之：
for (p = RCLASS(klass)->super; p; p = RCLASS(p)->super) {
    if (p已经包含过) {
        略过
    }
}

正如前面的注释所写，这段代码所要做的就是忽略已经包含的模块，这是一个经济实惠的选择。此外，这里还有一段代码：
if (RCLASS(p)->m_tbl == RCLASS(module)->m_tbl) {
    if (!superclass_seen) {
        c = p;    /* move insertion point */
    }
    ...
}

注释告诉我们，这里移动了插入点，这段代码保证了插入包含类之后的结构依然能够保证各包含类之间顺序的一致性。

谈及include_class_new时，我们曾经忽略了一段代码：
if (TYPE(module) == T_ICLASS) {
    RBASIC(klass)->klass = RBASIC(module)->klass;
}
else {
    RBASIC(klass)->klass = module;
}
(class.c)

这里，我们将新生成的包含类的klass字段设置为对应module，也就是建立起包含类与对应模块之间的联系。其实，这里设置klass多少有些偏离这个字段本身的含义，但对于包含类来说，把设置这个字段也算是“废物利用”，节省了一些空间。Module#ancestors方法（实现参见class.c的rb_mod_ancestors），正是利用了这个特点，去寻找一个模块的“祖先”。

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引出了一些很有意思的评论，沿着这些路走出去，还是会有一些不同的发现。

Java 6发布了，想必很多人还不没有来得及玩熟Java 5，很多人还在与1.4打交道，稳定归稳定，发展是不能停止的。Java 6并不像Java 5那样在语法上下了很大的功夫，更多的力气用在丰富API上。其中有一项是我比较感兴趣的，就是Compiler API，也就是JDK为我们提供的访问Java编译器的接口。下面便是一个使用Compiler API编译Java程序的例子。

import javax.tools.JavaCompiler;
import javax.tools.JavaFileObject;
import javax.tools.StandardJavaFileManager;
import javax.tools.ToolProvider;

public class Main {
    public static void main(String[] args) throws Exception {
        String sourceFile = "Hello.java";
        JavaCompiler compiler = ToolProvider.getSystemJavaCompiler();
        StandardJavaFileManager fileManager =
            compiler.getStandardFileManager(null, null, null);
        Iterable compilationUnits = fileManager.getJavaFileObjects(sourceFile);
        JavaCompiler.CompilationTask task =
            compiler.getTask(null, fileManager, null, null, null, compilationUnits);
        task.call();
        fileManager.close();
    }
}

作为一个最简单的例子，代码本身没什么值得太多解释的地方。它实际上完成的就是调用系统的Java编译器去实现完成编译的工作，因此，基本上等价于
javac Hello.java

之前，刚刚在blog中提到ASM，里面的代码生成工作是通过直接写bytecode完成的。现在有了Compiler API，可以考虑生成代码以Java源码的形式完成，然后，通过调用Compiler API对源码进行动态编译，这样，可以达到同直接写bytecode类似的作用。使用Compiler API，肯定不如直接生成bytecode来得高效，但对于不了解JVM指令的人来说也许是一种解决方案。

有了Compiler API，就可以在运行时直接编译Java程序，相当于把javac和java两个过程合二为一，这让Java代码拥有了类似于动态语言的特征。事实上，为了了解Compiler API，我确实做了一个这样的例子，不过，这样就要动不少手脚，不像这里展示的代码那样清晰简单。