页面

分类

Posts in category ‘程序设计’.

Arrays of Structures/Objects

2016年10月19日星期三, by wingfire ; 分类: 计算机技术, 程序设计; 0 comments

An interesting programming paradigm.

类似于数据库中的按列存储。库LibFlatArray

    Arrays of Structures is the normal programming model.

    Let's take a toy example, say I'm looking at some census data and have a structure that looks like:

    struct citizen_t {
        string first_name;
        string last_name;
        int salary;
        int age;
    };

    Then the Array of Structures container would be:
    vector<citizen_t> aos_citizens;

    The Structure of Arrays version of the same data would look like:

    struct soa_citizens_t {
        vector<string> first_names;
        vector<string> last_names;
        vector<int> salary;
        vector<int> age;
    };

    soa_citizens_t soa_citizens;


    Why does this matter?

    Let's say I want to calculate the average salary of 300 million citizens. 
    The code is a simple iterative average and very simple.

    // Array of Structures
    int avg = 0;
    int t = 1;
    for ( auto & c : aos_citizens ) {
        avg += (c.salary - avg) / t;
        ++t;
    }


    // Structures of Arrays
    int avg = 0;
    int t = 1;
    for ( int salary : soa_citizens.salary ) {
        avg += (salary  - avg) / t;
        ++t;
    }

    Run this under a simple benchmark:
    https://ideone.com/QNqKpD

    AoS 3.03523 seconds
    SoA 1.94902 seconds


    Both loops are doing the exact same work but the memory layout allows the second loop to run much faster.

Array-of-Structs: Array-of-Structs Struct-of-Arrays: Struct-of-Arrays

关于spurious wakeup的坑

2016年10月11日星期二, by wingfire ; 分类: 计算机技术, 代码相关, 程序设计; 0 comments

最近新开了一个叫mui的项目,打算用来写material的管理界面。这里面要实现一个跨线程的同步事件处理,和SendMessage类似,但是要求允许从任意线程发起SendMessage,但是对应的事件处理必须在事件循环所在的线程中被执行。让事件处理在特定线程中执行,这个挺常见,boost.asio也是这么保证的。但是,这种执行都是异步的,而我需要的是同步的。即线程递送事件后就被阻塞住,直到该事件的响应在主线程中处理完毕。

当然,这个完全可以直接使用mutex和condition_variable来实现。但是代码未免有些啰嗦,测试是不是正确也不方便。golang的channel恰好特别适合这个场景,反正也觊觎了golang的channel许久,既然用在这里正好,那就山寨一个吧。

channel默认是不带缓冲的,其中有个关键特性传递数据时producer和consumer的同步。网上很多的山寨都搞错了,把线程安全的queue当作了channel,这是不对的。除非queue满了(如果实现有此限制的话),否则往queue中push数据是不必等待有人接收的,不会被阻塞。channel则不同,producer输出数据的过程是被阻塞的,直到被consumer取走。这样,channel的数据传递过程就可以被当作同步点来使用,queue是没有这个功能的。channel的这个同步特性是非常重要的特点,来源于CSP。

带缓冲的channel呢?和queue有什么区别?我觉得是没有本质区别的。所以我觉得golang的设计在l概念上是很分裂的,带不带缓冲应该是完全不同的东西。带了缓冲,同步点机制就没有了。我没看golang的实现代码,但是我很怀疑内部其实也是两套实现,两者的差别其实是很大的。希望golang专家有兴趣可以指点一下。

背景交代完毕。

    void push(T* t) {
        std::unique_lock<std::mutex> lock(this->mutex);

        this->cv_producer.wait(lock, 
             [&] {return this->tmp == nullptr; });  // line 1

        this->tmp = t;
        this->cv_consumer.notify_one();

        this->cv_sync_producer.wait(lock, 
             [&] {return this->tmp == nullptr; });   // Line 2

        this->cv_producer.notify_one();  // line 3
    }

    T pull() {
        std::unique_lock<std::mutex> lock(this->mutex);

        this->cv_consumer.wait(lock, 
             [&] {return this->tmp != nullptr; }); // line 4

        T ret = *this->tmp;
        this->tmp = nullptr;

        this->cv_sync_producer.notify_one();  // Line 5
        return ret;
    }

和queue不同,放置完数据后,push动作会阻塞在line 2处,直到pull中取走数据。当push线程离开语句line 2时,pull线程也几乎同时离开其语句5. 这里就是所需要的同步点。queue的push是不必有语句 2和3,直接返回就好。

