页面

分类

Posts in category ‘代码相关’.

记一次字符串性能分析

2017年12月26日星期二, by wingfire ; 分类: 计算机技术, 代码相关; 0 comments

因为材质库增加了大量材质,不出意外地,Protein加载系统库时时间变长,也不出意外地,某产品那边表示性能很重要,必须解决.不多说了.

虽说Protein 4.0的时候,因为使用了Xirang重写实现,性能比3.0快了1~2个数量级,但是那个结果其实并不是因为Xirang够快,而是Protein 3.0实在太慢了.

Protein 4.0 其实也不快,以前虽然有过一些度量和分析,但是时间久远,,数据也没有存档.借这这一次,有机会再省视一下,发现大致有如下性能问题:

  1. 内存分配次数问题
  2. 隔离了实现的iterator
  3. 低效的已序序列的并、交、差问题
  4. Xirang.type中将copy construction分解为default construction + assignment的问题
  5. string的效率问题
  6. lexical cast的问题
  7. 二进制接口隔离导致的性能损失
  8. 访问type member和sub object的性能损失
  9. deserialize 时接口调用带来的性能损失

其中4、5和1的关系密切. 上面是做了优化后的结果了,优化之前1的情况还要糟糕得多.

因为对string做了比较细致的测量,所以这里就做一下分析和记录.别的部分有心情再说.

在一个典型应用的测试中,我记录了整个周期所有字符串的活动情况(注意,这不是某个时刻的系统快照,可能差异巨大):

  • 内容不同的字符串数量: 23916
  • 内存分配次数(除空串): 186959
  • 字符串共享计数: 1131117
  • 所有内容不同字符串长度合计: 1144861

xirang中的string设计成了immutable的,带引用计数,但是没有做小字符串的优化.因此这里的一次内存分配必然对应一次构造,实际做了186959次内存分配.

基于经验猜测,小字符串优化对性能影响是巨大的.那么在我的这个例子中,实际影响有多大呢?考虑在64位机器上实现string,那至少要能容纳一个指针,即8个字节.假设一个额外字节存储字符'\0',另一个字符用来做标记,那就是两个字符的额外开销.因此,我统计了长度分别为6,14,22,和30的情况如下表

长度类别数量内存分配次数共享计数字符总长度
6397317841118251728
14340211023550613133178
22618814124981970383360
3099631503821006513182629

百分比数据:

长度类别数量内存分配次数共享计数字符总长度
61.6617.009.890.15
1414.2258.9644.752.90
2225.8775.5572.477.28
3041.6680.4488.9815.95

从上述数据来看,采用32字节大小的string可以削减80%以上的内存分配操作,但此时共享技术削减的次数更高,达到88%.因此,单从次数上来说,再增加string的大小不太可能会更经济了.但是这么分析并没有考虑到共享方式的计数器增减对cache的毒害效应,因为共享计数器必须是原子的.但无论如何,32字节可能是一个值得考虑的上界.另外,随着string变大,额外引进的内存开销增加也是巨大的.

下面分析一下现有的string实现实际内存开销.一个string本身只含有一个指针,因此大小是8,数据部分包括计数器、hash值和size,在64位机器上大小是24,因此数据部分实际大小就是24 + N,考虑到对齐,数据部分大小将是32,40,48...这样的序列.

对长度6字节以下的字符串而言,系统实际分配的内存,数据部分大小是32,加上string本体,合计40字节.计算内存大小的公式采用:

本体大小*共享计数 + 数据大小*内存分配计数

因此内存开销分别为:

  • 6字节以下: 8*111825 + 32*31784=1911688
  • 7~14字节: 8*506131 + 40*110235=8458448
  • 15~22字节: 8*819703 + 48*141249=13337576
  • 23~30字节: 8*1006513 + 56*150382=16473496

如果为小字符串优化,当string大小取不同值时内存开销的变化:

  • 8字节: 8*111825=894600
    • 降低:1911688 - 894600 = 1017088
  • 16字节: 16*(111825 + 506131)=9887296
    • 降低: (8458448 + 1911688) - 9887296 = 482840
  • 24字节: 24*(111825 + 506131 + 819703)=34503816
    • 降低: (13337576 + 8458448 + 1911688) - 34503816 = -10796104
  • 32字节: 32*(111825 + 506131 + 819703 + 1006513)=78213504
    • 降低: (16473496+ 13337576 + 8458448 + 1911688) - 78213504 = -38032296

