雾雨魔法店

什么是维稳算法？ 维稳算法(Order Maintenance)是儒家思想君君臣臣的集大成者 - 这个算法使我们可以拿取任意两个事物，然后进行一个全序比较。 换言之，Order Maintenance可以看成一个链表，但是链表的所有元素直接可以快速比较前后。 也就是说，OM带有以下三个api： Head(): OM，取得链表头 Create(before:OM):OM，在before后插入一个节点 <=(lhs: OM, rhs: OM): bool，判断lhs是否在rhs的前面 OM的实现不是这篇文章的重点，就放在Order Maintenance - Google Slide这里了。 最近工作中发现了动态LCA（给予一棵树，处理树上的修改穿插着LCA查询）可以用OM解决。 另外碎碎念：Order Maintenance在Incremental Computing，Persistent Data Structure，跟String Algorithm上面都有应用，已经属于我走到那跟到那的变态跟踪狂了，下头算法！必须告它性骚扰！ 一般来说，这个问题可以用link cut tree解决，两者复杂度一样，但是思路跟工具都不一样。特别是用到了维稳算法！维稳算法解动态LCA也有各种各样的extension，比如魔改一下可以用来增量维护binding in lambda calculus。 具体操作如下： 我们可以给树的每个节点一个OM区间，并且用preorder traversal进出时间维护区间开闭。 具体操作是，给一颗新的树，我们可以维护一个OM timer。此timer在traversal递归进/出的时候会各进行一次自增，并且用自增前的两个值来初始化OM区间。这样，所有OM值都是独一无二的，并且树的区间包含子树的区间。同时，无直系亲属关系的两节点区间不相交。 新加入的叶子节点的区间可以用兄或（如果兄不存在）父的区间右端点连续插入两个值初始化。 我们维护一个装着区间的平衡二叉树。区间的序是左端点的序，而BST每一节点储存"该BST子树的最大右端点"。 这时候，找寻多个节点的LCA，成为了‘找寻最大的（左端点最右），包含所有节点区间的区间’。 这可以分两步完成： 0：去除所有不够左的左端点。由于是暂时的，我们不需维护平衡性，只需维护子树最大右端点，所以是O(log(n)) 1：在所有右端点足够右的子树里，寻找最右的左端点。 具体操作是： 当右子树子树最大右端点足够大的时候，递归进去。 否则，如果当下节点右端点足够大，返回。 否则，左子树子树最大右端点足够大，递归进去。 这是log(n)，跟link cut tree大O一样（但我认为更好懂也更优雅！） 另外顺带一提：Edward Kmett对这个问题的函数式特化版做了一个改进，达到了O(log(height))，见 On-line Lowest Common Ancestor

我们在上一篇文章中，描述了一个通用的优化技术： 找到时间差，把数据分成已知跟未知，并且用代码表示后者。 但是，这种做法有两个问题： 0 - 你需要费时费力去整这个东东，而且不是所有时候都能刚刚好复用代码。 1 - 如果我们预先不知道应该怎么区分呢？甚至，如果这是动态的呢？假设我们先接受一半的数据，等一会，然后接受另一半，那我们如何用上述的技巧？难不成把所有可能的分法都预先写一遍？ 所以，我们希望把上述技术，staging，自动化掉，使得程序员不再需要去关心之。 我们应该怎么做呢? 我们先从最基本的开始，先决定要操作的语言吧： type expr = | Var of string | Int of int | Add of (expr * expr) | Mult of (expr * expr) 这个语言，简单到了极点，只剩下+跟*两个操作了。别担心，我们会一步步扩展这个语言。 module ENV = Map.Make(String) let rec eval (e : int ENV.t) : expr -> int = function | Var v -> ENV.find v e | Int i -> i | Add (x, y) -> eval e x + eval e y | Mult (x, y) -> eval e x * eval e y 这是一个标准的definitional interpreter实现，中规中矩，并没任何出彩的地方。...

我们先从一个很简单的算法，快速幂，开始看起吧： let rec quick_mod x y m = if y = 0 then 1 else if y mod 2 = 1 then (x * (quick_mod x (y - 1) m) mod m) else quick_mod ((x * x) mod m) (y / 2) m let example_0 = quick_mod 10 1000 3 显而易见，10的n次方除3都会余1： utop # example_0;; - : int = 1 这个算法试图在y很大的时候，算(x^y) mod m。 很明显，这个算法只会进行log y次’*然后mod’的操作 - 我们把这个操作定义为⊕吧。 我们去深入思考一下 - 为什么本来要进行y次⊕，现在，我们只需要进行log y次⊕？...