简单吧?悲剧的是,因为spurious wakeup的缘故,这段代码有错误。所谓的虚假唤醒,就是condition variable并没有收到通知时,也被唤醒了。虚假唤醒的解释参见维基:https://en.wikipedia.org/wiki/Spurious_wakeup

当然,虽说发生虚假唤醒的条件无法断言,但实际上也不是完全不可捉摸的。就我在windows平台上所观察到的现象而言,似乎只有发生线程切换,且等待在同一个mutex上才会导致虚假唤醒。

假设有两个push线程A和B,当A等待在语句2处时,假设B等待在语句1. 这时pull线程进入,执行到语句5,企图通过cv_sync_producer唤醒线程A,然后自己返回了。本来期待的是A线程会被唤醒,然后把B释放,让下一个传输得以开始。然而因为虚假唤醒,偶然地,等在1处的线程B被唤醒了。B唤醒后,有可能抢在A之前被执行,于是也到等在了语句2处,释放了锁。A当然也会被唤醒 --本来唤醒目标就是它么--,但是因为B在等待前设置了tmp,A的条件检测失败,又重新进入等待。于是A、B都等在了语句2处。这是程序状态已经错误了。

接下来,又来了一个pull线程,消费掉了tmp,然后notify,释放出了一个等在2处的push线程,假设是A,那B线程还得等。此时的tmp将是null,导致pull进不来,但是此时2处的push也出不去,死锁。只要调用次数足够多,最终所有的push都会被积压在语句2处,而所有的pull则被堵在语句4,系统停摆 -- 当然,停摆之前的行为就已经错误了,所以停摆是好事,暴露了问题。

按照解决spurious wakeup的一般建议,设立一个条件变量的伴生标记,从条件变量被唤醒后,必须检查伴生的标记,以确保不是虚假唤醒。这段代码貌似也检查了标记tmp,但是这个标记是被两个条件变量共享了,因此出了问题。知道了原因和解决方案,纠正起来就很容易了:

    void push(T* t) {
        std::unique_lock<std::mutex> lock(this->mutex);

        this->cv_producer.wait(lock, 
             [&] {return this->tmp == nullptr; });

this->entered = true;

        this->tmp = const_cast<T*>(t);
        this->cv_consumer.notify_one();

        this->cv_sync_producer.wait(lock, 
             [&] {return this->tmp == nullptr; });

this->entered = false;

        this->cv_producer.notify_one();
    }

这是我第二次遭遇到虚假唤醒的问题了。但仔细回忆起来,恐怕很多年前在使用boost的时候似乎也遇到过一次,当时并没有搞明白具体原因,而是换了个实现消除bug了事。这次乘机查了一下boost 1.35的文档,果然里面是有提到虚假唤醒的问题的。这么说来,我其实已经是第三次掉同一个坑里了......

问题虽然解决了,但是不能不好奇为什么会存在虚假唤醒这样奇特的行为。掉进坑里三次固然是我的错,但这个坑本身显然是违背程序员人性的存在。从使用条件变量的角度来说,我看不出虚假唤醒有任何的利用价值,这个行为完全是负面的,为什么至今没有被消除呢?据此推测,这个特性存在的根源可能有两种可能,一种可能是技术上的限制,使得消除虚假唤醒不可能或者代价高昂。另一种可能,这就是一个早期的设计错误,只不过由于历史原因和技术壁垒,它被固化了。某个强势领域的错误渐渐地被固化成一种特性,这样的事情本来也是屡见不鲜的。

维基上的解释是,在某些架构上,要实现一个没有虚假唤醒条件变量可能大幅度拖慢条件变量的操作。看上去我的前一个猜测对了,那不难推测,这很可能和CPU的体系结构有关系。

那么,到底是哪些架构有这个问题?消除这个问题又会怎么付出性能代价的呢?这个链接 提出了同样的问题。这里有讨论,主要有两点理由,只涉及Linux。一个原因为signal,为了响应EINTR,按照惯例,系统调用是可能被EINTR中断并取消的,需要用户重新进入。第二个原因也和signal有关,Linux的内核通过系统调用futex实现signal,但是很难实现从内核代码回调signal handler,因此只好先返回用户空间。

我觉得这两个原因虽然是事实,但理由都很勉强。首先,系统调用响应signal是惯例,但并非真理。如果这是必须的话,难道lock操作也得响应signal?boost.thread的作者似乎也是这么认为的,代码是这样写的:

    BOOST_FORCEINLINE int pthread_mutex_lock(pthread_mutex_t* m)
    {
      int ret;
      do
      {
          ret = ::pthread_mutex_lock(m);
      } while (ret == EINTR);
      return ret;
    }

