上周在公司临时做了个小分享，科普了下 CPU 高速缓存，以及 Java 程序员应该关注的问题，比如利用时空局部性原理，避免多核下的伪共享(False Sharing)等，因为是下午临时写的 PPT，可能有一些谬误，有兴趣的不妨看看

或者直接看链接： http://www.slideshare.net/killme2008/java-cpu-64198539

最近关注这个问题是因为在阅读《现代体系结构上的 Unix 系统——内核程序员的对称处理和缓存技术》一书，这是伞哥推荐的书，确实非常棒，澄清了我很多概念，推荐有兴趣的朋友阅读下。

Java 里伪共享的问题（False Sharing）已经被谈论了很多，甚至 Java8 都引入了 @Contended来帮助你做数据对齐，但是还有一个问题似乎没什么人谈过，那就是在获得自旋锁时减少对高速缓存行的争用，为了说明这个问题，我写了个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;

public class BusyLock {

  private int count;
  // 自旋锁状态
  private AtomicInteger state;

  private BusyLock() {
      this.count = 0;
      this.state = new AtomicInteger(0);
  }

  /**
  * 利用 CAS 实现自旋锁
  */
  private void lock() {
      while (!state.compareAndSet(0, 1))
          ;
  }

  /**
  * 解锁
  */
  private void unlock() {
      state.set(0);
  }

  /**
  * 递增 count，使用自旋锁保护 count
  */
  public void incr() {
      lock();
      count = count + 1;
      unlock();
  }

  /**
  * 测试，开启 50 个线程递增 count，每个线程循环 10 万次。
  * 
  * @param warnUp
  * @throws Exception
  */
  public static void runTests(boolean warnUp) throws Exception {
      int threads = 50;
      int n = 100000;
      BusyLock bl = new BusyLock();
      Thread[] ts = new Thread[threads];
      long start = System.nanoTime();
      CyclicBarrier barrier = new CyclicBarrier(threads + 1);
      for (int i = 0; i < threads; i++) {
          ts[i] = new Thread(new Runnable() {

              @Override
              public void run() {
                  try {
                      barrier.await();
                      for (int j = 0; j < n; j++)
                          bl.incr();
                      barrier.await();
                  } catch (Exception e) {

                  }
              }
          });
          ts[i].start();
      }
      barrier.await();
      barrier.await();
      for (Thread t : ts) {
          t.join();
      }
      long duration = (System.nanoTime() - start) / 1000000;
      if (!warnUp)
          System.out.println("count= " + bl.count + ",cost:" + duration
                  + "ms");

  }

  public static void main(String[] args) throws Exception {
      // 测试，先 warm up
      runTests(true);
      // 实际测试
      runTests(false);
  }

}

代码稍微注释了下，熟悉 Java 类库的都应该可以理解。为了演示这个问题，这里没有用 ReentrantLock，而是使用 AtomicInteger 来实现自旋锁保护 count 这个资源，incr 方法会递增 count，启动 50 个线程并发循环调用 incr，然后计算耗时。

我们关注的是 lock 方法的实现：

1
2
3
4

private void lock() {
  while (!state.compareAndSet(0, 1))
      ;
}

利用 compareAndSet 来尝试更新 state，1 表示锁定状态，0 表示空闲，每个线程都尝试去取得锁的所有权，如果失败，进入 while 忙等待。compare-and-set 都是利用 CPU 提供的原子指令(一般是 test_and_set)来实现。

这个实现没有问题，但是当考虑到多核状态下的高速缓存的时候，如果对于锁的争用非常激烈，那么会有很多的线程在 while 上的 compareAndSet 原子操作上等待，保存 state 的缓存行就会在多个 CPU 之间『颠簸』，导致了不必要的总线争用。

为了减少总线争用，我们可以改进下 lock:

1
2
3
4
5
6
7
8

private void lock() {
  while (!state.compareAndSet(0, 1))
      //对于未能取得锁所有权的线程，在内层循环上等待
      //因为获取了 state 一份共享的高速缓存副本，
      //不会再进一步产生总线通信量
      while (state.get() == 1)
          ;
}

通过增加一个内循环 while (state.get() == 1)，让没有获得锁的线程在 state 状态上等待，避免原子操作，可以减少总线争用。每个忙等待的 CPU 都将获得 state 状态的共享副本，以后的循环都将在共享副本上执行，不会再产生总线通信。

当占有锁的线程释放锁（原子地设置 state 为 0）的时候，这些共享的副本会失效（write-invalidate 策略，比如常见的 MESI 协议）或者被更新到最新状态（write-update 策略），这时候才会产生总线通信。

测试两个版本的 lock 方法，在我的机器上有比较明显的差异，没有内层循环的 lock 版本耗时在 6-8 秒，而增加了内层循环的 lock 耗时在 2.5 -5 秒。

Clojure 的元编程是基于宏(Macro)来实现的。宏很强大，但是有些场合，我偶尔会怀念 Ruby 的 Method missing。

什么是 Method missing？

什么是 Method missing？看一个简单的例子，Ruby 的 Hash 访问是通过 [] 运算符：

1
2
3
4
5
6
7
8

 > h={a: 1, b: 2}
 => {:a=>1, :b=>2}

 > h[:a]
 => 1

 > h[:b]
 => 2

但是这种代码写多了也烦，我想用 dot 语法，也就是 h.a 来访问，可能更方便一点，这时候祭出 open class + method missing 就可以了：

1
2
3
4
5
6
7
8

  class ::Hash

    def method_missing(name, *args)
      return self[name.to_sym] if key? name.to_sym
      super(name, *args)
    end

  end

我们给标准库的 Hash 类添加了 method_missing 方法，它会『兜底』所有 Hash 没有实现的方法，将方法名和参数传递给 method_missing，我们在上面的例子里将方法名转为 symbol，然后判断这个 symbol 在 hash 里是否存在，如果存在，返回它对应的值，否则调用原始的 super.method_missing（也就是报错）。

修改之后，我们可以这么获取 h 中对应的值了：

1
2
3
4
5

> h.a
 => 1

> h.b
 => 2

Method missing 体现的就是 Ruby 的动态性，在求值 h.a 的时候，Ruby 运行时发现 Hash 没有 a 这个方法，那么会转而去调用 method_missing(a) 。

它有什么用呢？除了上面这个简单的例子之外，举一个更常见的场景——远程调用的本地客户端 stub。

通常，在静态类型语言里，RPC 定义一些远程接口，客户端如果想要『无缝』地调用这些接口，需要通过一层代理层，来将本地调用转化成远程调用，由代理层来处理远程调用的细节，客户端的代码显得更干净和规整。代理层通常是通过 RPC 接口定义工具编译生成代码。无论是 gRPC，还是 thrift 之类，都是这么做的。

但是有了 method missing，这一层代理就不需要有一个编译的过程，完全可以动态地将请求转发给远程客户端，发起真正的远程调用并返回结果。

还是以 Ruby 里的 JSON RPC 的一个实现库 jimson 为例，服务端实现一个 sum 接口：

1
2
3
4
5
6
7
8
9
10
11
12

require 'jimson'

class MyHandler
  extend Jimson::Handler

  def sum(a,b)
    a + b
  end
end

server = Jimson::Server.new(MyHandler.new)
server.start

客户端调用：

1
2
3

require 'jimson'
client = Jimson::Client.new("http://www.example.com:8999")
result = client.sum(1,2)

client.sum ， client 实质上并没有 sum 方法，它通过 method_missing 将这个调用转化成一个 JSON RPC 的 method 调用，同时将方法名称 sum 和参数 1, 2 传递给了服务端处理，处理完成后返回结果给调用客户端。

Clojure 里怎么办？

前一段时间，我在尝试用 clojure 实现一个 JSON RPC 调用库的时候，就一直琢磨这个问题，我有一个方法：

1
2
3

(ns example)
(defn sum [a b]
  (+ a b))

现在我可以在别的地方直接 require 调用：

1
2

