上周在公司临时做了个小分享，科普了下 CPU 高速缓存，以及 Java 程序员应该关注的问题，比如利用时空局部性原理，避免多核下的伪共享(False Sharing)等，因为是下午临时写的 PPT，可能有一些谬误，有兴趣的不妨看看 或者直接看链接： http://www.slideshare.net/killme2008/java-cpu-64198539 最近关注这个问题是因为在阅读《现代体系结构上的 Unix 系统——内核程序员的对称处理和缓存技术》一书，这是伞哥推荐的书，确实非常棒，澄清了我很多概念，推荐有兴趣的朋友阅读下。 Java 里伪共享的问题（False Sharing）已经被谈论了很多，甚至 Java8 都引入了 @Contended来帮助你做数据对齐，但是还有一个问题似乎没什么人谈过，那就是在获得自旋锁时减少对高速缓存行的争用，为了说明这个问题，我写了个例子： 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.

Clojure 的元编程是基于宏(Macro)来实现的。宏很强大，但是有些场合，我偶尔会怀念 Ruby 的 Method missing。 什么是 Method missing？ 什么是 Method missing？看一个简单的例子，Ruby 的 Hash 访问是通过 [] 运算符： > h={a: 1, b: 2} => {:a=>1, :b=>2} > h[:a] => 1 > h[:b] => 2 但是这种代码写多了也烦，我想用 dot 语法，也就是 h.a 来访问，可能更方便一点，这时候祭出 open class + method missing 就可以了： 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.

前言 原文地址：http://hypirion.com/musings/understanding-persistent-vector-pt-3 为什么翻译这系列博客？一直觉着翻译是学习的笨功夫，阅读一遍可能理解了概要，但是其实还是有很多细节遗漏了，翻译这个过程可以查缺补漏，更重要的是，我想重新写博客了 :D。 正文 关于 Clojure Persistent vectors 这个系列博客的 [Part 1](http://blog.fnil.net/blog/c9ce36719a8e37188fc51d27ca482504/ 翻译:深入理解 Clojure Persistent Vectors 实现 Part 1)和 [Part 2](http://blog.fnil.net/blog/3a2ce94a8eecdeffec608b6a6ed6f190/ 翻译：深入理解 Clojure Persistent Vectors 实现 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.

#前言 原文地址： 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 是否在这棵红黑树里： 我们从根节点 13 开始，和 22 对比下。因为 13 < 22，所以我们进入右分支。 新节点包含了 17，和 22 对比。因为 17 < 22，我们仍然进入右分支。 下一个我们进入的节点是 25。因为 25 > 22，我们进入左分支。 下一个节点是 22，因此我们知道 22 包含在这棵树里。 如果你想知道关于红黑树的更好的解释，我推荐你阅读 Julienne Walker 的 红黑树教程。

前言 原文地址：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）的时候，这显然行不通，因为我们想做的是去更新一个元素！我们必须拷贝整个数据结构，或者至少是部分。

闲来无事，尝试在本机编译下 JDK9 ，记录步骤如下。 准备 安装 Mercurial: brew install mercurial，熟悉下 hg 基本命令。 获取源码： hg clone http://hg.openjdk.java.net/jdk9/jdk9 jdk9 cd jdk9 bash ./get_source.sh 下载源码这个过程很漫长，压缩后都有 500 多M，建议找台国外的 VPS 获取源码压缩后再拷贝到本机。源码里的 README 和 README-builds.html 仔细阅读下，描述了 openjdk 整个编译过程和项目结构。 依赖软件安装： 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： brew install ccache 编译 编译就是 configure 和 make 两步，写个 build.

上周开始将线上服务往 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 编译器的优化更友好。

