陈硕的Blog

关于 std::set/std::map 的几个为什么

陈硕 (chenshuo.com)

2013-01-20

std::set/std::map (以下用 std::map 代表) 是常用的关联式容器,也是 ADT(抽象数据类型)。也就是说,其接口(不是 OO 意义下的 interface)不仅规定了操作的功能,还规定了操作的复杂度(代价/cost)。例如 set::insert(iterator first, iterator last) 在通常情况下是 O(N log N),N 是区间的长度;但是如果 [first, last) 已经排好序(在 key_compare 意义下),那么复杂度将会是 O(N)。

尽管 C++ 标准没有强求 std::map 底层的数据结构,但是根据其规定的时间复杂度,现在所有的 STL 实现都采用平衡二叉树来实现 std::map,而且用的都是红黑树。《算法导论(第 2 版)》第 12、13 章介绍了二叉搜索树和红黑树的原理、性质、伪代码,侯捷先生的《STL 源码剖析》第 5 章详细剖析了 SGI STL 的对应实现。本文对 STL 中红黑树(rb_tree)的实现问了几个稍微深入一点的问题,并给出了我的理解。本文剖析的是 G++ 4.7 自带的这一份 STL 实现及其特定行为,与《STL 源码剖析》的版本略有区别。为了便于阅读,文中的变量名和 class 名都略有改写(例如 _Rb_tree_node 改为 rb_tree_node)。本文不谈红黑树的平衡算法,在我看来这属于“旁枝末节”(见陈硕《谈一谈网络编程学习经验》对此的定义),因此也就不关心节点的具体颜色了。

数据结构回顾

先回顾一下数据结构教材上讲的二叉搜索树的结构,节点(Node)一般有三个数据成员(left、right、data),树(Tree)有一到两个成员(root 和 node_count)。

用 Python 表示:
class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

class Tree:
    def __init__(self):
        self.root = None
        self.node_count = 0

而实际上 STL rb_tree 的结构比这个要略微复杂一些,我整理的代码见 https://gist.github.com/4574621#file-tree-structure-cc

节点

Node 有 5 个成员,除了 left、right、data,还有 color 和 parent。

C++实现,位于bits/stl_tree.h
/**
 * Non-template code
 **/

enum rb_tree_color { kRed, kBlack };

struct rb_tree_node_base
{
  rb_tree_color       color_;
  rb_tree_node_base*  parent_;
  rb_tree_node_base*  left_;
  rb_tree_node_base*  right_;
};

/**
 * template code
 **/

template<typename Value>
struct rb_tree_node : public rb_tree_node_base
{
  Value value_field_;
};

见下图。

node

color 的存在很好理解,红黑树每个节点非红即黑,需要保存其颜色(颜色只需要 1-bit 数据,一种节省内存的优化措施是把颜色嵌入到某个指针的最高位或最低位,Linux 内核里的 rbtree 是嵌入到 parent 的最低位);parent 的存在使得非递归遍历成为可能,后面还将再谈到这一点。

Tree 有更多的成员,它包含一个完整的 rb_tree_node_base(color/parent/left/right),还有 node_count 和 key_compare 这两个额外的成员。

这里省略了一些默认模板参数,如 key_compare 和 allocator。
template<typename Key, typename Value> // key_compare and allocator
class rb_tree
{
 public:
  typedef std::less<Key> key_compare;
  typedef rb_tree_iterator<Value> iterator;
 protected:

  struct rb_tree_impl // : public node_allocator
  {
    key_compare       key_compare_;
    rb_tree_node_base header_;
    size_t            node_count_;
  };
  rb_tree_impl impl_;
};

template<typename Key, typename T> // key_compare and allocator
class map
{
 public:
  typedef std::pair<const Key, T> value_type;
 private:
  typedef rb_tree<Key, value_type> rep_type;
  rep_type tree_;
};

见下图。这是一颗空树,其中阴影部分是 padding bytes,因为 key_compare 通常是 empty class。(allocator 在哪里?)

tree

rb_tree 中的 header 不是 rb_tree_node 类型,而是 rb_tree_node_base,因此 rb_tree 的 size 是 6 * sizeof(void*),与模板类型参数无关。在 32-bit 上是 24 字节,在 64-bit 上是 48 字节,很容易用代码验证这一点。另外容易验证 std::set 和 std::map 的 sizeof() 是一样的。

注意 rb_tree 中的 header 不是 root 节点,其 left 和 right 成员也不是指向左右子节点,而是指向最左边节点(left_most)和最右边节点(right_most),后面将会介绍原因,是为了满足时间复杂度。header.parent 指向 root 节点,root.parent 指向 header,header 固定是红色,root 固定是黑色。在插入一个节点后,数据结构如下图。

tree1

继续插入两个节点,假设分别位于 root 的左右两侧,那么得到的数据结构如下图所示(parent 指针没有全画出来,因为其指向很明显),注意 header.left 指向最左侧节点,header.right 指向最右侧节点。

tree3

迭代器

rb_tree 的 iterator 的数据结构很简单,只包含一个 rb_tree_node_base 指针,但是其++/--操作却不见得简单(具体实现函数不在头文件中,而在 libstdc++ 库文件中)。

// defined in library, not in header
rb_tree_node_base* rb_tree_increment(rb_tree_node_base* node);
// others: decrement, reblance, etc.

template<typename Value>
struct rb_tree_node : public rb_tree_node_base
{
  Value value_field_;
};

template<typename Value>
struct rb_tree_iterator
{
  Value& operator*() const
  {
    return static_cast<rb_tree_node<Value>*>(node_)->value_field_;
  }

  rb_tree_iterator& operator++()
  {
    node_ = rb_tree_increment(node_);
    return *this;
  }

  rb_tree_node_base* node_;
};

end() 始终指向 header 节点,begin() 指向第一个节点(如果有的话)。因此对于空树,begin() 和 end() 都指向 header 节点。对于 1 个元素的树,迭代器的指向如下。

tree1i

对于前面 3 个元素的树,迭代器的指向如下。

tree3i

思考,对 std::set<int>::end() 做 dereference 会得到什么?(按标准,这属于undefined behaviour,不过但试无妨。)

rb_tree 的 iterator 的递增递减操作并不简单。考虑下面这棵树,假设迭代器 iter 指向绿色节点3,那么 ++iter 之后它应该指向灰色节点 4,再 ++iter 之后,它应该指向黄色节点 5,这两步递增都各走过了 2 个指针。

tree7

对于一颗更大的树(下图),假设迭代器 iter 指向绿色节点7,那么 ++iter 之后它应该指向灰色节点 8,再 ++iter 之后,它应该指向黄色节点 9,这两步递增都各走过了 3 个指针。

tree15 

由此可见,rb_tree 的迭代器的每次递增或递减不能保证是常数时间,最坏情况下可能是对数时间(即与树的深度成正比)。那么用 begin()/end() 迭代遍历一棵树还是不是 O(N)?换言之,迭代器的递增或递减是否是分摊后的(amortized)常数时间?

另外注意到,当 iter 指向最右边节点的时候(7 或 15),++iter 应该指向 header 节点,即 end(),这一步是 O(log N)。同理,对 end() 做--,复杂度也是 O(log N),后面会用到这一事实。