假设有多个pthread_mutex_lock已经被阻塞住了,因为signal要返回,这将导致惊群效应。这两个解释似乎并不那么可靠。正如猜测的,pthread_mutex_lock并不存在类似虚假唤醒的问题,手册明确写道:

If a signal is delivered to a thread waiting for a mutex, upon return from the signal handler the thread shall resume waiting for the mutex as if it was not interrupted.

并且

These functions shall not return an error code of [EINTR].

pthread_cond_wait的文档则说:

These functions shall not return an error code of [EINTR].

对于signal,

If a signal is delivered to a thread waiting for a condition variable, upon return from the signal handler the thread resumes waiting for the condition variable as if it was not interrupted, or it shall return zero due to spurious wakeup.

至此,我知道lock和wait都是同样经由futex实现的,从技术上来说,没有道理lock可以工作得仿佛不存在中断,而条件变量就不行。看来,虚假唤醒的根本原因并非是futex,毕竟windows平台上也有着同样的问题。

到目前为止,我还是没有找到有说服力的解释,倒是搜到一本书 《Programming with POSIX Threads》

不变式、断言、契约和异常之我见

2016年8月29日星期一, by wingfire ; 分类: 代码相关, 程序设计; 2 comments

说起不变式和断言,程序员们是不陌生的。然而,对其内涵的理解,以及如何运用,实践中却颇多谬误。

不变式和断言常常是同义词,都是用来进行程序正确性分析的手段。在分析和讨论程序正确性时,断言和不变式含义没什么区别。但断言常常也指用于检验不变式的语言设施。

在分析程序正确性时,一旦不变式被打破,意味着程序存在逻辑错误,此时就没有必要在这个逻辑错误的基础上继续讨论了。但是在实际编程中,我们使用断言来检验不变式,一旦失败,总还会有个程序行为,默认的行为一般是程序终止。这里的“终止”,是指abort,或core dump,而非优雅地退出。

进入正题前,让我们先岔开一下,来看另外一个问题。

在某些语言中,如Pascal,Oracle数据库中,过程可以分为两类,一类叫function,另一类叫procedure。这对于来自于C社区的程序员来说,这种区分貌似是颇为多余的。从语言的实现层面看,这两者似乎也是一致的,没有区分的必要。当然,情况并非如此。Procedure,也被称为方法(Method,含义不同于OO所谓的方法),是指那些存在副作用的过程。而Function,也被称为查询(Query),指那些不改变系统状态的程序过程。对程序员来说,这两类过程对系统的影响是截然不同的。这种划分不是出于底层实现的需要,而是出于程序员认知的需要。

方法和查询在语法上的形式可以完全一样,但语义差别巨大。方法的返回值是一般是要被检查的,而查询的返回值则可以安全忽略。查询不改变系统,因此无论被连续调用多少次--虽然也可能消耗资源--所返回的结果总是相同的,查询因此被称为幂等的。幂等也意味着可以任意叠加组合而不影响系统正确性。方法因为有副作用,一般是不能被任意叠加调用的,即通常不是幂等的。查询的一次调用,也被称为对系统的一次观测。一次观测可以获取一个或多个系统状态。

在程序设计中,应该仔细地区分方法和查询。一个方法可能产生多个副作用,哪些副作用期待被观测到,这在设计时要明确。除了那些被设计所规定的可观测的副作用,一个方法不应该有其他副作用且能被系统内的某个查询所观测。这意味着一个方法的副作用并不能在设计时完全自由地增减,还要受制于系统的已有部分,简言之,设计本身是受限的,受系统的语义一致性所限制。例如,假设有某个方法向文件中写入一段文本,并且返回操作结束后这个文件的长度,或者在接口文档中声称文件长度增加量为文本的长度。如果这里说明文件长度的行为是必要的,那么系统就应该同时提供获取被写文件长度的查询。如果不能提供这种查询,那么关于文件长度的副作用描述就应该从方法中--函数原型和文档中--删除。注意,这和通过系统外的工具查询获得文件长度的变化并不矛盾。

在实践上,出于性能考虑,某个方法可以设计为返回副作用引起的一个或多个重要状态变化。即便如此,仍然需要为所有的副作用提供查询。以STL中map::insert为例,insert返回被插入元素位置的迭代器和一个是否成功插入的标记。实际上,我们可以在调用insert方法之前通过find查询待插入元素是否已经存在,从而预判insert的可能副作用,也可以在insert之后,通过find被插元素然后获得插入的位置。这两者在性能上都有所损失,因此insert的返回值是必要的。另一方面,不能因为insert返回了相当多的信息就不再提供相关的查询。

