为什么我希望用C而不是C++来实现ZeroMQ(第二篇)

译注:这篇文章可能又会引起 C++ 程序员的诸多不适,就作者本文所描述的问题来看,某些“C++的问题”其实是可以有C++的解决方案的。请参阅侵入式和非侵入式容器。但是考虑到ZeroMQ是一个很底层的高性能网络库(ZeroMQ的目标是纳入Linux内核中,这也应该是改用C的一大原因,毕竟目前的ZeroMQ是用C++实现的),对错误处理、内存分配次数、并发效率等有着极高的要求,这些特定的限制往往不是所有的C++程序员所常见的应用场景。因此希望各位在阅读时能多从作者的角度来考虑这些问题,而不是一味地批判作者的C++编程实践能力。

上一篇博文中,我已经讨论过了在需要进行严格错误处理的系统底层基础架构的开发中需要避免使用一些C++特性(异常、构造函数、析构函数)。我的结论是,当为C++加上了这样的使用限制后,用C来实现的话会使得代码更简短也更容易阅读。这么做的副作用是消除了对C++运行时库的依赖,而这不应该轻易地去掉,尤其是在嵌入式环境下。

在这一篇博文中,我想从另一个不同的角度来探究这个问题。即:使用C++和C相比,在性能上有什么区别?理论上,这两种语言产生的程序性能应该是相同的。面向对象只不过是在过程式语言之上的语法糖而已,这使得代码对人类而言更加容易理解。人类大脑似乎已经进化为一种自然的能力来处理以流程,关系等这类实体为主的对象。

每个C++程序都能自动转换为等同的C程序——尽管这种说法理论上成立——但面向对象的观念使得开发者以特定的方式来思考并相应地以面向对象的方式来设计他们的算法和数据结构,而这反过来会对程序性能带来影响。

让我们来比较一下,C++程序员要如何实现对象链表:

注:假设包含在链表中的对象是不可赋值(non-assignable)的,因为这种情况下任何非简单的对象,比如持有大量内存缓冲区,文件描述符,句柄等这样的对象,如果对象是可赋值的,那么简单地使用std::list<person>就够用了,不会有任何问题。

C程序员更倾向于按照如下的方式解决同样的问题:

现在,让我们比较一下两种解决方案的内存模型:

首先注意到的是C++的解决方案对比C来说多分配了2倍的内存块。针对链表中的每个元素,都要创建一个小的帮助对象。当程序中有许多容器时,这些帮助对象的总数就会扩散开来。比如,在ZeroMQ中创建和连接一个socket将导致数十次内存分配。而在我当前正在做的C版本中,创建一个socket只需要一次内存分配,连接时会再需要一次。

很明显,内存分配的次数会引起性能问题。分配内存所花费的时间可能是无关紧要的——在ZeroMQ中,这并不是关键路径(请参阅关于ZeroMQ中关键路径的分析)——但是,内存使用量以及内存碎片带来的问题就非常重要了。这直接影响到CPU缓存是如何填充的,以及由此带来的缓存miss率。回顾一下,到目前为止对物理内存的访问是现代计算机上最慢的操作,这样就知道这种性能影响会有多严重了。

当然,这还没完呢。

实现方案的选择对算法的复杂度有着直接的影响。在C++版中,从链表中移除一个对象是O(n)的复杂度:

在C版本中,可以确保在常数时间内完成(简化版):

C++版本效率的低下是由于std::list的实现所致还是由于面向对象的编程范式所致呢?让我们深入的探究这个问题。

C++程序员不会以C的方式来设计链表的真正原因是因为这种设计破坏了封装的原则:“person”类的实现者必须要知道person的实例最终会存储到“people”链表中。此外,如果第三方开发者决定将其存储到另外一个链表中时,就必须修改person的实现。这正是奉行面向对象编程的程序员所极力避免的。

但是,如果我们不把prev和next指针放在person类内部,我们就必须把它们放置在别的地方。所以,除了多分配一个帮助对象外没有别的办法了,这正是std::list<>所采用的做法。

此外,虽然帮助对象中包含有指向“person”对象的指针,但“person”对象却不能包含有指向帮助对象的指针。如果这么做了,那就破坏了封装的原则——“person”就必须知道包含自己的容器。结果就是,我们可以将指向帮助对象(迭代器iterator)的指针转型为指向“person”,但反过来却不可以。这就是为什么从std::list<>中移除一个元素需要遍历整个链表,换句话说,这就是为什么需要O(n)的复杂度。