rb_tree 迭代器的递增递减操作的实现也不是那么一目了然。要想从头到尾遍历一颗二叉树(前序、中序、后序),教材上给出的办法是用递归(或者用 stack 模拟递归,性质一样),比如:(https://gist.github.com/4574621#file-tree-traversal-py

Python:
def printTree(node):
    if node:
        printTree(node.left)
        print node.data
        printTree(node.right)

如果考虑通用性,可以把函数作为参数进去,然后通过回调的方式来访问每个节点,代码如下。Java XML 的 SAX 解析方式也是这样。

Python:
def visit(node, func):
    if node:
        printTree(node.left)
        func(node.data)
        printTree(node.right)

要想使用更方便,在调用方用 for 循环就能从头到尾遍历 tree,那似乎就不那么容易了。在 Python 这种支持 coroutine 的语言中,可以用 yield 关键字配合递归来实现,代码如下,与前面的实现没有多大区别。

在 Python 3.3 中还可以用 yield from,这里用 Python 2.x 的写法。
def travel(root):
    if root.left:
        for x in travel(root.left):
            yield x
    yield root.data
    if root.right:
        for y in travel(root.right):
            yield y

调用方:
    for y in travel(root):
        print y

但是在 C++ 中,要想做到最后这种 StAX 的遍历方式,那么迭代器的实现就麻烦多了,见《STL 源码剖析》第 5.2.4 节的详细分析。这也是 node 中 parent 指针存在的原因,因为递增操作时,如果当前节点没有右子节点,就需要先回到父节点,再接着找。

空间复杂度

每个 rb_tree_node 直接包含了 value_type,其大小是 4 * sizeof(void*) + sizeof(value_type)。在实际分配内存的时候还要 round up 到 allocator/malloc 的对齐字节数,通常 32-bit 是 8 字节,64-bit 是 16 字节。因此 set<int>每个节点是 24 字节或 48 字节,100 万个元素的 set<int> 在 x86-64 上将占用 48M 内存。说明用 set<int> 来排序整数是很不明智的行为,无论从时间上还是空间上。

考虑 malloc 对齐的影响,set<int64_t> 和 set<int32_t> 占用相同的空间,set<int> 和 map<int, int> 占用相同的空间,无论 32-bit 还是 64-bit 均如此。

几个为什么

对于 rb_tree 的数据结构,我们有几个问题:

1. 为什么 rb_tree 没有包含 allocator 成员?

2. 为什么 iterator 可以 pass-by-value?

3. 为什么 header 要有 left 成员,并指向 left most 节点?

4. 为什么 header 要有 right 成员,并指向 right most 节点?

5. 为什么 header 要有 color 成员,并且固定是红色?

6. 为什么要分为 rb_tree_node 和 rb_tree_node_base 两层结构,引入 node 基类的目的是什么?

7. 为什么 iterator 的递增递减是分摊(amortized)常数时间?

8. 为什么 muduo 网络库的 Poller 要用 std::map<int, Channel*> 来管理文件描述符?

我认为,在面试的时候能把上面前 7 个问题答得头头是道,足以说明对 STL 的 map/set 掌握得很好。下面一一解答。

为什么 rb_tree 没有包含 allocator 成员?

因为默认的 allocator 是 empty class (没有数据成员,也没有虚表指针vptr),为了节约 rb_tree 对象的大小,STL 在实现中用了 empty base class optimization。具体做法是 std::map 以 rb_tree 为成员,rb_tree 以 rb_tree_impl 为成员,而 rb_tree_impl 继承自 allocator,这样如果 allocator 是 empty class,那么 rb_tree_impl 的大小就跟没有基类时一样。其他 STL 容器也使用了相同的优化措施,因此 std::vector 对象是 3 个 words,std::list 对象是 2 个 words。boost 的 compressed_pair 也使用了相同的优化。

我认为,对于默认的 key_compare,应该也可以实施同样的优化,这样每个 rb_tree 只需要 5 个 words,而不是 6 个。

为什么 iterator 可以 pass-by-value?

读过《Effective C++》的想必记得其中有个条款是 Prefer pass-by-reference-to-const to pass-by-value,即对象尽量以 const reference 方式传参。这个条款同时指出,对于内置类型、STL 迭代器和 STL 仿函数,pass-by-value 也是可以的,一般没有性能损失。

在 x86-64 上,对于 rb_tree iterator 这种只有一个 pointer member 且没有自定义 copy-ctor 的 class,pass-by-value 是可以通过寄存器进行的(例如函数的头 4 个参数,by-value 返回对象算一个参数),就像传递普通 int 和指针那样。因此实际上可能比 pass-by-const-reference 略快,因为callee 减少了一次 deference。

同样的道理,muduo 中的 Date class 和 Timestamp class 也是明确设计来 pass-by-value 的,它们都只有一个 int/long 成员,按值拷贝不比 pass reference 慢。如果不分青红皂白一律对 object 使用 pass-by-const-reference,固然算不上什么错误,不免稍微显得知其然不知其所以然罢了。

为什么 header 要有 left 成员,并指向 left most 节点?

原因很简单,让 begin() 函数是 O(1)。假如 header 中只有 parent 没有 left,begin() 将会是 O(log N),因为要从 root 出发,走 log N 步,才能到达 left most。现在 begin() 只需要用 header.left 构造 iterator 并返回即可。

为什么 header 要有 right 成员,并指向 right most 节点?

这个问题不是那么显而易见。end() 是 O(1),因为直接用 header 的地址构造 iterator 即可,不必使用 right most 节点。在源码中有这么一段注释:

bits/stl_tree.h
  // Red-black tree class, designed for use in implementing STL
  // associative containers (set, multiset, map, and multimap). The
  // insertion and deletion algorithms are based on those in Cormen,
  // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
  // 1990), except that
  //
  // (1) the header cell is maintained with links not only to the root
  // but also to the leftmost node of the tree, to enable constant
  // time begin(), and to the rightmost node of the tree, to enable
  // linear time performance when used with the generic set algorithms
  // (set_union, etc.)
  //
  // (2) when a node being deleted has two children its successor node
  // is relinked into its place, rather than copied, so that the only
  // iterators invalidated are those referring to the deleted node.

这句话的意思是说,如果按大小顺序插入元素,那么将会是线性时间,而非 O(N log N)。即下面这段代码的运行时间与 N 成正比:

 // 在 end() 按大小顺序插入元素
  std::set<int> s;
  const int N = 1000 * 1000
  for (int i = 0; i < N; ++i)
      s.insert(s.end(), i);

在 rb_tree 的实现中,insert(value) 一个元素通常的复杂度是 O(log N)。不过,insert(hint, value) 除了可以直接传 value_type,还可以再传一个 iterator 作为 hint,如果实际的插入点恰好位于 hint 左右,那么分摊后的复杂度是 O(1)。对于这里的情况,既然每次都在 end() 插入,而且插入的元素又都比 *(end()-1) 大,那么 insert() 是 O(1)。在具体实现中,如果 hint 等于 end(),而且 value 比 right most 元素大,那么直接在 right most 的右子节点插入新元素即可。这里 header.right 的意义在于让我们能在常数时间取到 right most 节点的元素,从而保证 insert() 的复杂度(而不需要从 root 出发走 log N 步到达 right most)。具体的运行时间测试见 https://gist.github.com/4574621#file-tree-bench-cc ,测试结果如下,纵坐标是每个元素的耗时(微秒),其中最上面的红线是普通 insert(value),下面的蓝线和黑线是 insert(end(), value),确实可以大致看出 O(log N) 和 O(1) 关系。具体的证明见《算法导论(第 2 版》第 17 章中的思考题 17-4。

stl_tree_bench

但是,根据测试结果,前面引用的那段注释其实是错的,std::inserter() 与 set_union() 配合并不能实现 O(N) 复杂度。原因是 std::inserter_iterator 会在每次插入之后做一次 ++iter,而这时 iter 正好指向 right most 节点,其++操作是 O(log N) 复杂度(前面提到过 end() 的递减是 O(log N),这里反过来也是一样)。于是把整个算法拖慢到了 O(N log N)。要想 set_union() 是线性复杂度,我们需要自己写 inserter,见上面代码中的 end_inserter 和 at_inserter,此处不再赘言。

为什么 header 要有 color 成员,并且固定是红色?

这是一个实现技巧,对 iterator 做递减时,如果此刻 iterator 指向 end(),那么应该走到 right most 节点。既然 iterator 只有一个数据成员,要想判断当前是否指向 end(),就只好判断 (node_->color_ == kRed && node_->parent_->parent_ == node_) 了。

为什么要分为 rb_tree_node 和 rb_tree_node_base 两层结构,引入 node 基类的目的是什么?

这是为了把迭代器的递增递减、树的重新平衡等复杂函数从头文件移到库文件中,减少模板引起的代码膨胀(set<int> 和 set<string> 可以共享这些的 rb_tree 基础函数),也稍微加快编译速度。引入 rb_tree_node_base 基类之后,这些操作就可以以基类指针(与模板参数类型无关)为参数,因此函数定义不必放在在头文件中。这也是我们在头文件里看不到 iterator 的 ++/-- 的具体实现的原因,它们位于 libstdc++ 的库文件源码中。注意这里的基类不是为了 OOP,而纯粹是一种实现技巧。

为什么 iterator 的递增递减是分摊(amortized)常数时间?

严格的证明需要用到分摊分析(amortized analysis),一来我不会,二来写出来也没多少人看,这里我用一点归纳的办法来说明这一点。考虑一种特殊情况,对前面图中的满二叉树(perfect binary tree)从头到尾遍历,计算迭代器一共走过多少步(即 follow 多少次指针),然后除以节点数 N,就能得到平均每次递增需要走多少步。既然红黑树是平衡的,那么这个数字跟实际的步数也相差不远。

对于深度为 1 的满二叉树,有 1 个元素,从 begin() 到 end() 需要走 1 步,即从 root 到 header。

对于深度为 2 的满二叉树,有 3 个元素,从 begin() 到 end() 需要走 4 步,即 1->2->3->header,其中从 3 到 header 是两步

对于深度为 3 的满二叉树,有 7 个元素,从 begin() 到 end() 需要走 11 步,即先遍历左子树(4 步)、走 2 步到达右子树的最左节点,遍历右子树(4 步),最后走 1 步到达 end(),4 + 2 + 4 + 1 = 11。

对于深度为 4 的满二叉树,有 15 个元素,从 begin() 到 end() 需要走 26 步。即先遍历左子树(11 步)、走 3 步到达右子树的最左节点,遍历右子树(11 步),最后走 1 步到达 end(),11 + 3 + 11 + 1 = 26。

后面的几个数字依次是 57、120、247

对于深度为 n 的满二叉树,有 2^n - 1 个元素,从 begin() 到 end() 需要走 f(n) 步。那么 f(n) = 2*f(n-1) + n。

然后,用递推关系求出 f(n) = sum(i * 2 ^ (n-i)) = 2^(n+1) - n - 2(这个等式可以用归纳法证明)。即对于深度为 n 的满二叉树,从头到尾遍历的步数小于 2^(n+1) - 2,而元素个数是 2^n - 1,二者一除,得到平均每个元素需要 2 步。因此可以说 rb_tree 的迭代器的递增递减是分摊后的常数时间。

似乎还有更简单的证明方法,在从头到尾遍历的过程中,每条边(edge)最多来回各走一遍,一棵树有 N 个节点,那么有 N-1 条边,最多走 2*(N-1)+1 步,也就是说平均每个节点需要 2 步,跟上面的结果相同。

说一点题外话。

为什么 muduo 网络库的 Poller 要用 std::map<int, Channel*> 来管理文件描述符?

muduo 在正常使用的时候会用 EPollPoller,是对 epoll(4) 的简单封装,其中用 std::map<int, Channel*> channels_ 来保存 fd 到 Channel 对象的映射。我这里没有用数组,而是用 std::map,原因有几点:

  • epoll_ctl() 是 O(lg N),因为内核中用红黑树来管理 fd。因此用户态用数组管理 fd 并不能降低时间复杂度,反而有可能增加内存使用(用 hash 倒是不错)。不过考虑系统调用开销,map vs. vector 的实际速度差别不明显。(题外话:总是遇到有人说 epoll 是 O(1) 云云,其实 epoll_wait() 是 O(N),N 是活动fd的数目。poll 和 select 也都是 O(N),不过 N 的意义不同。仔细算下来,恐怕只有 epoll_create() 是 O(1) 的。也有人想把 epoll 改为数组,但是被否决了,因为这是开历史倒车 https://lkml.org/lkml/2008/1/8/205 。)
  • channels_ 只在 Channel 创建和销毁的时候才会被访问,其他时候(修改关注的读写事件)都是位于 assert() 中,用于 Debug 模式断言。而 Channel 的创建和销毁本身就伴随着 socket 的创建和销毁,涉及系统调用,channels_ 操作所占的比重极小。因此优化 channels_ 属于优化 nop,是无意义的。

(.完.)

posted @ 2013-01-20 13:26 陈硕 阅读(8327) | 评论 (1)编辑 收藏

muduo多机协作网络编程示例一:单词计数及排序

去年我写了《Muduo 网络编程示例》系列文章,这些文章已经收入《Linux 多线程服务端编程:使用 muduo C++ 网络库》一书。这些文章讲的基本都是运行在单机上的网络程序,每个例子都只有一个程序(第7.13节例外)。我接下来打算继续写几篇文章,谈一谈分布在多台机器上、协作发挥作用的网络编程例子。

今天先讲第一个,单词计数及排序。单词计数(word count),顾名思义就是统计一个文本文件里边每个词出现了多少次。排序指的是按出现次数从多到少排序,也可以把问题改为“找出出现次数最多的1000个单词”。

这个问题有三个层次,第一是输入文件比较小,能完全放入内存;第二是输入文件比较大,不能一次性都放入内存;第三是输入文件分布在多台机器上,这需要用到网络编程。

第一个层次很好解决,几十行代码就搞定了。https://gist.github.com/4519962

第二个层次不难解决,基本思路是分而治之,先hash分块统计单词出现次数,将每一块按出现次数排序,最后归并。代码见 https://github.com/chenshuo/recipes/blob/master/puzzle/query_freq.cc ,分析见 http://www.cnblogs.com/baiyanhuang/archive/2012/11/11/2764914.html

第三个层次也不难,可以当做网络编程的练习来做。如果有合适的框架,可以轻松解决,因为单词计数是map reduce的经典范例,对出现次数排序也可以再用一步map reduce搞定(估计需要一个好的 shuffle 函数,简单hash是不行的)。

如果用普通网络编程,一种设计思路如下图,其中方框代表机器,椭圆代表输入输出文件,圆角矩形代表进程。思路跟第二个层次一样,先hash到多个shard文件(由hasher和receiver负责),再对每个shard文件排序(由sender负责),最后归并(merger)。

topk

注意这种思路适合求top K元素,不适合按出现次数排序全部单词,因为最终结果收集在一台机器上。目前这个sender实现的一个限制是,每个shard必须能全部放入内存,因为sender对shard排序是在内存中进行的。如果数据更大,还需要实现单机外部排序。

图中hasher和receiver的代码见muduo示例中的 muduo/examples/wordcount ;sender和merger的代码见 https://github.com/chenshuo/recipes/tree/master/topk 。注意merger没有使用muduo,而是采用阻塞网络编程。有兴趣的读者可以思考其背后的原因。要想发挥 merger 正常的性能,需要修改 /usr/include/boost/asio/basic_socket_streambuf.hpp ,增大缓冲区,即 enum { buffer_size = 8192 };

这可以看作是map reduce的原始实现,或者说用map reduce的思想手写了一些原始工具。如果把map reduce比作C语言,这里的几个程序相当于汇编写的函数。

以后我再写一个按出现次数全排序的例子吧,需要替换这里的sender和merger。

(.完.)

posted @ 2013-01-13 04:01 陈硕 阅读(3542) | 评论 (2)编辑 收藏

《Linux 多线程服务端编程:使用 muduo C++ 网络库》网上书店预订

内容简介

本书主要讲述采用现代 C++ 在 x86-64 Linux 上编写多线程 TCP 网络服务程序的主流常规技术,重点讲解一种适应性较强的多线程服务器的编程模型,即 one loop per thread。这是在 Linux 下以 native 语言编写用户态高性能网络程序最成熟的模式,掌握之后可顺利地开发各类常见的服务端网络应用程序。本书以 muduo 网络库为例,讲解这种编程模型的使用方法及注意事项。

本书的宗旨是贵精不贵多。掌握两种基本的同步原语就可以满足各种多线程同步的功能需求,还能写出更易用的同步设施。掌握一种进程间通信方式和一种多线程网络编程模型就足以应对日常开发任务,编写运行于公司内网环境的分布式服务统。

基本信息

cover

出版社:电子工业出版社

页数:xvi+600

定价:人民币89元

ISBN:9787121192821

豆瓣及网上书店预订

豆瓣:http://book.douban.com/subject/20471211/
互动:http://product.china-pub.com/3021861
亚马逊:http://www.amazon.cn/dp/B00AYS2KL0
当当:http://product.dangdang.com/product.aspx?product_id=23162953
京东:http://book.360buy.com/11163782.html

试读样章

前言与目录:https://chenshuo-public.s3.amazonaws.com/pdf/preamble.pdf
第1章:线程安全的对象生命期管理:https://chenshuo-public.s3.amazonaws.com/pdf/chap1.pdf
第6章:muduo网络库简介:https://chenshuo-public.s3.amazonaws.com/pdf/chap6.pdf
附录:https://chenshuo-public.s3.amazonaws.com/pdf/appendix.pdf
样章合集下载:http://vdisk.weibo.com/s/mtupb 共150页,包括第 11.5 节。

前言(节选)

本书主要讲述采用现代 C++ 在 x86-64 Linux 上编写多线程 TCP 网络服务程序的主流常规技术,这也是我对过去 5 年编写生产环境下的多线程服务端程序的经验总结。本书重点讲解多线程网络服务器的一种 IO 模型,即 one loop per thread。这是一种适应性较强的模型,也是 Linux 下以 native 语言编写用户态高性能网络程序最成熟的模式, 掌握之后可顺利地开发各类常见的服务端网络应用程序。本书以 muduo 网络库为例,讲解这种编程模型的使用方法及注意事项。

muduo 是一个基于非阻塞 IO 和事件驱动的现代 C++ 网络库,原生支持 one loop per thread 这种 IO 模型。muduo 适合开发 Linux 下的面向业务的多线程服务端网络应用程序,其中“面向业务的网络编程”的定义见附录 A。 “现代 C++”指的不是 C++11 新标准,而是 2005 年 TR1 发布之后的 C++ 语言和库。 与传统 C++ 相比,现代 C++ 的变化主要有两方面:资源管理(见第 1 章)与事件回调(见第 449 页)。

本书不是多线程编程教程,也不是网络编程教程,更不是 C++ 教程。读者应该已经大致读过《UNIX 环境高级编程》、《UNIX 网络编程》、《C++ Primer》或与之内容相近的书籍。本书不谈 C++11,因为目前(2012 年)主流的 Linux 服务端发行版的 g++ 版本都还停留在 4.4,C++11 进入实用尚需一段时日。

本书适用的硬件环境是主流 x86-64 服务器,多路多核 CPU、几十 GB 内存、千兆以太网互联。除了第 5 章讲诊断日志之外,本书不涉及文件 IO。

本书分为四大部分,第 1 部分“C++ 多线程系统编程”考察多线程下的对象生命期管理、线程同步方法、多线程与 C++ 的结合、高效的多线程日志等。第 2 部分“muduo 网络库”介绍使用现成的非阻塞网络库编写网络应用程序的方法,以及 muduo 的设计与实现。第 3 部分“工程实践经验谈”介绍分布式系统的工程化开发方法和 C++ 在工程实践中的功能特性取舍。第 4 部分“附录”分享网络编程和 C++ 语言的学习经验。

本书的宗旨是贵精不贵多。掌握两种基本的同步原语就可以满足各种多线程同步的功能需求,还能写出更易用的同步设施。掌握一种进程间通信方式和一种多线程网络编程模型就足以应对日常开发任务,编写运行于公司内网环境的分布式服务系统。(本书不涉及分布式存储系统,也不涉及 UDP。)

术语与排版范例


本书大量使用英文术语,甚至有少量英文引文。设计模式的名字一律用英文,例如 Observer、Reactor、Singleton。在中文术语不够突出时,也会使用英文,例如 class、heap、event loop、STL algorithm 等。注意几个中文 C++ 术语:对象实体(instance) 、函数重载决议(resolution) 、模板具现化(instantiation) 、覆写(override)虚函数、提领(dereference)指针。本书中的英语可数名词一般不用复数形式,例如两个 class,6 个 syscall;但有时会用 (s) 强调中文名词是复数。fd 是文件描述符(file descriptor)的缩写。“CPU 数目”一般指的是核(core)的数目。用诸如§11.5 表示本书第 11.5 节,L42 表示上下文中出现的第 42 行代码。[JCP]、[CC2e] 等是参考文献,见书末清单。

代码

本书的示例代码以开源项目的形式发布在 GitHub 上,
地址是 http://github.com/chenshuo/recipes/http://github.com/chenshuo/muduo/ 。本书配套页面提供全部源代码打包下载,正文中出现的类似 recipes/thread 的路径是压缩包内的相对路径,读者不难找到其对应的 GitHub URL。

本书假定读者熟悉 diff -u 命令的输出格式,用于表示代码的改动。

本书正文中出现的代码有时为了照顾排版而略有改写,例如改变缩进规则,去掉单行条件语句前后的花括号等。就编程风格而论,应以电子版代码为准。

联系方式


邮箱:giantchen_at_gmail.com

主页:http://chenshuo.com/book (正文和脚注中出现的 URL 可从这里找到。 )

微博:http://weibo.com/giantchen

博客:http://blog.csdn.net/Solstice

代码:http://github.com/chenshuo

陈硕

中国•香港

posted @ 2013-01-11 12:43 陈硕 阅读(4734) | 评论 (6)编辑 收藏

新书预告:《Linux 多线程服务端编程——使用 muduo C++ 网络库》

看完了 W. Richard Stevens 的传世经典《UNIX 网络编程》, 能照着例子用 Sockets API 编写 echo 服务, 却仍然对稍微复杂一点的网络编程任务感到无从下手? 书中示例代码把业务逻辑和 Sockets 调用混在一起,似乎不利于将来扩展?
  • 程序在本机测试正常,放到网络运行上就经常出现数据收不全的情况?
  • TCP 协议真的有所谓的“粘包问题”吗?该如何设计打包拆包的协议?又该如何编码实现才不会掉到陷阱里?
  • 带外数据(OOB)、信号驱动IO这些高级特性到底有没有用?
  • 网络协议格式该怎么设计?发送 C struct 会有对齐方面的问题吗?对方不用 C/C++ 怎么通信? 将来服务端软件升级,需要在协议中增加一个字段,现有的客户端就必须强制升级?
  • 要处理几千上万的并发连接,似乎书上讲的传统 fork() 模型应付不过来,该用哪种并发模型呢? 试试 select、poll、epoll 这种 IO 复用模型吧,又感觉非阻塞IO陷阱重重,怎么程序的 CPU 使用率一直是100%?
  • 要不改用现成的 libevent 网络库吧,怎么查询一下数据库就把其他连接上的请求给耽误了? 再用个线程池吧。万一发回响应的时候对方已经断开连接了怎么办?会不会串话?
  • 读过《UNIX 环境高级编程》,想用多线程来发挥多核 CPU 的效率, 但对程序该用哪种多线程模型感到一头雾水? 有没有值得推荐的适用面广的多线程 IO 模型? 互斥器、条件变量、读写锁、信号量这些底层同步原语哪些该用哪些不该用? 有没有更高级的同步设施能简化开发? 《UNIX 网络编程(第二卷)》介绍的那些琳琅满目的IPC机制到底用哪个才能兼顾开发效率与可伸缩性?
网络编程和多线程编程的基础打得差不多,开始实际做项目了,更多问题扑面而来:
  • 网上听人说服务端开发要做到 7x24 运行,为了防止内存碎片连动态内存分配都不能用, 那岂不是连 C++ STL 也一并禁用了?硬件的可靠性高到值得去这么做吗?
  • 传闻服务端开发主要通过日志来查错,那么日志里该写些什么?日志是写给谁看的?怎样写日志才不会影响性能?
  • 分布式系统跟单机多进程到底有什么本质区别?心跳协议为什么是必须的,该如何实现?
  • C++ 的大型工程该如何管理?库的接口如何设计才能保证升级的时候不破坏二进制兼容性?

这本《Linux 多线程服务端编程》中,作者凭借多年的工程实践经验试图解答以上疑问。当然,内容还远不止这些……


本书配套页面: http://chenshuo.com/book ,将不定期更新。

posted @ 2012-09-21 07:20 陈硕 阅读(3594) | 评论 (9)编辑 收藏

从《C++ Primer 第四版》入手学习 C++

《C++ Primer 第4版 评注版》即将出版,这是序言。PDF 版见:

https://github.com/downloads/chenshuo/documents/LearnCpp.pdf

从《C++ Primer 第四版》入手学习 C++

为什么要学习C++?

2009 年本书作者 Stan Lippman 先生来华参加上海祝成科技举办的C++技术大会,他表示人们现在还用C++的惟一理由是其性能。相比之下,Java/C#/Python等语言更加易学易用并且开发工具丰富,它们的开发效率都高于C++。但C++目前仍然是运行最快的语言[1],如果你的应用领域确实在乎这个性能,那么 C++ 是不二之选。

这里略举几个例子[2]。对于手持设备而言,提高运行效率意味着完成相同的任务需要更少的电能,从而延长设备的操作时间,增强用户体验。对于嵌入式[3]设备而言,提高运行效率意味着:实现相同的功能可以选用较低档的处理器和较少的存储器,降低单个设备的成本;如果设备销量大到一定的规模,可以弥补C++开发的成本。对于分布式系统而言,提高10%的性能就意味着节约10%的机器和能源。如果系统大到一定的规模(数千台服务器),值得用程序员的时间去换取机器的时间和数量,可以降低总体成本。另外,对于某些延迟敏感的应用(游戏[4],金融交易),通常不能容忍垃圾收集(GC)带来的不确定延时,而C++可以自动并精确地控制对象销毁和内存释放时机[5]。我曾经不止一次见到,出于性能原因,用C++重写现有的Java或C#程序。

C++之父Bjarne Stroustrup把C++定位于偏重系统编程(system programming) [6]的通用程序设计语言,开发信息基础架构(infrastructure)是C++的重要用途之一[7]。Herb Sutter总结道[8],C++注重运行效率(efficiency)、灵活性(flexibility)[9]和抽象能力(abstraction),并为此付出了生产力(productivity)方面的代价[10]。用本书作者的话来说,C++ is about efficient programming with abstractions。C++的核心价值在于能写出“运行效率不打折扣的抽象[11]”。

要想发挥C++的性能优势,程序员需要对语言本身及各种操作的代价有深入的了解[12],特别要避免不必要的对象创建[13]。例如下面这个函数如果漏写了&,功能还是正确的,但性能将会大打折扣。编译器和单元测试都无法帮我们查出此类错误,程序员自己在编码时须得小心在意。

inline int find_longest(const std::vector<std::string>& words)
{
  // std::max_element(words.begin(), words.end(), LengthCompare());
}

在现代CPU体系结构下,C++ 的性能优势很大程度上得益于对内存布局(memory layout )的精确控制,从而优化内存访问的局部性[14](locality of reference)并充分利用内存阶层(memory hierarchy)提速[15],这一点优势在近期内不会被基于GC的语言赶上[16]

C++的协作性不如C、Java、Python,开源项目也比这几个语言少得多,因此在TIOBE语言流行榜中节节下滑。但是据我所知,很多企业内部使用C++来构建自己的分布式系统基础架构,并且有替换Java开源实现的趋势。

学习C++只需要读一本大部头

C++不是特性(features)最丰富的语言,却是最复杂的语言,诸多语言特性相互干扰,使其复杂度成倍增加。鉴于其学习难度和知识点之间的关联性,恐怕不能用“粗粗看看语法,就撸起袖子开干,边查Google边学习[17]”这种方式来学习C++,那样很容易掉到陷阱里或养成坏的编程习惯。如果想成为专业C++开发者,全面而深入地了解这门复杂语言及其标准库,你需要一本系统而权威的书,这样的书必定会是一本八九百页的大部头[18]

兼具系统性和权威性[19]的C++教材有两本,C++之父Bjarne Stroustrup的代表作《The C++ Programming Language》和Stan Lippman的这本《C++ Primer》。侯捷先生评价道:“泰山北斗已现,又何必案牍劳形于墨瀚书海之中!这两本书都从C++盘古开天以来,一路改版,斩将擎旗,追奔逐北,成就一生荣光[20]。”

从实用的角度,这两本书读一本即可,因为它们覆盖的C++知识点相差无几。就我个人的阅读体验而言,Primer更易读一些,我十年前深入学习C++正是用的《C++ Primer第三版》。这次借评注的机会仔细阅读了《C++ Primer第四版》,感觉像在读一本完全不同的新书。第四版内容组织及文字表达比第三版进步很多[21],第三版可谓“事无巨细、面面俱到”,第四版重点突出详略得当,甚至篇幅也缩短了,这多半归功于新加盟的作者Barbara Moo。

《C++ Primer 第四版》讲什么?适合谁读?

这是一本C++语言的教程,不是编程教程。本书不讲八皇后问题、Huffman编码、汉诺塔、约瑟夫环、大整数运算等等经典编程例题,本书的例子和习题往往都跟C++本身直接相关。本书的主要内容是精解C++语法(syntax)与语意(semantics),并介绍C++标准库的大部分内容(含STL)。“这本书在全世界C++教学领域的突出和重要,已经无须我再赘言[22]。”

本书适合C++语言的初学者,但不适合编程初学者。换言之,这本书可以是你的第一本C++ 书,但恐怕不能作为第一本编程书。如果你不知道什么是变量、赋值、分支、条件、循环、函数,你需要一本更加初级的书[23],本书第1章可用作自测题。

如果你已经学过一门编程语言,并且打算成为专业C++开发者,从《C++ Primer 第四版》入手不会让你走弯路。值得特别说明的是,学习本书不需要事先具备C语言知识。相反,这本书教你编写真正的C++程序,而不是披着C++ 外衣的C程序。

《C++ Primer 第四版》的定位是语言教材,不是语言规格书,它并没有面面俱到地谈到C++的每一个角落,而是重点讲解C++程序员日常工作中真正有用的、必须掌握的语言设施和标准库[24]。本书的作者一点也不炫耀自己的知识和技巧,虽然他们有十足的资本[25]。这本书用语非常严谨(没有那些似是而非的比喻),用词平和,讲解细致,读起来并不枯燥。特别是如果你已经有一定的编程经验,在阅读时不妨思考如何用C++来更好地完成以往的编程任务。

尽管本书篇幅近900页,其内容还是十分紧凑,很多地方读一个句子就值得写一小段代码去验证。为了节省篇幅,本书经常修改前文代码中的一两行,来说明新的知识点,值得把每一行代码敲到机器中去验证。习题当然也不能轻易放过。

《C++ Primer 第四版》体现了现代C++教学与编程理念:在现成的高质量类库上构建自己的程序,而不是什么都从头自己写。这本书在第三章介绍了string和vector这两个常用的类,立刻就能写出很多有用的程序。但作者不是一次性把string的上百个成员函数一一列举,而是有选择地讲解了最常用的那几个函数。

《C++ Primer 第四版》的代码示例质量很高,不是那种随手写的玩具代码。第10.4.2节实现了带禁用词的单词计数,第10.6利用标准库容器简洁地实现了基于倒排索引思路的文本检索,第15.9节又用面向对象方法扩充了文本检索的功能,支持布尔查询。值得一提的是,这本书讲解继承和多态时举的例子符合Liskov替换原则,是正宗的面向对象。相反,某些教材以复用基类代码为目的,常以“人、学生、老师、教授”或“雇员、经理、销售、合同工”为例,这是误用了面向对象的“复用”。

《C++ Primer 第四版》出版于2005年,遵循2003年的C++语言标准[26]。C++新标准已于2011年定案(称为C++11),本书不涉及TR1[27]和C++11,这并不意味着这本书过时了[28]。相反,这本书里沉淀的都是当前广泛使用的C++编程实践,学习它可谓正当时。评注版也不会越俎代庖地介绍这些新内容,但是会指出哪些语言设施已在新标准中废弃,避免读者浪费精力。

《C++ Primer 第四版》是平台中立的,并不针对特定的编译器或操作系统。目前最主流的C++编译器有两个, GNU G++和微软Visual C++。实际上,这两个编译器阵营基本上“模塑[29]”了C++语言的行为。理论上讲, C++语言的行为是由C++标准规定的。但是 C++不像其他很多语言有“官方参考实现[30]”,因此C++的行为实际上是由语言标准、几大主流编译器、现有不计其数的C++产品代码共同确定的,三者相互制约。C++编译器不光要尽可能符合标准,同时也要遵循目标平台的成文或不成文规范和约定,例如高效地利用硬件资源、兼容操作系统提供的C语言接口等等。在C++标准没有明文规定的地方,C++编译器也不能随心所欲自由发挥。学习C++的要点之一是明白哪些行为是由标准保证的,哪些是由实现(软硬件平台和编译器)保证的[31],哪些是编译器自由实现,没有保证的;换言之,明白哪些程序行为是可依赖的。从学习的角度,我建议如果有条件不妨两个编译器都用[32],相互比照,避免把编译器和平台特定的行为误解为C++语言规定的行为。尽管不是每个人都需要写跨平台的代码,但也大可不必自我限定在编译器的某个特定版本,毕竟编译器是会升级的。

本着“练从难处练,用从易处用”的精神,我建议在命令行下编译运行本书的示例代码,并尽量少用调试器。另外,值得了解C++的编译链接模型[33],这样才能不被实际开发中遇到的编译错误或链接错误绊住手脚。(C++不像现代语言那样有完善的模块(module)和包(package)设施,它从C语言继承了头文件、源文件、库文件等古老的模块化机制,这套机制相对较为脆弱,需要花一定时间学习规范的做法,避免误用。)

就学习C++语言本身而言,我认为有几个练习非常值得一做。这不是“重复发明轮子”,而是必要的编程练习,帮助你熟悉掌握这门语言。是写一个复数类或者大整数类[34],实现基本的运算,熟悉封装与数据抽象。是写一个字符串类,熟悉内存管理与拷贝控制。是写一个简化的vector<T>类模板,熟悉基本的模板编程,你的这个vector应该能放入int和string等元素类型。是写一个表达式计算器,实现一个节点类的继承体系(右图),体会面向对象编程。前三个练习是写独立的值语义的类,第四个练习是对象语义,同时要考虑类与类之间的关系。

表达式计算器能把四则运算式3+2*4解析为左图的表达式树[35],对根节点调用calculate()虚函数就能算出表达式的值。做完之后还可以再扩充功能,比如支持三角函数和变量。


在写完面向对象版的表达式树之后,还可以略微尝试泛型编程。比如把类的继承体系简化为下图,然后用BinaryNode<std::plus<double> >和BinaryNode<std:: multiplies<double> >来具现化BinaryNode<T>类模板,通过控制模板参数的类型来实现不同的运算。


在表达式树这个例子中,节点对象是动态创建的,值得思考:如何才能安全地、不重不漏地释放内存。本书第15.8节的Handle可供参考。(C++的面向对象基础设施相对于现代的语言而言显得很简陋,现在C++也不再以“支持面向对象”为卖点了。)

C++难学吗?“能够靠读书看文章读代码做练习学会的东西没什么门槛,智力正常的人只要愿意花功夫,都不难达到(不错)的程度。[36]” C++好书很多,不过优秀的C++开源代码很少,而且风格迥异[37]。我这里按个人口味和经验列几个供读者参考阅读:Google的protobuf、leveldb、PCRE的C++ 封装,我自己写的muduo网络库。这些代码都不长,功能明确,阅读难度不大。如果有时间,还可以读一读Chromium中的基础库源码。在读Google开源的C++代码时要连注释一起细读。我不建议一开始就读STL或Boost的源码,因为编写通用C++模板库和编写C++应用程序的知识体系相差很大。 另外可以考虑读一些优秀的C或Java开源项目,并思考是否可以用C++更好地实现或封装之(特别是资源管理方面能否避免手动清理)。

继续前进

我能够随手列出十几本C++好书,但是从实用角度出发,这里只举两三本必读的书。读过《C++ Primer》和这几本书之后,想必读者已能自行识别C++图书的优劣,可以根据项目需要加以钻研。

第一本是《Effective C++ 第三版》[38]。学习语法是一回事,高效地运用这门语言是另一回事。C++是一个遍布陷阱的语言,吸取专家经验尤为重要,既能快速提高眼界,又能避免重蹈覆辙。《C++ Primer》加上这本书包含的C++知识足以应付日常应用程序开发。

我假定读者一定会阅读这本书,因此在评注中不引用《Effective C++ 第三版》的任何章节。

《Effective C++ 第三版》的内容也反映了C++用法的进步。第二版建议“总是让基类拥有虚析构函数”,第三版改为“为多态基类声明虚析构函数”。因为在C++中,“继承”不光只有面向对象这一种用途,即C++的继承不一定是为了覆写(override)基类的虚函数。第二版花了很多笔墨介绍浅拷贝与深拷贝,以及对指针成员变量的处理[39]。第三版则提议,对于多数class而言,要么直接禁用拷贝构造函数和赋值操作符,要么通过选用合适的成员变量类型[40],使得编译器默认生成的这两个成员函数就能正常工作。

什么是C++编程中最重要的编程技法(idiom)?我认为是“用对象来管理资源”,即RAII。资源包括动态分配的内存[41],也包括打开的文件、TCP网络连接、数据库连接、互斥锁等等。借助RAII,我们可以把资源管理和对象生命期管理等同起来,而对象生命期管理在现代C++里根本不是困难(见注5),只需要花几天时间熟悉几个智能指针[42]的基本用法即可。学会了这三招两式,现代的C++程序中可以完全不写delete,也不必为指针或内存错误操心。现代C++程序里出现资源和内存泄漏的惟一可能是循环引用,一旦发现,也很容易修正设计和代码。这方面的详细内容请参考《Effective C++ 第三版》第3章资源管理。

C++是目前惟一能实现自动化资源管理的语言,C语言完全靠手工释放资源,而其他基于垃圾收集的语言只能自动清理内存,而不能自动清理其他资源[43](网络连接,数据库连接等等)。

除了智能指针,TR1中的bind/function也十分值得投入精力去学一学[44]。让你从一个崭新的视角,重新审视类与类之间的关系。Stephan T. Lavavej有一套PPT介绍TR1的这几个主要部件[45]

第二本书,如果读者还是在校学生,已经学过数据结构课程[46],可以考虑读一读《泛型编程与STL》[47];如果已经工作,学完《C++ Primer》立刻就要参加C++项目开发,那么我推荐阅读《C++编程规范》[48]

泛型编程有一套自己的术语,如concept、model、refinement等等,理解这套术语才能阅读泛型程序库的文档。即便不掌握泛型编程作为一种程序设计方法,也要掌握C++中以泛型思维设计出来的标准容器库和算法库(STL)。坊间面向对象的书琳琅满目,学习机会也很多,而泛型编程只有这么一本,读之可以开拓视野,并且加深对STL的理解(特别是迭代器[49])和应用。

C++模板是一种强大的抽象手段,我不赞同每个人都把精力花在钻研艰深的模板语法和技巧。从实用角度,能在应用程序中写写简单的函数模板和类模板即可(以type traits为限),不是每个人都要去写公用的模板库。

由于C++语言过于庞大复杂,我见过的开发团队都对其剪裁使用[50]。往往团队越大,项目成立时间越早,剪裁得越厉害,也越接近C。制定一份好的编程规范相当不容易。规范定得太紧(比如定为团队成员知识能力的交集),程序员束手束脚,限制了生产力,对程序员个人发展也不利[51]。规范定得太松(定为团队成员知识能力的并集),项目内代码风格迥异,学习交流协作成本上升,恐怕对生产力也不利。由两位顶级专家合写的《C++编程规范》一书可谓是现代C++编程规范的范本。

《C++编程规范》同时也是专家经验一类的书,这本书篇幅比《Effective C++ 第三版》短小,条款数目却多了近一倍,可谓言简意赅。有的条款看了就明白,照做即可:

·         第1条,以高警告级别编译代码,确保编译器无警告。

·         第31条,避免写出依赖于函数实参求值顺序的代码。C++操作符的优先级、结合性与表达式的求值顺序是无关的。裘宗燕老师写的《C/C++ 语言中表达式的求值》[52]一文对此有明确的说明。

·         第35条,避免继承“并非设计作为基类使用”的class。

·         第43条,明智地使用pimpl。这是编写C++动态链接库的必备手法,可以最大限度地提高二进制兼容性。

·         第56条,尽量提供不会失败的swap()函数。有了swap()函数,我们在自定义赋值操作符时就不必检查自赋值了。

·         第59条,不要在头文件中或#include之前写using。

·         第73条,以by value方式抛出异常,以by reference方式捕捉异常。

·         第76条,优先考虑vector,其次再选择适当的容器。

·         第79条,容器内只可存放value和smart pointer。

有的条款则需要相当的设计与编码经验才能解其中三昧:

·         第5条,为每个物体(entity)分配一个内聚任务。

·         第6条,正确性、简单性、清晰性居首。

·         第8、9条,不要过早优化;不要过早劣化。

·         第22条,将依赖关系最小化。避免循环依赖。

·         第32条,搞清楚你写的是哪一种class。明白value class、base class、trait class、policy class、exception class各有其作用,写法也不尽相同。

·         第33条,尽可能写小型class,避免写出大怪兽。

·         第37条,public继承意味着可替换性。继承非为复用,乃为被复用。

·         第57条,将class类型及其非成员函数接口放入同一个namespace。

值得一提的是,《C++编程规范》是出发点,但不是一份终极规范。例如Google的C++编程规范[53]和LLVM编程规范[54]都明确禁用异常,这跟这本书的推荐做法正好相反。

评注版使用说明

评注版采用大开本印刷,在保留原书板式的前提下,对原书进行了重新分页,评注的文字与正文左右分栏并列排版。本书已依据原书2010年第11次印刷的版本进行了全面修订。为了节省篇幅,原书每章末尾的小结和术语表还有书末的索引都没有印在评注版中,而是做成PDF供读者下载,这也方便读者检索。评注的目的是帮助初次学习C++的读者快速深入掌握这门语言的核心知识,澄清一些概念、比较与其他语言的不同、补充实践中的注意事项等等。评注的内容约占全书篇幅的15%,大致比例是三分评、七分注,并有一些补白的内容[55]。如果读者拿不定主意是否购买,可以先翻一翻第5章。我在评注中不谈C++11[56],但会略微涉及TR1,因为TR1已经投入实用。

为了不打断读者阅读的思路,评注中不会给URL链接,评注中偶尔会引用《C++编程规范》的条款,以[CCS]标明,这些条款的标题已在前文列出。另外评注中出现的soXXXXXX表示http://stackoverflow.com/questions/XXXXXX 网址。

网上资源

代码下载:http://www.informit.com/store/product.aspx?isbn=0201721481
豆瓣页面:http://book.douban.com/subject/10944985/
术语表与索引PDF下载:http://chenshuo.com/cp4/
本文电子版发布于https://github.com/chenshuo/documents/downloads/LearnCpp.pdf,方便读者访问脚注中的网站。

我的联系方式:giantchen_AT_gmail.com                    http://weibo.com/giantchen

 

陈硕

2012年3月

中国·香港

 

评注者简介 :

陈硕,北京师范大学硕士,擅长 C++ 多线程网络编程和实时分布式系统架构。现任职于香港某跨国金融公司 IT 部门,从事实时外汇交易系统开发。编写了开源 C++ 网络库 muduo; 参与翻译了《代码大全(第二版)》和《C++ 编程规范(繁体版)》;2009 年在上海 C++ 技术大会做技术演讲《当析构函数遇到多线程》,同时担任 Stanley Lippman 先生的口译员;2010 年在珠三角技术沙龙做技术演讲《分布式系统的工程化开发方法》;2012年在“我们的开源项目”深圳站做《Muduo 网络库:现代非阻塞C++网络编程》演讲。

 



[1] 见编程语言性能对比网站 http://shootout.alioth.debian.org/ 和Google 员工写的语言性能对比论文

   https://days2011.scala-lang.org/sites/days2011/files/ws3-1-Hundt.pdf

[2] C++之父Bjarne Stroustrup维护的C++用户列表:http://www2.research.att.com/~bs/applications.html

[3] 初窥C++在嵌入式系统中的应用,请见http://aristeia.com/TalkNotes/MISRA_Day_2010.pdf

[4] Milo Yip在《C++强大背后》提到大部分游戏引擎(如Unreal/Source)及中间件(如Havok/FMOD)是C++实现的。http://www.cnblogs.com/miloyip/archive/2010/09/17/behind_cplusplus.html

[5] 孟岩《垃圾收集机制批判》:C++利用智能指针达成的效果是,一旦某对象不再被引用,系统刻不容缓,立刻回收内存。这通常发生在关键任务完成后的清理(clean up)时期,不会影响关键任务的实时性,同时,内存里所有的对象都是有用的,绝对没有垃圾空占内存。http://blog.csdn.net/myan/article/details/1906

[6] 有人半开玩笑地说“所谓系统编程,就是那些CPU时间比程序员的时间更重要的工作。”

[7] 《Software Development for Infrastructure》 http://www2.research.att.com/~bs/Computer-Jan12.pdf

[8] Herb Sutter在C++ and Beyond 2011会议上的开场演讲《Why C++?》
   http://channel9.msdn.com/posts/C-and-Beyond-2011-Herb-Sutter-Why-C

[9] 这里的灵活性指的是编译器不阻止你干你想干的事情,比如为了追求运行效率而实现即时编译(just-in-time compilation)。

[10] 我曾向Stan Lippman介绍目前我在Linux下的工作环境(编辑器、编译器、调试器),他表示这跟他在1970年代的工作环境相差无几,可见C++在开发工具方面的落后。另外C++的编译运行调试周期也比现代的语言长,这多少影响了工作效率。

[11] 可参考Ulrich Drepper在《Stop Underutilizing Your Computer》中举的SIMD例子。
   http://www.redhat.com/f/pdf/summit/udrepper_945_stop_underutilizing.pdf

[12]《Technical Report on C++ Performance》 http://www.open-std.org/jtc1/sc22/wg21/docs/18015.html

[13] 可参考Scott Meyers的《Effective C++ in an Embedded Environment》

   http://www.artima.com/shop/effective_cpp_in_an_embedded_environment

[14] 我们知道std::list的任一位置插入是O(1)操作,而std::vector的任一位置插入是O(N)操作,但由于std::vector的元素布局更加紧凑(compact),很多时候std::vector的随机插入性能甚至会高于std::list。见http://ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11Style.pdf 这也佐证std::vector是首选容器。

[15] 可参考Scott Meyers的技术报告《CPU Caches and Why You Care》和任何一本现代的计算机体系结构教材 http://aristeia.com/TalkNotes/ACCU2011_CPUCaches.pdf

[16] Bjarne Stroustrup有一篇论文《Abstraction and the C++ machine model》对比了C++和Java的对象内存布局。 http://www2.research.att.com/~bs/abstraction-and-machine.pdf

[17] 语出孟岩《快速掌握一个语言最常用的50%》 http://blog.csdn.net/myan/article/details/3144661

[18] 同样篇幅的Java/C#/Python教材可以从语言、标准库一路讲到多线程、网络编程、图形编程。

[19] “权威”的意思是说你不用担心作者讲错了,能达到这个水准的C++图书作者全世界也屈指可数。

[20] 侯捷《大道之行也——C++ Primer 3/e译序》 http://jjhou.boolan.com/cpp-primer-foreword.pdf

[21] Bjarne Stroustrup在《Programming--- Principles and Practice Using C++》的参考文献中引用了本书,并特别注明 use only the 4th edition.

[22] 侯捷《C++ Primer 4/e译序》

[23] 如果没有时间精读注21中提到的那本大部头,短小精干的《Accelerated C++》亦是上佳之选。另外如果想从C语言入手,我推荐裘宗燕老师的《从问题到程序:程序设计与C语言引论(第2版)》

[24] 本书把iostream的格式化输出放到附录,彻底不谈locale/facet,可谓匠心独运。

[25] Stan Lippman曾说:Virtual base class support wanders off into the Byzantine... The material is simply too esoteric to warrant discussion...

[26] 基本等同于1998年的初版C++标准,修正了编译器作者关心的一些问题,与普通程序员基本无关。

[27] TR1是2005年C++标准库的一次扩充,增加了智能指针、bind/function、哈希表、正则表达式等。

[28]作者正在编写《C++ Primer 第五版》,会包含C++11的内容。

[29] G++统治了Linux平台,并且能用在很多Unix平台上;Visual C++统治了Windows平台。其他C++编译器的行为通常要向它们靠拢,例如Intel C++在Linux上要兼容G++,而在Windows上要兼容Visual C++。

[30] 曾经是Cfront,本书作者正是其主要开发者。http://www.softwarepreservation.org/projects/c_plus_plus

[31] 包括C++标准有规定,但编译器拒绝遵循的。http://stackoverflow.com/questions/3931312/value-initialization-and-non-pod-types

[32] G++ 是免费的,可使用较新的4.x版,最好32-bit和64-bit一起用,因为服务端已经普及64位。微软也有免费的编译器,可考虑Visual C++ 2010 Express,建议不要用老掉牙的Visual C++ 6.0作为学习平台。

[33] 可参考陈硕写的《C++工程实践经验谈》中的“C++编译模型精要”一节。

[34] 大整数类可以以std::vector<int>为成员变量,避免手动资源管理。

[35] “解析”可以用数据结构课程介绍的逆波兰表达式方法,也可以用编译原理中介绍的递归下降法,还可以用专门的Packrat算法。可参考http://www.relisoft.com/book/lang/poly/3tree.html

[36]  孟岩《技术路线的选择重要但不具有决定性》 http://blog.csdn.net/myan/article/details/3247071

[37] 从代码风格上往往能判断项目成型的时代。

[38] Scott Meyers著,侯捷译,电子工业出版社。

[39] Andrew Koenig的《Teaching C++ Badly: Introduce Constructors and Destructors at the Same Time》

http://drdobbs.com/blogs/cpp/229500116

[40] 能自动管理资源的string、vector、shared_ptr等等,这样多数class连析构函数都不必写。

[41] “分配内存”包括在堆(heap)上创建对象。

[42] 包括TR1中的shared_ptr、weak_ptr,还有更简单的boost::scoped_ptr。

[43] Java 7有try-with-resources语句,Python有with语句,C#有using语句,可以自动清理栈上的资源,但对生命期大于局部作用域的资源无能为力,需要程序员手工管理。

[44] 孟岩《function/bind的救赎(上)》http://blog.csdn.net/myan/article/details/5928531

[45] http://blogs.msdn.com/b/vcblog/archive/2008/02/22/tr1-slide-decks.aspx

[46] 最好再学一点基础的离散数学。

[47] Matthew Austern著,侯捷译,中国电力出版社。

[48] Herb Sutter等著,刘基诚译,人民邮电出版社。(这本书繁体版由侯捷先生和我翻译。)

[49] 侯捷先生的《芝麻开门:从Iterator谈起》 http://jjhou.boolan.com/programmer-3-traits.pdf

[50] 孟岩《编程语言的层次观点——兼谈C++的剪裁方案》 http://blog.csdn.net/myan/article/details/1920

[51] 一个人通常不会在一个团队工作一辈子,其他团队可能有不同的C++剪裁使用方式,程序员要有“一桶水”的本事,才能应付不同形状大小的水碗。

[52] http://www.math.pku.edu.cn/teachers/qiuzy/technotes/expression2009.pdf

[53] http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Exceptions

[54] http://llvm.org/docs/CodingStandards.html#ci_rtti_exceptions

[55] 第10章绘制了数据结构示意图,第11章补充lower_bound 和 upper_bound的示例。

[56] 从Scott Meyers的讲义可以快速学习C++11 http://www.artima.com/shop/overview_of_the_new_cpp

posted @ 2012-07-06 09:00 陈硕 阅读(2594) | 评论 (3)编辑 收藏

《Muduo 网络库:现代非阻塞C++网络编程》演讲

2012年6月30日下午将在深圳做《Muduo 网络库:现代非阻塞C++网络编程》演讲,

这是PPT:

http://www.slideshare.net/chenshuo/muduo-network-library

演讲视频:

http://v.youku.com/v_show/id_XNDIyNDc5MDMy.html

http://youtu.be/YDnCAs894Bg 


活动介绍:

http://ouropensource.51qiangzuo.com/

posted @ 2012-07-01 23:55 陈硕 阅读(5275) | 评论 (29)编辑 收藏

发布一个适合服务端C++程序的高效日志库

PPT 见 http://www.slideshare.net/chenshuo/efficient-logging-in-multithreaded-c-server/

2012年6月30日在深圳的简短演讲:

http://v.youku.com/v_show/id_XNDIyMjUwMDYw.html

http://www.youtube.com/watch?v=KM_eQ6uRYdU

 


代码位于 muduo 网络库中的 muduo/base

https://github.com/chenshuo/muduo

muduo 0.5.0 也包含了这个日志库 http://code.google.com/p/muduo/

posted @ 2012-06-06 21:27 陈硕 阅读(8444) | 评论 (5)编辑 收藏

C++ 工程实践(12):C++ 编译链接模型精要

《C++ 工程实践》新增第15节“C++ 编译链接模型精要”  


PDF 下载: https://github.com/downloads/chenshuo/documents/CppPractice.pdf  

posted @ 2012-04-20 08:18 陈硕 阅读(2435) | 评论 (1)编辑 收藏

C++ 工程实践(11):用 STL algorithm 秒杀几道算法面试题

《C++ 工程实践》新增第14节“用 STL algorithm 秒杀几道算法面试题” 


PDF 下载: https://github.com/downloads/chenshuo/documents/CppPractice.pdf 

posted @ 2012-04-01 10:08 陈硕 阅读(2749) | 评论 (0)编辑 收藏

C++ 工程实践(10):再探std::string

本文总结了std::string的三种常见实现方式。 


全文见 https://github.com/downloads/chenshuo/documents/CppPractice.pdf 第13节。 

posted @ 2012-03-17 16:58 陈硕 阅读(3281) | 评论 (3)编辑 收藏

仅列出标题
共6页: 1 2 3 4 5 6 
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

随笔分类

随笔档案

相册

搜索

最新评论

阅读排行榜

评论排行榜