观测副作用并不都是可以随时进行的,有时需要一些准备工作。在map::insert的例子中,还有其他的副作用,例如,如果插入成功,map的size将增长1。要想观测这个效果,就必须在插入前记录map的size,插入后再次查询size,然后进行比较。关于方法和查询关系的描述往往容易让人误以为查询是附属于方法的,实事当然并非如此。确实存在某些查询只能服务于某个方法的情况,但是在map::insert的例子中,find和size查询显然都不是专为insert而设计的。对一个方法的所有副作用,都加以分析,看是不是所有的副作用都可以观测,这个步骤可以列入设计检查清单。实践中,我们总能检查出一些方法的副作用定义是不详细的,或者是不能观测的,这样的设计当然是需要修正的。

然而,性能是一个不能不考虑的方面。方法的副作用可能存在多种观测方式,我们有必要以最小算法复杂度提供必要的查询。有时候这会导致陷入两难,例如std::list::size()方法。为了实现常数时间复杂度的splice (来自两个list), 在C++98中,size允许是线性复杂度的方法,到C++11中,要求必须是常数时间。作为一般的原则,尽可能廉价地提供查询总是正确的,为此,甚至可以在一定程度上牺牲方法的性能。同样以splice为例,如果不考虑size()的效率,那么splice完全可以实现成总是常数时间的。当然,这种权衡只是一种经验规则,不能教条化。

如果一个系统的所有方法都满足其副作用可观测这一原则,这个系统的可测试性就完成了一半。在实践上来看,这将完成可测试性的一大半。

再回到断言。

区分方法和查询的可以帮助回答什么样的代码可以作为断言。一般而言,断言是一个表达式,而这个表达式必须是由查询组成的,不能有副作用。因为没有副作用,查询无论调用多少次,都不影响系统的逻辑正确性,因此,断言也有同样的性质,即必须也是幂等的。这就是为什么在实践中我们为什么可以在调试版本中保留断言,而在发布版中删除之,因为两者程序逻辑并未发生变化。我们也应该注意到,并没有什么逻辑上的原因要求将断言从发布版本中删除掉。去除断言是出于性能上的考虑。在相当多的实践中,都建议在发布版中保留断言,除非这么做会导致不可接受的性能损失(VC的STL为了支持调试,debug build的性能极差,真是吐槽无力)。

如何使用断言呢?这其实这包含三个部分:何时断言,何处断言,以及断言什么。很多讲不变式文章给出的例子是在一个循环开始前断言一个变量状态,在循环中或循环后再断言一个状态。这给初学者一种错觉,似乎断言只是为了帮助正确实现一个函数。断言的用途当然不仅于此,然而,这种感觉有一点是正确且重要的,即对实现者自身的怀疑和检验。断言并不直接证明程序是正确的,而是防备程序的某些错误的。这里所谓的“防备”也不是说程序员能够因此避免引入错误,而是寄希望于引入错误后能够发现。断言断的是程序员的“犯错”,是针对自身犯错可能的防范。

断言的另一个常见使用模式是用来描述函数执行前系统状态要满足的条件,和函数执行后系统状态将会满足的条件,即前条件和后条件。前条件也称前置条件、先验条件,后条件则也称为后置条件、后验条件。随着契约式程序设计思想的扩散,断言的这种使用方式就更加标准化了。在接口中描述的前后条件,是和接口的调用者之间的契约。前条件是调用者要保证达成的,后条件是函数的实现者承诺要达成的。在编程实践中,鼓励尽量用合法的语句来描述前后条件,但也有大量的情况是不可能用合法语句描述的,就需要辅之以文档,这种文档必须被认为是接口的一部分。对前后条件的检验,就成了对调用者可能出错的防范。

原则上来说,程序的实现者只需在认可的上下文中正确履行功能。以函数而言,其输出必须正确,这没什么疑问(呃,其实也未必没有争论)。但是其输入和开始执行前的系统状态也必须正确的要求,则往往被误解,认为即使前条件不满足,也应该尽力履行功能,美其名曰“防御式编程”。这是错误的。无论是在微观的程序编码层面、设计层面,甚至项目研发层面,都有个行之有效的原则,即快速失败原则(Fast Fail)。这个原则要求任何的错误都应该尽早地,尽可能响亮地暴露出来,而不是加以隐藏。工作流程也应该顺应此要求。失败并不可怕,可怕的是掩盖失败。所谓防御式编程是对可能出现的错误做详尽的检测,以利于从根源上加以消除,而不是鼓励就地对问题加以掩盖。有时候,分辨解决问题和掩盖问题并不是那么容易的事,尤其是在要说服合作者的时候。