简单来说,如果我们遵从面向对象的编程范式,我们就无法实现一个所有操作都是O(1)的链表。如果要那么做就必须破坏封装的原则。

注:很多人都指出应该使用迭代器而不是指针。但是,假设某个对象需要被包含在10个不同的链表中。你将不得不传递一个包含10个迭代器的结构体,而不是只传一个指针。此外,这并没有解决封装的问题,只是把问题移到了别处而已。当你希望将对象添加到一个新的容器类型中时,虽然你不用修改“person”的实现了,但你仍然不得不去修改包含迭代器的结构体。

这应该就是本文的结论了。但是这个主题实在太有意思了,我还想再问一个问题:这种低效到底是源于面向对象的设计还是说只是特定于C++语言呢?我们能否设想以一种面向对象的编程语言来实现所有相关操作都为O(1)复杂度的链表呢?

要回答这个问题我们必须理解问题的根本。而这个问题来自对术语“对象”的定义。在C++中“class”只是对C语言中“struct”的代名词,这两个关键字几乎可以互换使用。言下之意是指“对象”是一系列存储在连续内存空间中的数据集合。

这对于C++程序员来说是想都不用想的问题。但是让我们从不同的角度来分析“对象”。

我们说对象是一系列逻辑上相关联的数据的集合,在多线程程序中应该处于同一个临界区中受到保护。这一定义从根本上改变了我们对程序架构的理解。下面这张图展示了C语言版的person/people程序,并标识出了数据域应该由一个链表级的临界区(黄色部分),还是由元素级的临界区(绿色部分)来保护。

从面向对象的角度来看,这张图实在太诡异。“people”对象不仅包含有“people”结构体内的字段,还包含有“person”结构体中的一些域(“prev”和“next”指针)。

但是出人意料的是,从技术角度来看这种分解却十分有道理:

1.  链表级的临界区保护着黄色部分的字段,这确保了链表的一致性。另一方面,链表级的临界区并没有对绿色部分的字段进行保护(“age”和“weight”),因此      允许对单独的数据进行修改而不必锁住整个链表。

2.  黄色部分的字段应该只能由“people”类的方法来访问,尽管从内存布局上来看它们都是属于“person”结构体的。

3.  如果编程语言允许我们在“people”类的内部声明黄色部分的字段,那么封装的原则就不会被打破。换句话说,将“person”添加到其它链表中时就不需要         对“person”类的定义进行修改。

最后,让我们做一个概念性的实验,采用上述思想来扩展C++。请注意,我们的目标不是为了提供一种完美的语言扩展设计,更多的是为了展示在C++中实现这种思想的可能性。

也就是说,让我引入一种“private in X”的语法结构。它可以使用在类定义中,遵循“private in X”形式的数据成员在物理上(作者指的是按内存布局来看)属于结构体X的一部分,但是它们只能由被定义的类来访问:

我的结论是,如果ZeroMQ用C来实现的话,内存分配将更少,产生的内存碎片也更少。一些算法的复杂度将达到O(1),而不是O(n)或者O(logn)。

效率低下的问题不在于ZeroMQ的代码本身,也不是面向对象编程的固有缺陷,更多的是在于C++语言的设计上。当然,公平的说C++并不是唯一,同样的问题也存在于大多数——如果不是全部的话——面向对象编程语言中。

 

英文原文:martin_sustrik      编译:伯乐在线— 陈舸

【如需转载,请标注并保留原文链接、译文链接和译者等信息,谢谢合作!】

 

1 收藏 13 评论

关于作者:bigship

简介还没来得及写 :) 个人主页 · 我的文章 · 9

相关文章

可能感兴趣的话题



