generator、yield 与 coroutine

说到 generator 这个概念,想来似乎很简单,在 C++ 的世界里面更多的是 std::generate 这个 generic algorithm 里面用的概念,说穿了就是一个没有参数的 functor,返回的类型是用户希望生成的类型。似乎一度不是太被人关注,一个主要的原因可能是 C++ 里面更多的使用 iterator,但是其实 iterator 和 generator 一样都会面临类似的问题。不过我们也看到了,在写 for-loop 时 iterator 写起来更麻烦,而 generator 似乎要更简单一些,一些语言(如 python)如果支持对容器的 foreach 类型循环那对 generator 的支持就更不在话下。

为什么说 generator 和 iterator 会面临一样的问题呢?因为它们时常作为一个复杂的对象处理其部件的对外接口,如果你在这个对象里面干某些事情,那无非是顺理成章的过程,但这些事情的逻辑就会被封存在这个对象的方法里面,对于某些事情,我们还是希望这个遍历的逻辑和事情的逻辑是 decouple 的,这个标准的做法就是所谓的 visitor pattern。我们以一个简单的二叉树中序遍历过程来解释。

template <class T>
struct node {
  typedef T value_type ;

  T value ;
  node* left ;
  node* right ;
} ;

template <class node> void
inorder (const node* root, std::function<void(const node::value_type&)> f) {
  if (root == NULL) return ;
  inorder (left, f) ;
  f (value) ;
  inorder (right, f) ;
}

是不是看起来很简洁呢?试想我们如果希望提供类似的一个 generator 怎么办?hmm… 开始想吧!本质上这是一个类似“回溯”的问题,我们得在返回时记住当前的状态,这样下次调用这个 functor 时才能自己继续下去。要不写个试试?

enum color {
  WHITE, GREY, BLACK
} ;
template <class node>
struct inorder {
  typedef typename node::value_type value_type ;
  typedef std::pair<const value_type&, bool> return_type ;
  typedef std::pair<const node*, color> elem_type ;
  typedef std::stack<elem_type> stack_type ;
  stack_type s

  inorder (node* root) {
    assert (root != NULL) ;
    s.push (std::make_pair (root, WHITE)) ;
  }

  return_type
  operator() () {
    // find one that's the current leftest one, therefore without left child
    while (s.top ().second == WHITE && s.top ().first -> left != NULL) {
      elem_type t = s.top () ; s.pop () ;
      t.second = GREY ;
      s.push (t) ;
      s.push (std::make_pair (t.first, WHITE)) ;
    }
    elem_type t = s.top () ; s.pop () ;
    if (t.second == WHITE) { // first time, use current value
      t.second = GREY ; s.push (t) ;
      return std::make_pair (t.first->value, true) ;
    } else (t.second == GREY) { // the value has been traversed
      if (t.first -> right == NULL) // no more case!
        return std::make_pair (t.first->value, false) ;
      s.push (std::make_pair (t.first -> right, WHITE)) ;
      return operator() () ;
    }
  }
} ;

就这么一个很简单的事情似乎一下变得格外复杂了吧(以上代码未经验证,只做示意)。实际上我们知道比如后序遍历之类的 BLACK 就也用上了,一般的 graph 的遍历之类的就更不用说了。这也就是前面在讨论 coroutine 的时候所谓的 caller-callee 问题,如果我们作为 caller 调用 visitor,好处自然是我们的代码简单好维护,但是势必将遍历的逻辑封闭起来(某些情况下可能有用 policy class 来一定程度解决这个封闭性问题),visitor 侧代码如果希望提前终止遍历,或者抛出异常之类的强迫终止或者将后续代价减低。使用 generator 我们可以提前终止,所有的控制逻辑可以在一个简单的 loop 里面完成。看起来写 generator 要比 visitor pattern 更加灵活!但是写起来却复杂了这么多!如果你又想弄成别人好用的,还要写起来简单,那你就只能靠 yield 这类的东西了。