有趣的CS已经很久没动了。有外因跟内因。 外因是一直在忙，忙着准备OOPSLA的talk，忙着给talk，OOPSLA过后忙着做下一个project，就慢慢把这个忘了 内因是因为知识消耗得差不多了 - 有趣有用而且没基础本科生又能听懂的接近PL的内容。。。实在不怎么多 但是最近要给一些关于Partial Evaluation的talk，所以就随便写点吧。

假如我们有一段某种编程语言的 stack-based 字节码： const1 ; 将常量 1 压入栈顶 const3 add const3 mult halt 在一个经典的 C 编写的解释器中，我们可能会有一个用类似 switch 的东西实现的循环，来解释执行这段计算 (3 + 1) * 3 的字节码。 enum { OP_CONST1, OP_CONST2, OP_CONST3, OP_ADD, OP_MULT, OP_HALT, }; void interpret(uint8_t insn[], uint32_t stack[]) { int pc = 0; uint32_t *st = stack; next: switch (insn[pc++]) { case OP_CONST1: *st++ = 1; goto next; case OP_CONST2: *st++ = 2; goto next; case OP_CONST3: *st++ = 3; goto next; case OP_ADD: st[-2] = st[-1] + st[-2]; st--; goto next; case OP_MULT: st[-2] = st[-1] * st[-2]; st--; goto next; case OP_HALT: return; } } 有很多原因导致这段代码性能不佳：...

别急！ 别急！ 我们先别急着切入正文，而是先看看一道算法题： 圆角骑士魔理沙：数组多次取第X大元素 大家在评论区可以看到，这道题有一定的难度：不少人给出了错误，或者超时的答案。 尽管最高赞给出的答案的确是正确的，其实有一个简单很多的做法： 对N生成二叉搜索树，然后用M索引之。 等下，这不是O(n log n)的吗？ 所以才说别急！我们想一想，当M < N的时候，这个二叉树，并不是所有节点，都会被索引。 那，我们为什么要去把不会被用的二叉树部分构建出来捏？ 但是，我们怎么知道‘树的那一部分会被用上’？ 答案是，我们可以同时交叉构建树跟索引树的过程 - 默认情况下，树是没构建的。当我们索引没被构建过的树，我们会构建这里的最小一部分，然后保存下结果，再进行构建。 class LazyBST: def __init__(self, arr): self.constructed = False self.arr = arr self.size = len(arr) def idx(self, index): if not self.constructed: self.constructed = True self.head = self.arr[0] self.left = LazyBST([x for x in self.arr[1:] if x <= self.head]) self.right = LazyBST([x for x in self.arr[1:] if x > self.head]) if index < self....

今天想说一篇比较著名的paper：scalability! but at what cost? 这篇paper说的很简单： 以前，大家benchmark分布式框架(比如spark)比的是scalability，就是说看看1024个机器的spark比1个机器的spark快多少。但是，大家并没有比一个框架具体是多快！ 比如说，你可以想象我们给spark加入一些负优化，导致spark在一切任务一切机器配置上都要双倍时间。这时候，scalability是一样的！甚至，我们给计算加入负优化，而不动数据传输，这时候scalability甚至会变好！ 很明显，这是个发癫的metric。paper提出了另一个metric，COST，就是：我一台机器实现的代码，你们要开多少机器性能才追得上？ 有的时候，是100台机器！ 这paper的内容，其实到这就完结了。很明显，paper最重要的点是：谓，审稿人，别发电了，赶紧用一个正经点的metric。但很明显，改了metric以后这点就不需要再看了。 但我依旧认为这篇paper很有意义。 更具体的说，我们可以想象这样一个故事： 你是一个普通的Java程序员。有一天，你的程序跑得不够快，被PM要求加快速度。 这时候，你想：我应该上多线程！于是你看了看Java标准库的多线程怎么弄，怎么加锁，然后弄了弄，程序多线程以后快了点。 过了会，需求增长了，程序性能不够快了，但是你已经开了尽可能多的线程。这时候，你想：我用更多机器就好了！于是就弄上了spark，然后，请了些运维，弄了些机器连在一起。以后，当你计算力跟不上的时候，加机器就好了。 随着机器数量的增长，运维管得越来越麻烦，然后，你听说了一个叫做kubernetes的东东，可以自动跑你的计算，就不需要运维了。你弄了弄，花了不少时间弄各种配置。。。 但其实，是不是有另外一条路可以走？ 在最初，当你程序出现性能问题的时候，你可以看看如何进行算法或者实现上面的优化。但是你用了多线程。这时候，你要面对race condition，死锁，bottleneck，contention等等正确性上面或者性能上面的问题。 然后，你遇上了这些性能问题，认为可以上分布式解决，这时候要给出数据传输的开销，还要思考集群的拓扑架构，然后机子出问题了还要retry。 处理这些问题太麻烦，于是你用上了spark根k8s之类的。 这时候你看看，本来你遇上了一个性能问题，你选择使用一种新方法解决这个性能问题。但是，这个新方法需要很多心思才能优化好。你没花这些心思，于是依旧有性能问题。你于是继续找更新的方法去‘解决’之，etc。。 这时候，最后的方案，真的比认真优化单核性能简单吗？

