10
3
2019
6

红黑树到底是个什么树

红黑树使用得非常多,然而由于它不在我的本科教材上,我又不用自己实现它,所以我一直不知道它是什么样的。现在想了解一下,结果发现网上我看了好几篇的中文资料都是这种介绍方式——

假设要介绍的树叫梧桐树。文章会告诉你梧桐树会长多高,树叶长什么样,分叉有什么特征,它和棕榈树有什么不同,还会贴心地放一张或者多张梧桐树的照片给你看。

然而红黑树不是梧桐树啊!计算机科学也不是植物学啊!它是为特定目的人造的!所以你倒是说说它为什么会被设计成这个样子啊……

然后我去看了一眼英文维基百科上的介绍,才看了第一段就恍然大悟。

A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

意思是,红黑树是一种自平衡二叉树。每个节点有一个额外的比特,通常叫它颜色,并且是红的或者黑的。所以红黑树之所以叫红黑树,只是发明者为了方便叙述给加了点颜色,就跟数学里那些个着色问题(以及物理里夸克的颜色和味道)一样。为什么要加这些颜色呢?它们是用来保证树大致平衡的。

神奇了,为什么加了这么个颜色就能保证了?

Balance is preserved by painting each node of the tree with one of two colors in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

哦,是用特定的方法着色的,并且树被修改的时候会重新着色。神奇的算法使得这些操作非常高效。也算是用空间换时间了。

The leaf nodes of red–black trees do not contain data. These leaves need not be explicit in computer memory—a null child pointer can encode the fact that this child is a leaf—but it simplifies some algorithms for operating on red–black trees if the leaves really are explicit nodes.

红黑树的叶子节点总是黑色的,并且不包含额外的信息。所以实现的时候实际上不需要显式地存在,或者用同一个节点就好。它的存在只是为了简化算法描述而已。

红黑树的性质:

  1. 每个节点不是红色就是黑色。多出来一比特的信息,当然只有两种选择了。
  2. 根节点是黑色。
  3. 叶子节点是黑色。
  4. 红色节点的子节点是黑色。这是为什么非要加个不包含任何信息的黑色叶子节点了。不然弄出来红色叶子节点有点麻烦了。
  5. 任意节点到它下方的叶子节点,路径上的黑色节点数是相同的。再一次体现了黑色叶子节点的用处。

这些性质保证了,从根节点到所有叶子节点,最远的路径最多是最近的路径两倍远。不会特别远,甚至是退化成链表了。

然后是树上的操作。

查找就不用说了。二叉树的查找算法而已。

插入的时候,首先把新节点涂成红色,按二叉树的方式插进去,取代某个叶子节点,并自己长出两片叶子。然后修复一下。修复方案如下:

  1. 如果这是个根节点,那么涂黑就完事了。
  2. 如果它的上级节点是黑色,黑色节点下接红色节点,没事,不需要更多操作了。
  3. 如果它的上级节点是红色,并且它的上级邻节点是红色,这就坏事了,违反了性质4。那就把它们涂黑。可这样多了一层黑节点,又会违反性质5。那就把上上级节点涂红(由性质4,上上级节点之前肯定是黑色)。可如果上上级节点是根节点,又违反了性质2。不过上上级节点带的这部分子树肯定是没问题的,那就把整个上上级节点带的这棵子树当整体,递归修复一下好了。
  4. 如果它的上级节点是红色,并且它的上级邻节点是黑色,这还是破坏了性质4。而这个时候如果把上级节点涂黑,那么上上级节点不管涂不涂红,一边加了一个黑节点而另一边没有加,它这个子树本身就已经坏掉了,所以得想另外的办法。
    1. 第一步,如果上级节点在左边,而新加节点在右边,那就左旋。如果上级节点在右边,而新加节点在左边,那就右旋。其它情况不用动。由于是两个上下级红色节点在旋转,这样并不会再破坏任何性质。
    2. 第二步,两个红色节点和可以被取代的叶子节点已经准备好了,现在把上上级节点(也就是动过的子树的上级节点)用子树的根换掉,原来的挂到上一步空出来的叶子节点那里,并且把新根涂黑,把一开始那个碍事的黑色节点涂红。这样,两个红色节点就成了同一个黑色节点的子节点。性质4得到了保持,涂色过程只是把黑色上移取代之前的红色,一边的路径上少了个红色节点,另一边多了个红色节点而已,也不会破坏性质5。

删除就更复杂了。

  1. 如果被删除的节点有两个非叶子节点,按二叉树的方法删除节点,但是保持原来这个位置上节点的颜色。因为子树的根被保留颜色地替换了,所以这一步不会破坏性质。而少了的(被作为新子树根替换的)节点,递归这个删除算法就可以了,一直在深入,总能递归到没有两个非叶子节点的节点。
  2. 你不会想删叶子节点,也不能删它们。
  3. 所以剩下一种情况:被删除的节点最多有一个非叶子子节点。如果有的话就叫它 C 好了,没有就随便找个叶子节点当 C。那被删除的节点我们叫 M。
    1. 如果 M 是红色,那用 C 取代它即可。因为 C 肯定是黑色(而且是叶子节点)。
    2. 如果 M 是黑色,但 C 是红色,用 C 取代 M,并且把 C 涂黑。少了一个红色节点而已,没事的。
    3. 如果 M 和 C 都是黑色,这个时候 C 也一定是叶子节点。先用 C 取代 M,并叫新的 C 为 N,其上级节点为 P,P 的另一个子节点为 S。现在 N 这边少了个黑色节点,相对的,S 这边多了一个。
      1. 如果 N 是根节点(P 不存在),那么没事了。
      2. 如果 P 是黑色,并且 S 是红色,旋转一下,让 S 成为新的子树的根,并将 P 涂红。从颜色上看,只是红色从一个子节点跑到另一个,然后有棵子树从一边换到另一边了,性质不会被再度破坏。但之前被破坏的部分还没修复呢,现在是一个黑色下边有一个黑色的节点那里的路径上多了一个黑色节点,要走下边的步骤。
      3. 如果 P 和 S 都是黑色,N 那边不是被删掉了一个黑色节点吗,现在把 S 涂红,这样 P 的两边(N 和 S)都少了个黑色节点。子树没有问题,然而 P 这边的路径上少了个黑色节点。要么 P 是根节点,不用管了。要么 P 的邻节点那边的路径多了个黑色节点,情况就是一个子树,下方有一个黑色节点,并且这一边的路径上多了个黑色节点。如果子树的根是黑色,那么递归了,回去再走一遍上一步(3.3.2)就好。如果是红色,走下边的步骤。
      4. 如果 P 是红色,并且 S 和 S 的子节点都是黑色,把 P 和 S 的颜色交换一下,S 那边的路径少了个黑色节点,处理好了。
      5. 如果 P 是红色,N 位于左侧,并且 S 的左子节点是红色,右子节点是黑色。N 当然是黑色的啦。那么把 S 右旋,并且把旧 S 的左节点(新的子树根)涂黑,然后旧 S 自己(新右子节点)涂红。继续下边的步骤。
      6. 如果 P 是红色,N 位于左侧,并且 S 的左子节点是黑色,右子节点是红色,把 P 左旋一下,并把之前那个红色子节点涂黑。这样 N 那侧的路径多了个黑色节点。完成了。
      7. 如果 P 是红色,N 位于右侧。把上两步镜像一下就可以了。