如果认可了快速失败的设计哲学,对前条件的理解就可以做合理的极端化。在前条件不满足的情况下,一段程序可以任意行事,包括使程序崩溃--这是最大声的嚷嚷。这时候,断言防备的就不仅仅是函数实现者自身的失误,而是防备函数调用者的失误--尽管调用者和实现者可能是同一个人,我们还是有必要做出角色上的区分,这是两种不同的角色。可以借用生产者和消费者的术语,设计、实现接口的,是生产者,调用方是消费者。程序员在编程时总是不断在这两种身份中切换的,甚或兼而有之。作为消费者,必须明白调用一个函数前要满足哪些前提条件,这是你的职责所在。作为生产者,有权检验前提条件是否都成立,有任何一条不成立,按照契约式程序设计的观点,就有权“撕毁契约”。注意,要区分这里的权利和义务。义务是向别人承诺的,是你要保证做到的,无论这种义务是否能通过代码加以检查;而生产者所要求的前条件是权利,调用者无权要求生产者必须或不能对每一项权利加以检查。有些人是分不清其中的区别的。

以strcpy(char dest, const char src)为例,dest必须不是空指针,消费者很容易保证这一点,但不应指望strcpy必然会断言dest不为空。又例如,dest所指空间必须足够大,这一点,strcpy是很难检测的,strcpy可以放弃检测,但这不意味着strcpy放弃了该权利。再比如,dest和src必须都不是野指针(显然),但是检测并不容易,但是这仍然是调用者的义务,和strcpy的权利。

尽管理论上并不要求对“权利”一一核查,但是在实践上,对于那些能够检测的前置条件,我们还是应该尽量在实现的时候通过断言一一加以检测。除非这种检测过于昂贵而难以承担。比如性能损失很大,不可靠,太复杂等等。这种对前条件的充分检测,才是真正的所谓防御式编程。这种检测只需要断言,而不是通过if...else...的分支就地“解决”问题。即便发现是设计错误,这个问题也必然要带回到设计层面去分析解决,“就地”是不可能的。

要想一个函数能成功执行,所需的前提条件是相当多的。有些前后条件是作为常识或约定出现的,比如,合法的指针参数,足够的栈空间等等,引用非空,默认是不必列出的。列出来,反而意味者有特殊情况。而一个函数到底应该有哪些前条件?这基本上是一个设计问题,虽然实现的可行性也是必须要考虑的。而设计,是需要在一个上下文中加以选择和取舍的。

对于如何使用断言的三个问题,从契约式程序设计的观点来看,对于何时、何处使用断言,是很好回答的了。前条件当然是在进入函数后,立即完成(实际可能有更复杂的情况,某些检查会稍微延后)。后条件的检查则是在被调函数返回后。这中观点不意味着排斥传统的在一个复杂函数的内部实现中使用断言,只是那种使用方式不再是一个重要的议题了--这其实也意味着后条件的检验是相对不太重要的。

然而,对于断言什么的问题,就没有机械的条款可循了。什么东西可以称为前后条件,除了受制于函数的功能,更多的是受制于设计者的选择和设计决策 -- 一个函数具有什么功能一样是设计者决定的。但是作为一般的原则是,前条件尽可能地“苛刻”(放宽对调用者的前条件总是容易的),把环境定得很细,使得实现代码所必需处理的意外降低到最少。一言以蔽之,奉行极简主义,追求高内聚。C标准库的strcpy是这方面的一个正面例子。

然而,也要防止过犹不及。

我曾经遇到这样一个例子:一个渲染引擎有个两个图片加载函数--姑且称为LoadA和LoadB,这两个函数都是用来加载某种图片的,但是这种图片内部有两种格式的(渲染引擎所需),LoadA和LoadB分别只能正确加载预期的那种格式。当某次渲染效果错误时,发现是用户程序员用错了Load函数和对应格式的图片,渲染引擎程序员一开始认为这是用户程序员的错误。于是问题来了:用户程序员有什么办法能区分这两种图片吗?答:两者图片内部结构是有不同的。再问:这种结构不同的知识,是应该渲染引擎掌握,还是用户程序必须掌握?答:这是渲染相关的知识,用户程序逻辑不应该掌握。

至此,问题应该怎么解决就很清楚了。

据这个例子的目的是想说明,尽管要奉行极简主义,但是不能要求消费方去掌握属于生产方的知识--不是看这种知识是简单还是复杂,而要看其归属于哪一方。这种以谁掌握相关知识来进行判断有时也会遇到困难。在上面的例子中,如果引擎提供了一个函数来检测图片文件的类型,从而消费方有充分的知识得以正确选择LoadA或LoadB呢?这时,在这个例子中还可以通过性能、简单性加以选择和设计。然而,具体到某个项目,恐怕就难以作出一般的指导了。