(require '[example :as e])
(e/sum 1 2) ; => 3  

现在假设 sum 定义在远端服务端，我在本地客户端还想用 (e/sum 1 2) 这样的方式调用，并且还能查看文档、参数列表等元信息，我能怎么办？

最终我采用的解决办法也不是 method missing，当时还没有深入思考这个特性在 clojure 里应该怎么去实现。而是这样的方式：

• 引入 defrpc 宏用来定义远程函数，包装 defn，同时导出一份函数的元信息(doc, arglists等)给服务端。
• 扩展 JSON RPC 协议，添加特别的 method —— __metadata，专门用于发布服务端提供的 RPC 接口的元信息列表。
• 实现了一个 require-remote 宏，它会调用 __metadata 远程接口获取服务端的接口元信息，然后动态生成代理的 namespace 和 function，并 require 到当前 namespace。

最终，服务端的代码变成：

1
2
3
4
5

(ns example)
(defrpc sum
   "sum some numbers."
   [a b]
   (+ a b))

客户端在初始化 RPC 客户端之后（设置连接信息之类），只要替换掉 require 为 require-remote 即可：

1
2

(require-remote '[example :as e])
(e/sum 1 2) ; => 3  

这样的改动之后，基本上我原来的那些代码几乎不用做多少修改，只是替换下 defn（换成 defrpc） 和 require （换成require-remote）就可以完美地在拆分运行。

为了解决元信息获取接口的远程依赖和接口兼容问题，避免在打包编译的阶段报错，RPC 客户端也引入了元信息的本地缓存。

这个实现如果稍微整理下代码也可以开源出来，不过现在真的太懒，没有精力做这样的事情了，思路大体如此，有兴趣的自己实现也不难。

Clojure 的 method missing 在哪里？

说了这么多，还是没有提到正文， Clojure method missing 在哪里呢？在上一节，我不得不引入一个元信息发布接口，然后在客户端去动态根据这些元信息生成一堆代理的 namespace 和 functions，看起来比很多静态语言高明了一点，但是其实只是将代理层的编译从静态变为了运行时动态生成罢了。

本质上的问题，客户端在调用远程一个接口的时候，它在本地确实是不存在的，Clojure 或者 Java 之类的解决方案仍然是动态或者静态地生成代理层，代理层转发调用给远程客户端，而 Ruby 的 method missing 则是在运行时委托给 method_missing 转发给远程客户端，后者明显更具有『动态性』，前者因为有了编译的过程，为了让编译通过，需要代理层的存在，而后者不需要。

那么 clojure 有没有办法来引入 method missing 呢？

我先做了一个尝试，基于宏来实现，请看这个 gist。

我们先在 missing-test 里定义了 method-missing 和 hello 方法：

1
2
3
4
5
6
7
8

(ns missing-test)

(defn method-missing [func args]
  (println "missing '" func "' with args:" args)
  [func args])

(defn hello [name]
  (str "hello," name))

然后在另一个 namespace，我们尝试调用它：

1
2
3
4
5
6

(ns missing-example
  (:require [missing-test :as t]))

(with-method-missing (the-ns 'missing-test)
  (println (t/hello "dennis"))
  (println (t/world "dennis")))

这将会输出：

1
2
3
4

hello,dennis
missing ' world ' with args: dennis
[world dennis]
nil

hello 方法在 missing-test 里定义了，它返回 hello,dennis，而 world 方法没有定义，所以会去调用 method-missing，先打印 missing ' world ' with args: dennis，然后返回函数名和参数组成的 vector。

关键代码是 with-method-missing：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(defmacro with-method-missing [ns & body]
  (let [ns (eval ns)]
    `(do
      ~@(clojure.walk/postwalk
         (fn [form]
           (if (and (list? form)
                    (this-ns? ns (first form))
                    (method-missing? ns (first form)))
             (list `apply (get (ns-publics ns)
                               'method-missing)
                   (vec (cons
                         (name (first form))
                         (next form))))
             form))
         body))))

这个宏做的事情很简单，遍历整个 body 结构，发现任何一个 (a/b p1 p2) 这样的 list，会尝试解析下 a/b 在对应的 namespace 是不是存在，如果不存在 b 方法并且定义了 method-missing，就转而调用 a/method-missing 方法，也就是将 body 里的所有类似 (a/b p1 p2) 转成了 (a/method-missing p1 p2) 的 form。完整的代码参见 gist。

这里仍然没有任何的动态性，with-method-missing 将在编译期间展开，不存在的方法将替换成存在的 method-missing，这一切都在编译期间就决定了，不会拖到运行时。

那么，到底能不能实现真正动态的 method missing，并且去掉蹩脚的 with-method-missing，答案是可以的，但是需要去修改 clojure 编译器。

我尝试写的一个 patch，非常简单，在 var 解析的过程里加上一个步骤即可。

打上这个 patch 后，编写 method missing 很容易了：

1
2
3
4

(ns missing-test)

;;定义 method missing，简单地返回参数
(defn -method-missing [ & args] args)

到另一个 namespace 调用：

1
2
3
4
5
6