总之就是各种涂色和旋转,来保持二叉树和红黑树的性质不被破坏(红黑树是二叉树,所以旋转需要点技巧,不是想旋转就一定能旋转的)。看着复杂,照着前人已经想好的步骤去做其实也并不难。然而中文网络上几乎没有人解释这些步骤的目的,以至于让人理解不能 :-(

Category: 编程 | Tags: 算法 编程
9
9
2019
6

gdb 不肯加载调试信息怎么办?

更新完 buster,我的 morerssplz 崩了好几次了。第一次收到 Grafana 的通知时还以为出什么大事了呢,结果只是进程崩了。

这只 Debian 没有安装 systemd-coredumpctl 所以手动 ulimit -c unlimited 搞到了个 coredump。可随后问题来了:

(gdb) bt
#0  0x00007f9a5bd8b013 in ?? ()
#1  0x00007f9a5bd8bcfa in ?? ()
#2  0x0000000002bdb890 in ?? ()
#3  0x0000000000000000 in ?? ()

啥也没有?

我安装了 python3-dbg 啥的,它还是如此显示,以至于我一度认为 Debian 的 python3-dbg 包只包含调试版本的 Python 而没有 python3 包对应的调试信息。后来才发现不是这样的,因为直接加载 python3 是会读调试信息的:

>>> gdb python3
...
Reading symbols from python3...Reading symbols from /usr/lib/debug/.build-id/66/44f05b3a3ab9727ecee55c58681bc43b94d92e.debug...done.

然而 gdb 读这个 coredump 的时候压根就没尝试读取……即使我使用 symbol-file 命令加载了 python3 的调试信息也依旧如此。以至于我还以为函数调用栈被破坏了,但我越看越是感觉不像。

后来看到一个命令——sharedlibrary,让 gdb 加载动态链接库的调试信息的。这个也执行之后,终于能打出完整的调用栈了!

所以就是这程序崩在了动态链接库里,而 gdb 太懒根本不肯自动加载相关的调试信息,所以才什么都看不到的。

Category: 编程 | Tags: gdb
4
4
2019
4

系统在解析哪些域名呢?

最近用 Rust 写了个叫 capture-dns 的小程序,实时显示 DNS 查询结果的。配合 ipmarkup 的效果是这样的:

>>> sudo capture-dns lo | ipmarkup
[sudo] lilydjwg 的密码:
github.com -> 52.74.223.119(新加坡Amazon数据中心)
github.com -> 13.229.188.59(新加坡Amazon数据中心)
github.com -> 13.250.177.223(新加坡Amazon数据中心)
live.github.com -> 192.30.253.125(美国弗吉尼亚州阿什本GitHub)
live.github.com -> 192.30.253.124(美国弗吉尼亚州阿什本GitHub)
collector.githubapp.com -> 34.193.248.191(美国弗吉尼亚州阿什本Amazon数据中心)
collector.githubapp.com -> 52.20.29.9(美国弗吉尼亚州阿什本Amazon数据中心)
collector.githubapp.com -> 34.197.57.23(美国弗吉尼亚州阿什本Amazon数据中心)
api.github.com -> 13.250.94.254(美国Amazon数据中心)
api.github.com -> 13.250.168.23(美国Amazon数据中心)
api.github.com -> 54.169.195.247(新加坡Amazon数据中心)
ocsp.digicert.com -> 117.18.237.29(澳大利亚美国MCI通信服务有限公司(韦里孙商业Verizon Business)EdgeCast亚太网络CDN节点)

可以看到本地的软件们都在查询哪些域名,得到的 IP 又是什么。抓取的是应答,所以没得到 IP 结果的不会显示。我抓取的是 lo 网络接口,因为我本地有用 dnsmasq 做缓存。

其实这个程序一开始不是这样子的。群里有人想抓取系统上进行的 DNS 查询的域名。一开始是用 tshark 抓取的,然而它太占用内存了。我粗略看了一下 Python 的 scapy 工具,也用掉了大几十M内存。那么,用 Rust 写一个好了,也顺便练习一下 Rust。

这个程序运行时只有几M的内存占用,CPU 占用也是非常低的。不过它并没有做完全的协议分析,而是假设抓得的包是以太网帧封装的 IPv4 报文封装的 UDP 数据包里包着 DNS 应答报文。所以如果你是在 eth0 上跑 PPPoE 的话,抓 eth0 上的包就不行了,得抓 ppp0 这种了。当然你要是 IPv6 啊 DoH、DoT 啥的就更抓不到了。

后来我用 bcc 的 tcpretrans 脚本查看我这里到哪些地方的 TCP 连接不太通畅,然而经常会看到一些我猜不到是干嘛的 IP。所以就把这个程序改了一下,把域名对应的解析结果显示出来了。

Rust 不仅节省资源,而且开发的体验真的很棒呢,编译成功之后就能按我预期的运行了。也不用担心什么时候遇到个有问题的报文导致程序崩掉,因为写的时候就已经处理好了出错的情况。不像 Python 写的脚本,刚写好,一跑就抛个异常出来,提示我哪里不小心写错了。好不容易调试好了,跑着跑着,遇到意外情况就挂掉了……

Category: 编程 | Tags: Rust linux 网络 DNS
6
14
2018
3

递归遍历目录:Python vs Go vs Rust

群友提出了一个简单的任务:递归遍历一个很大的目录,根据文件名数一下有多少 JPEG 文件。怎么最快呢?然后他用了 Go 语言实现。

我忽略想起 Python 3.5 的 What's New 里提到,他们优化了 os.scandir 使得目录遍历快了好几倍(PEP 471)。其核心思想是:不进行不必要的 stat 系统调用,因为读目录获得了不少信息,原来都是丢弃掉了,现在改成了通过 DirEntry 对象来返回。这些信息包括文件名等,刚好有我们需要的。

于是 Go 做了这个优化没有呢?

翻了一下代码。Go 自带的实现位于 src/path/filepath/path.go 文件中。可以看到,它对每一个文件都 lstat 了。后来一阁指出,不仅如此,而且它还莫名其妙地对目录下的文件名进行了排序

呃,前者可以说是疏忽了,毕竟 Python 也是直到 3.5 才优化的。可是,它排那个序干嘛呢……

然后我又想到,Rust 那边如何呢?

结果是,Rust 对它所包含的东西非常审慎,标准库里并没有递归遍历目录的函数。那我们自己写一个?才不呢,用第三方库啦!可以看到,它也是返回 DirEntry 对象的。

后来了解到,Go 也有一个第三方的实现 godirwalk,对这些细节进行了优化。

光是了解实现不够。我们让它们来比试一下吧。顺便,把 find 和 fd 也拖进来好了。

任务:数一数一个拥有近万文件的目录下有多少 JPEG 文件。

实现代码:walkdir-test

结果:

   Rust: top:    4.78, min:    4.72, avg:    4.90, max:    5.46, mdev:    0.17, cnt:  20
 Go_3rd: top:    7.71, min:    7.64, avg:    7.79, max:    8.41, mdev:    0.16, cnt:  20
   find: top:   11.49, min:   11.32, avg:   11.76, max:   14.18, mdev:    0.59, cnt:  20
     fd: top:   18.17, min:   15.18, avg:   21.29, max:   29.94, mdev:    3.84, cnt:  20
     Go: top:   21.08, min:   20.91, avg:   21.28, max:   22.70, mdev:    0.37, cnt:  20
 Python: top:   29.66, min:   29.51, avg:   30.43, max:   35.84, mdev:    1.45, cnt:  20
Python2: top:   30.37, min:   30.10, avg:   30.85, max:   33.15, mdev:    0.75, cnt:  20

Rust 如预期一样是最快的。Go_3rd 就是那个第三方库的实现,也非常快的。fd 是 Rust 实现的,目标之一是快,但是这次并没有比老牌的 find 快。Go 自带的那个实现,十分令人遗憾地连 find 都没比过呢,不过还是比 Python 快了不少。Python 2 这次终于没有跑在 Python 3 前边了(虽然差距很小),我猜是 PEP 471 那个优化的功劳。

对了,还有代码行数:

  15 Python/walk
  29 Rust/src/main.rs
  30 Go/walk.go
  33 Go_3rd/walk.go

Rust 竟然不是最长的。不过确实是字符数最多的。

话说 Go 的 } 竟然也是有规定的,结构体的不能另起一行写,只能跟 Lisp 的风格那样堆在一行的尾巴里。