最近都在参加Splash/OOPSLA，就暂停了有趣的CS系列。 再过几天就回盐湖城了，今天也有点空，于是就写一写一些感想。 这某种意义上是我的第0个conference - 我以前参加过一次PLDI，但那是本科，也没给报告，也参加过一次ICLR，但那是virtual，而且给了报告，poster没啥人听，就相当于傻站了一个小时 我觉得最大感想，就是累 - 从离开盐湖城，到大概几天后回到盐湖城，我参加了几乎整整两周的会议+traveling。 travel的时候在飞机上或者在机场或者在车上，难以休息，到了会议早上要听报告听到黄昏，途中还穿插着社交 - 而社交很多时候都是一对一或者多对一交流工作跟idea，往往比单纯听报告还劳累。 不得不感叹，体力还是很重要的，而由于我太宅，体力好差，甚至怀疑比不上我认识的一个50多岁的教授，衰，希望可以慢慢锻炼改善。 另一个发现的短板是，口才不行。由于New Zeland（OOPSLA举行的地方）旁边就是ANU/Google Sydney，他们做的东东刚刚好也跟我做的有交集，所以我也过去宣传了一下我的工作。一般来说，我导师都会跟着去，跟其他人connect，也会帮忙回答各种问题。今天在Google Sydney宣传的时候导师在坐飞机，而且得到了一些关键问题，于是我就当机了，进入对对对模式，也可能会对后续落地有影响。如果有导师在解围，估计会好很多，但是这并不是知识差距 - 在project相关知识上我们俩知道的基本上一样，甚至我应该还多一些。这就是我没这个随机应变的能力。这就有点头疼，毕竟体力差可以去运动场找回来，但这样的报告机会差不多一年才有一次。 不过说点更正面的！我去了动物园！看到了kiwi！还有emu，摸起来毛茸茸的，也不知道躲！还摸了鳗鱼，很冷，所以就是冻鳗了！我从今以后，就是冻鳗高手了！！！ OK，说回正事，talk好像挺可以的，有很多人喜欢，而且结识了很多圈内人，好像都觉得工作挺有价值的。甚至，在visit ANU的时候，我们pair program成功在mmtk里面弄出了工作的hacky prototype。也跟做memory allocator的人讨论讨论了，可能可以用在这些地方。不得不说Steve的眼光真是毒辣，他arrange了一个跟allocator maintainer的meeting，说了下可能用得上，还真猜中了。 另一个重要的事情是，超人也会流血。在oopsla/澳大利亚，我近距离接触了一些以前只能在教科书跟经典paper上看到的人物，而这过程中我认为它们更像走在前面的前辈，是普普通通的人，而不是一种‘神话生物’。诚然，我能力跟各种做教授年龄比我存在年龄还大的人对比，有很大差距，但我认为这差距可以随时间缩小甚至填补。 甚至，我还看了一个著名教授做了一个。。。烂活。如果你挡着名字跟会议，我还会以为是各种奇怪workshop的新人论文。某种意义上，这反而很有价值（笑）。（当然，请大家别猜是谁，我还想活） 另外，跟各种教授还有工业界的人聊了聊以后，再去了次Google以后，对做教授或者去工业界的抗拒度降低了，其实还行，挺好的。当然，如果能被富婆包养就最好了，这样就可以一心做research，不考虑什么教书什么grant，也比工业界有更多自由，想做什么做什么。如果大家认识富婆，可以介绍介绍给我！ 至于看了什么talk? 跟人闲聊的时候学到了probabilistic separation logic，很漂亮。在普通的分离逻辑里面，magic wand代表的是两段内存没有交集，而在probabilistic separation logic里面，表示的是两个概率分布独立！ 而我认为最有意思的talk，是Deciding program properties via complete abstractions on bounded domains。简单的说，就是在一定条件下，有loop, ifelse, assignment的语言里面抽象解释可以是complete的，而且这个completeness是composable的 - 就是说只要对ifelse/assignment complete，也会自动对loop complete。以前没怎么见过这样的工作。 明天还有meeting跟socialize，睡觉。

“Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowchart; it’ll be obvious.” – Fred Brooks, The Mythical Man Month (1975) 吐槽一下，最近手指好疼，怀疑打字打太多了，等下有空看看医生，orz 我们先看这一个著名的笑话： 三个程序员被要求穿过一片田地，到达另一侧的房子。 菜鸟程序员目测了一下之间很短的距离，说：“不远！我只要十分钟。” 资深程序员看了一眼田地，想了一会，说：“我应该能在一天内过去。”菜鸟程序员很惊讶。 大神程序员看了一眼田地，说：“看起来要十分钟，但我觉得十五分钟应该够了。” 资深程序员冷笑了一声。 菜鸟程序员出发了，但只过了一会，地雷爆炸了，炸出了巨大的洞。这下他必须偏移预定的路线，原路返回，反复尝试穿过田地。最后他花了两天到达目的地，到的时候颤颤发抖，还受了伤。 资深程序员一出发就匍匐前进，仔细地拍打地面，寻找地雷，只有在安全的时候才前进。他在一天的时间内小心谨慎地缓慢爬过了这片地，只触发了几个地雷。 大神程序员出发之后径直穿过了田地，十分果断。他只用了十分钟就到了另一边。 “你是怎么做到的？”另外两个人问道，“那些地雷怎么没有伤到你？” “很简单，”他回答道，“我最初就没有埋地雷。” 一般来说，我们写程序，都是这样的步骤： 0：写出程序 1：写测试 2：通过测试查找错误，回到0修补，如果没发生问题就假装程序写好了 这时候有一个很大的问题：debug是一个很麻烦的过程，而且debug后不代表程序没有问题，只代表了程序在这些测试上没有问题（所以你还要牢费心力找测试）。更严重的问题是，在多线程或者分布式系统里面，同一段代码同一段输入，问题是概率性的：有可能会发生，也有可能不会发生。更更糟糕的一点 - 这些分布式代码，比如paxos的实现，往往是最核心的代码，当这些代码发生问题后，会带垮整个服务器集群，造成巨大的损失。 但是，为什么我们要劳心劳力的去debug？我们不把错误放进程序，不就好了？ 或者，我们更进一步，为什么要写程序？把程序种子埋土里，然后过几天等程序长大了，就收掉，不就行了？ 你先别笑，这的确是编写复杂程序的一个方法。 更具体的说，当我们程序运行到一半，假设我们随机修改一下变量的值，很明显程序不会没问题的继续运行下去。 比如说，如果我们在写一个二叉搜索树，当我们运行的时候，把一颗树的最左节点跟最右节点交换了，那接下来可能会找不到需要的值。 也就是说，我们的程序需要遵守一定的规则(invariant)。对于上面的例子来说，我们需要遵守的invariant是，一个二叉树的左边的所有节点小于等于自身，自身小于等于右边的所有节点。 所以，我们写程序的时候，要保证这些invariant的正确性。但是，我们可以反过来，从这些invariant，推导出一个程序！ 更具体的说，我们 0 - 写下程序输入跟输出符合的条件，一般来说，输入的条件并不等价于输出的条件，所以这时候，这两个条件之间，是有一个空缺的 1 - 根据这些规则，猜出一小段代码，这些代码会把这些空缺变得更小，然后我们不停进行这个操作，直到空缺消失。这时候，程序就编写完成了。...