(ns missing-example)
(require '[missing-test :as t])

(t/hello 3)  ;; => ("hello" 3)

(t/world (range 1 10))  ;; => ("world" (1 2 3 4 5 6 7 8 9))

hello 和 world 方法都在 missing-test 里没有定义，因此调用 -method-missing 方法，返回调用的方法名称和参数。

前言

原文地址：http://hypirion.com/musings/understanding-persistent-vector-pt-3

为什么翻译这系列博客？一直觉着翻译是学习的笨功夫，阅读一遍可能理解了概要，但是其实还是有很多细节遗漏了，翻译这个过程可以查缺补漏，更重要的是，我想重新写博客了 :D。

正文

关于 Clojure Persistent vectors 这个系列博客的 Part 1和 Part 2 应该可以让你对 persistent vector 的工作原理的有个大概的了解，但是，其实这里仍然有许多不同的方法可以消减（算法）的常数因子（的影响）。可能最容易理解的部分是尾部（tail），我们将在这篇博客里介绍。

尾部的基本原理

回想下 (conj [1 2 3 4] 5) 这个操作的可视化展示，没有任何尾部实现时：如果在最右叶子节点有空间，我们仅需要拷贝向下到达该叶子节点的路径，并将最后这个新元素插入到拷贝中。

有尾部的时候会有什么不同呢？让我们瞧下：

不再是在树里面保存最右叶子节点，取而代之，我们在 vector 的头部(header)就持有一个它的直接引用：这是上篇博客后加入 vector 头部的最后部分。指向最右叶子节点的引用称为尾部。

对于 conj 操作，我们以检测尾部有没有足够空间而告终。因为这里刚好是这种情况 —— 我们拷贝了尾部，并将新元素插入其中。请注意这是常量时间，不是近乎常量时间。所以，每次在尾部有空余空间的时候，我们 conj 新元素到 vector 的时候，我们都是在做常量时间的操作。

这使得批量操作变得特别快。如果你接连做大量的 conj 操作，结果是每个操作的耗时平均起来更少。对于一个分支因子是 2 的 vector， 1/2（50%） 的 conj 操作（平均起来）是常量时间。如果将分支因子替换成 32， 31/32 的所有 conj 操作都将实际上是常量时间。只有 3.1% 的操作是近乎常量时间，意味着我们得到一个相当显著的常数削减。对于连续的 disj 操作我们也得到同样的性能好处。

所以这看起来是非常吸引人的改进。但是我们如何实现它呢？

尾部偏移量（tail offset）

在我们了解如何实现实际操作之前，我们需要学习一个很容易理解的概念：一个 vector 的尾部偏移量。为了理解 vector 一些操作需要做的修改，我们需要了解这个概念。

尾部偏移量其实就是元素在一棵树里的总量（译者注：请注意，现在最右叶子节点不在树里了，而是在 vector 头部作为尾部存在，因此树里的元素是减少了）。在实践中，就是 tail_offset = vector.length - tail.length。就是这么一个公式，没有比这个公式更多的解释了。我们需要尾部偏移量的理由是，有的时候我们需要回去执行『老的』操作：查找或者修改元素要求我们知道它们是不是在树里，或者是否在尾部里。

举一个尾部偏移量的例子，回想下前文提到的 5 个和 6 个元素的 vector。5 个元素的 vector 在它的尾部里只有一个元素，所以他的尾部偏移量是 4（译者注：vector 长度 5 减去尾部长度 1，结果为 4，后文类似）。拥有 6 个元素的 vector 的尾部偏移量也是 4， 因为它的 尾部引用有 2 个元素。

更多尾部偏移量的例子请参考上图中的两个 vector。拥有 7 个元素的 vector 的尾部偏移量是 6，而有 10 个元素的 vector 的尾部偏移量是 8。

查找

有没有尾部引用，对于在 vector 中查找一个值的过程来说并没有太大的不同。从根本上有两种情况要考虑：

• 我们想要查找的值在尾部。
• 我们想要查找的值在树里面。

这里就是我们需要使用到尾部偏移量的地方。查找过程写成伪代码看起来是这样：

1
2
3
4
5

if lookup_index < tail_offset:
  # tree_lookup = old lookup technique
  return tree_lookup(lookup_index)
else:
  return tail[lookup_index - tail_offset]

因为我们知道尾部偏移量就是元素在树里的总量，我们仅仅需要检查待查找的元素是否比尾部偏移量小。如果是，我们就执行『老的』查找过程，否则，我们知道它在尾部。在那种情况下，我们把索引减去尾部偏移量（这就是我们称之为偏移量的原因），然后使用计算得来的新的索引位置到尾部里查找。

更新

跟查找的实现类似，更新也跟原来的更新实现非常相似。唯一的区别发生在你想更新的值就在尾部里面。再次有两种情况：一是你要更新的值在树里面，另一个就是你要更新的是尾部。

1
2
3
4
5
6
7
8

if update_index < tail_offset:
  # tree_update is the old update technique
  return tree_update(update_index, elt)
else:
  vector_copy = copy_head(this)
  vector_copy.tail = copy_tail(this.tail)
  vector_copy.tail[lookup_index - tail_offset] = elt
  return vector_copy

首先，我们看下更新的元素在树里面的情况。我们仍然以 Part 1 里的老例子为例，更新索引位置 5 的元素：

1
2

(def brown [0 1 2 3 4 5 6 7 8])
(def blue (assoc brown 5 'beef))

这可以得到下面这棵树：

正如 Part 1 所解释的那样，我们做了路径拷贝并替换叶子节点上的元素。但是呢，注意到它们共享了尾部：毕竟，它没有变动，因此为什么要费心去拷贝它呢？

第二种情形是我们要修改的元素在尾部。让我们重用前面的例子，但是将索引位置修改 8：

1
2

(def brown [0 1 2 3 4 5 6 7 8])
(def blue (assoc brown 8 'beef))

这次看到我们拷贝了 vector 的『头部』和尾部，然后在它上面执行了修改操作。因为我们对树没有做任何修改，我们就可以和没有修改之前的 vector 共享树的部分。这个操作的耗时就是常量的，不是近乎常量级的。

插入

查找和更新都很简单，但是如果我们查看下插入和删除呢？没错，结果是它们也同样不难。对于插入来说，我们再次有两种情形要考虑，但是这次有一点点不同：

• 在尾部有足够空间。
• 在尾部没有空间了。

第一种情况非常容易：拷贝下尾部，在它的末尾插入新元素。这篇博客的第一幅图刚好就展示了它是如何工作的。但是当尾部没有足够空间的时候我们应该怎么办？

原理和 Part 1 描述的插入过程很像，但是有一点小修改：不再是插入一个单一的值，替代地，我们插入一个叶子节点。回想下，尾部就是一个叶子节点，被 vector 的根节点直接指向。

在上面的示例里，褐色 vector 的尾部已经满了：你没法往尾部插入更多的元素了。一个 conj 操作将创建蓝色的 vector，在那里面我们了解到我们必须将尾部本身插入树中。按照 Part 1 的规则，我们将尾部放入树里面，然后创建一个新的尾部用来存放新元素。

实际上，插入本身不需要更多解释了，并不难理解和掌握它。但是当一个实际的 vector 实现做插入的时候，需要特别小心处理索引。幸运地是，实现过程中需要面对的最大困难是所谓大小差一的错误（off-by-one error，译者注：也就是数组索引位置处理不当，通常在边界的时候多处理或者少处理了一个元素）。

删除

当处理删除的时候，我们面临一个设计上的抉择：某些情况下，我们不得不把叶子节点向上移动作为尾部。但是什么时候应该这样做呢？我们应该在 vector 里保留空的尾部吗？并且只有在对一个尾部已经为空的 vector 执行出队操作的时候才去向上移动叶子节点吗？或者，我们总是保留一个非空的尾部在 vector 中？

结果证明至少有两个理由要求我们保证在所有情况下尾部为空^[1]：最显而易见的理由是你现在能够保证 peek 操作一定是常量时间的。另一个不那么明显的理由是随机查找，平均来说将更快：如果在尾部查找一个元素比在树里查找耗时更短，那么更好的是让尾部保持『满』的状态，而不是一个空的尾部。

因此，我们以 —— 你可能猜到了 —— 两种不同的情况处理来结束讨论：

• 在尾部，我们拥有多于一个的元素。
• 在尾部，我们只有一个元素。

正如我刚才提到的，不会有任何 vector 会在尾部没有元素（除了空的 vector 这种异常情况）。假设尾部至少有一个元素在完全没有问题的。

如果在尾部我们有多于一个的元素，我们只需要拷贝这个尾部，删除它的最后一个元素，然后返回新的 vector。上面的例子显示给我们只有尾部不同，正是我们预期的那样。

请记住如果我们对同一个 Persistent Vector 做两次出队操作，我们将创建两个尾部，尽管它们的内容是一样的：

如果我们在尾部只有一个元素，我们需要将树中的最右叶子节点『提升』为新的尾部，还要将它（译者注：最右叶子节点）从树上移除。这些步骤跟在没有尾部的 vector 执行查找和出队一个元素的操作相似，只是将查找和删除元素替换为查找和删除叶子节点。

最复杂的例子出现在你需要删除空的节点并干掉根节点，就像 Part1 描述的那样。但是，如果你按照 Part 1那里介绍的规则行事，并且将叶子节点当做『元素』，你会觉的还好处理。下面就是这么个例子，把最右叶子节点『提升』为根节点。

Next Up

这个系列的下一篇将解析 transient：我们为什么需要它们，以及它们的工作原理。最终这个系列博客的最后一篇博客将包含 ArrayList 和 Persistent Vector 的性能对比。

[1] 持有非空尾部的有没有什么不利的地方？从理论角度出发，空的 vector 将更多是一种边缘情况，因为它不符合这个规则（译者注：指尾部非空）。但是从实践角度出发，这没有关系。空的 vector 本来就是一种特殊情况，因此采用这个设计后，实现本身并不会更复杂。

前言

• 原文地址： http://hypirion.com/musings/understanding-persistent-vector-pt-2
• 上一篇： 翻译:深入理解 Clojure Persistent Vectors 实现 Part 1

正文

在前一篇关于 Clojure Persistent Vectors 的博客里（如果你还没有读过，请点击阅读），我们大致理解了 vector 里元素的插入、更新和出队操作是如何工作的。我们还没有真正了解到是如何定位到正确的元素，在这篇博客我将介绍查找元素是如何实现的。

为了理解我们是如何在树的节点里面选择正确的分支，我想最好是先给这些结构一个合适的名称，并解释为什么这样命名。通过一个数据结构的名称来解释分支选择似乎听起来很奇怪，但是如果考虑到这个名称可能描述了它的工作原理的话，这还是有意义的。

名称

Clojure persistent vector 数据结构的一个更正式的名称是 持久的按位分区的矢量前缀树(persistent bit-partitioned vector trie)^[1]。我在前篇博客介绍的其实是持久的按数字分区的前缀树(persistent digit-partitioned vector tries)是如何运行的，但是不用担心，一个按位分区前缀树只是一个按数字分区的前缀树的优化，对于上篇博客的内容来说，两者并没有区别。在本篇博客，会介绍一点两者在性能上的小区别。否则它们其实没有根本上的差异。

我猜测你可能并不了解上面段落提到的这些术语，所以我将在下文一一解释。

持久性

在上一篇博客，我使用了术语持久性（persistent）。我说我们想要数据结构是持久的，但是并没有真正解释到底持久性本身意味着什么。

一个称为持久的数据结构并不修改它自己本身：严格来讲，他们并不一定要在内部是不可变的，只是需要被（外界）认为是不可变的。无论何时你在一个持久的数据结构上执行了更新、插入或者删除操作，一个新的数据结构将返回给你。老的版本仍然是一致的，并且无论什么时候你给它一个输入，它总是返回同样的输出（译者注：也就是没有副作用，side effects）。

当我们谈论一个 完全 持久的数据结构的时候，这个数据结构的任何版本都是可以修改的，意思是作用在某个版本上的所有可能的操作，都可以作用在另一个版本上。在早期的『函数式数据结构』时代，更常见的方式是和数据结构一起『欺骗』，通过修改内部结构让老的版本随着时间逐渐『腐朽』，同时跟最新版本相比是越来越慢。虽然如此，Rich Hickey（译者注：Clojure 作者）决定让 Clojure 持久数据结构的所有版本都有一样的性能承诺，无论你正在使用的是数据结构的哪个版本。

矢量(Vector)

一个矢量就是一个一维的可增长的数组。例如 C++ 的 std::vector 或者 Java 的 java.util.ArrayList 就是可变矢量的实现。实际上也没有比这个更多的解释了。一个矢量前缀树是指一棵用来表示矢量的前缀树(trie)。它并不一定必须是持久的，但是在我们这里介绍的是持久的。

前缀树（Trie)

前缀树是特殊的一种树，我想最好先解释更多的常见的树来展示前缀树的实际不同之处。

在红黑树和其他类型的二叉树里，映射或者元素存在于内部的节点上。选择正确的分支是通过比较元素/关键字(key)和当前节点来确定的：如果元素比当前节点的元素小，那么我们选择左分支，如果更大，我们就走到右分支。叶子节点通常都是空指针或者 nil，不包含任何东西。

“Example red-black tree” by Cburnett, CC-BY-SA 3.0

上面图中的红黑树是从维基百科的文章里摘录过来的。我并不想详细介绍它是如何运作的的，但是我们选择一个小小的例子，看看我们是如何判断 22 是否在这棵红黑树里：

1. 我们从根节点 13 开始，和 22 对比下。因为 13 < 22，所以我们进入右分支。
2. 新节点包含了 17，和 22 对比。因为 17 < 22，我们仍然进入右分支。
3. 下一个我们进入的节点是 25。因为 25 > 22，我们进入左分支。
4. 下一个节点是 22，因此我们知道 22 包含在这棵树里。

如果你想知道关于红黑树的更好的解释，我推荐你阅读 Julienne Walker 的 红黑树教程。

从另一方面观察，一棵前缀树将它的所有的值都保存在它的叶子节点中^[2]。选择正确的分支是通过使用关键字的一部分来定位。因此，一棵前缀树可以有多于两个的分支，在我们这里，它最多拥有 32 个分支！

大致的一棵前缀树插图展示在上面图中。它展示的前缀树是一个 map：接收长度为 2 的字符串，当字符串在前缀树里存在的时候返回一个整数。ac 的值是 7，而 ba 的值是 8。前缀树是这么工作的：

对于字符串，我们把字符串拆成字符。然后使用第一个字符，找到表示该值的边(edge)，然后沿着边往下走。如果该值没有找到对应的边(edge)，我们就停止访问，表示它在前缀树里不存在。否则，我们继续使用第二个字符来查找边，不停下去直到没有剩余字符了。最终完成的时候，如果存在，我们就返回当前的值。

以 ac 字符串为例，我们按照下列步骤处理：

1. 把 ac 拆成成 [a, c] 的字符列表，并从前缀树的根节点开始。
2. 判断对于字符 a，节点上有没有一条边，如果存在，我们沿着这条边向下访问。
3. 判断对于字符 c，节点上有没有一条边，如果存在，我们同样沿着这条边向下访问。
4. 后面没有剩余的字符了，这就是意味着当前节点包含了值 7，因此我们返回 7。

Clojure 的 Persistent Vector 就是一棵前缀树，它把元素的索引位置(index)作为关键字(key)使用。但是，正如你所料到的那样，我们需要将索引整数按照某种方式拆分。为了拆分整数，我们要么使用数字分区的方式，或者它的更快版本——位分区。

数字分区（Digit partitioning）

数字分区的意思是说我们把关键字拆分成数字，作为填充前缀树的基础。例如，我们可以将关键字 9128 拆分成 [9, 1, 2, 8]，基于这个列表将元素放入前缀树中。如果前缀树的深度超过了这个数字列表的大小，我们可能还需要在列表前面填充一些 0。

我们也可以使用任何其他我们喜欢的基数，不仅仅是 10。这样一来，我们就需要将关键字转换成想要使用的基数，并使用转换后的数字。仍然以 9128 为例，9128 换算成基数为 7 的数字就是35420，接下来我们就要使用列表 [3, 5, 4, 2, 0] 来查找或者插入前缀树。

（译者注：图中的 9145 显示错误，其实是 9128。）

上面这棵前缀树（横向展开，不包含我们不会访问的边和节点）展示了我们如何遍历一棵数字分区的前缀树：我们挑选了最高位有效的数字，在这里是 3，然后进入那个指定的分支。接着以同样的方式使用第二高位有效的数字，一直到没有剩余的数字为止。当我们访问到最后分支的时候，和我们在一起的对象 —— 这里就是最后数组的的第一个对象（译者注：绿色的 0） —— 就是我们想要定位的对象。

如果你知道怎么找到数字，那么实现这样一种查找程序并不很难。下面是一个 Java 版本的实现，与查找无关的细节都被剥离掉了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class DigitTrie {
  public static final int RADIX = 7;

  // Array of objects. Can itself contain an array of objects.
  Object[] root;
  // The maximal size/length of a child node (1 if leaf node)
  int rDepth; // equivalent to RADIX ** (depth - 1)

  public Object lookup(int key) {
    Object[] node = this.root;

    // perform branching on internal nodes here
    for (int size = this.rDepth; size > 1; size /= RADIX) {
      node = (Object[]) node[(key / size) % RADIX];
      // If node may not exist, check if it is null here
    }

    // Last element is the value we want to lookup, return it.
    return node[key % RADIX];
  }
}

rDepth 的值表示根节点的一个子节点的最大大小：一个有 n 个数字组成的数字，将拥有 RADIX 的 n 次幂数量的可能值，而且我们必须能将它们毫无冲突地全部放入前缀树。

在 lookup 方法的 for 循环里，size 的值表示当前节点的一个子节点的可以拥有的最大大小。对于每个我们访问过的子节点，这个 size 大小被分支因子递减，分支因子即是数字前缀树的基数。

对结果做一次取模运算的原因是为了忽略掉高位有效数字 —— 那些我们在前面用于分支选择的数字。我们可以在每次分支选择进入子节点的时候从关键字里移除高位数字，但是在那种情况下，代码会变得稍微复杂一点^[3]。

位分区

数字分区的前缀树通常需要做大量的整数除法和取模运算。在每次分支选择的时候必须执行这些运算会带来不少的时间损耗。如果可能，我们当然更想要加快这一部分的运算。

因此，正如你所料，位分区前缀树是数字分区前缀树的一个子集。所有基于 2 的次幂（2, 4, 8, 16, 32 等）为基数的数字分区前缀树，都可以转成位分区前缀树。只要了解一些位运算的知识，我们就能移除这些耗时的算术运算。

从概念上讲，它的工作原理跟数字分区是一样的。尽管如此，我们原来把关键字拆分为数字，现在替换成拆分为预定义大小的位簇(bit chunk)。对于 32-路的分叉前缀树来说，每一部分都需要 5 位，对于 4-路的分叉前缀树来说，每一位簇需要 2 位。更一般的说法，我们需要的是和我们的指数大小一样的位数（译者注：举例来说，32 是 2 的 5 次幂，5 是指数，因此是 5 位）。

但是，这样做为什么更快呢？通过使用一些位运算的技巧，我们可以同时消除整数的除法和取模。如果 power 是 2 的 n 次幂，我们可以得到 x / power == x >>> n^[4] 和 x % power == x & (power - 1)。这两个公式其实是等价，跟整数的本质表示有关，也就是位组成的序列。

如果我们使用这个结果，并和前面的实现组合起来，我们将得到下列代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class BitTrie {
  public static final int BITS = 5,
                          WIDTH = 1 << BITS, // 2^5 = 32
                          MASK = WIDTH - 1; // 31, or 0x1f

  // Array of objects. Can itself contain an array of objects.
  Object[] root;
  // BITS times (the depth of this trie minus one).
  int shift;

  public Object lookup(int key) {
    Object[] node = this.root;

    // perform branching on internal nodes here
    for (int level = this.shift; level > 0; level -= BITS) {
      node = (Object[]) node[(key >>> level) & MASK];
      // If node may not exist, check if it is null here
    }

    // Last element is the value we want to lookup, return it.
    return node[key & MASK];
  }
}

这近似于 Clojure 语言的实现。看 Clojure 语言里的这些代码来检验这一点。唯一的区别是它做了边界检查以及末尾检查。

需要重点注意的是在这里我们不仅改变了运算符，而且还把 rDepth 值替换成了 shift 值。不再是存储完全的值，而只是存储指数部分。这使得我们可以对关键字使用位移运算，也就是 (key >>> level) 这一段。如果你相当熟悉位运算，其他部分也都很直白，容易理解。虽然这样，我们还是为不熟悉这些技巧的朋友举个例子。下面这个解释很详细，如果你觉的自己已经理解了，可以忽略。

为了图形化展示，假设我们只有 2 位分区（4-路分叉），而不是 5 位（32-路分叉）。如果我们想在一棵拥有 887 个元素的前缀树里查找某个值，我们有 shift 值等于 8：根节点的所有子节点每个最多可以包含 1 << 8 == 256 个元素。宽度(width)和掩码(mask)也都同时被改变：掩码 mask 是 3，而不是原来的 31。

假设我们想查找的关键字 626 对应的内容， 626 的二进制表示是 0000 0010 0111 0010。按照上面或者 Clojure 语言里编写的算法，一步一步介绍，我们会按照下列步骤处理：

• node 被设置为根节点，而 level 设置为 8。
• 因为 level 大于 0，我们开始进入 for 循环。
  • 我们先执行运算 key >>> level，在这里就是 636 >>> 8，这将消去前面（低位）的 8 位，剩下来是 0000 0010，也就是十进制的数字 2。
  • 接下来计算掩码 (key >>> level) & MASK == 2 & 3。掩码将前两位之外的位都设置为 0。这里的结果没有区别，结果仍然是 2。
  • 我们将当前节点 node 设置为它在位置 2 的子节点。
• 将 level 减去 2，设置为 6。
• 因为 level 还是大于 0，我们继续执行 for 循环。
  • 我们再次计算 key >>> level == 636 >>> 6。这将切掉后 6 位，剩下的是 0000 0010 01，也就是十进制的数字 9 。
  • 然后执行掩码运算： (key >>> level) & MASK == 9 & 3，换成二进制就是 1001 & 0011，这会消去最前头的 10，剩下的是 01，也就是十进制的数字 1。
  • 我们将当前节点 node 设置为它在位置 1 的子节点。
• 将 level 减去 2，也就是设置为 4。
• 因为 level 还是大于 0，我们继续执行 for 循环。
  • 636 >>> 2 留给我们的是 0010 0111 00。
  • 前面（低位）的两位是 0b00 == 0。
  • 我们将 node 设置为它的第一个子节点，也就是索引位置为 0 的子节点。
• 将 level 减去 2，也就是设置为 0。
• 因为 level （最终）不再大于 0，我们跳出了 for 循环。
• 我们对 key 使用 mask 做了一次掩码运算，返回二进制 10。因此，最后我们返回 node 节点在索引位置 2 的内容。

这几乎也是你在 Clojure vector 里的执行一次查找值的操作所经历的每一步机械指令，只是深度变成了 5。这样的 vector 将包含 1 到 3300 万元素。实际上，位移和掩码运算是现代 CPU 里最高效的运算之一，所以这让整个处理过程更加有效。从性能角度来讲，查找过程剩下的唯一『痛点』是高速缓存 miss。对于 Clojure 来说，这些都交由 JVM 自身很好地被处理了。

这些就是前缀树和 Clojure Vector 实现里如何查找元素的所有内容了。我猜这里最难理解的部分是位运算，其他任何部分都非常直白。你只是需要对前缀树如何工作有一个粗略的了解，这就够了！

如果你读完这篇博客，接下来的一篇 Part 3，将解释尾部引用 —— vector 的一个性能优化原理。

[1] 如果你想更学究一点，你可能想讨论这到底是不是 正式 的名称。Daniel Spiewak 在他的演讲 “Extreme Cleverness” 里将它们称为 “位映射矢量前缀树"（Bitmapped Vector Tries）。在 Clojure 社区里。他们更倾向于称之为 vector 或者 persistent vector。我们的目标并不是提供一个最广为人知的名称，而是一个名称可以在这系列博客里解释这个数据结构最重要的特性：即这是一个持久的前缀树，通过使用把元素的索引按位分区的方式来模拟一个 vector。

[2] 这里我撒了点小谎，只是为了让解释更简单一些：一些前缀树的变种可能会将它们的值实际存储在内部节点上，但是我们要讲解的这个不是这样。

[3] 尽管如此，它却可能更快！x86 上的div 指令（除法）会把商数和余数存在两个不同的寄存器里，因此我们能承受无论如何都要执行的除法。剩下的唯一工作就是 subl 指令，它可以比取模运算更快。如果你想实现一个非常快的按数字分区的前缀树，这里需要注意下。

但是这取决于你使用的基数。在特定情况下，一个除法运算可以分解成一些位运算和乘法运算的组合，一个取模运算也可以采用类似的方式优化。

[4] 小提示：在 Java 里，>>> 是一个逻辑位移（任何移掉的多出来位都会补为 0），而 >> 是一个算术运算（移掉的位都将和最高有效位拥有同样的值）。因为我们并没有使用有符号位，所以这里其实几乎没有区别，尽管我猜测 >>> 在某些机器架构上可能会比 >> 更快。

对于 C/C++/GO 的朋友们来说，>>> 等同于无符号类型的 >> 。

前言

• 原文地址：http://hypirion.com/musings/understanding-persistent-vector-pt-1

这系列博客对理解 clojure vector 实现很有帮助。尝试翻译下，许久没有做这样的工作，很可能有谬误的地方，欢迎指正。

正文

你可能或多或少听说过 Clojure 的 Perisistent Vectors。它是由 Clojure 的作者 Rich Hickey 发明的（受到 Phil Bagwell 论文 Ideal Hash Trees 的影响），能做到增、改、查和 subvec （截取片段）操作近乎 O(1) 的时间复杂度，并且每个修改操作都创建一个新的 vector，而不是修改原来的。

那么，它们是如何做到这一点的呢？我将尝试通过一系列博客来解析整个实现，每篇博客关注一部分。这将是一次深入细节的解析，包括围绕在实现层面上的一些不同的、看起来略显怪异的东西。

今天，我们将学习一些基础的知识，包括更新(update)、添加(append)和出队(pop)。Clojure 的 PersistentVector 使用这些基础操作作为核心，并且采用了一些优化性能的技巧，例如 transient vector 和 tail （vector 末尾）引用。我们将在后续的博客里解析这些技巧。

基本理念

可变（mutable）的 vector 或者 ArrayList 都只是数组，根据需求自动增长或者缩小。当你接受可变性(mutability)的时候，这没有问题，一切工作的很好，但是当你想要持久性（persistence）的时候，这将是个大问题。你的修改操作将变得非常缓慢，并且耗费大量的内存，因为每次修改你都不得不总是去拷贝整个数组。如果有什么办法能够在不损失查找、更新操作性能的前提下，避免数据的重复拷贝，一切将变得非常美好。而这就是 clojure persistent vector 所实现的，在平衡有序树（balanced, ordered trees)的基础上实现。

基本的思路就是实现一个类似二叉树的数据结构。唯一的区别是它的内部节点最多只有两个子节点，并且不包含元素自身。元素是有序的，也就是最左叶子节点的元素就是第一个元素，而最后一个元素就在最右叶子节点上。暂时地，我们要求所有的叶子节点都在同一个深度上（注释1）。作为例子，我们看看下面这棵树：它包括 0 -8 范围的整数，0 在第一个位置，8 在最后面。数字 9 表示 vector 的大小：

如果我们想添加一个新的元素到 vector 末尾，并且假设 vector 还是可变的(mutable)，我们将 9 插入到最右的叶子节点，如图：

但是问题在这里：如果我们希望 vector 是不可变的，也就是持久（persistent）的时候，这显然行不通，因为我们想做的是去更新一个元素！我们必须拷贝整个数据结构，或者至少是部分。

为了在保证持久性的前提下，最小化数据拷贝的代价，我们将做路径拷贝：我们把下达(down to)将要修改或者插入的值的路径上的所有节点拷贝，并在到达底部的时候使用新值替换原来的。下面是一个多次插入新元素的例子。一个 7 个元素的 vector 和一个 10 个元素的 vector 共享了结构：

粉色的节点在两个 vector 之间共享，同时棕色和蓝色是分隔的部分。其他没有显示在这里的 vector 可能也跟这些 vector 共享一些节点。

更新(Update)

最容易理解的『修改』操作可能是更新或者替换 vector 中的值，所以我们将先解释下更新是如何工作。在 Clojure 里，更新 vector 对应着 assoc ，或者 update-in/update。

为了更新一个元素，我们需要往下遍历树，去往元素所在的叶子节点，向下遍历的过程中，我们同时拷贝路径上的节点来保证持久性。当我们向下到达元素所在叶子节点的时候，我们拷贝该叶子节点并替换成我们想要的新值。最后返回一个新的 vector，带着被修改的路径。

看一个例子，假设我们要在一个 0 至 8 的 vector 上执行 assoc 操作：

1
2

(def brown [0 1 2 3 4 5 6 7 8])
(def blue (assoc brown 5 'beef))

blue (蓝色部分)这个 vector 包含了被拷贝的路径，内部结构展示如下:

这里假定了我们知道如何找到要更新的叶子节点，看起来非常容易（我们将在这个系列的后续部分介绍如何找到这条到达目标索引位置的路径）。

添加（Append）

添加（在末尾位置插入新元素）跟更新没有太大区别，除了一些我们为了保存新值而需要新增节点的边缘情况，本质上有三种情况：

1. 在最右叶子节点有空间可以放入新元素。
2. 在根节点有空余空间，但是最右叶子节点没有。
3. 在当前根节点没有足够空间。

我们将讨论这三种情况，它们的解决方案并不是很难掌握。

1: 跟 assoc 一样

无论何时，当最右叶子节点有空余位置的时候，插入一个新元素就跟执行 assoc 一样：拷贝向下遍历的路径，在新创建的叶子节点上，将值存入最右元素的右边。

以 (conj [0 1 2 3 4] 5) 为例子来说明，添加新元素之后的内部结构如下，蓝色是新的 vector，棕色是原有的：

仅此而已，没有什么神奇的，只是路径拷贝和发生在叶子节点的插入操作。

2: 需要的时候创建节点

同样，如果最右叶子节点没有空余的位置怎么办？庆幸地是，我们永远不会终结于一个错误的叶子节点的位置：我们总是能找到正确的路径遍历到正确的叶子节点。

相反，我们认识到，其实是我们想要到达的节点还不存在（指针是 null）。当节点还不存在的时候，我们可以创建一个并且将它作为要拷贝的节点。

在上面的图中，粉色的是新创建的节点，蓝色的节点是我们拷贝的节点。

3: 根节点溢出

最后一种情况是根节点溢出。这发生在当前根节点对应的这棵树已经容纳不了更多新元素的时候（译者注：也就是树『满』了）。

处理这种情况也不难理解：我们创建一个新的根节点，并将老的根节点设置为新节点的第一个元素。自此以后，我们新建节点的操作就跟前面的方法一样。下面例子中紫色的是新的根节点，新创建的节点是粉色的。

译者注：同时树的深度增加了一层。

解决问题是一回事，但是判断这一问题何时发生也同样重要，幸运的是这也很容易。当它是一棵二叉树的时候，（根节点溢出）发生在原有 vector 的大小是 2 的次幂的时候。更一般地讲，一个 n 叉树构成的 vector，当它的大小是 n 的次幂时， 根节点就会在新增元素的时候溢出。

出队（Pop）

出队（移除 vector 最后一个元素）也同样不难掌握。出队类似添加，也面临三种情况：

1. 最右叶子节点包含了多于一个的元素。
2. 最后叶子节点只包含了一个元素（出队后将为 0 个元素）。
3. 出队后，根节点只包含了一个元素。

本质上，他们只是前面添加部分所描述的三种情况的复原，都不是非常复杂。

1: dissoc

再次，我们面临的情况跟我们更新一个 vector 类似：我们拷贝了遍历到最右叶子节点的路径，删除这个节点上的最右元素。因为最右叶子节点包含了多于一个的元素，所以移除该节点的最右元素后至少还保留了一个元素，我们不需要再做任何额外的事情。

需要牢记在心的是，对一个 vector 做多次出队操作并不会得到『同一个』(identical) vector：他们是相等的(equal)，但是并不共享同一个根节点，例如：

1
2
3

(def brown [0 1 2 3 4 5])
(def blue (pop brown))
(def green (pop brown))

将会形成下面的内部结构：

2: 移除空节点

无论何时当你遇到叶子节点只有一个元素的时候，你需要一些不同的处理。不惜任何代价，我们都想要避免在树里面出现空节点。所以一旦发现一个空节点，我们替代地返回一个 null。它的父节点将会包含一个 null 指针，而不是一个指向空节点的指针。

在上图里，棕色的 vector 是原来的，蓝色的是出队后的新 vector。

不幸地是，跟移除叶子节点上的元素相比，这并不简单。可以看到，如果我们返回一个空指针给一个节点，该节点原来只包含了一个子节点，我们必须将子节点转成一个空指针返还：清空一个节点的结果将向上层传播。这里要处理正确可能要一点技巧，但是本质上它只是查看下新的子节点，如果它是 null，并且预计要放在索引为 0 的位置（也就是第一个位置），这种情况我们就返回 null。

如果用 clojure 实现，它看起来是一个递归函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

(defn node-pop [idx depth cur-node]
  (let [sub-idx (calculate-subindex idx depth)]
    (if (leaf-node? depth)
      (if (== sub-idx 0)
        nil
        (copy-and-remove cur-node sub-idx))
      ; not leaf node
      (let [child (node-pop idx (- depth 1)
                            (child-at cur-node sub-idx))]
        (if (nil? child)
          (if (== sub-idx 0)
            nil
            (copy-and-remove cur-node sub-idx))
          (copy-and-replace cur-node sub-idx child))))))

当这样的函数实现后，节点的删除操作都已经完全兼顾到了。看下面这张图的例子，出队后的 vector（蓝色）移除了两个节点：包含 c 元素的叶子节点和它的父节点。

3: 移除根节点。

到此为止我们已经覆盖了所有情况，除了最后一种情况。在当前实现中，如果我们从一个 9 个元素 vector 里执行一次出队操作将得到下面的结果：

没错，我们将得到一个只包含了指向一个子节点的根节点。但是这个根节点没有什么用处，因为当我们要查找或者更新节点的时候，我们总是绕过这个根节点向下进入子节点。如果添加新元素，那也会创建新的根节点，因此我们更想消除这个无用的根节点。

这里做的事情可能是本篇博客最容易理解的部分：当我们执行完出队操作后，检查下根节点是不是仅包含了一个子节点（比如检查第二个子节点是不是 null）。如果是这种情况，而且根节点不是一个叶子节点，那么我们可以简单地将这个根节点替换成它的唯一子节点。

正如期望的那样，结果就是一个新的 vector(蓝色的)，使用了原来 vector 的根节点的唯一子节点作为新的根节点：

译者注：树的深度也减少了一层。

O(1) != O(log n)

不少人很可能要说这个算法的时间复杂度怎么能说是 O(1)。实际上，以二叉树为例，它的复杂度应该是 O(log₂ n)，相对 O(1) 还是差的比较远。

尽管如此，没有人规定我们只能在每个节点保存两个子节点（通常称为分支因子）。Clojure 的 vector 每个节点包括 32 个子节点，这样做的结果是深度很小的浅树。实际上，如果 vector 的元素数量少于 10 亿个，整棵树的深度最多 6 层(log₃₂ 1000000000)。8 层深度的树可以包含 350 亿的元素，这种时候，我认为内存消耗是更严重的问题了。

为了实际说明这种区别我们看下这个例子：这里是一个包含了 14 个元素的四叉树，只有 2 层深度。如果你向上滚动鼠标看下前文包含了 13 和 12 个元素的两棵二叉树，他们都已经是 4 层深度了，比四叉树的深度多了一倍。

极浅树的后果是，我们倾向于将 Clojure vector 修改和查找操作认为近似（effectively）于常数时间，尽管理论上它们是O(log₃₂ n)的复杂度，了解大 O 记法的朋友应该知道这等价于 O(log n)，但是从营销角度，人们更喜欢加上常数因子。

继续阅读

希望本篇博客能让你更好地理解 Clojure Vector 是如何工作的，以及在更新、添加和出队这些操作背后隐含的理念，同时非正式地描述这些操作是如何做到高效的。插入和出队的更进一步的优化是可以实现的，在我写完 vector 的更多『关键』部分后，我们再来探讨这些优化。尤其是理解 tail 引用， transent vector 和 subvec 是如何工作的更有意义，在我们讨论微小实现细节之前。

系列博客的第二篇将更详细地关注分支(branching)，以及如何查找元素。

[1] 你可以认为这是对路径选择的简化，虽然它同时包括了由于 JVM 自适应优化带来的对 JVM 性能的影响。我们将在后面更深入地探讨这一点。

闲来无事，尝试在本机编译下 JDK9 ，记录步骤如下。

准备

• 安装 Mercurial: brew install mercurial，熟悉下 hg 基本命令。
• 获取源码：

1
2
3

hg clone http://hg.openjdk.java.net/jdk9/jdk9 jdk9
cd jdk9
bash ./get_source.sh

下载源码这个过程很漫长，压缩后都有 500 多M，建议找台国外的 VPS 获取源码压缩后再拷贝到本机。源码里的 README 和 README-builds.html 仔细阅读下，描述了 openjdk 整个编译过程和项目结构。

• 依赖软件安装：

1
2
3

GNU make >= 3.81
JDK 8
XCode 7.3

官方推荐是 Xcode 6.3，否则会有一些不兼容问题，不过因为 JDK9 分支本来就是在开发中，我后面简单在编译阶段先简单地将所有编译告警信息忽略。

后面编译的时候，发现还需要依赖 freetype，可以单独安装，也可以简单地安装 X11 支持。由于水果从 10.5 开始移除了 X11 的支持，为了继续运行 X11 程序，Apple搞了一个开源项目 XQuartz 来继续提供 X11 的支持。从官方网站 https://www.xquartz.org/ 下载 dmg，安装即可。

为了加快后续可能重复编译速度，支持下 --enable-ccache，安装下 ccache：

1

brew install ccache

编译

编译就是 configure 和 make 两步，写个 build.sh：

1
2
3
4
5

#!/bin/bash
bash ./configure --with-freetype-include=/usr/X11/include/freetype2 --with-freetype-lib=/usr/X11/lib
  \ --enable-ccache --disable-warnings-as-errors
make clean
make all

XCode 7.3 会遇到比较多的兼容问题，很多告警会被当成错误退出，因此先禁止掉 -Werror 选项， configure 的时候加上 --disable-warnings-as-errors。

整个编译过程在我的机器上挺快的，刷几个新闻就结束了。前面折腾这些编译告警的时候比较烦，索性先全部禁止了。

运行

进入 build/macosx-x86_64-normal-server-release/images/jdk 就可以看到一个标准的 JDK 结构：

1
2
3
4

$bin/java -version
openjdk version "9-internal"
OpenJDK Runtime Environment (build 9-internal+0-2016-05-08-160141.dennis.jdk9)
OpenJDK 64-Bit Server VM (build 9-internal+0-2016-05-08-160141.dennis.jdk9, mixed mode)

上周开始将线上服务往 clojure 1.8 迁移，原来是还是使用 1.6，升级过程没有太多问题，除了一些依赖库冲突之外，基本没有遇到困难。本来想尝试 clojure 1.8 引入的 direct-linking 技术，可惜我们的代码使用了不少 redefine function 的特性，加上使用了 direct-linking 后不能使用 nREPL 做 hot fix，不得不放弃这一特性。

Direct-linking 简单来说是省略了函数调用中的 var lookup 的过程，直接在函数的调用点上使用 JVM 的 invokestatic 指令调用该函数的静态方法 invokeStatic。

我们知道 clojure 里的每个函数都是一个对象，这个对象的类继承 clojure.lang.AFn，实现了 IFn 接口，其中有一系列 invoke 的实例方法。 在 clojure 1.8 后，生成的函数字节码引入了一个 invokeStatic 的静态方法，来包装原来实现的 invoke 方法， 而原来的实例方法 invoke 将调用委托给新的静态方法 invokeStatic。在使用了 direct-linking 后，如果你调用某个函数，将直接会调用这个函数对应的类的静态方法 invokeStatic，类似 Java 代码 MyFunctionXXXX.invokeStatic(...args) 的效果。由于是静态链接了类，如果你重新定义了 MyFunction，生成一个新类 MyFunctionYYY，调用者无法感知到新的类，还是会去调用老的类 MyFunctionXXXX 的静态方法 invokeStatic。这就是 direct-linking 带来的限制。启用了 Direct-Linking 后，由于没有 var lookup 这个 clojure runtime 过程存在，全部的调用都是 JVM 的 invokestatic 指令，理论上对 JIT 编译器的优化更友好。

最后，如果函数声明为 ^:dynamic，是不会被静态链接的，这个很容易理解。除了原有 ^:dynamic 之外，还引入了 ^:redef 的新元信息，如果声明为 ^:redef，就表示这个函数可能会被重新定义，那么也不会被静态链接。

从一个简单的 benchmark 看，静态链接可以带来比较明显的性能提升，初步测试在 3%-7% 左右，并且因为减少了每个函数类的静态初始化代码（主要是初始化要调用的函数的 var），变相地可以提升 clojure 程序的启动速度和缩减字节码大小。

上周 5 在公司做了个分享，有兴趣的看看：《Clojure 1.8 Direct-Linking What/Why/How》

问题

Clojure 的数据结构都是不可变的，通常我们也很少在 clojure 里使用 Java 的可变数据结构；其次，Clojure 的 FP 风格也提倡你的函数应该是无副作用的，同样的参数传递给某个函数，他应该每次都返回同样的结果，没有额外的状态改变等。这就造成一个后果，状态或者数据都需要通过参数来传递，那么往往造成参数列表很长，我们可以用《Refactor Clojure(2)》和《Refactor Clojure(3)》提到的手法来改善长参数列表的函数的接口。

不过，我们还是遇到这样一个问题：在函数之间参数的不匹配，我们无法保证每个函数的参数列表维持一个一致的风格，特别是涉及到二方或者三方库的调用的时候，你在 A 函数里调用 B，在 A 内部对 A 输入的参数做了一些处理，添加、移除或者转换参数列表后传入给 B 函数，这里就就有所谓阻抗不匹配的问题。如果 A 要在内部对 B 发起多次调用，并在 B 的参数列表已经长的话，无可避免代码显得非常累赘。

例如这么一个场景：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

(defn query-objects [app table where opts]
  (let [conn (db/get-connection app)]
    (if (cache-table? app table)
      (db/with-table-cache
        (db/with-connection conn
          (db/query :table tabl
                    :where where
                    :offset (:skip opts)
                    :limit (:limit opts))))
      (db/with-connection conn
        (db/query :table tabl
                  :where where
                  :offset (:skip opts)
                  :limit (:limit opts))))))

query-objects 会调用 db 库的函数来做查询，我们配置了某些应用启用查询缓存，通过 cache-table? 这个判断来决定是否启用查询缓存，如果启用，那么需要将 db/query 的执行放在 db/with-table-cache 的上下文里执行。其次， db 库使用 offset 选项来指代我们提供给外部用户的 skip，因此，我们不得不在这里做一次参数的转换：

1
2

:offset (:skip opts)
:limit (:limit opts)

可以看到下面这个调用在代码里出现了两次：

1
2
3
4
5

(db/with-connection conn
        (db/query :table tabl
                  :where where
                  :offset (:skip opts)
                  :limit (:limit opts)))

如果未来我们进一步支持其他功能，例如指定某个应用只允许查询某张表权限控制之类，需要引入更多的分支判断（if else 的消除是另一个重构话题），那么上面这段代码可能将出现在 query-objects 的更多地方。

解决

我们可以先做一个事情，将 db/query 的参数提取出来成一个 local var，类似 conn:

1
2
3
4
5
6
7
8
9
10
11
12

(defn query-objects [app table where opts]
  (let [conn (db/get-connection app)
        new-opts [:table tabl
                 :where where
                 :offset (:skip opts)
                     :limit (:limit opts)]]
    (if (cache-table? app table)
      (db/with-table-cache
        (db/with-connection conn
          (apply db/query conn new-opts)))
      (db/with-connection conn
        (apply db/query conn new-opts)))))

因为 db/query 接收的是可选参数，我们不得不将 new-opts 变成一个 vector，并且使用 apply 来调用 db/query。

不谈 apply 性能上的微小损耗，下面这样的代码出现两次仍然是累赘的：

1
2

(db/with-connection conn
  (apply db/query conn new-opts))

其实我们可以将这个调用抽取成一个闭包来使用，形如：

1
2
3
4
5
6
7
8
9
10
11
12

(defn query-objects [app table where opts]
  (let [do-query (fn []
                   (db/with-conn (db/get-connection app)
                     (db/query conn
                              :table tabl
                               :where where
                               :offset (:skip opts)
                               :limit (:limit opts))))]
    (if (cache-table? app table)
      (db/with-table-cache
        (do-query))
      (do-query))))

我们定义了一个局部函数 do-query，它是一个闭包，它在内部调用了 db/with-connection 和 db/query 做真正的查询工作，并且 close over 了 query-objects 传入的参数并做了转换，真正执行查询在的逻辑变得更清晰:

1
2
3
4

(if (cache-table? app table)
      (db/with-table-cache
        (do-query))
    (do-query))

一方面是嵌套层次的减少，一方面我们也尽量将抽象层次保持在一个层级之上。

do-query 本身对 db 库的调用也消除了 apply 和重复代码，考察未来的扩展的几种情况：

• 如果未来我们添加更多分支，也只需要调用这个局部闭包函数来执行真正的查询操作，
• 如果某个特殊分支需要给 db 库传入额外的参数，我们可以扩展 do-query 加入额外的可选参数提供给特殊分支调用，
• 最后，如果 do-query 的逻辑进一步扩展，我们可以很方便的将这个函数提取到 query-objects 之外，成为一个独立的调用方法。

讨论

这个手法的步骤如下：

• 找出重复的函数调用。
• 将该调用放入一个局部函数内。
• 修改所有重复调用地方，替代以局部函数调用。

这个手法，其实跟 Java 里的 Extract Class + Extract method + Move method 的重构类似，当你在使用 eclipse 的时候， refactor 菜单就提供了 Extract class 的功能，你可以选中一段代码，然后点击 Extract class，eclipse 会找出这段代码里使用的变量，尝试帮你创建一个类，你还可以选择是作为内部类还是顶级类存在。接下来，你可以使用 extract method 将重复的调用提取成单独方法，然后使用 move method 将该方法移动到第一步提取出来的类，这样一来，我们就将重复的代码调用封装到一个单独的类里面，如果这是一个内部非静态类，你还可以在内部类获得外部类的实例变量，类似闭包，所以有人说内部类是 OO 的闭包。

问题

在《Refactor Clojure(2)》我们介绍了如何使用 optional map 解决参数列表过长的问题，通过引入有意义的命令选项，一定程度上让用户使用起来更方便，不过它也有缺陷，比如 :or 没有自动加入 :as 结果的陷阱，以及用户可能将参数名称可能不小心拼写错误，特别是后者，在 Clojure 里是很容易发生的，这种错误也通常只能运行时才能发现。

本质上，我们的目的是生成一个有效的查询选项：

1

{:skip skip :limit limit :query-keys query-keys :include include}

为了避免用户拼写错误，也许我们可以类似使用设计模式里的 Builder 模式，提供一系列更为明确的的 setter 函数来让用户构建一个有效的选项 map。

解决

不过我们不准备引入一个可变的 Java 对象，而是思考构建选项的过程是什么样？

我们会从一个默认值 map 开始 {:skip 0 :limit 100}，然后用户加入 skip 的时候，往这个 map 添加一项：

1

(assoc {:skip 0 :limit 100} :skip 100)

用户添加 limit 的时候，再加入一个选项：

1

(assoc (assoc {:skip 0 :limit 100} :skip 100) :limit 10)

如果用户设定 query-keys，我们也一样，再次 assoc:

1

(assoc (assoc (assoc {:skip 0 :limit 100} :skip 100) :limit 10) :query-keys ["a" "b" "c"])

不过这个嵌套层次很难看了，按照《Refactor Clojure(1)》，我们可以用 thread 宏来简化：

1
2
3
4

(-> {:skip 0 :limit 100}
    (assoc :skip 100)
    (assoc :limit 10)
    (assoc :include-keys ["a" "b" "c"]))

最终生成我们要的选项 map:

1

{:include-keys ["a" "b" "c"], :limit 10, :skip 100}

如果我们将这个过程中的每个步骤封装层一个小函数提供给用户，用户就不会再遇到写错参数名字的事情，如果函数名字写错，Clojure 编译器将立即报错。

第一步，我们编写一个 query-options 函数来返回一个默认选项：

1

(defn query-options [] {:skip 0 :limit 100})

加入 skip， 就写一个 skip 函数：

1

(defn skip [m skip] (assoc m :skip skip))

注意，skip 接收参数两个参数，一个是当前的选项 map，一个是 skip 值。

limit,query-keys 和 include 也类似：

1
2
3

(defn limit [m limit] (assoc m :limit limit))
(defn query-keys [m query-keys] (assoc m :query-keys query-keys))
(defn include [m include] (assoc m :include include))

那么用户就可以这么使用：

1
2
3
4

(-> (query-options)
    (limit 10)
    (query-keys ["a" "b" "c"])
    (include "OtherTable"))

这样就可以生成：

1

{:include "OtherTable", :query-keys ["a" "b" "c"], :limit 10, :skip 0}

我们的目的达到了。 原来的 query-objects 转而使用一个真正的 map 来接收参数：

1
2

(defn query-objects [table where options]
  ......)

用户使用变成这样：

1
2
3
4

(query-objects "TestTable" {:a 1} (-> (query-options)
                                      (limit 10)
                                      (query-keys ["a" "b" "c"])
                                      (include "OtherTable")))

更进一步，其实我们可以将 table 和 where 参数也作为选项，加入两个函数：

1
2

(defn table [m table] (assoc m :table table))
(defn where [m where] (assoc m :where where))

我们先简单实现 query-objects 来返回选项：

1

(defn query-objects [opts] opts)

那么用户的使用可以更进一步简化为：

1
2
3
4
5
6
7

(-> (query-options)
    (table "TestTable")
    (where {:a 1})
    (limit 10)
    (query-keys ["a" "b" "c"])
    (include "OtherTable")
    (query-objects))

清晰明确并且有编译器检查，我们的问题解决了。

讨论

由于 clojure 里强调不可变数据，因此传统的 builder 模式需要将 builder object 转成参数来传递，通过将参数 keyword 转成小函数的方式，我们来保证用户的调用参数是合法有效的，同时使用 thread 宏来『串起』构建整个过程。这一系列小函数，我愿意称之为 builder function。

更进一步，我们其实可以包装 thread 宏，提供一更符合习惯用语的 select 来替代：

1
2
3
4

(defmacro select [ & body]
  `(-> (query-options)
       ~@body
       (query-objects)))

使用方式更进一步简化为：

1
2
3
4
5

(select (table "TestTable")
  (where {:a 1})
  (limit 10)
  (query-keys ["a" "b" "c"])
  (include "OtherTable"))

其实呢，这就是 sqlkorma 的方式，哈哈。不过这里其实我们也用到了一个重构手法：使用宏来构建调用模板，减少重复代码并提供 DSL。这将是后面将要介绍的。

这个系列准备提到的方式可能对大多数 clojure 老手来说都不新鲜，我的目的主要是自己归纳总结，并且同时重构自己的代码，其次是针对解决方式，引出一些讨论。因此每篇博客都分成三部分：

• 问题，说明这次要解决什么问题。
• 解决，提出初步的解决方案和最终本文要讨论的解决方案。
• 讨论，针对这个解决方案做进一步的扩展讨论。

权且抛砖引玉，欢迎有兴趣的朋友参与讨论。

问题

通常，我们开始写一个函数来完成某个功能，可能一开始只需要一两个参数就够了，接下来用户提出更多的定制化需求，不可避免，你可能需要传递更多参数进来。当一个方法的参数膨胀到 5 个以上，哪怕 clojure 有内置的 metadata 文档系统，这个函数也不可避免的难用起来。如果这是一个内部方法，也许还能承受，但是如果开放给用户，它的易用性就很成问题。

除了参数过多之外，很可能大多数参数用户是不需要的，内部应该提供一些默认值给这些参数，而不是每次都让用户传递。

以一个问题为例子，我们有这么一个查询接口，一开始他是这样的，你需要传递查询的表名和 where 条件：

1

(defn query-objects [table where])

接下来，发现用户需要分页功能，我们增加了 skip 和 limit:

1

(defn query-objects [table where skip limit])

过了没几分钟，用户提出希望能指定返回的对象的字段列表，ok，我们继续增加一个 keys 参数：

1

(defn query-objects [table where query-keys skip limit])

又过了几天，用户提出需要能排序和关联查询，好吧，我们需要加入排序字段和 include 字段：

1

(defn query-objects [table where query-keys skip limit order include])

这个过程如果再持续下去，这个方法的参数将无可避免地膨胀，它的问题包括：

• 用户需要知道参数名，也需要知道参数的顺序。
• 另外一个就是刚才提到的默认参数，可能大多数用户只是想查询第一个页，每页 100 条，那么 skip 和 limit 默认就是可以是 0 和 100等。这样的用户目前也不得不传递很多参数进来。
• 万一哪天你想修改这两个默认值，你需要去修改所有调用这个方法的地方，这完全违背了开闭原则（是的，哪怕是 FP，我们也希望遵循开闭原则。）

解决

一个简单的解决办法可能是使用重载参数，请注意 clojure 仅支持参数个数的重载，不支持参数类型重载：

1
2
3
4
5
6
7

(defn query-objects
 ([table where query-keys]
    (query-objects table where query-keys 0 100))
  ([table where query-keys skip limit]
    (query-objects table where query-keys skip limit))
  ([table where query-keys skip limit order include]
  ......))

这样，老用户仍然可以使用 (query-objects table where) 来简单查询，其他用户也可以选择对应的参数版本来调用，skip 和 limit 我们也给了一个默认值来调用，一切看起来挺 ok。

不过，如果一个用户希望是查询表的时候排序某个字段，然后不想设定 skip 和 limit，他仍然不得不调用最多参数的版本：

1

(query-objects "TestTable" {:a 1} 0 100 "createdAt" nil)

问题仍然没有解决，用户仍然很痛苦。

在《重构》这本书里，遇到这种情况给出的解决方案就是将参数包装成对象—— parameter object，如果参数很多， parameter object 还可以使用 builder 模式来构造。

在 clojure 里，我们会用 map 来包装这些参数，利用强大的 destructring，我们还能为参数提供默认值：

1
2

(defn query-objects [table where & {:keys [query-keys skip limit order include]}]
  ......)

这里的 & 表示后面的参数是可选的参数，{:keys [query-keys skip limit order include]} 表示我们预计可选参数是偶数个，可以组合成一个 map，并且 key 都是 keyword 类型（Keyword 就是类似 Ruby 的 symbol，符号），我们要取出其中的 query-keys skip limit order include 这些参数。

这样一来，用户可以选择自己传入什么参数：

1
2
3

(query-objects "TestTable" {:a 1})
(query-objects "TestTable" {:a 1} :skip 0 :limit 10)
(query-objects "TestTable" {:a 1} :skip 0 :limit 10 :query-keys ["key1" "key2"])

不过这里我们没有为 skip 和 limit 设置默认值，这可以通过 :or 来提供：

1
2
3

(defn query-objects [table where & {:keys [query-keys skip limit order include]
                                    :or {skip 0 limit 100}}]
  ......)

通过 :or {skip 0 limit 10} 我们为这两个参数提供了默认值。

destructring 是在编译器做的展开，同时支持在 let 和 loop 上，因为 defn、 fn 等展开后内部用到了 let，因此可以直接对参数使用 destructring。关于 map destructring 更多请参考 Map binding destructuring-Map%20binding%20destructuring)。

如果我们还想对整个参数 map 做一个引用 var，可以使用 :as:

1
2
3
4

(defn query-objects [table where & {:keys [query-keys skip limit order include]
                                    :or {skip 0 limit 100}
                                    :as options}]
  ......)

在函数体内， options 将指代整个参数 map 对象。但是，请注意 options 将不包括默认值，如果参数没有提供，它在 options 里也不会出现，这可能是一个陷阱。

1
2
3
4
5
6
7

(defn query-objects [table where & {:keys [query-keys skip limit order include]
                                    :or {skip 0 limit 100}
                                    :as options}]
  [skip limit options])

(query-objects  "TestTable" {:a 1})
#=> [0 10 nil]

讨论

可以看到 optional map 比较好的解决了参数过多的问题，通过为参数提供更有意义的命名(keyword)的方式，也避免用户需要明确记忆参数顺序的问题。

但是这种方式也存在缺陷，用户很容易写错参数名称，比如用户不小心这样调用：

1

(query-objects "TestTable" {:a 1} :sklp 100 :limit 10)

不小心将 skip 写成了 sklp，导致实际 skip 限定根本没有生效。这种问题，我们可以利用 clojure 内置的契约编程范式来解决，为函数加入 :pre 约束：

1
2
3

(defn query-objects [table where & {:keys [query-keys skip limit order include]]
  {:pre [(every? #{:query-keys :skip :limit :order :include} (keys options))]}
  ......)

我们使用 :pre 元信息加入强制约束谓词 (every? #{:query-keys :skip :limit :order :include} (keys options))，要求 options 出现的参数名称只能在 :query-keys :skip :limit :order :include 范围内，如果传入其他参数，将抛出断言异常：

1
2

(query-objects  "TestTable" {:a 1} :sklp 3)
#AssertionError Assert failed: (every? #{:query-keys :limit :include :order :skip} (keys options))  user/query-objects

不过这里参数名称重复了两次，一次在参数列表，一次在断言，理论上我们可以通过某种方式来消除，这是另一篇博客要讲的了。