PS: 没想到之前给 swapview 写的 benchmark 程序在另外的项目里用上了呢,果然写东西还是通用些的好。


更新:在群友的提示下,我找了一个更大的目录来测试,结果很不一样呢。这次遍历的目录是 /usr,共有 320397 个文件。

     fd: top:  265.80, min:  259.84, avg:  273.89, max:  319.76, mdev:   15.03, cnt:  20
   Rust: top:  269.98, min:  266.86, avg:  272.82, max:  282.84, mdev:    4.17, cnt:  20
 Go_3rd: top:  361.17, min:  359.05, avg:  363.82, max:  370.22, mdev:    3.31, cnt:  20
   find: top:  454.03, min:  450.79, avg:  458.51, max:  467.31, mdev:    5.08, cnt:  20
 Python: top:  624.80, min:  615.73, avg:  630.67, max:  640.88, mdev:    6.79, cnt:  20
     Go: top:  890.03, min:  876.98, avg:  910.63, max:  967.14, mdev:   24.84, cnt:  20
Python2: top: 1171.38, min: 1157.19, avg: 1189.99, max: 1228.09, mdev: 4186.28, cnt:  20

可以看到,唯一的并行版本 fd 胜出了~Rust 版本紧随其后,显然在此例中并行并没有多么有效。Go_3rd 还是慢于 Rust 但也并不多。然后,经过优化的 Python 终于在更大的数据量上明显胜过了 Go 以及 Python 2 这两个浪费了很多系统调用的版本。

Category: 编程 | Tags: python go 编程语言 Rust
7
14
2017
12

swapview 更新

距离上一次 swapview 的更新已经一年多了。在这段时间里,不少语言有了比较大的更新,所以再跑一次。

首先是运行不了或者有问题的语言和实现:

  • Julia: 新版本不向后兼容,运行不了。求修
  • Nim: 标准库有些函数的行为有改变:walkFiles 不再返回目录文件,split 不再将连续的空白符作为一个分隔符。
  • Erlang: 不再支持 ~.0f 格式化字符串。

其中不向后兼容的,Julia 和 Nim 还没到达 1.0 版,所以坑人了也就坑了。Erlang 不知道是怎么回事。

然后是有警告的:

  • R: 文件打开失败有警告。不是大问题,不过有点烦。如果你知道怎么去掉它,请告诉我。
  • Elixir: 函数无参调用时不加括号会触发警告。看来 Elixir 也不喜欢 Ruby 函数调用不加操作的行为了呢。

还有发行版的锅:

  • CSharp: mono 与 chicken 冲突,无法安装,所以跑不了。
  • Haskell: Arch Linux 不再支持静态链接了。需要改一下编译参数。

我还对代码做了一些改进:

  • Rust_parallel: 用 rayon 换掉了 threadpool。rayon 更适合这种并行任务处理。另外稍微改进了一下代码。
  • NodeJS: 使用 ECMAScript 6 语法(箭头函数和 const / let 变量声明)。去掉不必要的分号。
  • C: 支持 Android 平台。
  • 修正了一些实现的格式化输出(还剩下一些)。

