coding4fun 词频统计的优化思路

在这次的 coding4fun 活动中已经有很多同学分享了精彩的优化思路。我的思路其实大同小异，下面就挑一些于众不同的地方分享吧：

第一个不同点：

     在结构上选择了 简化版的 Trie 作为查找结构。简化版 Trie 的结构就是一颗 n 叉树, 每个节点对应一个状态。选择简化版 Trie 的原因是它的树状结构很容易用 CAS实现无锁并行，而相比 hashtable 没有 hash 冲突和 rehash的问题，相比复杂 Trie 结构如 Double-Array Trie 又比较容易实现：

       简化版 Trie 的一个重要参数就是树的宽度（W），对应每一层有多少个子节点，它等于存放子节点的数组大小。如果 W 越大，每个节点占据的内存就越大，节点利用率就越低。Trie 的每一层可以有不同的 W,  在极限外推下，如果 Trie 树的第一层 W非常大，保证绝大部分节点在第一层能放下，这个内存结构就与 hashtable 没有太大区别了：

       对 Trie 的调优集中在节点利用率上。如果节点利用率越高, 相同单词量的情况下数据结构占据的内存就越小（假设内存能完全放下的话）, CPU 随机访问这些节点的 cache hit 就会越高。—— 短时间内没法对树的查找复杂度 O(log n) 进行改造, 所以只能设法降低数据结构的内存占用（工作集）。

       Trie 树的查找是先把输入拆分成一系列 “状态” 序列, 然后根据这组状态序列在用 “树” 表示的状态迁移有向图中定位最终的节点。在简化的 Trie 结构中, “状态”的总数就决定了 Trie 树的宽度 W 。因此怎样把输入有效的拆分成 “状态” 或者说定位子节点 index 是同样重要的, 例如输入字符串 ‘ABCDEFG’：

1. 如果按原始 char 内码拆分, 生成的子节点 index 序列是： { 65, 66, 67, 68, 69, 70, 71 }，需要一棵 W = 256 的 Trie 树存放；
2. 如果只考虑字母, 忽略大小写压缩一下, 生成的子节点 index 序列是： { 0, 1, 2, 3, 4, 5, 6 }，只需要一棵 W = 26 的 Trie 树就能放下；
3. 如果在上一条的基础下, 按 Bit 逐位拆分每个字母，则产生的 index 序列是： { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0 }, 只需要 W = 2 的 Trie（它其实是棵二叉树） , 但是查找路径会增加很多。

BTW：其实这就是Bitwise Trie，不过第一 Java 下不能利用 CPU 指令优化位运算，第二 Bitwise Trie 更适合定长输入，所以测试性能并不太友好。

1. 更加灵活（复杂）的拆分办法，在上述按 Bit 拆分的基础上, 再合并相邻 Bit 增加宽度, 降低查找路径。例如合并 3 位： { 0, 4, 0, 4, 0, 3, 0, 2, 2, 1, 6, 0 }, 需要一个 W = 8 的 Trie 存储。这个方法可以让任意 W 值的 Trie 树接受任意的状态序列输入。

       为了方便对不同 W 和结构的 Trie 性能进行测试, 我定义了一组 Tries / Sequencer 接口, 由 Tries 接口维护 “状态” 数据结构，Sequencer 产生 “状态” 的 index 序列。 在全部的测试中我尝试了若干种不同的 Tries 和 Sequencer 实现，最后发现按照方式 2 来最大限度的压缩 index 序列的 AlphabetSequencer 与最简的 SimpleTries/ConcurrentTries（使用 CAS 并行插入节点） 实际性能最好。这一块就不多介绍了, 大家有兴趣可以阅读 Gitlab 的代码。

第二个不同点：

       与大部分同学利用内存映射文件一次性把文件读到内存不同，我在一开始就直接把文件平均分成若干个分区，让每个工作线程单独扫描一个分区进行分词，这样可以实现完全并行：

       因为平均分区这个办法太简单, 可能会出现尾部 “半个单词” 的问题, 漏掉分区结尾的单词。解决尾部半个单词的办法很简单，写成伪代码是这样的：

       If（不是从文件开头读取） {

              忽略分区的第一个单词；

       }

       读取和计算分区中的单词；

       If（没有读到文件末尾） {

              继续向后多读一个单词，直到单词结束；

       }

       具体的并发执行过程如下图。其中并发加载是最慢的，消耗一般在 3s以上，而并发排序一般是 6x-8x 毫秒：

        实际调优中发现, 尽管多个线程并发访问相同的数据结构,  但是因为单词总量不大（3w 多）, Trie 树的绝大部分节点都是在运行的最初阶段插入的, CAS 冲突消耗的时间很少（100-200ms 级别）, 主要的消耗还是在树查找与内存访问。