直接登录
最新评论
  • ytj   2012/11/26

    不同意文章看法,这种比较是极不公平的。

    首先,STL根本不是为面向对象编程设计的(STL的发明人和C++发明人都是这么说的,而且STL容器也没有公共基类,连接口都不完全一样)。

    其次,效率问题不是C++与C的问题,拿C语言照样可以写出非侵入式容器。

    最后,C语言那种写法,面对每种类型都要重新实现链表所有操作(除非假设有某种一致的类型布局,不过这种东西就像一个定时炸弹)。既然文章都提供了链接,不明白为什么不直接用boost::intrusive,可以获得和C完全相同的效率,而且不会有C中那么多问题。

  • steven   2013/03/01

    扯淡,C的那种实现方式在C++中配合list使用的话就写
    std::list,然后每次都是用迭代器进行使用,效果和在C里面使用列表是完全一样的。我实现想不出你这样比较有什么意义,这个根本不是语言的问题,而是你自身设计的问题。

  • steven   2013/03/01

    kao,刚刚写的是std::list 居然没出来

  • abc   2013/09/05

    boost有侵入式的list,有什么问题?
    如果不爽,自己写一个侵入式list有什么问题?

  • abc   2013/09/05

    效率低下的问题不在于ZeroMQ的代码本身,也不是面向对象编程的固有缺陷,更多的是在于C++语言的设计上
    ---------------
    这种说法,实在搞笑。只能说自己不会c++而已。

  • 别问我是谁   2013/09/05

    "在C++版中,从链表中移除一个对象是O(n)的复杂度:

    void erase_person(person *ptr)
    {
    for (std::list ::iterator it = people.begin();
    it != people.end(); it++)
    {
    if (*it == ptr)
    people.erase(it);
    }
    }" 作者根本不懂C++!有了当前元素的iterator,people.erase(it);一句话就可以删除。同样是O(1)时间复杂度。不用iterator而用原始指针,只能说明作者还在用C++的编译器写C程序而已。

  • 抓狂   2013/10/18

    同意作者观点
    1. 消息库,本身就是追求简单和效率,主要是内存和队列操作,没有太复杂的语义,用C足够了。
    2. C++虽然支持了面向对象,但其代价是增加了语法复杂度,同时亦然有C本身固有的“缺陷”:手动内存管理和指针运算。现在C++是两边不讨好:系统级开发不需要用它,应用级开发不敢用它,剩下的估计就是历史遗漏的各种框架和图形库了。

  • 奏之章   2014/01/08

    std::list迭代器是做什么的?
    博主真的会C++么...?
    标准库并不是最好的库.只是方便使用的库...
    觉得非侵入设计不好,可以自己实现个侵入式设计的模板,和C实现完全一样的内存布局又有什么难度?

  • rao   2015/03/19

    作者确实是不懂c++,看来zeromq的质量堪忧!
    对于如何保持person,作者不知道有模板,或者是如下:
    template list {
    struct Element {
    T content;
    Element* prev
    Element* next
    }
    }
    相差不大。
    至于后面的list元素删除,c版本用了双向链表,难道list就不能用双向链表?

  • 「但是,假設某個對象需要被包含在10個不同的鏈表中。你將不得不傳遞一個包含10個迭代器的結構體,而不是只傳一個指針。」
    以作者所說的C實現(person自帶prev與next),一個person對象怎能被包含在10個不同的鏈表中?
    難道這個person對象能帶10個next,10個prev?
    要在C裡面把同一個對象放在10個不同的鏈表中,最終還是需要在鏈表裡放指針,指往真正的對象。那和std::list有甚麼分別?
    而且用C的話,要不每種struct都定義一種專用的鏈表,要不就用void*然後強制轉換,並祈禱千萬不要傳錯別的類型的鏈表。
    反而在C++裡,可以像樓上指出的一樣,用模版自動定義這種「內建鏈表指針的對象」。

    另外那個「多次內存分配」的問題,仔細點看,他的std::list放的是person*而不是person,那當然要每次再額外分配空間給person呀……
    他的C實現實際上是類近於std::list,根本沒得比。
    我不清楚各種廠商的STL怎樣實現std::list,但如果是定義一個struct list_container { T*prev; T*next; T data; };的話,存取data應該只是單純的由編譯器計算偏移量進行存取吧?
    那不論是分配內存的次數,還是存取data的開銷,都跟C一樣吧。
    當然內存使用量也許不同,但這要看具體STL實現。記憶中微軟曾經大幅優化過各種STL容器的內存使用量……

    C++的確是很難用,過份複雜,我也不喜歡C++(雖然只是初學),但作者的批評實在太扯。

  • 作者c++水平实在初等,对模板理解堪忧,为什么是std::list 而不是std::list ?
    也不知道迭代器,为什么要拿void erase_person(person *ptr)和void erase_person(struct person *ptr)比而不是void erase_person(std::list ::iterator)和void erase_person(struct person *ptr)比?

  • vkyii   2016/04/29

    作者是用着C++的Cer,不要强求太多

跳到底部
返回顶部