最后结果如下。因为 CPU 换成了 i7-7700HQ,所以耗时都比之前少了不少。另外注意,前排几名只有前三名都是多线程的,所以 Go_goroutine 比那些 C 和 C++ 版本快很正常。

           Rust_parallel: top:   30.48, min:   27.76, avg:   32.48, max:   37.80, mdev:    2.78, cnt:  20
               C++98_omp: top:   31.24, min:   29.04, avg:   34.42, max:   49.48, mdev:    4.52, cnt:  20
            Go_goroutine: top:   68.30, min:   61.87, avg:   75.89, max:  142.91, mdev:   16.39, cnt:  20
                   C++14: top:   83.17, min:   82.23, avg:   84.71, max:   92.58, mdev:    2.76, cnt:  20
             C++14_boost: top:   83.58, min:   83.20, avg:   84.58, max:   91.00, mdev:    1.72, cnt:  20
                   C++98: top:   83.71, min:   83.09, avg:   85.19, max:   91.48, mdev:    2.44, cnt:  20
                    Rust: top:   91.45, min:   90.81, avg:   93.08, max:   99.38, mdev:    2.07, cnt:  20
                       C: top:   91.49, min:   90.49, avg:   93.41, max:   99.44, mdev:    2.53, cnt:  20
                   C++11: top:   91.81, min:   91.33, avg:   93.52, max:  102.80, mdev:    3.04, cnt:  20
                     PHP: top:   93.91, min:   93.37, avg:   94.98, max:   99.42, mdev:    1.47, cnt:  20
                   OCaml: top:  106.85, min:  105.75, avg:  109.34, max:  118.03, mdev:    3.37, cnt:  20
                     Nim: top:  109.28, min:  108.44, avg:  110.75, max:  117.43, mdev:    2.13, cnt:  20
         D_parallel_llvm: top:  111.25, min:  109.43, avg:  113.21, max:  117.26, mdev:    2.33, cnt:  20
              D_parallel: top:  116.77, min:  114.69, avg:  118.95, max:  125.45, mdev:    2.87, cnt:  20
                    PyPy: top:  126.23, min:  124.29, avg:  128.34, max:  134.07, mdev:    2.79, cnt:  20
                  D_llvm: top:  129.63, min:  128.52, avg:  131.32, max:  137.65, mdev:    2.41, cnt:  20
                  LuaJIT: top:  132.68, min:  131.31, avg:  134.36, max:  143.07, mdev:    2.57, cnt:  20
                      Go: top:  135.57, min:  132.37, avg:  139.25, max:  148.37, mdev:    4.50, cnt:  20
                       D: top:  146.30, min:  145.00, avg:  149.14, max:  159.02, mdev:    3.85, cnt:  20
                Haskell2: top:  150.92, min:  149.41, avg:  153.25, max:  164.60, mdev:    3.53, cnt:  20
                 Python2: top:  155.36, min:  152.26, avg:  158.55, max:  170.20, mdev:    4.60, cnt:  20
                    Vala: top:  159.55, min:  157.87, avg:  161.40, max:  166.52, mdev:    2.26, cnt:  20
                  Erlang: top:  163.00, min:  158.63, avg:  168.76, max:  181.77, mdev:    7.09, cnt:  20
                   Lua51: top:  166.58, min:  164.58, avg:  168.89, max:  181.71, mdev:    3.69, cnt:  20
                   Lua52: top:  168.48, min:  167.40, avg:  170.82, max:  178.11, mdev:    3.36, cnt:  20
           Python3_bytes: top:  174.30, min:  172.65, avg:  176.83, max:  181.64, mdev:    2.91, cnt:  20
                   Lua53: top:  180.20, min:  177.79, avg:  185.01, max:  199.41, mdev:    6.07, cnt:  20
                    Perl: top:  180.22, min:  177.30, avg:  182.21, max:  186.09, mdev:    2.44, cnt:  20
              FreePascal: top:  180.85, min:  179.35, avg:  184.23, max:  197.83, mdev:    4.84, cnt:  20
                 Python3: top:  181.72, min:  178.47, avg:  184.09, max:  189.67, mdev:    2.99, cnt:  20
                    Ruby: top:  199.82, min:  197.16, avg:  203.62, max:  218.32, mdev:    4.92, cnt:  20
                 Chicken: top:  234.69, min:  232.11, avg:  239.61, max:  248.39, mdev:    5.63, cnt:  20
             PyPy3_bytes: top:  238.55, min:  237.18, avg:  242.08, max:  253.68, mdev:    4.53, cnt:  20
                   Guile: top:  254.49, min:  249.14, avg:  260.40, max:  275.83, mdev:    7.12, cnt:  20
              ChezScheme: top:  265.63, min:  262.52, avg:  268.56, max:  278.53, mdev:    3.94, cnt:  20
                    Java: top:  291.35, min:  283.94, avg:  302.36, max:  324.82, mdev:   12.38, cnt:  20
                  NodeJS: top:  317.01, min:  314.61, avg:  321.04, max:  332.05, mdev:    4.71, cnt:  20
                    Dart: top:  329.39, min:  325.63, avg:  334.57, max:  351.19, mdev:    6.92, cnt:  20
           Ruby_rubinius: top:  359.76, min:  357.74, avg:  363.13, max:  373.02, mdev:    4.45, cnt:  20
          CommonLisp_opt: top:  360.57, min:  358.41, avg:  365.15, max:  378.44, mdev:    5.76, cnt:  20
                     Tcl: top:  367.38, min:  363.28, avg:  372.89, max:  388.57, mdev:    6.65, cnt:  20
          CommonLisp_old: top:  376.27, min:  371.99, avg:  379.66, max:  390.55, mdev:    4.33, cnt:  20
                   PyPy3: top:  384.12, min:  376.60, avg:  390.16, max:  401.39, mdev:    7.32, cnt:  20
            CoffeeScript: top:  414.40, min:  393.13, avg:  432.25, max:  466.42, mdev:   20.64, cnt:  20
   CoffeeScript_parallel: top:  451.12, min:  425.11, avg:  464.92, max:  491.52, mdev:   17.05, cnt:  20
            NodeJS_async: top:  454.78, min:  437.13, avg:  465.18, max:  489.06, mdev:   13.02, cnt:  20
         Racket_compiled: top:  510.97, min:  505.22, avg:  516.20, max:  527.69, mdev:    6.23, cnt:  20
                  Racket: top:  520.70, min:  515.11, avg:  525.28, max:  533.79, mdev:    5.87, cnt:  20
         NodeJS_parallel: top:  673.38, min:  664.38, avg:  687.60, max:  724.04, mdev:   16.32, cnt:  20
                   Scala: top:  719.27, min:  698.23, avg:  740.32, max:  815.95, mdev:   27.27, cnt:  20
           Bash_parallel: top:  769.14, min:  751.56, avg:  775.91, max:  791.40, mdev:    8.82, cnt:  20
                 Haskell: top: 1036.33, min: 1013.27, avg: 1048.70, max: 1090.21, mdev: 4186.25, cnt:  20
                  Elixir: top: 1097.32, min: 1075.24, avg: 1113.36, max: 1144.80, mdev: 4186.26, cnt:  20
                       R: top: 1141.37, min: 1120.69, avg: 1156.42, max: 1177.79, mdev: 4186.26, cnt:  20
                    Bash: top: 1368.00, min: 1323.22, avg: 1479.66, max: 1994.19, mdev: 4077.71, cnt:  20
              POSIX_dash: top: 1841.09, min: 1833.25, avg: 1851.09, max: 1881.68, mdev: 3897.64, cnt:  17
               POSIX_zsh: top: 2124.79, min: 2110.81, avg: 2134.32, max: 2156.40, mdev: 3841.56, cnt:  15
              POSIX_bash: top: 2200.64, min: 2195.09, avg: 2206.75, max: 2221.41, mdev: 3807.09, cnt:  14
                  CSharp: FAILED with entity not found
                   Julia: FAILED with entity not found