最近电脑坏了，所以上周没法写文章，抱歉。 随着AWS Automated Reasoning Group的兴起，可以感受到了编程语言在工业界的影响力的加大（这不废话吗，这么多人都被吸过去了），顺带不久前看了github semantic的ICFP Experience Report，想了想可以写一写关于这些的内容。 这方面一写paper是(缩写C)，讲coverity的程序分析框架在应用的时候的问题，<Fusing Industry and Academia at GitHub (Experience Report)>(缩写G)讲github内部的程序分析框架semantic，还有(缩写A)，讲AWS如何利用SMT solver对云上控制权限的验证。 其实ACG三篇paper都有很多共通点，我觉得与其一篇篇介绍，不如对ACG做一些总结 为什么要整X? A:没说 C:我们一开始是为了publish paper，在几百万行代码上抓了很多错误，publish了paper以后，就觉得可以搞个大的。开家公司，请几个销售员躺着数钱钱，当然这考虑完全错误 G:做一个更好的，知道语义而不是只知道unstructured text的git diff 有没有遇到什么克苏鲁问题？ A:没有 C:好多，惨惨，哭哭。有一次我们跑用户的make，结果用户用了个奇奇怪怪的make语法写path，结果在蝴蝶效应下变成了rm -rf *。用户经常会给我们奇奇怪怪，不符合C语言标准的程序，然后因为各种原因无法改C编译器，最后要我们改自己的C parser。还有一次，给用户抓出use after free error，用户说free了以后还没malloc，所以freelist没有被复写，可以继续用，气死偶嘞！（整篇paper都是各种这些克苏鲁问题） G:没有，卧槽free了后依赖于没有malloc继续用也太克苏鲁了 有没有遇到什么不克苏鲁的问题？ A: 我们遇到的最大问题是只有很小一部分用户会写SMT Query或者First Order Logic。但是，AWS有一百万用户，没有办法教这一百万个用户都写SMT。所以，我们把问题反转过来 - 对于一个输入（系统设置），我们会返回所有的信息（对于所有最终用户X跟数据Y，X能不能访问Y）。这时候，AWS用户只需要检查这些访问权限报告，就知道行不行了。 我们遇到的另一个问题是，当我们升级我们的SMT solver的时候，有的时候以前能Solve的Query会timeout，于是对一些用户来说，以前行的东东就不行了。我们的解法是，弄一个大大的portfolio，各种solver version都丢进去。 C: 我们也一样有软件升级问题。当我们升级完我们的静态分析器的时候，我们往往能抓更多错误，但这是不好的！更准确的说，我们的PM往往都想要一个这样的故事：‘我们引入了静态分析器，然后发现了X个错误，然后在过去Y个月里面，我们把这X个错误一步步消除掉！现在，我们的程序没有错误了！’，然后当他们升级软件的时候，错误越来越多，就会很气气！ 另一个问题是，用户会不停提交代码，而如果你以前报过一次错误，同样的错误就不要再报了。我们写了一个错误database，然后会把所有分析出来的错误跟这个一一对比，只报告新的。 还有一个问题是，当我们报错误的时候，用户有时候看不懂，然后就会把我们的错误看成误报。当用户认为我们误报的时候，就会更不信任我们的工具，于是下次我们报错会更可能认为是误报。于是，我们需要很好的错误信息，并且对于一些复杂的静态分析，给出好错误信息更难，如果我们给不出好错误信息，我们宁愿不要这个分析。 G: 我们的新git diff能给出很有用的summary，于是得到了更多momentum（大概是有更多资源招程序员整这个）。但是用户不想安装跟用我们的新git diff。我们只好弃掉这个project。 更具体的说，我们不做git diff了，我们用我们整的静态分析工具弄一个Code Navigator，当你指定一个函数的时候，我们用静态分析找出这个函数用在那。 总结： 我觉得这三个工作都有一个共通点：如何包装销售自己的工作(Story)很重要。这里的销售并不是’口才很好‘的意思，而是’向谁卖什么‘。对于A用户来说，他们甚至不知道什么是SMT! 这时候，这整个工具就相当于’隐形‘的，需要跟用户打交道的地方小了很多（只剩下保证版本不会regress）。C用户会不停看到Coverity的工具，于是要求也最高。G也一样有这个问题，但是他们明白Story是可以改的，于是换了一个就好了。 当然，C的方法并不一定更’不好‘ - 在一些时候，这可以抓出’关键的错误‘，而semantic则做不到这个（因为已经包装成不是抓错误工具了）。更重要的是，C引入了一个叫’话语权‘的概念。当你的工具刚刚引入的时候，大家都不知道你的工具是做什么的，也不信任你的工具，于是会e.g.把错误看成误报，不看错误，或者就e.g.不会升级，或者买静态分析服务。所以这里有一个很典型的网络效应 - 在前期要给出很多精力去一个个服务用户，但是后面工具变出名了以后就不需要了。C也说了一句‘好日子在后头’之类的话：在以前静态分析没有C的时候这么流行，于是它的前辈要做的斗争更难。可以预想的是，很多这些都是‘一次性开销’，后续工具的应用会更简单。 另外，Github：Haskell真香，ICFP是我的秘密武器！