问题 Clojure 的数据结构都是不可变的，通常我们也很少在 clojure 里使用 Java 的可变数据结构；其次，Clojure 的 FP 风格也提倡你的函数应该是无副作用的，同样的参数传递给某个函数，他应该每次都返回同样的结果，没有额外的状态改变等。这就造成一个后果，状态或者数据都需要通过参数来传递，那么往往造成参数列表很长，我们可以用《Refactor Clojure(2)》和《Refactor Clojure(3)》提到的手法来改善长参数列表的函数的接口。 不过，我们还是遇到这样一个问题：在函数之间参数的不匹配，我们无法保证每个函数的参数列表维持一个一致的风格，特别是涉及到二方或者三方库的调用的时候，你在 A 函数里调用 B，在 A 内部对 A 输入的参数做了一些处理，添加、移除或者转换参数列表后传入给 B 函数，这里就就有所谓阻抗不匹配的问题。如果 A 要在内部对 B 发起多次调用，并在 B 的参数列表已经长的话，无可避免代码显得非常累赘。 例如这么一个场景： (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?

问题 在《Refactor Clojure(2)》我们介绍了如何使用 optional map 解决参数列表过长的问题，通过引入有意义的命令选项，一定程度上让用户使用起来更方便，不过它也有缺陷，比如 :or 没有自动加入 :as 结果的陷阱，以及用户可能将参数名称可能不小心拼写错误，特别是后者，在 Clojure 里是很容易发生的，这种错误也通常只能运行时才能发现。 本质上，我们的目的是生成一个有效的查询选项： {:skip skip :limit limit :query-keys query-keys :include include} 为了避免用户拼写错误，也许我们可以类似使用设计模式里的 Builder 模式，提供一系列更为明确的的 setter 函数来让用户构建一个有效的选项 map。 解决 不过我们不准备引入一个可变的 Java 对象，而是思考构建选项的过程是什么样？ 我们会从一个默认值 map 开始 {:skip 0 :limit 100}，然后用户加入 skip 的时候，往这个 map 添加一项： (assoc {:skip 0 :limit 100} :skip 100) 用户添加 limit 的时候，再加入一个选项： (assoc (assoc {:skip 0 :limit 100} :skip 100) :limit 10) 如果用户设定 query-keys，我们也一样，再次 assoc: (assoc (assoc (assoc {:skip 0 :limit 100} :skip 100) :limit 10) :query-keys ["a" "b" "c"]) 不过这个嵌套层次很难看了，按照《Refactor Clojure(1)》，我们可以用 thread 宏来简化：

这个系列准备提到的方式可能对大多数 clojure 老手来说都不新鲜，我的目的主要是自己归纳总结，并且同时重构自己的代码，其次是针对解决方式，引出一些讨论。因此每篇博客都分成三部分： 问题，说明这次要解决什么问题。 解决，提出初步的解决方案和最终本文要讨论的解决方案。 讨论，针对这个解决方案做进一步的扩展讨论。 权且抛砖引玉，欢迎有兴趣的朋友参与讨论。 问题 通常，我们开始写一个函数来完成某个功能，可能一开始只需要一两个参数就够了，接下来用户提出更多的定制化需求，不可避免，你可能需要传递更多参数进来。当一个方法的参数膨胀到 5 个以上，哪怕 clojure 有内置的 metadata 文档系统，这个函数也不可避免的难用起来。如果这是一个内部方法，也许还能承受，但是如果开放给用户，它的易用性就很成问题。 除了参数过多之外，很可能大多数参数用户是不需要的，内部应该提供一些默认值给这些参数，而不是每次都让用户传递。 以一个问题为例子，我们有这么一个查询接口，一开始他是这样的，你需要传递查询的表名和 where 条件： (defn query-objects [table where]) 接下来，发现用户需要分页功能，我们增加了 skip 和 limit: (defn query-objects [table where skip limit]) 过了没几分钟，用户提出希望能指定返回的对象的字段列表，ok，我们继续增加一个 keys 参数： (defn query-objects [table where query-keys skip limit]) 又过了几天，用户提出需要能排序和关联查询，好吧，我们需要加入排序字段和 include 字段： (defn query-objects [table where query-keys skip limit order include]) 这个过程如果再持续下去，这个方法的参数将无可避免地膨胀，它的问题包括： 用户需要知道参数名，也需要知道参数的顺序。 另外一个就是刚才提到的默认参数，可能大多数用户只是想查询第一个页，每页 100 条，那么 skip 和 limit 默认就是可以是 0 和 100等。这样的用户目前也不得不传递很多参数进来。 万一哪天你想修改这两个默认值，你需要去修改所有调用这个方法的地方，这完全违背了开闭原则（是的，哪怕是 FP，我们也希望遵循开闭原则。） 解决 一个简单的解决办法可能是使用重载参数，请注意** clojure 仅支持参数个数的重载，不支持参数类型重载**：