对比旧结果,可以看到有一些比较大的变化:

Rust 快了不少,并行版一跃成为最快的实现。C++98 OpenMP 版紧随其后。Rust 单线程版也上升了四名,与 C、C++ 版本接近,并超越了所有的 D 实现。Go 并行版也提升了不少,位居第三,但它花费的时间比前两名所花费时间的总和还要多……并且结果也不是很稳定(标准差比前二十名都要大不少)。

Nim 慢了不少,可能是因为没字符串分割函数可用,我改用了 pegs。这东西很慢的样子,也许正则还会快一点……C 也落后了一些,但是与 C++ 版本的差距不大。Haskell 大概是因为改用动态链接的原因,慢了少许。

PyPy 快了很多,竟然超越了 LuaJIT。Erlang、Guile、Rubinius 也都大幅上升,而 NodeJS 不知道怎么了,全面落后于 Python、Ruby、Lua。PHP 更新到 7 之后依旧非常非常快。

完整的排名变化可以看这里

Category: 编程 | Tags: go 编程语言 Rust
5
31
2017
7

换用 Rust 解析 pcap:快了1000倍!

前天手上有个VPS的提供商发来通知,说VPS在攻击别人的80端口,被第三方投诉了-_-|||

我跑上去看了好久,啥也没发现。进程列表、登录日志、网络使用、各服务我能找到的日志都检查了一遍,也跑了遍 dpkg --verify,啥也没发现。没办法,我就留了句 tcpdump 命令,看看能不能抓到那些恶意流量:

sudo tcpdump -vv -s0 -w port80.log '(dst port 80 and src host 123.456.789.0) or (src port 80 and dst host 123.456.789.0)'

盯了好久,一直只看到有零星的正常访问。

就这么放了一天。第二天想起来的时候过去一看,哇塞,抓到了 2.1G 的包!看来真出问题了。先分析一下得到的 pcap 文件吧。

这么大的 pcap,自然不能拿 Wireshark 打开了。我知道 scapy 能够读取 pcap,于是用它读取 pcap,收集另一方的 IP 地址,看看流量到底都去哪里了。代码很简单,20多行。跑起来~progress 告诉我需要半小时……

于是半小时过去了。我能看到它访问了不少IP,很多是意料之外的。我就想,这些流量是什么时候发生的呢?不过我可不想再花半小时等结果了。然后再想得到点别的数据又得半小时。而且 Python 这种动态类型的语言,稍微复杂一点之后就容易抛异常。说不定快跑出结果的时候,抛个异常出来,前边就全白跑了……

所以就试试 Rust 啦。去 docs.rs 上一搜,还有好几个可以解析 pcap 的库呢。那就第一个吧,叫「pcap」的这个。程序写起来也挺容易的,甚至代码行数都跟 Python 版相仿。时间的处理也是用了一个之前没用过的库「chrono」。并没有花多长时间,直接在文档里找到我需要的功能,然后编译通过就成了 O(∩_∩)O~

extern crate pcap;
extern crate chrono;

use std::collections::BTreeMap;
use chrono::prelude::*;

fn main() {
  let mut capture = pcap::Capture::from_file("../port80.log").unwrap();
  let mut distribution = BTreeMap::new();
  while let Ok(pkt) = capture.next() {
    let t = pkt.header.ts.tv_sec;
    let by_hour = t / 3600 * 3600;
    let dt = Local.timestamp(by_hour, 0);
    *distribution.entry(dt).or_insert(0) += 1;
  }

  for (t, c) in distribution {
    println!("{}: {:8}", t.format("%Y-%m-%d %H:%M"), c);
  }
}

然后花了几秒编译出来优化版本的程序,跑起来~然后我切换到另一个 shell 去跑 progress。啥,没找到进程?再回来一看,哦哦,已经跑完了!只花了一两秒!

这是一千倍的差别啊!虽然两个程序所做的事情并不一样,比如 Python 版用的 scapy,实际上会把整个网络包的各层协议都给解析了,而不像 Rust 版只解析了 pcap 的记录头。但是我又没有别的选择,就像我也不能让 Python 别管引用计数一样。

对于这种小任务,Python 还是强在对少量数据的交互操作,比如 Jupyter Notebook 就很强大。而数据量一旦大起来,就是 Rust 的天下了 :-)

Category: 编程 | Tags: Rust tcpdump
1
6
2017
3

如何快速高效地修 bug?

看到知乎上的一个问题,心血来潮,随意写写,请读者不要太较真。

看回答,有一些可操作性很强的答案。但是呢,你知道的,考试好不代表能力强,如果你只是学习别人的方法而并不理解,那么学来之后只会是东施效颦而不能融会贯通。所以呢,我也来发表一下自己的见解。