因为数据搜集方法的原因,这里的内存增减变化只意味着内存使用足迹的变化,不等于某个时刻的系统状态.不难看出,16字节是一个转折点.从性能上来讲,考虑到cache,复制16个字节的数据很大概率上是远远快于修改引用计数器的.因此,对于Protein来说,有充分的理由实施小字符串优化,不但能够减少58.96%的内存分配操作,同时也降低内存使用,还能避免共享计数器对cache的毒害,一举三得.

接下来从频率的角度分析.取top 1000的高频字符串:

Top N    allocate       share       chars
100:     97675      726303      1716
200:     110745     888819      3894
300:     127047     942431      5446 
400:     131816     967705      7878
600:     139471     989569      11372
800:     144086     1000744     15038
1000:    147762     1006869     18484

23916:   186959     1131117     1144861

百分比:

Top N    allocate       share       chars
100:     52.24      64.21       0.15
200:     59.23      78.58       0.34
300:     67.95      83.32       0.48 
400:     70.51      85.55       0.69
600:     74.60      87.49       0.99
800:     77.07      88.47       1.31
1000:    79.03      89.02       1.61

23916:   100        100         100

仅仅是前100条就占据了所有字符串一半以上内存分配操作和60%以上的共享计数开销,因此预置静态字符串池很可能是值得的.假设放300条数据,即便算上额外内存开销,也只需要10K左右--实际因为无需引用计数,将能降低内存占用,依赖于池的实现,这里不再详细计算了--但却能够消除60%~80%的内存分配和共享计数操作.代价是内存分配操作要换成查表操作,且查找失败的概率32.05%,这是额外惩罚.但对于共享计数操作部分,将是完全的净收益,因为不再需要修改共享计数器了.这里字符串池的查找性能将是至关重要的,完美hash表,前缀树都有可能是候选。

字符串池、小字符串优化和共享数据,这三种措施可以同时实施,只是string的实现也需要分别处理这三种状态。这可能使实现变得有点复杂,但是对于Protein和使用的系统来说,字符串的性能是及其重要的,每一点微小的提高都是值得的.

一种Observer的实现

2017年8月24日星期四, by wingfire ; 分类: 计算机技术, 代码相关; 0 comments

Observer 模式是很常用的,但是要想实现得正确,并不容易.一个常见但并不很容易解决的问题是在Notify的过程中添加或删除Observer.

一般而言,对于一个目标,可以注册多个观察员对象,这就需要某种列表来记录,这个列表通常可以作为目标的数据成员来实现的.当需要发出通知时,代码大致如下

for(auto& v : observers)
    v.notify(event);

这段代码很简单,但是可能遇到问题,取决于notify的行为。若notify内还会注册/注销观察者,其效果就相当于在遍历的循环内修改了被遍历的容器的元素,若observers的类型是C++ 的std::vector,那将导致未定义行为。即使是std::list,若注销的恰好为当前的观察者,也会导致迭代器失效。而要想避免这种错误,实现起来并不容易。

上述错误发生的前提之一是遍历期间修改了容器,因此,如果在notify实际并不会修改容器,那就没什么问题。虽然API层面上无法保证不被误用,但可以增加一些检查加以防范:

void changed(const event &e){
  assert(!this->is_notifying);
  this->is_notifying = true;
  for(auto& v : observers)
    v.notify(e);
  this->is_notifying = false;
}

void register(observer_type o){
   assert(!this->is_notifying);
   observers.emplace_back(std::move(o));
}

void unregister(observer_type o){
   assert(!this->is_notifying);
   observers.emplace_back(std::move(o));
   observers.erase(std::remove(observers.begin(), observers.end(), o), observers.end());
}

注意,上述代码假设observer_type是可以判等的,std::function显然不满足要求.changed函数不是异常安全的,所以应该写成:

void changed(const event &e){
  assert(!this->is_notifying);
  var_saver guard(this->is_notifying, true);

  for(auto& v : observers)
    v.notify(e);
}

那如果需要允许notify内部注册注销呢?一种可行但低效的做法是,在遍历之前先复制:

void changed(const event &e){
  auto tmp = observers;
  for(auto& v : tmp)
    v.notify(e);
}

这么做的代价可能是相当昂贵的,尤其是当changed发生得非常频繁的时候.还有另外一个问题,即删除的observer不能及时得到处置,仍然可能被发送消息,这可能会带来恼人的结果.为了效率,能否既及时处置注销的观察者又不复制observers呢?

先试试看list类型,似乎简单一些:

void changed(const event &e){
  for(auto i = observers.begin(); i != observers.end(); ){
    auto& v = *i++;
    v.notify(e);
  }
}

可惜,这是错的. i虽然提前递进了,但是无法保证删的不是i所指的那一个,实际上,i无法定位到一个安全的位置上去。嗯,似乎还有办法:

void changed(const event &e){
  for(size_t i = 0; i < observers.size(); ++i){
    auto& v= observers[i];
    v.notify(e);
  }
}

这里observer的类型是vector,这段代码不会导致未定义行为.是不是没问题了?仍然不是.

如果在notify期间删除了在i之前的观察者,导致vector后面的元素都前移,这样在遍历的时候当前i后面的一个将被跳过.这种不确定性是难以被接受的.也不能通过检查observers.size()来察觉这一点,因为notify可以既删又加.

比较一下上述两种方法的得失,因为每一个observer都是特定的,下标法虽然避免了未定义行为,却丢失了observer的身份信息,iterator法的问题是虽然保住了身份信息,却没料到对象自己被删。因此修补的方法是对于下标法,要补记录观察者标志信息,对于iterator法,要将对象身份信息和对象本身脱钩。这两个方法的修订版就变得一致起来:以一种标记法标记observer,标记不依赖observer对象而存在。直观的表示法是

struct item{
   T identify;
   bool is_removed;
   observer_type* observer;
};

上面代码中的类型T应该是什么?原则上,可以是为observer分配的序号,字符串名称,或任何其他类似的东西。但是一个天然的identify就是observer的地址,因此T的类型可以取observer_type*.另外,is_removed可以通过把observer设为nullptr来表示,可以去掉。于是修改为:

struct item1{
   observer_type* identify;
   observer_type* observer;
};

这和下述表示本质上等价:

struct item2{
   bool is_removed;
   observer_type* observer;
};

对于上述定义,unregester都不立即将其从observers中删除,两者的区别在于,对于item1,把observer置为nullptr,identify不动,item2则把is_removed置为true,observer不动.于是changed可以实现为:

void changed(const event &e){
  for(size_t i = 0; i < observers.size(); ++i){
    auto& v= observers[i];
    if (!v.is_removed)
        v.observer->notify(e);
  }

  //注意: 不能在此清理observers中is_removed的项

}

实际上item1/2如果不马上删除,那本身就可以充当observer的identity,因此可以进一步简化为:

std::vector<observer_type*> observers;

void changed(const event &e){
  for(size_t i = 0; i < observers.size(); ++i){
    auto v= observers[i];
    if (v != nullptr)
        v->notify(e);
  }
}

void register(observer_type* observer){
   assert(!contains_(observer));
   observers.emplace_back(observer);
}

void unregister(observer_type* observer){
   assert(contains_(observer));
   auto pos = std::find(observers.begin(), observers.end(), observer);
   *pos = nullptr;
}

实际上,直接得到上面最后的结果也并不困难.剩下的问题是什么时候从observers中实际删除已删除的那些observer呢?这需要在相关函数中中判断一下,是否处于递归过程中,如果不处于递归,就执行实际的删除操作。那如何知道是否处于递归呢?一个简单的方法是计数。

struct counter_guard{
    int & counter;
    counter_guard(int& c) : counter(c){++counter;} 
    ~counter_guard(){--counter;}
};

int enter_counter;

void changed(const event &e){
  counter_guard guard(enter_counter);
  bool has_removed = false;
  for(size_t i = 0; i < observers.size(); ++i){
    auto v= observers[i];
    if (v != nullptr)
        v->notify(e);
    else
        has_removed = true;
  }

  if (has_removed && enter_counter == 1)
    observers.erase(std::remove(observers.begin(), observers.end(), nullptr), observers.end());

}

void register(observer_type* observer){
   assert(!contains_(observer));
   counter_guard guard(enter_counter);
   observers.emplace_back(observer);
}

void unregister(observer_type* observer){
   assert(contains_(observer));
   counter_guard guard(enter_counter);
   auto pos = std::find(observers.begin(), observers.end(), observer);
   if (enter_counter == 1)
     observers.erase(pos);   // no recursive
   else
     *pos = nullptr;    // in recursive
}

如果只在unregister中处理删除节点是不够的,因为真正导致递归的只是changed函数。相对来说changed是会被频繁调用的,因此将真正的删除放在changed中完成。要注意到上面changed中has_removed的计算并不精确,如果在迭代第i个观察者时,前面的某个被注销了,has_remove并不能感知,也就不会删除,要到下一次触发changed才能实际检测到。这样的实现是基于下述假设:

  • unregester相对发生概率低
  • 延迟做实际删除并无重大影响

以上是针对单线程情形下的分析和实现。对于多线程,则情况还要复杂得多,需要引入递归锁对执行线程进行保护。注意不能使用可升级的递归读写锁,因为递归过的顶层过程已经占有读锁,底层是不可能成功升级为排它锁的,这将导致死锁.即便锁的实现支持升级本线程的读锁为写锁,两个线程的竞争也将导致死锁无法避免.