尽管断言什么很大程度上取决于设计者的取舍和决定,很难像另外两个问题一样作出机械的指导,但也还是有些指南可供参考,不至于茫然无措。

  • 区别方法和查询
  • 功能分解和正交
  • 定义基本操作集合(其中的函数都是不能通过别的函数来实现的),以区别于复合操作(原则上都是可以基于基本操作集合中的函数来实现的)
  • 最小化函数功能
  • 极简主义
  • 在恰当的粒度级别上进行抽象。

需要对第6条做一点说明。软件离不开抽象,在什么层次上,针对什么进行抽象,不同性质的项目也会有不同。以具有一定规模的C++项目而言,可能的抽象层次有:函数、类、组件、模块。其中,模块常常可以对应为一个动态库。解释什么是模块有点困难,C++并没有对组件的直接支持。但是,在我看来,组件恰恰是最重要的抽象级别。识别一个组件,要看它是否提供了一组相对完整且封闭的功能。这种识别不是全然清晰的。以STL为例,vector算是一个组件吗?还是所有的容器是一个组件?还是说容器+算法+迭代器+内存管理算是一个组件?在我看来,这还得看在什么层次上进行设计和讨论。STL显然是作为一个整体被设计出来的,尽管容器看上去相当独立,没有迭代器、算法和内存管理的容器是不完整的。但是,这不妨碍我们在实现一个新容器时把它看作一个独立的组件来设计。因此,在我看来,STL是一个由多个子组件构成的单一大型组件。区别组件和其他抽象的关键在于,组件关注的中心是功能组。函数、类则有很多语言结构方面的东西要处理(至少在现代C++中这很突出),模块则要较多考虑依赖和物理抽象的问题,各有侧重。一般而言,我们要站在组件和组件间交互的角度来进行设计上的选择和取舍。

这些指南并不告诉你如何选择前条件,只是你选择的前条件应该尽力促使系统满足这些要求。这些指南的存在意味着前条件的设计不是个纯技术的问题,有相当多的经验和艺术的成分。

我们可以出于同样的原则选择后条件。再次强调的是,和前条件一样,哪些东西成为后条件也是个设计问题,而不是实现问题,至少主要不是实现问题。那有没有可能我调用你一个函数的时候,前条件都满足了,但是后条件就是无法满足呢?作为调用者,按照我们关于契约的理论,你无须担心,满足后条件是被调函数的义务,不是你的。你需要担心的是,如果你在实现一个函数的时候,发现某种情形下,后条件无法达成,怎么办?这时,如果你认为前条件的设计是正确合理的,那你唯一的选择就是抛出异常。由此也可以得出一个推论,如果某个被调用函数会抛出异常,可即便如此,你还是应该且能够达成后条件,那显然就应该捕获异常了。

至于异常安全的问题,那是另外一个主题,不在这里展开了。有兴趣的可以参考10年前的旧文《如何编写异常安全的C++代码》 https://icerote.net/blog/post/65

从断言和契约式程序设计出发,我们可以得到一个相当形式化的关于异常的使用方式。这和老旧的书籍中对于异常使用时机的建议是截然不同的。或许你会质疑这种形式化并没有从本质上消除老旧建议中问题分析的结论的不确定性,只是将那种分析转移到了接口设计步骤中去了。确实如此。可是这种转移不正是我们期望的吗?好的软件技术和方法就是要能够让程序员将精力尽量转移到问题分析和设计上去啊。

正经话说完了,下面开喷。

  • 断言就是用来帮助调试的

有道理,脑子是用来头疼的嘛。吃核桃仁的时候用门夹核桃了吧?

  • 断言允许忽略是个好主意,也是必要的

脑子是个好东西,但不是人人都有。死人三天后也能复活的嘛,你说呢?

  • 异常太难用了

当然,断言也一样难用。对没脑子的来说,难度其实和写个函数是一样的。

  • 没人能写异常安全的代码

也没有人能写没有bug的程序,所以也没有人会写程序。

关于函数返回值

2016年6月5日星期日, by wingfire ; 分类: 计算机技术, 程序设计; 2 comments