首先,你要定位 bug。这时,你需要:

  1. 注重逻辑性。不要做没有证据的结论。如果你有猜测,就去证实或者否定它。比如某次,同事代码返回的数据有问题,认为是缓存用的 Redis 有问题,返回了错误的数据。然而没人去对此猜测进行求证……我去确认了一下,Redis 收到了请求,并且响应正常。接下来,排除所有其它可能的原因之后,最后剩下的那个就是真相。真相就是,代码里有个 } 的位置放错了,因为它刚好在一屏之后的位置,所以没有人发现……(是 Vim 帮我找到的)
  2. 基本的方法论。比如二分法。比如最小化测试用例。如果你要提问,要懂得提问的智慧,不管是向搜索引擎还是向人,你都需要提出正确的问题
  3. 知识面。你写 Web 后端的话,普通的 HTTP 得懂,浏览器的开发者工具得会用。简单的 JavaScript 也有会点儿。简单地说就是,你要精于你自己主攻的部分,然后要熟悉你的上下游。再比如如果你使用 CPython 的话,你要准备一份 CPython 的源码,并且要能够流畅地阅读 C 代码。
  4. 工具。工欲善其事,必先利其器。一大堆调试用的工具,你至少得知道它们能干什么,需要的时候能用。比如 strace、lsof、gdb、git bisect,还有高级点的 sysdig、systemtap、perf 等等。当然还有一堆不是专门为调试而设计的通用工具,比如 the silver searcher 或者 ripgrep。一个快速的全文搜索工具能帮你在最短时间内找到相关的代码或者日志。你不必成为正则表达式大师,但是简单的一定要会,不然面对上千个匹配结果你要怎么办呢?Vim 有一个插件 Mark,能够同时高亮多个模式,非常利于调试期间阅读代码和日志。投入时间学习使用高效的工具,不要把时间浪费在等待和人工搜索上,也不要让自己忙于琐事而断了灵感和线索。

最后,不要不断地、毫无目的地换个环境啦,换个版本啦,换个用户啦,这样子找问题。如果这样做很有效的话,大家都去买彩票去了。

找到 bug 之后,理解它是如何产生的。当你理解之后才能真正修好它。就像你感冒了吃抗生素,根本没有用。

Category: 编程 | Tags: 编程 软件开发
2
6
2015
19

小谈 Rust

最近很火的 Rust 前不久发布了 alpha 版。正式版虽不说指日可待(还在各种大改中),但是也不是那么遥远了。而经过了这么久,再见 Rust,感觉完全不一样呢。

还记得第一次见 Rust,是在 Fantix 的博客上。现在只记得当时看到各种~和生命周期的东西,挺头疼的。而这次是看到 Rust for beginners 以及已经被合并到《The Rust Programming Language》这本书的官方 guide。感触很容易概括:「一门实用的类 Haskell 语言,是我很早就想要的东西呢。」于是才有了我的第一个 Rust 程序,以及后来的 各种语言实现的 swapview

当然后来事实证明 Rust 不仅仅有着与 Haskell 类似的代数数据类型,比如有表示空的 unit 类型、表示可选的 option 类型、用于返回结果或错误的 Result 类型。作为一名曾经苦学 Haskell 还折腾过 OCaml 的人,看到这些熟悉的类型,感到甚是亲切。这种类型系统最大的特点是类型安全、没有 null 指针/类型。

我接触到的绝大多数编程语言,都会有 null 指针,或者 null / none / nil 类型:

  • C、C++:「Segmentation fault」
  • Java:还记得经常在日志里露脸的「NullPointerException」吗
  • Python:一不小心就会出现的「AttributeError: 'NoneType' object has no attribute 'xxx'」
  • Lua:「attempt to index global 'xxx' (a nil value)」
  • 等等

都是一个不小心,没注意检查对象是不是 null 值就用,然后程序跑着跑着就出错了。

