Arthur tiancaiamao@gmail.com atom egg for Chicken www.zenlife.tk Copyright (c) 2015, Arthur Mao 伟大的野心家,实践家 Arthur的博客 2005-07-31T12:29:29Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <h2>1. 简约而不简单</h2> <p>优雅的代码是一门艺术,更多取决于品味。我喜欢简短,可读的代码。完成同样的功能,使用的代码越短这份代码越优雅。有些人说,我也喜欢写简短的代码,你看:</p> <pre><code>while (*s++ = *t++); </code></pre> <p>这种“优雅”作为教科书级别的经典,实在教坏了不少人。且不说前缀加加和后缀加加的语法设计糟点,这里副作用的操作还依赖返回值,我只能呵呵。然而有些人还特别喜欢抠语言的边边角角,以此号称精通某语言,一股阿Q的“茴香豆的茴字有三种写法”的画面就映在脑中。</p> <p>还有些人喜欢在if后面省略大括号来少几行代码,或者在有些地方省略else语句以减少几行代码。比如:</p> <pre><code>if xxx doSome1(); doSome2() </code></pre> <p>第二个语句本来是满足条件才执行的,结果就直接执行了。又或者这种:</p> <pre><code>if xxx { if yyy { doSome1() } else { doSome2() } } </code></pre> <p>想着把条件合并了少几个分支少二行代码:</p> <pre><code>if xxx &amp;&amp; yyy { doSome1() } else { doSome2() } </code></pre> <p>在xxx为假的条件是不应该执行doSome2的,在这种地方玩小聪明特别容易翻船。这些都不是我说的那种简短和优雅,优雅的代码首先需要是正确的。</p> <p>顺便说句,从语言设计的角度,我是支持if必须写全else分支的。为什么呢?在函数式语言里面,没有statement只有expression,所有expression都应该有一个返回值,返回值是要有类型的。对于if,它的then分支和else分支的类型应该是相同的。然而如果if不写else分支,试想这种:</p> <pre><code>(set! a (if xxx 1)) </code></pre> <p>由于只写了then分支没写else分支,if的返回类型是未知的,到底是int还是空类型呢?于是a的类型也是未知的,这对类型推导很不好。类型系统对于程序的正确性非常重要,so,我支持if不能省略掉else条件。</p> <p>当然,这只是针对我自己认为合理的语言设计而言。对于像Go这类传统的语言,那么建议做法是跟着标准风格走。标准的风格应该怎么写呢?<strong>如果要省略else分支,应该将异常分支写到前面,然后用return尽早退出</strong>,像这样子省略else分支:</p> <pre><code>if err := xxx; err != nil { handle(err) return } if err := yyy; err != nil { handle(err) return } </code></pre> <p>反例写出来是很丑的:</p> <pre><code>if err1 := xxx; err1 == nil { if err2 := yyy; err2 == nil { doSome() } else { handle(err2) } } else { handle(err1) } </code></pre> <h2>2. 借鉴好的东西</h2> <p>不过Go语言里面error处理确实不太好,到处充斥着这样的代码,还是很丑的。让我们思考下如何让错误处理稍微优雅一点。</p> <p>下面这个例子,假设我们要从数组里面Unmarshal一个数据结构出来:</p> <pre><code>func (l *mvccLock) UnmarshalBinary(data []byte) error { buf := bytes.NewBuffer(data) err := ReadNumber(buf, &amp;l.startTS) if err != nil { return errors.Trace(err) } err = ReadSlice(buf, &amp;l.primary) if err != nil { return errors.Trace(err) } err = ReadSlice(buf, &amp;l.value) if err != nil { return errors.Trace(err) } err = ReadNumber(buf, &amp;l.op) if err != nil { return errors.Trace(err) } err = ReadNumber(buf, &amp;l.ttl) if err != nil { return errors.Trace(err) } return nil } </code></pre> <p>错误处理的逻辑跟正常逻辑是混在一起的,造成阅读干扰。如果定义一个辅助结构,然后把Read实现成它的方法,把error记录成它的内部状态:</p> <pre><code>type marshalHelper struct { err error } func (mh *marshalHelper) ReadNumber(r io.Reader, n interface{}) { if mh.err != nil { return } err := binary.Read(r, binary.LittleEndian, n) if err != nil { mh.err = errors.Trace(err) } } </code></pre> <p>于是我们就可以这样写了:</p> <pre><code>func (v *mvccValue) UnmarshalBinary(data []byte) error { var mh marshalHelper buf := bytes.NewBuffer(data) mh.ReadNumber(buf, &amp;v.vt) mh.ReadNumber(buf, &amp;v.startTS) mh.ReadNumber(buf, &amp;v.commitTS) mh.ReadSlice(buf, &amp;v.value) return errors.Trace(mh.err) } </code></pre> <p>注意到没有?丑爆了的error处理消失了,这就优雅多了!这段代码其实是我从项目里面拿的一个真实例子,<a href="https://github.com/pingcap/tidb/blob/d7a92e1e2380e2159f9a01b3efa00f275a0da96e/store/tikv/mock-tikv/mvcc.go#L73">在这里</a>可以看到。</p> <p>如果熟习函数式语言并且了解monad的话,其实明眼人是可以看出来的,这里本质上是使用了函数式语言里面的monad的技巧。返回值的类型是</p> <pre><code>data result = None | Error of error </code></pre> <p>然后让错误处理走另一条通路了。想了解更多可以看看<a href="https://fsharpforfunandprofit.com/rop/">这里</a>,顺便说句,F# for fun and profit这个系列写的真心不错,强力推荐。</p> <h2>3. 语言影响思维模式</h2> <p>函数式语言真的是好东西,无论是否使用,都应该看一看,对于写优雅的代码很有帮助。这里的错误处理只是一个例子。很多东西只有在见过之后,大脑才能形成概念,直到有机会把概念用到其它的地方,触类旁通。parser combinator在函数式语言里面是一个非常经典的教程,由于我之前看过,有一次写Go的时候就看到了启发。场景是这样子的,kv存储引擎里面存了mvcc的信息,数据的布局类似这样子:</p> <pre><code>// Key layout: // ... // Key_lock -- (0) // Key_verMax -- (1) // ... // Key_ver+1 -- (2) // Key_ver -- (3) // Key_ver-1 -- (4) // ... // Key_0 -- (5) // NextKey_lock -- (6) // NextKey_verMax -- (7) // ... // NextKey_ver+1 -- (8) // NextKey_ver -- (9) // NextKey_ver-1 -- (10) // ... // NextKey_0 -- (11) // ... // EOF </code></pre> <p>需要从goleveldb里面读取这些东西,解析需要的部分,并且根据是否遇到锁以及版本信息做一些额外的处理。整个代码开始是写的比较恶心的,因为访问要操作一个iterator,然后有一些中间状态的需要存下来,当iterator遍历的操作跟数据处理逻辑耦合之后,代码就很丑了。后来突然灵光一闪:这不是正是可以从parser combinator借鉴的场景么?interator抽象成一个stream,我只需要定义很多小的&quot;parser&quot;,这里是decoder,每个decoder只做一点点事情,比如只解析一下lock数据的decoder,比如只解析一个mvcc value数据的decoder,甚至什么都不解析,只将iterator移到下一个mvcc记录的decoder。然后将它们组合使用,就可以发挥无穷威力。</p> <p>定义一个interface,所有的decoder都是实现这个接口,状态相关的存到实现的decoder内部。</p> <pre><code>type iterDecoder interface { Decode(iter *Iterator) (bool, error) } </code></pre> <p>函数可以组合但是不能记录状态,而对象是记状态不易组合。monad本质是上把状态记录到了类型里面,来实现带副作用的。</p> <p>我从函数式语言那边受了很多启发,很多时候它都教会我写更好的代码。当然,面向对象也有教我很多东西。</p> <p>之前我们的<a href="https://github.com/pingcap/tidb/blob/a264f81acc1e69d3f20cb2815873e7659843e675/executor/new_distsql.go#L280">项目里面有一个IndexLookUpExecutor</a>,这个东西做的事情是由多个goroutine并行地从数据库里读索引,解析索引数据,再利用索引数据里面解析出来的信息去并行地读数据库的表数据。这块代码很乱,经常出各种bug,比如退出有goroutine泄漏,或者关闭channel时卡死。一方面原因是逻辑比较复杂,涉及到goroutine的并行,并且状态比较多。另一个更重要原因,就是代码写的烂(陈年老代码,经过很多人的手,逻辑复杂,不敢动,逢改必引入bug,这种代码最让人咬牙切齿)。怎么重构它呢?我仔细分析了复杂性的原因:数据结构内部维护了太多状态。</p> <p>那么基于面向对象的思维,将它拆小,IndexLookUpExecutor被做成了indexHandler,tableHandler,每个对象只管理自己的内部状态,goroutine相关的控制也移到对象内部。IndexLookUpExecutor不再关注对象内部的状态,通过方法来交互indexHandler和tableHandler。对象各自管理自己的内部状态,并且状态小了之后,一下子就可维护了。</p> <p>其实都是很老生常谈的概念:<strong>模块化。一个函数只做一件事情。高内聚,低耦合。对象内部状态不需要暴露给外面,通过对象的方法交互</strong>。无关设计模式,只是最基本的道理。面向对象的重要道理就是,把状态控制在对象管理的范围之内,函数式那边的答案是类型。</p> <p>最好不要成为只精通某一门语言的专家(尤其不要是C艹语言),无论是过程式的,函数式,面向对象的,都多了解一些,有助于知道在合适的时候该使用什么方式才是合理的。语言决定了思维模式,这是真的。拿Go语言来说,如果一直停留在锁这种底层的东西上面,其它语言里即使自己实现一些机制,也没法像goroutine/channel体验到CSP/Actor之些高层思维带来的酸爽。有了语言内置的支持以后,做并发编程的思维完全就进入到了一个更高层的抽象。</p> <h2>4. 抽象再抽象</h2> <p>记得SICP那本书里面,一直在教人们抽象再抽象,其实这是写好代码非常重要的一环。在编程语言里面,处于抽象的顶点的概念是什么呢?递归。迭代是人,递归是神!</p> <p>我们知道,面试的时候可能会要求写一个链表反转,默认会用C语言之类的低级语言。然而如果语言可选,我会拿lisp糊他一脸,你丫的傻逼面试官,教你重新写代码:</p> <pre><code>(define reverse [] -&gt; [] [X | Y] -&gt; (append (reverse Y) X)) </code></pre> <p>简洁,易读,bug free,这才是优雅呀!</p> <p>再说一个排序的例子,我不想说快排,太欺负C语言了。就说冒泡排序吧,正好可以看个不动点的例子。</p> <pre><code>(define fix-point1 F X X -&gt; X F X Y -&gt; (fix-point1 F (F X) X)) (define fix-point F X -&gt; (fix-point1 F (F X) X)) </code></pre> <p>不动点就是,X=F(X)。一个函数对参数执行之后,得到的结果还是那个参数。</p> <pre><code>(define bubble [] -&gt; [] [X | Y] -&gt; (bubble1 X Y)) (define bubble1 X [Y | Z] -&gt; [Y | (bubble1 X Z)] where (&gt; X Y) X [Y | Z] -&gt; [X | (bubble1 Y Z)]) </code></pre> <p>我们看bubble1这个递归函数,它的功能是将链表冒泡一遍。X和Y分别是链表当前的头节点,如果X大于Y,则交换位置。递归的做这个动作,交换两节点,做一遍就冒泡了一遍。亮点来了...</p> <pre><code>(define bubble-sort X -&gt; (fix-point bubble X)) </code></pre> <p>一遍一遍地冒泡,直到达到一个不动点,排序就OK了。这是我看到过的最漂亮的代码之一!嗯,shen语言看到的例子。</p> <p>我给过很多人很高的评价,给过很多项目的代码很高的评价,比如常提到在贵司里面<a href="https://github.com/coocood">@coocood</a>写代码还是挺有节操的,还有包括<a href="https://github.com/iamxy">@iamxy</a>也是,虽然很少写代码了。再比如云风代码非常值得学习下,还有王垠的代码也是写得相当漂亮的(可惜都删了)。一些项目,像lua的源代码,skynet源代码等等都是很值得学习的。但是若说我见过的最优雅的代码,还是<a href="http://www.shenlanguage.org/">shen语言</a>的源代码。我不止一次推崇这份代码了----这真的是艺术家的作品!</p> <h2>5. 不要被表达能力束傅</h2> <p>写代码是一门艺术,对于艺术家来说,代码的表达能力非常重要。语言的表达能力强,就可以用更简洁的代码完成复杂的功能,代码也就更加的优雅。语言既影响思维方式的,也能阻碍表达的。有些东西在这门语言里面体会不到,非得另一门语言里面才能,这便说明语言同时阻碍了表达。</p> <p>表达能力的极致是什么呢?lisp的宏。这是唯一一种不阻碍表达的方式。很多人不喜欢lisp的语法,其实lisp根本没有语法。真正的lisp程序员会创造属于自己的lisp,只有自己按自己的语法表达,才是随心所欲。shen语言真正做到了这一点。</p> <p>最初看到 |> 和 >>= 这些符号的时候,简直被惊艳到了。中缀运算符的能力非常强大,像这样写代码:</p> <pre><code>x |&gt; add 1 |&gt; times 2 </code></pre> <p>后来发现其实这个操作其实用函数是可以完成的,不需要中缀运行符:</p> <pre><code>(fun compose X [] -&gt; X X [F | Fs] -&gt; (compose Fs (F X))) (compose x [(add 1) (times 2)]) </code></pre> <p>看到模式匹配,觉得是个好东西,其实lisp早就能支持了,一直没注意而已。看到类型系统时觉得,这么好的东西,lisp能不能吸收进来呢?我在shen语言那里得到了答案。</p> <p>曾经看过一个20几万行的游戏服务器的代码,真的很不优雅。按理说它完成的功能根本没必要那么大的代码量。原因是它有近一半的代码,全是在处理发包解包,全部手写硬编码的。那个年代还没有protobuf,没有grpc这些东西。假如有DSL,有代码生成器,那这一半的代码都可以干掉了。重复,低效的劳动。</p> <p>后来看到shen的YACC惊呆了,100多行不到200行的实现!最惊讶的是它的类型系统居然是用生成代码的方式实现的,只实现了一套逻辑引擎,然后生成类型推导的规则了喂给逻辑引擎,一套类型系统就搞定了。整个项目4000多行代码,在我看来比那20万行代码要多得多。</p> www.zenlife.tk/coding-like-an-artist.md 2017-09-17T00:57:42Z Coding like an artist 2017-09-17T00:57:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <h2>系统执行一条SQL,到底慢在哪里?</h2> <p>如何跟踪一个分布式事务的所有行为?使用 <a href="http://opentracing.io/">opentracing</a>! opentracing 是一个标准的分布式 tracing 的协议。支持 Go, JavaScript, Java, Python, Ruby, PHP, Objective-C, C++, C# 等等许多的语言(暂时没看到 rust 的库)。</p> <p><a href="https://github.com/opentracing/specification/blob/master/specification.md#the-opentracing-data-model">一些基本的概念</a>:一个 Trace 是由许多 Span 构成的一个有向无环图。Span 之间的边的关系叫做 Reference。</p> <p>Span 里面的信息包括:操作的名字,开始时间和结束时间,可以附带多个 key:value 构成的 Tags(key必须是string,value可以是 string, bool 或者数字),还可以附带 Logs 信息(不一定所有的实现都支持),也是 key:value形式。</p> <p>下面例子是一个 Trace,里面有8个 Span:</p> <p><img src="static/trace-span.png" alt /></p> <p>Reference 是记录 Span 之间的相互关系,目前定义了两种: ChildOf 和 FollowsFrom。ChildOf 很好理解,就是父亲 Span 依赖另一个孩子 Span。比如函数调用,被调者是调用者的孩子,比如说 RPC 调用,服务端那边的Span,就是 ChildOf 客户端的。很多并发的调用,然后将结果聚合起来的操作,就构成了 ChildOf 关系。如果父亲 Span 并不依赖于孩子 Span 的返回结果,这时可以说它他构成 FollowsFrom 关系。</p> <p>可视化之后,将得到这样的视图:</p> <p><img src="static/trace-relationship.png" alt /></p> <h2>举一个栗子</h2> <p>这里有一个很好的例子来说明,如何一步一步的支持 opentracing。</p> <p>首先,我们需要知道整体架构大概的样子,比如:</p> <p><img src="http://opentracing.io/documentation/images/OTHT_2.png" alt /></p> <p>这是一个 Web 请求的例子,客户端发起请求,经过认证服务,计费服务,然后请求资源,最后返回。</p> <p>接着,如果我们把 gRPC 和整个大致的流程串起来,可以看到一个大体的工作流程:</p> <p><img src="http://opentracing.io/documentation/images/OTHT_3.png" alt /></p> <p>如果我们继续细化组件内部的埋点,可能会变成这样子:</p> <p><img src="http://opentracing.io/documentation/images/OTHT_4.png" alt /></p> <p>又或者是这样子:</p> <p><img src="http://opentracing.io/documentation/images/OTHT_5.png" alt /></p> <p>具体的将以Go语言为例来说明。调研过 Go 语言的几个 opentracing 的实现,主要是</p> <ul> <li><a href="https://github.com/sourcegraph/appdash/">Appdash</a></li> <li><a href="http://jaeger.readthedocs.io/en/latest/">Jaeger</a></li> <li><a href="http://lightstep.com/">LightStep</a></li></ul> <p>AppDash是sourcegraph开源的一个实现,上手最容易,它有一个in memory的后端可以直接嵌到应用里面,零外部依赖,但是后端和界面的功能做的比较弱。</p> <p>LightStep是一个家做 tracing 的公司,后端以服务形式提供出来,各语言支持的库也挺丰富,但暂时没有具体测试过。</p> <p>Jaeger是uber开源的实现,基于ZipKin的,功能比较强大,组件也比较复杂。还好有一个 all-in-one 的 docker 镜像。我们就用它了。</p> <p>初始化好全局的 Tracer,就可以用了。</p> <pre><code>tracingCfg := cfg.OpenTracing.ToTracingConfig() tracer, _, err := tracingCfg.New(&quot;TiDB&quot;) if err != nil { log.Fatal(&quot;cannot initialize Jaeger Tracer&quot;, err) } opentracing.SetGlobalTracer(tracer) </code></pre> <p>grpc 还是很方便的,有相应的包可以直接加上 tracing 功能:</p> <pre><code>import ( &quot;github.com/grpc-ecosystem/go-grpc-middleware&quot; &quot;github.com/grpc-ecosystem/go-grpc-middleware/tracing/opentracing&quot; ) unaryInterceptor := grpc_middleware.ChainUnaryClient( grpc_prometheus.UnaryClientInterceptor, grpc_opentracing.UnaryClientInterceptor(), ) streamInterceptor := grpc_middleware.ChainStreamClient( grpc_prometheus.StreamClientInterceptor, grpc_opentracing.StreamClientInterceptor(), ) conn, err := grpc.Dial( addr, grpc.WithInsecure(), grpc.WithTimeout(dialTimeout), grpc.WithInitialWindowSize(grpcInitialWindowSize), grpc.WithInitialConnWindowSize(grpcInitialConnWindowSize), grpc.WithUnaryInterceptor(unaryInterceptor), grpc.WithStreamInterceptor(streamInterceptor)) </code></pre> <h2>哪些地方该埋点?</h2> <p>所有关键代码路径,执行比较耗时的地方(走io),跟外部组件交互的地方(grpc)。</p> <p>以 TiDB 为例,比如收到一个SQL请求执行的流程:</p> <ol> <li>parse</li> <li>compile</li> <li>execute</li></ol> <p>事务两阶段提交的过程:</p> <ul> <li>prewrite</li> <li>commit</li></ul> <p>异步或同步取TS的过程;coprocessor执行过程;事务重试等等...</p> <h2>该如何埋点?</h2> <p>调用链信息必须通过某种方式一直传递下去,Go 语言是传递 ctx 参数,tracing 信息被藏在 ctx 里面。</p> <pre><code>span := opentracing.SpanFromContext(ctx) ctx := opentracing.ContextWithSpan(ctx, span) </code></pre> <p><strong>尽量不要把 ctx 存储在对象里面!!!</strong></p> <p>这个问题跟编程语言里面的静态作用域动态作用域有一点点像。<a href="http://www.zenlife.tk/go-context.md">我以前也写过,context本质上是动态作用域</a>,动态作用域是很evil的。这次不扯无关的话题,只是强调下:</p> <pre><code>对象创建时候的上下文,跟执行对象方法时候的上下文,并不是同一个 我们应该始终trace使用时的上下文 </code></pre> <p>举例一:request sender。假设有一个 sender 对象,并且这个对象可能是复用的。那么,创建对象对象的时候保存下来的上下文,跟调用 <code>sender.Send()</code> 的时候的上下文,有可能并不是同一个。</p> <pre><code>sender := RegionRequestSender{ctx} sender.Send(msg1) // another message sender.Send(msg2) </code></pre> <p>举例二,ddl的问题。DDL对象在创建的时候有一个 ctx,它会起后台的 worker,前台收到消息会分发到后台worker。那么 tracing 的应该是:收到消息,分发到worker,worker处理完消息,返回结果的过程。每次来新的消息,都是一个新的 ctx,而不是DDL对象创建的时候那个ctx。假设需要cancel,也是cancel掉某一次消息处理的上下文,而不把把DDL对象cancel掉。</p> <p>给事务加 tracing,坏的做法在 Begin 的时候把 ctx 存到 txn 对象里面:</p> <pre><code>txn := store.Begin(ctx) txn.Commit() </code></pre> <p>好的做法,在Commit的时候把参数带上去:</p> <pre><code>txn.Commit(ctx) </code></pre> <p><strong>trace 应该以一个请求的生命期(调用链)为单位,而不是以事务为单位</strong></p> <p>由于 SQL 的特殊性,一个query跟一个事务并不是一一对应的关系。如果把 trace 以一个事务为单位,两个地方处理起来比较麻烦。一个是用户用 <code>begin ... commit</code> 发多次请求,这种情况必须将 ctx 存储起来。另一个是 retry 的处理。</p> <p>retry 重试了事务就没了?这样不对。在retry里面重新取了ts,重新生成新的txn对象...但是其实还是同一个事务,这个信息非常重要,我们要记录下来。如果基于事务记录,这一块逻辑很乱,而基于一个请求的生命期,这个就比较容易。</p> <p>但是我们还是要把事务和 trace 绑定起来。使用 Tags!为每个事务记录 txn.id 的 Tag 信息,就可以处理 <code>begin ... commit</code> 了。</p> <pre><code>type Span interface { SetTag(key string, value interface{}) Span } </code></pre> www.zenlife.tk/use-opentracing.md 2017-10-30T20:22:42Z opentracing 使用介绍 2017-10-30T20:22:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>在我接触过类型之后,就觉得这是好东西,lisp里面没有真是太可惜了。于是就一直在思考:如何为lisp加类型,才是合理的方式。这一块水太深了,搞了好久也没算搞透彻,这里算是记录一些碎碎念。</p> <ol> <li>HM</li> <li>类型即约束</li> <li>宏和逻辑引擎</li></ol> <h2>HM</h2> <p>谈及类型系统肯定会说到大名鼎鼎的 Hindley–Milner,第一个要说的就是HM。</p> <p>为什么HM是最流行的一个类型系统呢?我觉得它有一些特别的优点:简单,soundness,并且decidable。</p> <p>soundness是说,如果一个类型系统的规则推导出来的类型,跟程序真实执行得到的值的类型是一致的,那么这个类型系统就是soundness的。soundness也就是指正确性,如果能保证soundness,那么只要通过了类型系统的程序就不会出错(get stuck)。</p> <p>decidable是说,一个类型系统的规则是可以求解的。举个极端的例子,如果要知道程序的类型,需要真实地把程序执行一遍,程序可能是死循环的,那这样的做法就不是decidable的。</p> <p>HM非常基础,然后能保证是soundness的。然后它是decidable,计算复杂度还很低。用大O表示复杂度是O(?)忘记了。所以像ML,Haskell的类型系统基本都是在HM之上的变种,Haskell做的可能更激进一些。</p> <p>为什么使用HM或者照搬ML,Haskell的类型并不适合lisp?</p> <p>本质上是哲学问题。lisp追求的是灵活性和表达能力,而类型则是正确性,会限制一些“可能”正确的程序。</p> <p>举个例子,这个表达式:</p> <pre><code>(lambda (x) (cond ((= x 3) 42) ((&gt; (strlen x) 5) #t))) </code></pre> <p>输入参数x的类型可能是 <code>integer|string</code>,而返回值的类型可能是 <code>integer|boolean</code>,并且还是有关联的,整个函数的类型则是 <code>integer-&gt;integer|string-&gt;boolean</code>。</p> <p>HM系统不让这么干,如果写类似的东西必须加tag并定义类型。要求输入以及返回值的类型都是确定的,通过规则的约束,保证写出来的代码都是对的,但是也误杀了一些“其实是”对的程序。这跟lisp追求的灵活性的矛盾,限制了表达能力。</p> <p>tagged union必须是正交的。如果非正交,就需要子类型判等。实现HM的时候,用tag的判等比较好做,然而有子类型,把等于换成集合的属于关系,就很难处理了。</p> <p>另外还有宏的问题,宏可以把一门语言完全变成另一门语言,带宏了之后,跟支持类型系统也是很冲突的。</p> <p>如果生硬地模仿ML或者Haskell的东西,我觉得这个方向是不对的。语法会特别丑,而且怪怪的,这种做法给lisp加类型还不如直接换语言呢。反面教材参见<a href="https://github.com/lexi-lambda/hackett">hackett</a>,和<a href="https://github.com/LuxLang/lux">lux</a>。</p> <h2>类型即约束</h2> <p>接下来要讲的是第二个点,类型即约束。</p> <p>彭飞写过一篇《王垠,请别再欺负我们读书少》,王垠反击写了一篇《到底是谁欺负谁读书少》,那一次的PK堪称惊天地,泣鬼神。最后以王垠完胜,彭飞删除了原文收场。神仙打架,我们凡人看戏。<a href="https://www.zhihu.com/question/42315543">知乎上还有人提问</a>:PLT零基础的人,要看懂王垠和彭飞在《王垠,请别再欺负我们读书少》里讨论的内容,需要掌握哪些知识?</p> <p>我的态度,怎么说呢?拒绝看不懂以下公式的人讨论王垠的水平:</p> <p><img src="http://upload-images.jianshu.io/upload_images/68562-eae6c6cd2eecfb4a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/500" alt /></p> <blockquote> <p><a href="http://yinwang0.lofter.com/post/183ec2_c9184be">王垠:每一个函数的类型,就是这个函数本身。没有比函数本身更能够描述函数的特征的类型</a></p></blockquote> <p>这观点真是让我眼前一亮,尤如醍醐灌顶一般。对于lisp,从实用而不是学术的角度,并不需要特意去追求类型系统是sound的,它只要能帮助我们检测出一些错误,这就够了。这个套路就是,类型即约束,我们并不需要知道某个东西确切的类型,而只是知道哪些使用方式违反了约束,是不安全的。</p> <p>王垠的做法走抽象解释,更类似静态分析而不是类型推导,把程序虚拟的跑一遍,然后去发现各个表达式的类型,这个过程中关于类型使用时的约束信息就建立起来了。</p> <p>跟着知乎的链接,我发现更早就有一些论文研究,比如soft typing scheme。比如Erlang的Dialyzer/Typer。</p> <p>实际上HM在实现tagged union扩展的时候,就已经在推导规则里面不可避免地引入了一定程度的约束系统。如果允许子类型之后,约束扮演的角色就相当重了。</p> <p>如果我们检查到可能出现了类型错误,并不是拒绝掉程序,而只是警告,这其实是非常有用的。可以在类型安全跟程序的灵活性里面取得一个平衡。这个方向对于给lisp加类型绝对是更可取的做法。</p> <h2>宏和逻辑引擎</h2> <p>lisp没有类型,怎么办?忘记哪天网上闲逛看到一个观点:真正的lisp高手答案都是logic engine。起初没有引起重视,直到后来遇到shen语言,才真正的理解了这句话,然后费了老大的劲找到原出处。</p> <blockquote> <p><a href="https://news.ycombinator.com/item?id=2595036">fogus:&quot;Macros and logic engine versus type system... to the death.&quot;</a></p></blockquote> <p>fogus 这哥们对于lisp还是非常有见地的,不管是<a href="http://blog.fogus.me/2011/05/03/the-german-school-of-lisp-2/">lisp爱好者</a>,还是<a href="http://blog.fogus.me/2011/10/18/programming-language-development-the-past-5-years/">非lisp爱好者</a>,都可以看一看。</p> <p>给lisp加类型,如果从实用角度出发,我们可以把soundness/decidable都给划掉,不sound也没关系,能帮我们发现错误就好;不decidable也没关系,写代码的时候都repl的,只需要做到如果跑不出来,那一定代码写的有问题。于是,我们从两个角度来评判给lisp加类型:</p> <ul> <li>表达能力</li> <li>复杂性 (实现,使用)</li></ul> <p>leslie lamport 老爷子大家都熟习吧?搞分布式领域,如果没听过这位老爷子的,建议尽早改行。用他的话说,就是当年他研究分布式领域的时候,比尔盖茨还穿着开裆裤在玩泥巴!我无意之中发现,他还写过类型方面的文章:Should Your Specification Language Be Typed? 这篇文章的主张是用集和论来表达类型。类型系统跟集合论,跟逻辑学,都有着莫大的联系。关于逻辑,计算的还有一个<a href="https://zh.wikipedia.org/wiki/%E6%9F%AF%E9%87%8C-%E9%9C%8D%E5%8D%8E%E5%BE%B7%E5%90%8C%E6%9E%84">柯里-霍华德同构</a>。</p> <p>比如像用集合论来表示类型,这想法就是很新颖的,因为表达能力不再受限在HM的框架,复杂性可能就有点高了。</p> <p>用逻辑引擎的做法在表达能力是上无与伦比的。以shen语言为例,我在<a href="https://www.zhihu.com/question/60702229/answer/213029957">知乎上回答</a>过,这里搬过来:</p> <p>为了说明它的先进性,让我们看一个例子。如果我要定义一个集合类型set,该怎么办?集合是这样的,它里面没有重复的元素。</p> <pre><code>(datatype set ____________ [] : (set A); if (not (element? X Y)) X : A; Y : (set A); ================ [X | Y] : (set A);) </code></pre> <p>这段代码是说,空[]算是一个集合;</p> <p>如果Y是一个集合,如果X不是Y里面的元素,那么,<code>[X | Y]</code>也是一个集合。</p> <pre><code>[1 2 3] : (set number) [&quot;sasdf&quot; &quot;bc&quot;] : (set string) [1 1 2] : type error [&quot;aa&quot; 1] : type error </code></pre> <p>shen是通过手写相继式演算(Sequents Calculate)来定义类型的。datatype里面全部是一些Horn Claus,来指定什么情况下可以证明一个东西是某种类型。这里有一篇相继式演算的<a href="http://logitext.mit.edu/logitext.fcgi/tutorial">教程</a>。</p> <p>这种方式表达能力是完胜的。使用复杂性方面,描述基本的类型比HM那一套稍复杂,但是比起在lisp里面强加一套表示类型的语法,还是有优势的。实现方面,datatype其实是lisp宏,sequent rules会被先编译成的类似prolog语言,然后编译到kernel lambda。</p> <p>我觉得这个做法跟lisp简直是的绝配! 论文的话,POPL 17的 Type Systems as Macros,也用到了这个方法,DSL定义规则,加逻辑引擎实现。</p> www.zenlife.tk/typed-lisp.md 2017-11-12T10:24:42Z 一些思考:为lisp加类型 2017-11-12T10:24:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>Shen语言号称是 write once, run anywhere。怎么做的呢?并是不将源代码编译成汇编或者二进制,而是编译到一个更简单的叫做<a href="https://github.com/Shen-Language/wiki/wiki/KLambda">klambda</a>的语言,以下简称kl。kl扮演了一个虚拟机或者平台无关层的角色,但比较有意思的是:它是一个lisp语言。</p> <p>kl是一个非常精简的lisp,几乎接近于lambda演算,大概有50多个系统函数,包括一些IO相关的。klambda存在的主要意义就是方便port,目前Shen语言已经有common lisp,elisp,C,F#,haskell,scheme等等很多的port了。Shen语言可以完全用kl实现,虽然Shen是用Shen语言写的,但它实现是将Shen语言编译到kl,运行在kl,编译到kl,如此完成自举。</p> <p>kl比scheme还要精简许多。回头想想,scheme还是太复杂了,像<code>call/cc</code>的连续,卫生宏,这些其实都是很复杂的不好实现的feature。Shen暂时还没有Go的实现,想了解下kl的特性,所以用Go语言写了一个解释器。其实对于写过lisp解释器的人都是老生常谈的东西。</p> <h2>eval/apply</h2> <p>最基本的就是<code>eval(exp, env)</code>,常量直接返回;符号就去环境里面查找定义;调用就是将实参和形参绑定,在新的环境里面apply闭包;lambda就将表达式,参数和环境一起保存起来,生成闭包。</p> <h2>lisp1 vs lisp2</h2> <p>kl是类似lisp2的,它有一点很特殊的地方:符号求值得到的是符号本身:</p> <pre><code>(4-) aaa aaa </code></pre> <p>我比较熟习scheme,但是scheme是lisp1的。实现这个feature的时候我玩了一点trick:对符号求值的时候,先到环境里面找,找得到就当变量,找不到直接返回该符号。</p> <pre><code>((lambda x x) 1) // 返回1,因为x被当作变量 ((lambda x y) 1) // 返回符号y,因为y在环境里面找不到,当符号处理 </code></pre> <p>然后函数和变量用了两个不同的namespace,其实也就是hash表啦。</p> <pre><code>(set *v* (lambda x x)) (value *v* 3) </code></pre> <p>变量使用变量的hash表,而函数使用函数的hash表。</p> <pre><code>(defun f (x) (+ x 1)) </code></pre> <p>变量就用set和value,函数定义就用defun。像比如</p> <pre><code>(value f) (*v* 1) </code></pre> <p>都会出错,混着用都是不行的。</p> <h2>partial apply和自动柯里化</h2> <p>kl语言规范要求,它必须是支持partial apply的。也就是说:</p> <pre><code>(5-) (+) #&lt;procedure&gt; </code></pre> <p>函数+本来需要两个参数,如果不提供,它会返回一个partial的函数。支持partial是很好的,比如可以这样写:</p> <pre><code>(0-) (map (+ 1) [1 2 3]) [2 3 4] </code></pre> <p>而不用像scheme那样写成:</p> <pre><code>&gt; (map (lambda (x) (+ x 1)) '(1 2 3)) (2 3 4) </code></pre> <p>怎么实现呢?其实很容易,判断一个参数是否足够,如果不够,当前的部分参数保存到环境中,生成一个新的闭包返回。当这个闭包下次有足够参数了,再被调用的时候,就继续完成运算。比如</p> <pre><code>(defun (add x y) (+ x y)) </code></pre> <p>发现参数不够,自动生成一个闭包返回:</p> <pre><code>(add x) =&gt; (lambda (y) (+ x y)) </code></pre> <p>由解释器自动改写就行了。</p> <h2>实现尾递归</h2> <p>kl语言规范要求,必须实现尾递归优化,即执行尾调用的时候函数栈不会增长。Go语言是不支持尾递归的,在一门不支持尾递归的语言里面,实现这个feature需要一点技巧,这个技巧叫做蹦床(trampoline)。</p> <p>先看一个例子:</p> <pre><code>(eval (eval (eval (eval (eval (eval </code></pre> <p>虽然Go语言有分段栈,但仍然是有大小限制的。如果是这样递归下去,栈就暴掉了。一般函数式语言才要求尾递归优化,因为函数式语言里面递归太重要了,并且喜欢用递归来实现循环。</p> <p>蹦床是这样一个技术:</p> <pre><code>func eval(ctl Control) { ... ctl.Finish = false return } func trampoline() { for !ctl.Finish { eval(ctl) } } </code></pre> <p>eval函数需要递归调的地方,改成设置好标记并return,把eval丢一个循环里面,然后判断标记了做相应的动作。由于eval在循环里面是有机会返回的,所以栈不会一直涨,如此实现尾递归。</p> <h2>异常机制</h2> <p>其实partial和尾递归都还好,异常机制麻烦一点。kl里面有两个异常处理相关的东西:</p> <pre><code>(simple-error str) (trap-error (exp xxx) (lambda x (handle x))) </code></pre> <p>前者会生成一个error对象,而trap-error则是一个特殊表,它先执行里面的表达式(exp xxx),如果成功就直接返回,如果是error,由将error传给后面的exception handler去处理。</p> <p>在异常处理这一点上,我觉得kl做法是对的。对比scheme,曾经觉得continuation高大上。现在仔细想想,虽然用continuation是可以实现所有异常机制,但是continuation太难实现了。异常处理属于corner case,所以比较麻烦,adhoc的东西麻烦一点也就那样了,而如果为了解决一个比较麻烦的东西,去实现更麻烦的continuation,这不是缘木求鱼么?</p> <p>解释器里面的异常处理并不复杂,在前面有了尾递归的基础之后,做异常只需要改一个地方:</p> <pre><code>func eval(ctl Control) { ... ctl.Finish = exception return } </code></pre> <p>标记一下异常,然后直接到trampoline去处理。</p> <hr /> <p>其实是整个上个周末花了二三天的时间撸的一个东西,结果有几个小坑,导致今天才勉强调通了。<a href="https://github.com/tiancaiamao/shen-go/tree/b5c2985d8680355acb34e3de7a45c985389e6e2c">上代码</a>。注意到这个项目名用的是<code>shen-go</code>而不是kl,其实还是有一点野心的。先写一个解释器熟习一下语言规范,后面考虑做字节码编译器,以及整合Go丰富的标准库。</p> <p>想体验一下的同学可以这么玩:</p> <pre><code>go get github.com/tiancaiamao/shen-go/cmd/kl cd $GOPATH/src/github.com/tiancaiamao/shen-go $GOPATH/bin/kl -s shen.kl Shen, copyright (C) 2010-2015 Mark Tarver www.shenlanguage.org, Shen 20.1 running under Go, implementation: gc port 0.0.1 ported by Arthur Mao (0.000000-) (define fact 0 -&gt; 1 N -&gt; (* N (fact (- N 1)))) fact (1.000000-) (fact 5) 120.000000 </code></pre> <p>更多细节就参见<a href="http://www.shenlanguage.org/learn-shen/">Shen的官网</a>了。</p> www.zenlife.tk/klambda.md 2017-11-16T02:04:42Z klambda解释器 2017-11-16T02:04:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>我们有一个对延迟很敏感的模块,这个模块需要访问网络中的另一台机器去取一个时间戳。实现一次分布式事务,需要执行这个操作两次,如果这里拿时间戳慢了,整个事务的延迟就会上升。理论上内网环境同机房一次网络的round trip应该在0.5ms以内,大部分简单读请求应该落在1ms,80%请求的延迟预期也是4ms以内。有客户反鐀说这里有30ms以上的延时,在内网环境用sysbench跑OLTP测试了一下能够复现,于是查了一下这个问题。</p> <p>在opentracing里面观察,这一步确实存在较大的延时,日志里面也有打印大量的慢log,影响了事务整体的完成时间。首先方向是确定慢在哪里,到底是网络有问题还是runtime有问题。</p> <p>一个同事观察到,跑这个模块的benchmark时,额外开启1000个goroutine的worker,每秒钟tick空转,跟只跑benchmark对比,发现前者的延迟要比后者高出许多。怀疑runtime有问题。</p> <p>另一个同事先单独跑测试,并观察网络,会发现网络重传对结果有明显影响;然后改到客户端服务器在同一机器上再测试,排除掉网络干扰,结果发现进程之间会相互影响;再将服务器和客户端分别绑到不同核之后,服务端处理时间比较稳定,而客户端仍然出现高延迟。到这一步的结论基本上是:runtime和网络都不能保证稳定。</p> <p>然而runtime的影响能使达到几十ms级别么?看起来不太合理。在我印象中,怎么都应该控制在微秒数量级,即便回到Go语言1.0的版本,stop the world的GC也不见得这么挫。何况现在都优化到1.9了,GC早就不会stop the world的了。于是我使用go tool trace工具,继续分析问题。不看不知道,一看还真吓了一跳。</p> <p><img src="static/scheduler.png" alt /></p> <p>抓的这一段图,红线箭头是指收到网络消息,ublock了goroutine的Read操作。注意,<strong>从网络消息可读,到读网络的goroutine被再次调度,中间花费了4.368ms</strong> !!! 我甚至找到一些更极端的场景,从收到网络消息可读,到goroutine实际被唤醒,花费了19ms。这里先插入讲一下业务情况,出于性能考虑,业务实现是做了batch的,所以请求都会通过channel转发到一个goroutine上,由那个goroutine去batch的发请求。显然这个goroutine是非常关键的,因为其它的goroutine都是依赖于它。这里ms级别的调度延迟,直接会对业务整体延迟产生很大影响。</p> <p>然后说下goroutine的调度时机,goroutine是协程,如果可以执行,会一直执行,直到阻塞才会放弃CPU。比如执行遇到锁了,或者读channel,或者读io请求等等。goroutine被切换出去之后,如果条件满足了,会被丢到ready队列里面去排队,等待被再次运行。然而,<strong>具体什么时候会被执行,是不确定的</strong>,跟排队的任务队列长度,排在它前面的任务要执行的时间,以及当时的负载情况等等很多因素有关。</p> <p>这里的问题不是GC,而是调度。最终的延迟问题是跟Go的调度设计相关的,主要是协程的公平调度策略:</p> <ul> <li>不可以抢占</li> <li>没有优先级的概念</li></ul> <p>由于不可以抢占,假设网络消息好了,但这个时刻所有的CPU上面都正好有goroutine在跑着,并不能将谁踢掉,于是读网络的那个goroutine并没机会被唤醒。</p> <p>由于没有优先级的概念,假设终于有goroutine阻塞并让出CPU了,这时让谁执行完全是看调度器的心情,读网络的那个goroutine运气不好,又没被唤醒。</p> <p>只要goroutine不走到函数调用,是没有机会触发调度,不会让出CPU的。</p> <p>Go声称可以开千千万万个goroutine,其实是有开销的:越多的goroutine被“公平”调度,越可能影响其中重要goroutine的唤醒,进而影响整体延迟。</p> <p>回头再想之前同事那个测试,空跑worker会影响延时,也就能解释通了:由于被调度概率均等,越多无关的goroutine,则干活的那个goroutine被调度的概率越低,于是导致延迟增加。</p> <p>Go的垃圾回收虽然不stop the world,仍然可能影响延迟:GC是可以打断goroutine,要求让出CPU的,而什么时候goroutine被再次调回来又看脸。</p> <p>有太多太多的因素来影响调度,使整个runtime内的延迟变得不可控。平时压力小时调度上可能看不出什么来,然而尤其在压力大的时候,就表现得越差。</p> www.zenlife.tk/go-scheduler-pitfall.md 2017-11-19T00:35:42Z 记一次latency问题排查:谈Go的公平调度的缺陷 2017-11-19T00:35:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>想不到居然已经时隔一个多月了,<a href="klambda.md">接上篇</a>,编译到字节码的工作算是基本完成。<a href="https://github.com/tiancaiamao/shen-go">shen-go</a>是shen语言在Go的实现。前几天给shen-go打上了v0.1的tag。不知道多少天熬夜,连续好多周末宅着调试代码,看到所有的测试都跑通那一刻,真是感觉所有的努力都没有白费。</p> <p>好的代码是艺术品,功能确定好,反复打磨,当一行代码也不能再增加,并且一行代码也不能减少的时候,就比较接近于完美了。其中<a href="https://github.com/tiancaiamao/shen-go/blob/16ae75533739e9138c8eaa914beb3cc0ae3d3753/compiler/compile.shen">有50行我是比较满意的</a>,称得上可以拿出手的作品。</p> <p>50行代码的编译器!就像王垠的40行一样,大多数的人不会看得懂它干了什么,嗯,所以编译器对他们永远是魔法。</p> <p>其实还可以更短,真正也就40行,这么短的代码里,实现尾递归优化,支持了异常机制,还做了自动curry化!</p> <p>编译出来字节码是<a href="https://github.com/tiancaiamao/shen-go/blob/16ae75533739e9138c8eaa914beb3cc0ae3d3753/bytecode/compile.bc">长这样子的</a>,很奇怪是不是?偷懒直接用sexp表示的。</p> <p>事情总算可以告一段落,接下来是写一些可能的优化方向。</p> <p>JIT 是肯定不做的,坑太深了。一个很重要的点就是克制自己什么东西都想弄一弄,明确哪些feature是重要的,不然技术的研究就没完没了了。其实做的过程中,好几次差点没克制自己去写一个C语言的版本,光想想涉及GC就没完没了。(如果哪一天真用 C 重写了,那它应该放到 cora 那个项目里面了,神圣的代码仓库里面只能有 C 和 lisp。嗯,“每个lisper都应该拥有属于自己的lisp”)</p> <p>纯的 evaluator 执行效率太低了,bytecode 是一个比较好的折中的平衡点,投入的精力和达到的效果。在这个大的取舍之下,考虑的就是三部分:</p> <ul> <li>编译器优化</li> <li>虚拟机优化</li> <li>运行时优化</li></ul> <p>虚拟机优化方面, <a href="https://xavierleroy.org/talks/zam-kazam05.pdf">zinc 的PPT</a>里面讲到的大部分,差不多都优化到头了。最新的master正在拆环境,静态部分和动态部分。环境和调用栈合并没做,编译期决定变量位置没做。都是在考虑了代码引入的复杂程度,和带来的性能提升上面,做的取舍。</p> <h2>peephole optimizations</h2> <p>加速特定的函数来实现优化效果。由于 shen 到 klambda 的编译是用 shen 实现的,也就是会跑 bytecode。里面的 hash 等等常用函数,如果用原生实现而不是跑 bytecode,这块应该是可以有不少收益的。</p> <p>涉及到的主要包括 hash,dict。然后还有文件IO相关的,都可以改用原生实现去替换掉 shen 编译器里面的 bytecode 实现。还有一些基本的函数。它里面有些函数的实现效率实在让人看不下去,比如 <a href="https://github.com/tiancaiamao/shen-go/blob/16ae75533739e9138c8eaa914beb3cc0ae3d3753/ShenOSKernel-20.1/sources/sys.shen#L163">symbol?</a></p> <h2>fixnum tagging</h2> <p>目前在 shen-go 里面,所有东西都是用一个 Obj 表示的,是一个boxed value。它实际上是一个指针,指向一块内存。那里面将类型和值打包到一块了。 数字类型,现在直接用的 float64。也是开始做的时候深思熟虑后的取舍:float64 其实表示定点数其实可以是&quot;准确&quot;的,根据IEEE 754标准,只要算出阶码部分,再看后面多少位尾数为0,可以确定它是否真的有小数部分。</p> <p>那么 fixnum tagging 又是要优化什么呢?是这样的,假设内存是对齐的,由于 Obj 都是指针,最低3位必然全是0。如果用最低一位为1当作区分,我们可以剩下63位用来存储 fixnum。这样子,最后1位为0它就是一个数字,否则它是一个指针。数字类型就可以不用在堆上分配空间了。</p> <p>在 C 里面是司空见惯的技巧,尚不确定 Go 里面能不能做,Go是托管内存的,乱玩也许会 panic。</p> <h2>threaded code</h2> <p><a href="https://en.wikipedia.org/wiki/Threaded_code">Threaded code</a>又是一项在 C 里面非常常用的技巧。准确来说是 gcc,编译器提供了一个扩展,可以直接拿到标签对应的机器指令的地址,于是可以直接jmp过去,让指令预测更友好,相对于 switch-case 的写法要更加高效。</p> <pre><code>switch instruction { case Push: case Pop: } </code></pre> <p>很不幸,这个 Go 语言里面似乎搞不了。</p> <pre><code>thread: &amp;pushA &amp;pushB &amp;add ... pushA: *sp++ = A jump *ip++ pushB: *sp++ = B jump *ip++ add: addend = *--sp *sp++ = *--sp + addend jump *ip++ </code></pre> <h2>优化symbol表示</h2> <p>对于 lisp 语言,优化 symbol 还是很有必要的。目前我还是用 string 来实现的,而实际上 symbol 应该就类似于指针,symbol 做 eq 比较应该是没任何开销的。</p> <p>可以做一个 trie 树结构做去重,存储开销比 hash 低,创建 symbol 的时候先查。每个 symbol 直接在一个数组上面分配,返回在数组的位置记录到 trie 树结构里面。这样对每个 symbol 就有唯一的对象了,也不用逐个字符比较。</p> <h2>优化函数调用</h2> <p>现在的函数全部是放在一个哈希表里面的,好处很明显:实现很简单,像递归函数完全不用特别对待;可以处理将编译期和运行期分离,比如:</p> <pre><code>(defun f (X) (g X)) </code></pre> <p>函数f的定义里面引用到了g,g是可以编译期不用知道的,也不用预先声明。</p> <p>缺点是,函数调用其实是运行期去查 hash 表的。前面既然说了 symbol 优化,symbol 全局唯一,可以被优化成指针。如果我们在 symbol 结构里面额外绑定一个函数的指针,就可以避开函数调用的时候去查 hash 表了。调用过程也就从 hash 查表过程直接变成了取结构体里面的field。</p> <h2>优化let编译</h2> <p>好吧,我承认我偷懒了,let 我是转是 lambda 去做了。</p> <pre><code>(let X 3 (let Y 5 X)) </code></pre> <p>转换出去是</p> <pre><code>((lambda X ((lambda Y X) 5)) 3) </code></pre> <p>这样做出来有个问题:注意在里层的lambda中的 X 是闭包的,所以会有在堆上额外的分配。如果直接做 let 编译,这里就可以做到栈上分配了。说起来还有尾递归优化那边,我得检查一下代码,应该也还有提升的空间。</p> <h2>const常量去重</h2> <p>跟 symbol 类似。</p> <p>......</p> www.zenlife.tk/shen-go-optimize.md 2017-12-24T11:04:42Z shen-go接下来的一些优化方向 2017-12-24T11:04:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <h2>做的最有成就感的事情:shen-go项目</h2> <p>shen语言是一门lisp方言,它有很多平台下的实现。shen-go这个项目就是我写的Go语言对应的实现。</p> <p>lisp让我着迷很久。理想的lisp语言应该是什么样子,其实发现shen语言时,已经找到了。只是去年我说谎了,说打算放弃lisp了。除非到达了或者永远达到不了了,否则怎么可能真的放得下?</p> <p>每个程序员都有一颗自己发明编程语言的心,希望创造一点什么。梦想像一颗不知什么时候播下的种子,在无意中慢慢的长大。经历了风雨,经历了日晒,没有夭折,这一切只是使它更加茁壮。</p> <p>现在亲手实现出来,终于得到解脱。嗯,最后的二个多月,想想一年又要一事无成,也算是有一点点慰藉。</p> <p>Another lisp? who cares? lisp注定只是那些天才的玩具,我能看清大势,就比如,语言的巴别塔应该在更高的层面上消除,我相信WebAssembly才是未来。但确实会遇到有许多有趣的东西,比如今年知道了逻辑学。至少对编程的兴趣不减。对我有意义,这就够了。</p> <h2>读到的最好的书《公正:该如何是好》</h2> <p>居然是在绿皮火车上,一个奇妙的夜晚读完的。福利/自由/德性,这本书里介绍三种不同的思想,对公正的探讨。辩证都很有深度,书中的例子也非常不错,强烈推荐。读完这本书再看《经济学原理》时,发现有不少共通的,可惜经济学原理没能在17年读完。</p> <p>书读太少,其它倒没什么值得写的。感觉该重启读书习惯了。这几年不经意发掘的一项潜能:专注的看书,读完一本书只需要几个小时到十几个小时。小说更快,像岩井俊二的《情书》,用不到二个小时。只是心里颇不宁静时,无法施展。</p> <h2>坚持的最好的习惯:背单词</h2> <p>讲个笑话,某次中午吃饭时玩手机,同事是在刷头条kill time,而我在逛知乎,我说他太low了,鄙视了他一把;后来某个中午,他跟我说改逛知乎了,我说已经不逛知乎了,把时间利用起来背单词了,又鄙视了他一把;许久以后,我自言自语,嗯,升级到逛quora了。</p> <p>从八九月份到现在,大概坚持了100多天吧。也就每天投入半个小时,还是用中午和下午吃饭在路上挤的时间,并不强求每天要背多少。后期还看一看《摩登家庭》。</p> <p>郁闷的是几个月前测试词汇量7000+,前几天测了一下才7300,背了后面忘掉前面。同事测着玩直接就7500,真想找块豆腐撞死。</p> <h2>最大的情绪波动:图拉的离开,还有十一青海湖</h2> <p>内心很少有什么情绪波动,或者说大部分时间都比较抑郁,偶尔比较狂燥(后来发现有个名词叫狂燥抑郁,fuck)。图拉是我为一只小刺猬取的名字,<a href="https://www.zhihu.com/question/28598281/answer/178174255">它不经意地来,又匆匆地走</a>。</p> <p>青海湖,似乎很早以前就在骑行目的地里面了。这次十一长假,终于还了一个愿。还是那一句,除非到达了或者永远达到不了了,否则怎么可能真的放得下?只是故事是始料未及的。</p> <p>如果能选择,这一切都不要发生,也不要有回忆。我会选择平静而强大,也不要循环着《偷故事的人》默默感伤。</p> <h2>还有好多的愿望</h2> <p>满怀期待的大多失望了。比如电影没看多少,反倒印象深刻的是某次闲逛,有个地方放老电影,看到《关于莉莉周的一切》,那种震撼。Being spontaneous。不经意的发生着。也许就是命运吧。</p> <p>我还有好多好多的愿望,未读完的书,未做完的事。许多可能会有趣的东西,世界语,摄影...所有的通往未知的路。只是 plan A 也许永远到达不了了。此时此刻 ----</p> <p>“站在时间的窄口,孑然一身,却无比勇敢”。</p> www.zenlife.tk/2017.md 2017-12-31T10:44:42Z 2017年终总结 2017-12-31T10:44:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>C 太底层了,写代码真的不舒服。不爽的地方之一是要手动管理内存,另一个是对象信息缺失。我们看一个例子,假设要实现一个 hash 表。</p> <pre><code>struct HashEntry { int key; int value; }; </code></pre> <p>如果我们希望是一个更通用的 hash 表。那么 hash 表的 key 和 value 应该是 <code>void*</code> 类型。一旦 key 是一个指针以后,我们就必须考虑内存管理。如果我们是一个浅拷贝语义,那么根据谁分配谁释放的原则,这块内存就应该是由外面去释放的。然而这里立马会遇到一个问题:如果 hashEntry 里面把 key 浅拷贝了一份,外面把那块内存释放了,这里就会出现悬挂指针(dangling pointer)。所以这里不能是一个浅拷贝语义。</p> <p>假设我们是一个深拷贝语义,会面临什么问题? 首先,对象的递归拷贝性能和实现上都是不靠谱的。需要所有的对象里面引用的对象,都实现一个clone的方法。其次是释放,有clone就要有释放,于是释放函数也要全部有。要释放两次,外面一次,在 hash 析构的时候还要做一次,把 entry 给释放掉,如果忘记了释放,就泄漏了。</p> <p>所以这里我们最好是一个move语义。一旦把 key value 放到 hash 里面之后,内存管理的归属就转到 hash 里面了。外部如果还持有,那也只是一个引用。我说过 rust 心智负担太重,从这个角度看是有一点不公正的。作用域/生命期/ownship,问题摆在那里,不管有没有制造那么多概念,手动管内存还是得考虑的。</p> <p>但是问题并没有完,如果 key 是简单的对象,比如 <code>char*</code>,我们只需要 free 就好了。而如果是复杂对象,它里面还引用其它的东西,那就需要有一个析构函数。最终这个 hash 会很丑:</p> <pre><code>typedef bool (*eq_func) (void*, void*); typedef int (*hash_func) (void*); typedef void (*free_func) (void*); void new_hash(eq_func, hash_func, free_func) </code></pre> <p>丑的原因是什么呢?根源之一是对象信息缺失,一个通用对象必须是 <code>void*</code> ,如何做 key 判等,如何得到一个 hash 值,如何释放对象,这些都必须额外提供。</p> <p>好,请今天的主角出场:fat pointer !</p> <p>fat pointer是用来解决对象信息问题的。它的基本原理是这样,分配一个对象出去时,故意在返回地址的前一个地址预留一个空间,也就是多分配一个指针的空间,在那里面放上对象类型信息。对象类型信息有点像 vtable。</p> <pre><code>var alloc(size_t data_size) { struct Header* head = calloc(1, sizeof(struct Header) + data_size); head-&gt;type = type; return ((var)head) + sizeof(struct Header); } </code></pre> <p>注意,使用 fat pointer 之后释放的时候,就不能直接释放原指针了,要把 free 的位置前移一个。这些东西可以封装起来,提供比较友好的库,<a href="http://libcello.org/">Cello</a> 已经这么干了。</p> <p>fat pointer 只是加入了额外的对象信息,但是并不会干扰普通的 C 代码,并不是强制使用,这一点还是很 neat 的。有了对象信息之后,实现通用的 hash 表,就友好多了。因为 <code>eq_func</code>,<code>hash_func</code>,<code>free_func</code> 那一堆东西都可以跟对象绑定到一起,少了很多维护负担。</p> <p>有了对象信息之后,在这个基础之上实现 GC 是不是一个好主意呢?我认为不是。在 C 里面实现 GC ,获取 <code>scan_root</code> 是比较 trick 的。另外,GC 需要对象信息。而如果在 fat pointer 对象里面混入了原生 C 对象,在 scan 遍历对象信息时就会 panic。像无论是 GC,或者是 coroutine,我认为这些东西最好丢到一个虚拟机层去做。但是真这么做也会涉及到另一个问题,托管内存跟原生内存的交互。</p> <p>托管内存跟原生内存的交互,只在需要的时候使用托管内存,不使用就不为性能买单。理想很美好,现实很骨感。</p> <p>这里需要一条约束:原生内存不能以任何形式去引用到托管内存。因为托管内存随时可能被 GC 掉,如果原生内存里面引用了,就可能出现悬挂指针了。我只发现了一门语言真正把这个事情做对了,就是 lua。做对是做对了,然而交互的时候 API 真的还是不太爽。shen-go 暂时不敢用 C 重写,担忧的点就包括这些。但是很多底层的东西,像threaded code,fixnum tagging用 Go 都是做不了的。</p> <p>Anyway,fat pointer 提供对象信息,这个想法是挺不错的。Cello 库使用基本功能,也是挺不错的。</p> www.zenlife.tk/fat-pointer.md 2017-01-07T11:14:42Z 在 C 里面使用 fat pointer 2017-01-07T11:14:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>刚刚给shen-go打上了v0.2版。从v0.1到v0.2主要做的是一些性能优化相关的事情,分享一些数据。</p> <p>最早的时候我实现了一个klambda解释器,那时跑shen的测试需要165s完成。</p> <p>在发布v0.1版的时候,实现了编译到bytecode,跑测试时间大概是25s的样子,从纯的解释器到未优化过的bytecode,大概是快了6倍多。</p> <p>接着就是v0.1到v0.2版做的事情,<a href="shen-go-optimize.md">前面有提到过</a>:</p> <p>vm的大幅改进,主要是将环境拆成堆上和栈上两部分,尽量地避免在堆上分配对象。加上vm那边一些细节上的优化,这块做了之后时间缩短到了16s。</p> <p>对hash函数做了 peephole optimizations,时间缩短到15.3s。</p> <p>接着对variable? integer? 等几个函数做 peephole optimizations 之后,时间缩短到13.9s。</p> <p>调整了 symbol 的表示,不再是string而直接记一个offset,比较就可以不用string比较。做了这个之后时间是12.5s。</p> <p>优化了函数调用,从map实现改到了直接数组offset获取,最终是11.6s。</p> <p>let的优化没做,peephole optimization还可以再彻底一些,感觉得如果做到极致,估计能就刚进10s的样子。</p> <p>threaded code 和 fixnum tagging 我尝试了一下,在Go语言里面都做不了。如果是换成 C 语言写vm,可以做这些优化,并且内存管理也做的更激进一些,我推测bytecode方式的极限可能在 7-8s。</p> <p>顺便分享一些 shen 在其它语言下实现的数据。</p> <p>shen-c 是完全基于解释器实现的,太挫了就不想说它了。</p> <p>shen-scheme 在 chibi-schem 下的实现,大概是22s的级别。这也是一个字节码实现,还是 C 语言做的,只比我 bytecode 未优化的时候略快一点,也算是挺挫的了。无节操的推测一下可能是scheme的异常处理机制拖累了它。</p> <p>shen-jvm 是直接编译到 JVM 的,速度大概在 4.几秒的样子。</p> <p>shen-cl 官方维护的版本,通过 common lisp 编译到 native 的实现,速度大概也是同样量级,4.5s。比 shen-jvm 慢一点点。</p> <p>shen-chez,这就是王垠说的世界上最牛的编译器,1.6s!还真是一个秒天秒地的版本,我算是领教了。</p> <p>F#看论坛上给的结果,好像都是10几秒的版本吧,Truffle 好像更慢一点。我没具体去测。不过如果编译到某个平台的虚拟机,比如.Net或者Graal,这结果还真是挺挫的。</p> <p>结论就是,bytecode大概就10-20s的量级了,做得非常有节操会进10s内。而JVM虚拟机这种带了JIT或者common lisp到native的大概就4s的级别。最牛B的chez吊打其它。</p> <p>shen-go 在基于 bytecode 实现里面已经最快的了。基本做不下去。弃坑弃坑</p> <p>供参考,以上。</p> <p>(最后,数据都有时效性,只是当下的比较,说不定哪个升级下变牛逼了,就不准确了。</p> <p>所以嘛,想知道准确的性能测试结果,这东西最好自己做)</p> www.zenlife.tk/shen-go-v0.2.md 2017-01-08T01:06:42Z shen-go v0.2发布:从165s优化到11s 2017-01-08T01:06:42Z Arthur http://www.zenlife.tk tiancaiamao@gmail.com <p>switch 在 Go 的编译器里面几乎没做过什么优化,性能还是挺低下的。</p> <p>写成这样子:</p> <pre><code>switch c { case 0: case 1: case 2: case 3: ... } </code></pre> <p>跟直接写成</p> <pre><code>if c == 1 { } else if c == 2 { } else if c == 3 { } </code></pre> <p>就没啥太大区别。</p> <p>也不能责怪编译器蠢,毕竟 Go 语言里面还要支持像 string 类型,支持表达式,以及像这种</p> <pre><code>switch c.(type) </code></pre> <p>C 语言里面 switch 语句是会优化成跳转表的,比较高效。</p> <p>可以考虑换种写法,</p> <pre><code>var jumpTable []func(){} // 把各个case要做的事情做成函数放到一张表里 f := jumpTable[c] // 直接通过case id找到对应的函数 f() // 并跳转去执行 </code></pre> <p>我测试了一下 Go 的 switch 到底有多么低效,case 稍多,放了32个。</p> <p>https://gist.github.com/tiancaiamao/28fd53ff9b29eaac30f84b4ba04e2e7e</p> <p>对比的结果是:</p> <pre><code>switch cost: 70.476µs jumt table cost: 9.065µs </code></pre> <p>大部分时候没有写那么多switch case的需求,但是有一个场景还是会用到,就是 interpreter。在 C 里面可以做 threaded code,在 Go 里面做不了。我还是希望做出 Go 能达到的最佳优化,于是把 shen-go 的指令分发从 <a href="https://github.com/tiancaiamao/shen-go/commit/92ae53e4555a09a215e9546ade466d682195906e#diff-89570c464637c8d662a375fdd8f47b90L145">switch方式</a>切换到了 <a href="https://github.com/tiancaiamao/shen-go/commit/92ae53e4555a09a215e9546ade466d682195906e#diff-89570c464637c8d662a375fdd8f47b90R149">jump table</a>。</p> <p>结果很今人失望,性能反而下降了。分析原因,主要是 swtich 的写法可以充分利用到函数内联,比如</p> <pre><code>switch c { case opPrimCall: primCall() case opPop: stackPop() } </code></pre> <p>这里面的primCall和stackPop这些都是可以inline的,而jump table由于函数地址是动态获取的,利用不到编译器的inline优化。</p> <pre><code>vm.code[vm.pc](vm) </code></pre> <p>相当于节省了switch定位具体哪一条操作的开销,却引入了额外的函数调用开销。</p> <p>有没有什么方法能够既不使用低效的 switch,又能充分利用到函数内联呢?</p> www.zenlife.tk/go-switch-statement.md 2017-01-13T21:24:42Z switch在Go语言的性能 2017-01-13T21:24:42Z