你青睐什么样的编程观点?实效的或是符合理论的?命令式的还是函数式的?无论是哪一种,函数的返回值在其中都起着极其重要的作用。然而,受某些风格,甚至仅仅是某些库的影响,存在着一种抛弃函数返回值的风气。即使在某些情况下没有彻底抛弃,也被降格为二等公民使用,不得不让人大跌眼镜。对C/C++这类语言来说,参数很容易有多个,但是返回值只有一个,这意味着返回值的设计比参数的设计更重要。不可思议的是,这么重要的设施,没有成为设计上的兵家必争之地,反而就这么被许多人固化为传输错误码的通道,甚至干脆被抛弃了。买椟还珠,也不过就是这样吧?

确实,在某些库(如COM相关的)中普遍存在着用返回值来标示错误码的做法,但是这么做不意味着都是正确的,更不意味着这么做都是好的。其中一些是因为语言本身的缺陷所导致的困扰,另一些是工程上的优化和折衷,还有一些则完全是错误传统的继承和扩散。在语法上,C和C++都只有一个返回值。然而存在迂回的方法模仿多个返回值。例如,为返回值定义一个struct,将所有的函数输出定义在这个struct中。这么做是可行的,但是一来太麻烦,二来受制于传统,并未被广泛采用。C++11中提供了更好的工具,std::tuple。然而,对tuple的使用仍然不够广泛,传统的库也没有完成这样的转变,有些库因为接口依赖或兼容方面的原因,也不适合依赖标准库。即便如此,我们仍然应该认识到函数返回值被弱化是一种工程限制或错误实践,而绝不是学习和效仿的对象。在许多现在语言中,多返回值都是受到语言直接支持的。

以C运行库和Posix库的函数为例,大多数情况下函数的返回值都是和函数职责直接相关的,如open,并非仅仅返回错误码。用errno存储错误码当然不理想,也带来很多问题,但比起放弃返回值还是好很多。放弃返回值,函数的输出只好通过输出参数来传递。输出参数带来的不仅仅是函数调用形式的变化,也丧失了重要的逻辑表达方式。程序逻辑很重要,逻辑的表达方式同样重要。不同于返回值方式,输出参数方式除了要用额外的语句定义输出变量外(导致表达啰嗦),还妨碍组合调用且丧失了链式处理。if(obj.foo().bar())这样极具表达力的语句是无法在没有返回值的情况下完成的。g(foo(), bar())这样简单的表达也会啰嗦到让人发指:

      T f;
      U b;
      foo(&f);
      bar(&b);
      R result;
      g(&result, f, b);

这还是极简单的例子,就不要提稍微复杂点的了。

也不要辩解说什么有迂回的方式能达成链式调用和组合调用,然而正如C/C++有迂回的方式支持多返回值,然而那并没有在实践中正常发挥作用。

说的远一点,在C++ Java这样的语言中引入异常机制付出了多大的代价?很大!无论是教育,实践,甚至是运行时代码,都付出了不小的代价。可是我们为什么要花那么大代价引入异常?仅仅是为了“优雅地“传播错误码吗?仅仅就传播错误码而言,异常算不上多优雅。但是,异常解放了返回值,仅此一点,就值回我们为异常付出的所有努力。

但还有很多人,继续走在放弃返回值的道路上。可悲。

Xirang Array的一个缺陷分析

2015年5月9日星期六, by wingfire ; 分类: 计算机技术, 程序设计; 0 comments

最近写了一个程序,用来将Protein的asset对象转换成新的xirang的运行时对象,基本完工。但是,在运行这个转换工具程序的时候,遇到了一个不稳定重现的问题。稍微跟踪了一下代码,发现是在序列化新系统中的一个Array对象时,引用的元素Type无效。

序列化获取Type的过程非常简单,它检测到了问题,但调用栈并不包含问题根源的事发现场。我没有立刻去跟踪代码去定位问题发源地,而是仔细回忆了设计逻辑。

为了抛弃历史包袱和保持新的运行时的单纯性,Protein和新系统分处在两个运行时中,相互是隔绝的。转换程序中有个特别繁琐的地方,就在于要将Protein的asset对象的每个property,逐个地赋值给对应的新系统中对应对象的data member.因为property和data member分属不同的系统,因此,即使它们具有逻辑上相同的数据类型(如int32),其对应的运行时Type也不可能相同(两个int32指向不同的类型)。因此,我在赋值的时候做了一点hack:

    ConstCommonObject src = ...
    CommonObject dest = ...

    ConstCommonObject fake_src(dest.type(), src.data());
    dest.assign(fake_src);

src来自于Protein,dest来自于新系统.这段hack对大多数类型都工作的很好,然而对于Array却是错误的。究其原因,要谈到Array的设计和实现。