而 Haskell 和 Rust 都能有效地避免这一点,至少是你可以预先察觉,因为它返回的是不一样的类型。比如在 Rust 中,想要把字符串解析成整数,你写let a: i32 = "123".parse()不成。因为不是所有字符串都能解析成整数的,所以parse方法会返回一个Result<i32,ParseIntError>类型(早期版本是返回Option<i32>)。你需要显式地处理错误——或者忽略,如果你希望在出错的时候程序崩溃的话。不管选哪条路,写的时候都是明确知道这个地方可能出错的。不像我写 Python 时那样,直接想当然地写int(xxx),很少会想到想当然以为是个整数表示的xxx其实可能是别的什么东西(比如None)。我总不可能在每一次按.键(取属性)、(键(函数调用开始)、[键(取下标)时都先想想「相关对象会不会是奇怪的东西、是的话要怎么处理」吧?当然这样的错误处理会比较麻烦。如果一个项目不值得这样麻烦的错误处理的话,那就换个更适合的语言去做就是了。

Rust 另一个小特点是,if这类条件判断后边只能是布尔值,和 Haskell 一样,而和 Python、Lisp、Lua 等都不同,就更别说没有真正的布尔类型的 C 了。这样更严谨,挺好的,意义明确。像把0当成假值这种事 Lua 就不干,把空容器当假这事 Python 喜欢但是别的语言又不一样。早先版本的datetime模块甚至认为午夜是假的、其它时间才是真的……

Rust 还有个显著的特点是,关键字都特别短,但是不至于短到不认识,比如pub, fn, mut, ref, impl等。有些人不喜欢,我倒是觉得挺好的。非要写一长串字符浪费空间嘛,虽然现在的显示器不是终端机那样一行只能显示80字符,但我要分割成多列呢。笔记本显示器可以显示两列代码对照着看,外接显示器要显示两行三列还不计偶尔会用到的侧栏呢。

Rust 还继承了 Python 式的显式名称导入。只要不用星号,一个名字是从哪里来的,当前文件里搜一下就找到了。不像 Ruby 那样子,String 莫名其妙多了个方法不知道是干什么的?拿 Google 搜索整个互联网吧……

Rust 资源管理很有特点,我还没在其它语言里看到这种。Rust 程序里,编译器知道每一个对象的生命周期,所以可以在编译期就插入相应的释放资源的代码,不需要 gc 过一段时间停下所有工作来检查一遍。也不像引用计数那样得维护计数,引起很多不必要的内存写请求。毕竟 Rust 的目标是像 C++ 那样高效的系统级编程语言嘛。当然引用计数如果需要还是可以有的。最初 Rust 的另一目标——像 Erlang 那样的并发性,因为绿色用户级线程被官方移出之后就大打折扣了。不过因为类型检查和生命周期推断,线程安全的特性还是保留了下来。

Rust 有各式各样的 trait,类似于 Haskell 里的类型类。要指定资源释放时调用的函数的话,直接实现Drop trait 就可以了。比如我的:

struct AtDir {
  oldpwd: Path,
}

impl AtDir {
  fn new(dir: &str) -> io::IoResult<AtDir> {
    let oldpwd = try!(std::os::getcwd());
    try!(std::os::change_dir(&Path::new(dir)));
    Ok(AtDir { oldpwd: oldpwd })
  }
}

impl std::ops::Drop for AtDir {
  fn drop(&mut self) {
    std::os::change_dir(&self.oldpwd).unwrap();
  }
}

使用的时候直接在需要的作用域时生成一个变量就好,就像下边这样子。Rust 保证在其生命周期结束时调用drop方法。而且是按其所有者变量定义的顺序的逆序调用的。不像 Python,PEP 442折腾了之后,反而是把我一个模块的__del__方法在解释器关闭时的调用顺序弄错了。虽然 Rust 没有 Python 那样的with语句,但是拿Drop可以做到一样的效果,而且能保证调用的时机与预期的一致。

let _cwd = match AtDir::new(directory_name) {
  Ok(atdir) => atdir,
  Err(err) => return Err(err.desc.to_string()),
};

Rust 编译器及标准库目前大部分(92.0%)使用 Rust 编写。而在此之前,Rust 竟然是使用 OCaml 编写的。这从侧面解释为什么目前 79.4% 使用 Go 编写 Go 语言用起来那么像 C(因为它的开发者用的是 C,设计目标好像也是更好的 C),而 Rust 虽然有很多借鉴自 C++ 的东西,导致其语法有些像 C,但写起来完全没有 C 和 Go 那样原始的感觉。这也是我更喜欢 Rust 的原因之一。

目前,除了还在改来改去,让我的程序过几天就各种报错编译不了之外,作为一名初学者,我能发现的另一个缺点就是编译极其费时了,特别是普通优化和链接时优化全开的时候,我一运行时间不到 0.2 秒的小程序,竟然需要半分钟才能编译好……

对了,之前给 Arch Linux 打包的 thestinger 不再打包 Rust 了,所以我开始在 archlinuxcn 源里维护64位的 rust-git、cargo-git(因为 Rust 更新的原因,至今还没打包成功……)以及 vim-rust-git。这些包是自动更新的,因此不出问题的话,有更新就会在一天内更新。

PS: 写的时候有点赶,希望没有写得太乱 ( >﹏<。)

Category: 编程 | Tags: Rust
1
6
2015
41

众编程语言间的 swapview 之战

swapview 起源于我很早之前看到的一个 shell 脚本。当时正在学习 Haskell,所以就拿 Haskell 给实现了一遍。为了对比,又拿 Python 给实现了一遍。而如今,我又在学习另一门新的语言——Rust,也拿 swapview 来练习了。相比仅仅输出字符串的「Hello World」程序,swapview 无疑更实际一些:

  • 文件系统操作:包括列目录、读取文件内容
  • 数据解析:包括简单的字符串处理和解析,还有格式化输出
  • 数据处理:求和啊排序什么的
  • 流程控制:循环啊判断啊分支什么的都有
  • 错误处理:要忽略文件读取错误的

因此,swapview 成为了依云版的「Hello World」:-)

感谢所有给 swapview 提交代码的朋友们

本文只是借 swapview 这个程序,一窥众编程语言的某些特征。很显然,编程语言们各有所长,在不同的任务下会有不同的表现。而且 swapview 各个版本出自不同的人之手,代码质量也会有所差异。

闪耀!那些令人眼前一亮的语言们

从运行效率上来看,C 如预期的一样是最快的。但令人惊讶的是,由我这个 Rust 初学者写的 Rust 程序竟然紧随其后,超越了 C++。

而原以为会跟在 Rust 之后的 C++,却输给了作为脚本语言存在的 Lua 语言的高效实现 LuaJIT(与 Rust 版本相当)。而且非 JIT 版本的 Lua 5.1 和 5.2 也都挺快的。Lua 这语言自带的功能非常少,语法也简单,但是效率确实高,让人又爱又恨的。

失望!那些没预期中的高效的语言们

没想到 Python 2 也挺快的,很接近 Go 了。PyPy 大概是因为启动比较慢的原因而排在了后面。Python 3 有使用两个版本的代码,Python3_bytes 把文件读取改为使用 bytes,仅在需要的时候才解码成 str。仅此之差,运行速度快了10%。可见 Python 的 Unicode 处理十分耗时,难怪 Python 3 在各种测试中都比 Python 2 要慢上一截。至于 PyPy3,怎么跑到那么靠后的地方去了呢……

Go 很快。至少比 Python 快。但也仅此而已了,不仅比 C++ 慢,甚至连 Lua(非 JIT 版)都不如。Go 语言版本虽然不是我写的,但我看过代码,感觉很原始。至少比 Lua 原始。看起来 Go 只不过是带接口和并发支持的 C 而已。而且,作为静态类型的编译型语言,却我却有一种很不放心的感觉。大约是因为我改动时发现传给 fmt.Printf 的参数类型和数目错了都不会得到警告或者错误的原因。而且我从来没见过 Go 编译时出现警告,对于还没入门的初学者写的、改过的程序,这样子不科学啊。早期我倒是见过 Go 报错了,但那只不过是编译器还不完善的表现而已。

传闻 NodeJS 很快。但至少它在 swapview 这种脚本中没能体现出来。正常版本比 Python 3 还要慢一点。而使用异步啊并行什么的版本还要慢上差不多三分之一,不知道怎么搞的。

编译型的 Chicken、OCaml、Haskell 都排在了一众脚本语言后边,虽然很可能是对语言本身不熟导致写出来的程序比较慢,但还是挺令人失望的。经过高手优化的 Haskell2 版本效率接近于 Python 3,但也到此为止了(因为不想使用 cabal 安装依赖,所以 Haskell2 没有参与这场对决)。我曾见过有人把 Haskell 代码优化到比 C 还快,但我宁愿去看汇编也不要去读那种代码……

Lisp 系(Chicken、Racket、SBCL(标注为 CommonLisp 的项)、Guile)也都挺慢的。不知道 LispWorks 之类的会不会快一大截呢。

预料之中的以及结果截图

Ruby 比 Python 略慢一点。

Java、Elixir 比较靠后。没办法,它们启动慢。也许以后我会出不考虑启动时间的版本。

以下是本文发表前的测试结果截图。其中 Erlang 版本因为有问题被信号所杀所以被扔在了最后。

测试结果截图

测试使用的是benchmark子目录中的 Rust 程序,使用cargo build --release命令即可构建。另外也可以使用 farseerfc 的 Python 脚本。

代码量

Elixir 代码量挺少的。Python、Ruby 也挺不错。Java 版本竟然跟 Haskell 一样。不管是 JavaScript 还是 CoffeeScript 都比较长,比 Java 还长。Rust 比 Python 长不少,但也比 Go 短不少。而 Go 比起 C、C++ 要短一些。最长的,除了我不了解的 Pascal,竟然还有因为程序出错还没有测试的 Erlang!如果不算按行读取的 line_server.erl 的放大,只有不到一百行,倒还不算多。

                  Elixir:   50
                   Julia:   51
           Python3_bytes:   53
                  Python:   56
                    Ruby:   56
                  Racket:   58
                    Bash:   63
                   OCaml:   65
          CommonLisp_old:   67
          CommonLisp_opt:   67
           Bash_parallel:   69
             C++14_boost:   69
                   Guile:   70
                 Haskell:   73
                 Chicken:   75
                    Java:   75
                  NodeJS:   76
                    Vala:   78
                Haskell2:   81
                       D:   86
                    Rust:   88
                   C++14:   89
                  CSharp:   91
                     Lua:   91
            NodeJS_async:   93
            CoffeeScript:   93
   CoffeeScript_parallel:   95
                     PHP:   97
           Rust_parallel:   98
                      Go:  103
                   C++11:  128
                   C++98:  141
                       C:  149
              FreePascal:  185
                  Erlang:  232

编译速度

这个比较非常粗糙,比如联网下载依赖也被算进去了。不过可以肯定,不算下载依赖部分的话,Rust 是最慢的!其次是 Haskell。标榜编译速度非常快的 Go 并不是最快的,和 C++ 不相上下(当然不知道代码复杂之后会如何了)。

0.36 C
0.60 FreePascal
0.80 OCaml
0.83 CoffeeScript_parallel
1.48 CSharp
1.67 Vala
1.68 Erlang
2.13 NodeJS_async
2.27 C++14
2.49 Go
2.53 CoffeeScript
2.90 C++11
3.01 C++98
3.23 Java
3.52 Racket
3.98 NodeJS
6.05 CommonLisp_opt
7.07 D
9.01 C++14_boost
10.41 Haskell
13.07 Rust
14.74 Chicken
15.37 Rust_parallel

结语

这个项目最初只是练习而已。后来不同语言的版本有点多,于是才演变成众编程语言的竞技。也就随意地测试了一下在给定需求下不同语言的表现而已。其实比较有意思的部分,一是使用正在学习的编程语言写作程序的新奇感、新知、新的领悟(这也是我的测试程序使用 Rust 编写的原因),二是对比不同编程语言的风格和对同样需求的处理方式。

各位读者对 swapview 有任何补充和改进,欢迎贡献代码哦~项目地址:https://github.com/lilydjwg/swapview

更新区

2015年1月9日更新:又收到了不少版本和改进,以下是最新的测试结果。很不幸地,现在已经跑得很快的 Erlang 在测试中又没反应被杀掉了。并行版的 Rust 的结果很不稳定,这次跑得好快!C++ 的除了 C++98 版的之外都到 Rust 前边去了。PHP 竟然比 LuaJIT 还要快!D 怎么到 PyPy 后边去了。

2015年1月9日的测试结果截图

2015年1月10日更新:C++ 版本继续改进,好多都超越 C 了,Rust 1.0.0alpha 的并列版本又快又稳定,Erlang 版本终于跑完了全部测试而没有出事,LLVM 版 D 快了好多。

2015年1月10日的测试结果截图

2015年1月18日更新:继续更新。又添加了若干语言,不过期待中的 Nim、Zimbu 以及传统脚本语言 Perl、Tcl 依旧缺席中。另外,正文也进行了更新,重新计算了代码量,添加了编译速度的粗略比较。

2015年1月18日的测试结果截图

12
24
2014
39

Rust 初体验(真快!)

最近又看到 Rust 的相关东西了,入门指南也写得挺不错的。这语言我越看越喜欢。

Rust 的目标是系统级编程,就像 C 那样,快速高效。同时它继承了 Haskell 的诸多特性,包括其类型系统(包括类型类和类型推断)、模式匹配。而读写起来,又和 Python 差不多简单明了。简直是把这三种语言的优点全学到了!(当然 Rust 不仅仅受到了这几种语言的影响啦。)

当然,要体验一门编程语言,最好的方式就是使用它。于是我拿它实现了我最开始用来练习 Haskell 用的 swapview 程序。

swapview 的功能是,读取/proc下每一个进程目录下边的cmdlinesmaps文件,得到其命令行和 swap 使用量,然后排序、格式化,并打印出来。

Haskell 第一版实现挺慢的:

swapview  1.27s user 0.26s system 98% cpu 1.555 total

我随手写了个 Python 版,效率翻了一倍还要多!很令人惊讶的呢。作为解释执行、还一直被认为很慢的 Python 竟然在没有任何优化的情况下就超过了编译型的 Haskell:

swapview.py  0.35s user 0.18s system 97% cpu 0.548 total

后来在 IRC 上遇到一位懂行的人,用了不少手段优化,最终得到了 Haskell 第二版:

swapview2  0.42s user 0.15s system 98% cpu 0.583 total

比 Python 版略慢。

才学 Rust 没几天,我对 Rust 比对 Haskell 更不熟。花了不少时间查阅文档、调整代码。不过因为之前的 Haskell 基础,也没遇到太大的困难。结果如下:

swapview  1.84s user 0.15s system 97% cpu 2.038 total

呃呃呃,怎么比 Haskell 版本还要慢上不少啊?

本来是找 profiling 方法的。翻着 rustc 的 man 文档,看到了-O选项,眼前一亮——我忘记告诉编译器要优化了!这是启用优化的结果,比 Python 版又快了一倍:

swapview  0.10s user 0.13s system 96% cpu 0.237 total

真棒呢~

不过很遗憾的是,它的格式化函数的第一个参数必须是字面量,连常量都不行。因为那是个宏,要在编译期解析格式……另外似乎也不支持现在连 JavaScript 都已经支持了的 generator(只支持 iterator,得先写一个 struct 才能用)。

PS: Rust 的文档挺赞的,和 Python 的一样有 JavaScript 实现的搜索功能,比起 Nimrod 和 Zimbu 的好用太多了。

PPS: 谁有兴趣可以贡献个 Go 版、C 版、C++ 版、LuaJIT 版什么的=w=


2014年12月25日更新:目前的结果是(运行时间):Rust < LuaJIT < C++14 (gcc 4.9.2) < Lua 5.1 / 5.2 << Python 3 < Haskell <<< OCaml < SBCL。手动测试的。有空我再写个好点的自动测试程序。

2015年1月6日更新:添加了更多的编程语言,以及更准确的运行时间测试,请见新文章编程语言对决——战场:swapview

Category: 编程 | Tags: Haskell 编程语言 Rust

| Theme: Aeros 2.0 by TheBuckmaker.com