关于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的程序,所以也没有人会写程序。

C++ locale 一例

2016年5月31日星期二, by wingfire ; 分类: 计算机技术, 代码相关; 0 comments

csv格式的数据是由逗号分隔的,C++标准库的iostream在读取时则是以空白分隔的。自然的,希望通过设置iostream,指定分隔符。然而在istream上并没有直接的方法来设置,也没有相关的manipulator来履行相关操作。实际上,istream的输入空白符控制是直接通过locale来完成的。

C++的locale一向恶名昭著,如果对C++ locale缺乏系统的了解,大概连怎么Google都是问题。网上的不少回答都是不可能。搜到一个CSDN上的帖子,通过hack ctype::table()返回的表:

     ifstream in;

       const ctype<char>& _Fac=_USE(in.getloc(),ctype<char>);
       WORD* pCltab=*(WORD**)((BYTE*)&_Fac+16); // 直接位移取mask地址
       pCltab[',']|=_SPACE; // 把','也加入分隔条件`

但是这个实现问题是非常多的,那个_Fac+16更是黑手,根本无法移植。

ctype实际上是可以被定制化的,在这里有个例子 http://en.cppreference.com/w/cpp/locale/ctype

代码:

        #include <iostream>
        #include <locale>
        #include <sstream>

        struct csv_whitespace : std::ctype<wchar_t>
        {
            bool do_is(mask m, char_type c) const
            {
                if ((m & space) && c == L' ') {
                    return false; // space will NOT be classified as whitespace
                }
                if ((m & space) && c == L',') {
                    return true; // comma will be classified as whitespace
                }
                return ctype::do_is(m, c); // leave the rest to the parent class
            }
        };

        int main()
        {
            std::wstring in = L"Column 1,Column 2,Column 3\n123,456,789";
            std::wstring token;

            std::wcout << "default locale:\n";
            std::wistringstream s1(in);
            while (s1 >> token) {
                std::wcout << "  " << token << '\n';
            }

            std::wcout << "locale with modified ctype:\n";
            std::wistringstream s2(in);
            csv_whitespace* my_ws = new csv_whitespace; // note: this allocation is not leaked
            s2.imbue(std::locale(s2.getloc(), my_ws));
            while (s2 >> token) {
                std::wcout << "  " << token << '\n';
            }
        }

我需要的处理char,看上去我只需要写个std::ctype,然后重写do_is就好了。很不幸,这行不通。

标准中定义了std::ctype的特化版本,而这个特化版本是没有do_XXX系列的函数。不太清楚为什么标准是这样的,估计可能为了性能。既然不能定制,是不是只能hack了呢?如果hack,怎么做才是比较好的呢?回头看一下CSDN的那段代码: WORD pCltab=(WORD*)((BYTE)&_Fac+16); 这段代码是为了获得ctype内部的转换表,实际上有对应的函数:table().但是table的返回值是const指针类型,不允许修改内部值。强行const_cast然后修改是有风险的:

  1. const数据可能是共享的,修改以后可能改变系统默认的行为,很危险。
  2. const数据可能是写保护的,并不能修改。

在Linux + gcc环境就属于情况2。幸运的是,可以通过C++标准库的API来达到目的。总体步骤是:

  1. 以某个ctype为模板,复制创建一个table
  2. 修改table以符合需要
  3. 以table为参数创建新的ctype对象
  4. 以新ctype为参数创建locale

示例代码:

        using namespace std;
        std::locale customized_locale() {
            std::locale loc("C");
            static ctype<char>::mask s_table[ctype<char>::table_size];
            auto table = use_facet<ctype<char>>(loc).table();
            std::copy(table, table + ctype<char>::table_size, s_table);


            s_table[','] = ctype<char>::space;

            // ' '  (0x20)  space(SPC)
            //'\t'  (0x09)  horizontal tab(TAB)
            //'\n'  (0x0a)  newline(LF)
            //'\v'  (0x0b)  vertical tab(VT)
            //'\f'  (0x0c)  feed(FF)
            //'\r'  (0x0d)  carriage return (CR)
            s_table[' '] &= ~ctype<char>::space;
            s_table['\t'] &= ~ctype<char>::space;
            s_table['\v'] &= ~ctype<char>::space;
            s_table['\f'] &= ~ctype<char>::space;
            // Don't override \r & \n

            ctype<char>*  fac = new ctype<char>(s_table);
            return std::locale(loc, fac);
        }

vc 和 gcc下都成功运行

下一页