Array的设计借鉴了std::vector。std::vector的参数类型是编译时绑定的,一旦绑定就不能改变。对于Xirang来说,其中Type的建立,相当于是在编译期完成的,因此设计成绑定后不能改变。这个体现在Array对应的Type上,其中的类型参数value_type是不会被改变的。但是在实现Array的时候,我犯了几个错误。

  1. Array内部持有元素的Type。这个从设计上来说,是冗余的。要使用Array对象,首先需要以其Type为模板,绑定类型参数value_type,得到一个新的Type.假设value类型为int32,绑定后的类型为array_int32. 对于类型为array_int32的CommonObject来说,内部是不必持有元素类型int32的,因为从array_int32开始,按图索骥是可以知道其元素类型的。但是因为早期CommonObject和宿主C++对象之间交互能力的限制,使得Array对象不能不持有元素类型。
  2. Array的default ctor。为了实现C++的值语义,Array被设计成有默认构造,但是在1的设计下,Array又必须持有元素的Type,而这个Type又必须有效,默认构造无法满足设计1,因此这两个要求是矛盾的。作为妥协,默认构造出的Array状态将是invalid的。
  3. Array的copy ctor中,把参数的元素类型作为自己的元素类型。很显然,copy ctor的参数对象必须和自身处于同一个runtime,这样其持有的元素类型将是本系统的。但是如有违反,copy ctor无法检测到的。
  4. Array的assignment首先要求入参的元素类型和自己相同,其次不应该改变自身持有的类型--这是“绑定”这一涵义自然得到的推论。但是,因为在2中的妥协,存在invalid状态的Array,这时就需要接受并替换自身持有的元素类型,同样,此事无法检测到入参元素对象是否是本系统的。

这次的问题就是在我将一个Protein系统的array_color4对象赋值到新系统中导致的。尽管我在赋值时,通过伪造src的类型(但内存布局相同,因此伪造合法),解决了array本身的类型必须来自同一个runtime的问题,但是此方法无法影响其内部持有的元素Type(color4对应的),导致新系统中的Array对象实际持有了Protein系统Type的引用。当Protein的runtime销毁后,这个Array对象所引用的Type也就无效了。此事,不难得出结论,Array对象持有一个元素Type的引用不是一个良好的设计。

那么,为什么Array存在如此多的不合理设计和实现呢?这又是因为旧的Xirang中CommonObject和宿主C++对象之间交互手段的设计导致的。

在旧的Xirang中,提供了模板函数template <T> T& bind(CommonObject obj)用于将一个Xirang对象绑定成一个C++对象的引用,但是实现上,其间缺少一个中间层的设计,用于返回类型T的代理。在新的Xirang中,插入这样一个中间层所需的支持已经完备,理论上,我们可以借此完美解决前述的设计错误了。

新系统提供了一个模板Ref来得到C++对象的引用,也可以特化成返回一个对象引用的代理,还可以通过偏特化,提供多种返回代理,以适应不同的需求。

因此Ref(obj)可以返回对象ArrayProxy,ArrayProxy的实现大致如下:

    struct ArrayProxy{
           Type value_type;
           void* data;
           // all methods of Array......
    };

这和现有Array的实现几乎一模一样,除了ctor, dtor, assignment, swap等特殊函数。但是却足以将元素Type的引用消除掉,且不会引入任何额外的性能开销。

回顾整个问题。在我最初实现Array的时候,就认识到这个实现不完善,持有元素Type多余。虽然当时也有考虑到多个runtime,但是没有考虑到需要跨runtime转换数据。所以,我当时认为这个主要是实现上的妥协。但是经过对这次的缺陷的分析,我认识到这确实是一个设计缺陷,而不只是一个实现问题。要修正Array本身并不难,但是修正使用了Array的地方,工作量可就不小了。

设计之间存在依赖性,一个设计缺陷可以是另一个设计缺陷导致的。这次的事件再次强化了我的一个观点,那就是发现设计缺陷是不容易的,修正的代价也更高,尽量做出正确的设计,即时调整不合适的设计是非常重要的。流程可能对此问题有帮助。这样的设计缺陷如果有良好的设计审查过程,是极有可能避免的。尽管设计审查也不一定能生效,因为在早期,有效解决这个问题的基础设施就不存在,但是设计审查本身还起到知识传播和交流的作用,因此无论如何不算浪费。

DRY,有些时候叫SPOT,可能不少人知道,但是这些原则不仅适用于函数、类,数据结构的设计同样重要。对于数据重复和冗余,了解数据库设计范式是很有借鉴意义的,尤其是第三范式。另外,从信息出发的分析也是很有效的。逻辑上,Array对象持有的元素类型和Array对应的Type中的value_type必须是同一个,那么设计上,却导致同一个信息分处两处,这就是信息冗余,是不良的设计。

下一页