说起来 yield 跟 return 挺类似的,只是 return 之后还记住了当前的位置,下次回来的时候继续走下去就行了,单纯为了这个 yield 功能,我们的确没必要动用比较复杂的 coroutine 实现(比如最近进入 boost 的 coroutine,这个更接近于一些编写 service 里面需要协作的一些方法之间切换,比 thread 更为轻量的一种策略)。那么如果写 C++ 的话有没有别的思路呢?其实依赖于 Duff’s device 的 stackless coroutine 是一个比较实用的选择。wiki 上面关于 C++ 的 generator 其实就是受到这个 Duff’s device 的启发通过宏模拟的,本质上就是将一些循环等状态放在一个类成员里面,而实现的 operator() 里面在重新进入时能够跳回上次结束的位置,但是由于当时使用的循环等变量值保留了下来,这次的执行就和上次没结束继续下去是完全一样的。搞清楚了这些关系,可能能帮助你通过那个奇怪的宏实现你需要的功能,但是本身还是非常 tricky 的,因为少不留神出了错的话,调试是很难的。

这也难怪,python、C# 和 scala 等语言都开始提供 yield 关键字,从语言层面上简化了这个故事。如果 C++ 有 yield 上面的代码基本上就是

template <class node> const node::value_type&
inorder (node* root) {
  assert (root != NULL) ;
  if (root -> left)
    inorder (root -> left) ;
  yield (root -> value) ;
  if (root -> right)
    inorder (root -> right) ;
  throw finished ;
}

嗯,没错,看起来简单,理解起来更简单!其实学习 scala 里面一个很重要的概念就是通过递归你会发现这个过程跟数学归纳法是如此相似,你很容易理解清楚算法的正确性,像前面那个中序遍历的回溯算法,我敢打包票里面有 bug,但是递归的问我有没有写错的话,我却敢很肯定的说,没啥问题。如果每个语言都有类似 yield 的支持,我想程序员都不必经常写回溯的代码了。后面 scala 的笔记里面有一个 8 皇后问题的求解就是一个典型的通过 recursion 和 yield 求解的典范。

最后既然我们了解了一些 yield 方面的东西,很自然的我们就希望能够看清楚比如 python/scala 他们的 yield 到底干了些什么,会引入多少额外的 overhead,与手写回溯代码比是不是效率上也更具优势?

——————
And he came unto his father, and said, My father: and he said, Here am I; who art thou, my son?

Advertisements
generator、yield 与 coroutine

一个有关“generator、yield 与 coroutine”的想法

  1. zt 说:

    看了几篇国内同学谈类似概念的 blog,也许是运气不好,看到有人说用 thread 实现这个 generator 不是挺简单的么,我顿时石化了。

    我们知道早期服务器通过多进程来处理多个请求,发现进程太 heavy 了,于是后来发展到多线程来处理请求,这样一来可以共享的东西变容易,但是请求一多,即便是轻量级的线程切换代价还是太高。

    到更先进的框架下,使用线程池,将请求任务拆分到线程上通过更加轻量的 coroutine 来做(比如 boost.asio 的设计应该就是这个路数),往往实际应用服务器的线程数达到一定数量后就没有增加的需要了,而 coroutine 能够帮助我们将处理的流程从线程里面分割的更细,这样一来理论上可以大大减少某些线程因为 IO 而挂起的问题(线程挂起后切换 thread 的代价比切换 coroutine 要更高)。

    当然似乎另一种解决方案是 node.js 系的 callback,不过我的感觉是 callback 只是一种设计的方式,它本身也有一些问题(似乎见过一篇比较这两种实现的文章,后面仔细体会下),它本身一样不能解决 IO 的问题。

    至于这里谈的 generator/yield 那只是 coroutine 使用方法里面的一个特例。为了一个 generator/yield 说我用线程库来实现,岂不是有点舍本逐末吗?

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s