所有由IndignantAngel发布的文章

扩展模板库的新方法 – 善用函数的ADL查找

问题

随着C++语言的发展,越来越多的C++类库都使用模板库提供给大家使用。模板库通常使用基于对象的设计,相比传统的面向对象的设计而言,前者的每个模块可以单独使用,而不依赖框架。整个模板库的框架,只是一个胶水层,让各个组件之间按照某种协议,组合到一起,形散而神不散,发挥出强大的功能。而且模板库非常好扩展。模板库的扩展通常有以下三种模式:

  1. 函数重载;
  2. Policy Based Design, 按照框架规定好的协议导出指定的type,计算好特定的静态常量和实现特定的函数;
  3. 特化traits或者一些特定模板组件的特化;

由于前两种方式比较简单,还要就是没有找到比较好的素材,鄙文暂时主要讨论第三种扩展方式。在实现iguana的过程中,我们发现模板特化和宏的结合,在碰到命名空间的时候,我们一筹莫展。案例如下,

REFELCTION宏实质上生成了一个在全局命名空间下的类模板的特化的代码。但是由于宏是预处理阶段,生成的代码在client命名空间下。C++的语言规范不允许在一个命名空间中特化另一个命名空间的类模板,也不允许在一个命名空间下特化全局命名空间的类模板(全局的情况MSVC能编过,我是服气的)。这里是一个参考链接。

那么我们库中遇到的问题,用下列简化的代码给出,有兴趣的读者可以到各个编译环境下测试。

其实这个限制并不是无解,只要你保证REFLEACTION宏在全局命名空间下,就不会出错。例如BOOST_FUSION_ADAPT_STRUCT宏,也是用相同的方法规避的。但是你会发现这样对使用来说非常不便,你偶尔不得不把一个完整的命名空间的代码block拆成两个。我们得找另外一种方法来扩展我们的模板库,而不受限于命名空间。

解决方案

什么样的扩展方法,可以跨越命名空间的限制?仔细阅读过template C++的读者应该不难发现,就是函数的ADL查找。我们用如下代码来说明,如何利用函数的ADL查找。

简单解释一下,下面的代码是如何工作的。首先,函数的ADL查找,是apply函数尝试调用to_extend的时候,不仅会查找lib命名空间下的符号,也会去查找T类型所在命名空间的符号。我们定义的to_extend函数在client命名空间下,foo类型也在client命名空间下。那么ADL查找肯定可以找到to_extend函数的符号。然后,我们没有选择类模板的特化,而是选择了使用to_extend函数,返回一个它内部定义的类型作为policy的功能。这个思想有点类似Andrei Alexandrescu大神的MDC中第11章节的Multimethod的蹦床函数,trampoline funciton. 有了这些,我们就可以在任意命名空间下来扩展我们的模板库,当然配合宏使用也没有问题了。在iguana中具体实现的小细节,可以参考reflection.hpp里面的实现。

使用timax::bind, 来获取一个std::function对象

使用timax::bind, 来获取一个std::function对象

Motivation

刚刚发布的rest_rpc,接口易用性很高。例如服务器注册业务函数的接口:

我们希望将字符串”add”与业务函数client::add绑定。在示例中add是一个类型为int(int,int)的普通函数。除了普通函数,我们希望这个接口可以接受任何callable类型的对象,包括普通函数、仿函数、lambda表达式。这可以通过function_traits,可以很容易的达成。

但是如何兼容类的非静态成员函数?

使用std::bind?很遗憾,C++标准并没有明确定std:bind的返回值。更遗憾的是,std::bind返回的类型是一个拥有泛型operator()的结构体,也就是说,它的operator()是一个模板函数。因此,我们无法用function_traits做进一步的处理。而且适用std::bind,还有一个不便利的地方,我们在使用std::bind的时候,还需要填补placeholder.

于是,我们决定撸一个timax::bind,直接为用户返回std::function<Ret(Args…)>对象,这样可以让funtion_traits正常工作。

Design

什么该做,什么不该做

timax::bind并没有重新实现一个std::bind,而是封装并扩展了std::bind. 重复造轮子的工作不该做,而让std::bind在我们的应用场景下更好用是应该做的事情。timax::bind扩展的工作主要有两项:
1. 包装std::bind,为用户返回一个std::function对象;
2. 在函数参数都默认的情况下,不需要用户填上placeholder;

要做的工作

timax::bind的设计思路如下图:

我们用代码来详细解释一下

Implementation

timax::bind的实现,由上图可以看出,主要工作是两个方面。
1. 推导std::function<Ret(Args…)>中的Ret和Args…;
2. 返回一个可以构造std::function<Ret(Args…)>的对象;

推导参数主要看timax::bind是否绑定了参数,或者占位符。因为,绑定了额外的参数,会让函数的形参数目和顺序发生改变。在不绑定任何参数的情况下,是最简单的,同原来函数的返回类型与形参列表相同。

无额外绑定参数情形

正如上文所述,这种情况非常简单,因为返回类型很好确定。我们可以使用function_traits,推导出返回的std::function模板实例化后的类型。那么剩下的工作就是要构造一个对象,能够正确调用我们绑定的函数,并初始化std::function实例化后的对象实例。根据Design章节的附图,我们分成四种情况:
1. 绑定的是一个callable(函数、仿函数、lambda表达式和函数对象);
2. 用一个类对象绑定一个类的非静态成员变量;
3. 用一个类的裸指针绑定一个类的非静态成员变量;
4. 用一个类的智能指针绑定一个类的非静态成员变量;

绑定一个普通callable的实现很简单,我们用一个lambda表达式包装了一下调用。这里用到了C++14的auto lambda表达式,使用auto和variadic特性,让编译器自动帮我们填写函数的signature. 如果没有C++14的特性,还真不知道怎么实现比较方便,欢迎各路大神在这里指教一下,如何只用C++11的特性来实现。

剩下三种情况的实现方法,也很明了了,唯一要确定的是调用语义。而且,我们的实现是支持多态的。

最后利用模板元,特化和重载决议等一些modern C++的惯用法,把这些实现像用胶水一样粘起来,统一成一个接口给外层用就可以了。

有额外参数绑定的情形

有额外参数的情形就麻烦一些了,因为函数的形参列表发生了改变。绑定了实参,形参列表会变小;绑定了占位符,形参列表的顺序可能会改变。那么如何计算返回的std::function的实例化类型呢?切入点在placeholder!

也就是说,我们在计算返回类型与形参列表的类型的时候,只需要考虑placeholder而可以忽略所有实参。接下来继续用代码来描述计算类型额过程。

对于有绑定实参的情形,可以看出,我们只关心占位符placeholder,所以结果也完全正确。如果没有任何占位符,那么形参列表就是void. 在rest_rpc中,timax::bind_to_function模板就是负责推导std::function实例化类型的元函数,详细可以参见function_traits.hpp的151行。剩下的事情就是调用std::bind了,这就很简单了。

Some Tricks

在实现timax::bind的时候,有一些实用的C++小技巧,简化了我们的代码复杂度。在这一个小节跟大家分享一下。

判断一个对象是否是智能指针

因为智能指针不能像裸指针一样访问pointer-to-member-function,要先get()出裸指针,再访问。所以,我们要区分裸指针跟智能指针两个类型。判断一个类型是否是裸指针,直接实用std::is_pointer就能完成,但判断是否是智能指针,得自己实现。

智能指针都重载了operator->,并都有get接口访问裸指针,我们就用这两个条件来判断一个类型是否是智能指针,代码如下,这应该是当前C++版本最简单的SFINAE技巧:

如果T是智能指针,那么两次decltype就能够计算出表达式类型,那么voider就能够导出void,并生成is_smart_point<T, void>的特化,返回std::true_type. 否则,特化不存在,就导出std::false_type.

兼容boost::placeholders

兼容boost::placeholders是一个无奈之举,因为包含了boost/bind.hpp就会自动把_1和_2引入全局命名空间下,还会与标准库的占位符冲突。好在兼容的工作很简单,特化一下std::is_placeholder就能够解决了。

Tail

timax::bind的实现特别简单,但是为rest_rpc注册业务函数带来了便利。这就是C++的魅力,在语言工具和标准库功能不够的时候,你随时都有可能为自己定制和扩展C++. 定制和扩展势必会用到一些模板元和宏元,会写一些思路不同于常规程序的代码。但这些代码的出现,是为了让常规代码更符合人类直观感受的逻辑思维。看到一些人喜欢妖魔化C++的种种特性,甚至把回字的四种写法拿出来嘲讽这些代码是咬文嚼字,工笔对偶的华而不实。我只能说,不同的需求关心的问题大相径庭。在编写库的时候,需要实现者反复琢磨,接口是否符合常规逻辑思维,是否类型安全,是否是富类型能涵盖所有等等,才有了使用者顺滑的开发体验。《C++语言的设计与演化》诠释了BS对C++设计哲学的源点,不以个人喜好来增删语言的特性,所以我们才能看到一个强大的编程语言。然而新标准也出的忒慢了吧! 愿rest_rpc功能越来越完善,C++er越来越好,也欢迎各路大神来访purecpp.org和QQ群296561497一起讨论C++的开()发()经()验()。

rest_rpc新增异步客户端接口

rest_rpc新增了异步客户端接口,其设计的目的是为了简化异步接口的使用,还消除异步接口的使用限制条件。我们先来看看异步客户端是如何使用的。

一个可以运行的简单示例在这里。简而言之,async_client和call返回的task都是线程安全的。task的类型是根据用户定义的强类型协议来决定的,并且task接口是参照std::future来设计的,接口简单。

由于异步客户端的call接口立即返回的特性,用户极有可能在task.get()返回前再次调用call函数。所以rest_rpc的异步客户端的内部使用了一个链表来管理用户使用call函数的调用,保证request-response顺序的正确性。异步客户端除了有取消接口之外,还实现了超时。便于debug,超时时间目前都设置的是60s.配置task和链接超时的接口应该不久就会实现。

如何优雅地管理constant buffer

1. Preface

Constant buffer是我们在编写shader的时候,打交道最多的一种buffer resource了。constant表明了constant buffer中的数据,在一次draw call的执行过程中都是不变的;而在不同的draw call之间,我们可以修改其中的数据。它是我们把数据从CPU传递到GPU最常见的方法。constant buffer的概念和定义就不在这里赘述了,鄙文主要讨论如何优雅的管理constant buffer.

2. How to create and manipulate constant buffer gracefully.

Constant buffer在各种api中都有很好的支持,如在DX11中,以cbuffer为类型的闭包,可以定义一个constant buffer.

cbuffer可以根据你自己对它的功能或者buffer数据改变的策略来定义。在DX11中,我通过shader reflection的接口发现,没有在cbuffer闭包中的变量,都会被放到一个名叫@Globals的constant buffer中。当然这也取决你的fxc.exe的版本。其实让我们苦恼的并不是如何使用DX或者GL等这些api创建一个constant buffer对象,而是我们为了使用constant buffer,通常情况下需要在我们的引擎或者客户端的程序代码中,创建一个内存布局和大小与GPU端统一的数据结构。例如,我们要使用 transforms和change_every_frame这两个cbuffer,我们还要定义如下C的struct,和一些额外的代码。

这是一件很让人困扰的事情。首先,如果你开发了一个新的shader并使用了一个新的cbuffer的定义,那么你不得不修改你的引擎或者客户端代码。添加新的数据结构,还有使用和更新的代码。如果是这样,我们的程序或者引擎的扩展性就太差了!其次,你得非常小心的处理constant buffer内存布局的规则,否则你的数据不会正确的传递。例如,light_position后面要更一个float作为补位。我们应该把这些交给程序自己,而不是自己来做重复的工作。在C++中,我们必须要把这些与类型相关,也就是受限于编译期的,改成到运行期当中来计算。管理的基本方法如图所示:

726345-20160522235430982-157258810

 

将一个cbuffer分成的两个部分,一个大小跟GPU中cbuffer大小一致的memory block,和一个对cbuffer各个成员的描述meta data. 如何来实现呢?在最开始,我们需要一个枚举来描述所有的基本类型,例如float,float3,float4x4,这是从编译期转向运行期的第一步。

然后,我们需要一个结构体来描述整个constant buffer,例如change_every_frame这个cbuffer,我们要描述整个buffer的大小,light_color的data format,还有相对于cbuffer头地址的偏移量等。并且还要支持在cbuffer中使用结构体和数组。所以这个结构体应该是自递归的。如下面的代码

在编译shader之前,还需要多做一件事情,就是解析shader code中的cbuffer,把这些meta data都获取出来,创建好numeric_layout对象。当然,都已经解析了cbuffer,讲道理应该把整个shader codes都解析一遍,创建一个完整的effect框架。这部分的功能,我正在研究和开发中,希望能顺利完成并同大家分享。然后在渲染框架的与平台无关的代码部分,抽象一个constant buffer类型,并使用这个numeric_layout创建与平台无关的constant buffer对象。有了这个constant buffer对象,平台相关的代码就有足够多的信息正确创建设备上的cbuffer的对象了,无论是dx还是gl. 那么总体的流程如图:

726345-20160523001044826-737496802

在很多图形api中,对cbuffer的部分更新做的并不是很好,如只更新change_every_frame中的light_color分量。DX的UpdateSubresource无法实现,gl3.1之后有了ubo,才可以使用glSetBufferSubData来实现。在我们管理的cbuffer下,我们可以部分更新cpu中的cbuffer的memory,在一起update到gpu上来模拟这种部分更新的实现。

3. Use the powerful compile time computation of C++ to manipulate constant buffer

接下来聊聊如何利用C++新标准强大的编译期计算来方便我们创建cbuffer. 上述将编译期迁移到运行期的方法,很适合在渲染框架中使用。运行期化的代码,虽然能解决问题,但是创建的过程还是比较复杂。在写实验和测试的代码这类很小的程序的时候,上图的流程就显的笨重了。所以,我在实现numeric_layout的时候,提供了使用用户自定义类型来创建cbuffer的metadata的方法,以便小型程序使用。使用起来非常简单,代码如下:

首先定义自定义的cbuffer的结构体,跟shader code中的一模一样的结构体;然后使用boost::fusion做编译期的反射;最后使用numeric_layout的另外一个构造函数创建cbuffer的metadata,共cbuffer创建使用。大概的实现思路如下。

1. 使用large_class_wrapper<T>来避免不必要的栈内存分配。由于定义我们的constant buffer的数据结构往往是一个结构体,而我们创建numeric_layout对象并不需要这个结构体的实例或者实例的引用,只需要编译期的反射信息。我们没有必要去创建一个无用的对象,而是把类型传递给large_class_wrapper<T>类模板,让它带上类型信息,但是这个类模板本身是一个空类,大小为1,甚至会被编译期优化掉。所以这里使用large_class_wrapper<T>可以避免不比较的内存开销。

2. 然后,在使用被fusion适配成sequence之后的用户自定义类型T,对numeric_layout进行初始化。根据cbuffer的内存对齐规则,对sequence中的每一个成员类型做计算,当前成员类型计算的过程依赖上一个成员计算的结果。那么numeric_layout的构造函数调用的detail::init_variable_layout_from_tuple函数实现如下,

3. numeric_layout的构造函数,在编译期计算出了T在GPU中的大小,算法与运行期的原理基本相同,只是改写到编译期计算了。

目前还不支持struct中嵌套struct,我想不久的将来应该会支持的。仓库在这里,不过我写的很慢,连平台无关的代码都还没有写完。接下来会准备研究glslang,hlslcc,还有vulkan的SPIRV的一些库和tools的开源项目,来解决one shader all platforms的问题。

4. Tail

constant buffer曾经是我引擎开发工作当中一个比较痛苦的环节,每写一个shader,每多一个effect就得在C++代码中添加相应的数据结构和逻辑显得很DRY。而后错误的更新cbuffer招致的痛苦的调试过程也是历历在目。还有当我看到maya的cgfx如此灵活和强大功能更让我觉得cbuffer是得好好管理一下了。Powered by modern cpp and modern graphics api,希望我自己实现的渲染框架,可以在不添加一行C++代码的同时,还能高效的正确渲染新加入的effect,杜绝DRY的设计和实现。

弱弱地发一个semaphore

Semaphore在有些场景下比条件变量好用。比如用一个Fence Value和一个条件变量来实现线程间同步,用一个信号量就可以等价替换。

以上是这个信号量实现的外观。模板参数SemaT的类型如果是void,信号量用std::condition_variable,std::mutex和一个flag值来模拟实现;不是void的时候,是一个policy参数,根据不同的平台适配不同的实现。

模拟的信号量实现,其实是simple_semaphore<void, false>这个特化实例。模拟的实现如下:

平台相关的实现,使用系统的API效率会更好一些。所以,继续对simple_semaphore特化,为平台相关的实现,实现一个外观。

平台相关的实现,具体就是要实现policy类,特化一个is_platform_semaphore这个traits. 这里暂时只实现了windows平台下的。

最后再根据平台来选择要使用的Semaphore实现

这个简单的semaphore只实现了wait()和signal()方法,而且初始化的时候提供了初始信号量为0的构造方法。当然也能应付大部分场景。

理解使用内存访问排序的原子操作

数据竞争与乱序执行

当至少两个线程并发的访问一块没有任何保护的内存,并至少有一线程执行写操作,这个时候会发生数据竞争。为了避免这种情况的发生,我们可以在每个线程中分别加入一个临界区,通常是一个互斥锁,来保护该线程的读或写的代码段。事情似乎很简单,当线程要访问这块内存的时候,先加锁进入临界区,操作完成之后再解锁退出临界区。全部的事情只多了一个加锁和解锁的操作。可是,在使用无锁编程的场景下,事情就没有这么简单了。

如果我们不使用临界区保护我们的代码段,就会导致数据竞争条件成立。我们对内存的操作才完成了一半,就会因线程调度等原因轻而易举地让另外一个线程开始对相同的内存进行读或写操作。这时会发生截断读写(torn read and write)的问题。还有比这个更糟糕的,程序并不是按照你编码的那样运行。

编译器看到我们的代码,觉得如果程序按照这样运行太糟糕了,便吐槽到,“噢,我想你的这些代码并不是这个意思,就按照我的修改来执行吧”!结果,我们的代码逻辑,就这样被调整了顺序。然后事情扔给了处理器,可是处理器跟人类一样“聪明”,并不会老老实实地一条一条指令挨着执行下去,它会按照自己的方式调整处理事情的顺序让程序更快。

以上在实际中无时无刻都在发生。虽然对于单线程而言,这些乱序都是透明的,等价的。但是当我们从另外一个线程,来看这个线程的时候,可想而知事情全乱套了。另外一个线程在这个时候再访问这块内存,可能会导致未定义的行为。这里有一个测试乱序执行的小代码。

unorder

事实上,从源代码到最终的执行,除了编译器优化和处理器乱序执行之外,各级缓存没有即使刷到内存与处理单元的私有缓存都会导致乱序的结果。参考[1]中的解释,我们无法分辨到底是其中的哪一个环节导致乱序的发生。这时,为了避免数据竞争,我们要介入代码的生成与执行规则,让它们按照一定的顺序来访问这块内存。

顺序

先看一个栗子,这个栗子出自于[2]中5.3节。

reader线程是执行reader_thread()的线程;writer线程是执行writer_thread()的线程。reader线程,一直在等待writer线程把data_ready变量置为true,并访问data中第一个元素的变量。而writer线程向空的data中插入一个元素,并把data_ready置为true. 利用注释中对操作的字母编号,我们来列举一下这里栗子中操作的顺序关系:

1. A发生在B之前(A happens before B);
2. C发生在D之前(C happens before D);
3. B与C同步(B synchronizes with C);
4. 可以保证A发生在D之前(A inter-threaded happens before D).

这里出现了好几个术语,happens-before,synchronizes-with和inter-thread happens-before等关系。下面逐个解释。

同步关系 – synchronizes-with

同步关系是反应原子变量之间的顺序关系,且仅对原子变量。引用[2]中的一句定义,a suitably tagged atomic write operation W on a variable x synchronizes-with a suitably tagged atomic read operation on x that reads the value stored by either that write(W), or a subsequent atomic write operation on x by the same thread that performed the initial write W, or a sequence of atomic read-modify-write operations on x by any thread, where the value read by the first thread in the sequence is the value written by W. 讲人话就是指,对同一个原子变量的两个操作读和写,如果他们都标上了正确的内存访问排序(memory ordering)的标识,那么读操作和写操作在各种情况下就是同步的,也就是说对原子变量的读取的值,就是同步的写操作写进去的值。

下一章再解释什么是内存访问排序。同步关系并没有明确地指明一个先后顺序关系,它只是能够保证读取操作的值,如果是写入操作的结果,就可以确定一个严格的先后顺序,写发生在读之前。而这是需要我们用代码来保证的,比如上一个示例中C操作的while循环,还有自旋锁的实现。

除了确定一个先后顺序关系之外,同步关系影响着事发优先(happens-before)优先,序列优先(sequenced-before)关系和线程间的事发优先(inter-threaded happens-before)关系。同步关系可以链接各个优先关系,并把优先关系传递下去。稍后我们就可以看到它是如何传递的。而同步关系对其他优先关系作用的细节,稍后再做讨论。

序列优先 – sequenced-before

序列优先明确的指出了一个先后关系。参考[3]给出的定义,序列优先是针对单线程而言的,即在同一个线程中有两个操作X,Y,当X的求值在Y的求值开始之前就完成了,X就是序列优先于Y. 对这一章一开始给出的例子而言,C就是序列优先与D,而A是序列优先于B的。序列优先关系比较简单。

事发优先(包括线程间的) – (inter-threaded) happens-before

这里把happens-before与inter-threaded happens-before放在一起讲。首先它们都明确的指出了一个先后关系。它们之间的关系,参考[3]中的定义,我给出了下图。

prior

 

上图给出的定于与[3]略有不同,因为[3]中有循环定义的行为。但是[3]中的某些定义可以归纳到优先顺序的传递性质。上图中多出了一个依赖优先(dependency-ordered before)关系,这个关系也是可以跨线程的,我们也放到下一章来讲解。

从上图可以看出事发优先与跨线程的事发优先关系都是由同步关系,序列优先关系组合构造出来的,还有依赖优先关系。结合本章一开始给出的例子,我们可以得出:

1. A事发优先于B – A序列优先与B,B与C同步;
2. B事发优先与D – B同步于C,C序列优先于D;

优先顺序的传递

事发优先顺序是可以安全传递的。A事发优先于B,B事发优先于C,就能够得出A事发优先于C的结论。如果我们把事发优先和跨线程的事发优先定义展开,还能得出更丰富的结论。

1. X与Y同步,Y事发优先于Z << X事发优先与Z;
2. X跨线程事发优先于Y, Y跨线程事发优先与Z << X事发优先于Z,有可能X与Z在同一个线程;
3. A与B同步,B跨线程事发优先于C << A事发优先于C;
//…

在实际应用场景中,我们通常需要使用优先顺序的传递来确保操作的先后关系,来保证并发访问共享数据的可见性。然而,在文章的一开始提到过乱序执行的问题。对于本章一开始给出的示例中,操作A是如何保证序列优先与操作B的,B可能乱序到A之前;还有C是如何保证序列优先与D?前面提到过,同步操作是标记上了正确的内存访问排序标识的。并且还提到过,同步关系影响着这些优先关系。接下来的章节,将对这个问题做详细讨论。

C++11中的memory ordering

同步关系除了在一定条件下,保证了自身原子变量的先后关系之外,还通过标记一个同步语义,内存访问顺序标识,来构造与其他原子或非原子变量操作的顺序关系。在c++11的标准中,有六种原子变量操作的内存访问排序标识,定义在enum std::memory_order枚举变量中。详细见下表。

memory_order

 

顺序一致 & memory_order_seq_cst

先来谈谈最简单的排序类型,顺序一致的访问排序。这也是原子操作默认的行为。load操作如std::atomic<T>::load(),store操作如std::atomic<T>::store(),还有read-modify-write操作如std::atomic<T>::compare_exchange_weak(),都可以使用这个标识。再看上一节的示例中,使用的都是默认的原子操作的排序,也就是顺序一致的。示例展示了一个线程的load操作如何与另外一个线程的store操作同步。但是,顺序一致的排序,功能更为强大。我们把文章最开始测试乱序的代码稍作修改,就能够说明。

顺序一致保证了原子操作,不会被乱序执行,并且更进一步。标识了memory_order_seq_cst的原子操作,只要执行完成了,对其他各个线程都是可见的!就如上面的代码,t1线程的x.store(1)与t2线程的y.store(2)必有一个先执行。如果t1的先执行,那么由于顺序一致的保障,t2对x的load操作一定与t1对x的store操作同步,反之亦然。绝对不会出现不使用原子变量时,发生由乱序或者缓存导致的r1与r2同时为0的情况。顺序一致如此强大,它们阻止了编译的部分优化和处理器的乱序执行,并及时同步缓存与内存。从而,当一个线程的store操作发生完成后,其他各个线程对这个原子变量的读取能够达到一致。可想而知,它们的性能开销也是很大的。

这里也可以做出一个推论,一个线程中的两个顺序一致的原子操作,存在一个严格的序列优先关系。这也是为什么上一章示例中,操作A肯定优先于操作B,操作C优先于操作D的原因。

松弛的排序 & memory_order_relaxed

介绍的第二种内存访问排序标识,就是memory_order_relaxed. 事实上它不负责任何synchronizes-with语义。它仅仅只能保证,对原子变量的读写的原子性,没有截断读取的问题。如果我们把上面顺序一致的代码改成松弛的,它的行为将会与不使用原子变量的行为一样。

Acquire & Release语义

memory_order_acquire同memory_order_release是成对使用的。acquire只能对原子变量的load操作使用,而release只能对原子变量的store操作使用。在我看来,acqurie与release只能实现顺序一致下的一个场景,就是读与写同步,并构造一个store事发优先于load的关系,并保证store之前所有内存操作对load之后的内存操作可见。它比顺序一致要轻量,所以在某些架构平台下,它的性能比顺序一致要好很多。改造一下ordering一章中的示例,把顺序一致的操作变为acquire&release,是等价的。

这就是我为什么杜撰它们为acquire & release语义的原因。只有当操作B与C同步了之后,才能保证操作A对操作D可见。借用[4]中的一个比喻,操作A就好像是你在对自己本地的私有代码仓库实现新的功能,操作B就好比是使用git push,向远程仓库提交;当你第二天要开始新的代码任务前,也就是操作D,你需要从远程仓库git pull最新的代码,也就是操作C. 这也是acquire & release语义唯一正确的使用场景。值得一提的是,store之前的内存操作既可以是原子操作也可以是非原子操作。

memory_order_acq_rel也是为acquire & release语义服务的,只是它被限定在rmw操作上使用。我们再改造一下读写同步的栗子。

有了acquire & release语义后,这个栗子就很好理解了。compare_exchange_weak()会先执行一个load操作,如果比较成功再执行一个store操作。那么memory_order_acq_rel就告诉这个rmw操作,load时使用acquire,store时使用release. 在上面的栗子中,B1操作与C1的load操作部分,形成了一个acquire & release语义;而C1的store操作部分与D1形成了一个acquire & release语义。这样,使得rwm_thread线程成为了一个承上启下的作用。当然在实际应用中,不会这么实现,这里是为了说明,memory_order_acq_rel是为rmw操作量身定做的,本质上也是为acquire & release语义服务。

依赖优先与依赖携带关系(dependency-ordered before & carries dependency into)

上一章介绍事发优先关系的时候,提到过依赖优先。递延到此时此刻,是因为需要借助acquire & release语义来解释,就会简单许多。首先来介绍一下依赖携带关系。

根据[3]给出的定义,操作X与操作Y之间有依赖携带关系的必要条件,是A序列优先与B. 此外,还需要满足一个条件。A的求值结果作为B的操作数,或者A在求值过程中对一个scalar变量M有修改,并且B使用了M.定义的细节请参阅[3]中的文档。memory_order_consume就是用来暗示代码的依赖关系来约束先后顺序的,同memory_order_acquire一样,它也只能用在原子变量的load操作。

有了依赖携带关系,接着来看依赖优先关系。与acquire & release语义类似,consume & release也是成对使用的,只是它release store操作之前的内存操作约束更少。如果一个原子变量的release store操作同另外一个线程的同一个原子变量的consume load操作同步,并且release store之前的内存操作X与release store操作携带依赖关系,那么consume load操作之后的任何内存操做都能看见X. 我们再通过一个栗子说明。

结合这个栗子,reader_thread线程中的C2操作一旦判断成功,即ptr不为空指针,那么C2就与writer_thread中的B2操作同步。这时的同步是consume & release语义的同步。这意味着依赖优先于B2全部操作,对D2都是可见的。前面的A21,A22,A23的操作对D2都是可见的。

内存访问排序小结

我们看到了六种C++11标准库的内存访问排序的标识。列举了一些synchronizes-with的场景,顺序一致、acqurie & release和consume & release三种场景。松弛的原子操作并不负责任何synchronizes-with的关系。三种不同的同步关系,会影响旁边代码的事发先后关系,如acquire与consume的不同,还有顺序一致与其他非顺序一致同步的不同。此外,同步关系也是连接事发优先与序列优先的纽带。通过控制对共享内存的访问顺序,帮助我们保证代码在运行时对共享内存的访问安全。

参考文献

[1] https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2
[2] c++ concurrency in action
[3] http://en.cppreference.com/w/cpp/atomic/memory_order
[4] http://preshing.com/20130922/acquire-and-release-fences/
[5] http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/

 

Understand std::atomic::compare_exchange_weak() in C++11(译文)

 

原文地址:http://www.codeproject.com/Articles/808305/Understand-std-atomic-compare-exchange-weak-in-Cpl

背景

本文源自爆栈网上的一个提问。Compare-and-swap(CAS)是一个原子操作指令。在多线程中充当同步的组件模块。C++11在语言级别上支持原子操作,让我们能够写出可移植的多线程代码,并可以跨越支持标准的全部平台。

了解CAS到底是什么,在维基百科上有一篇很好的文章。简而言之,CAS操作从内从中读取值,并与一个预期(expected)的值做比较(compare),如果相等,就把一个预先定义好的所需的(desired)值存到那个内存地址。最重要的是,所有这些都是在以一个原子的方式进行的。从这个意义上讲,如果另外一个线程改变了这个值,那么CAS会失败。

C++11中的CAS

当预期的值与对象真正持有的值相等,那么它将返回成功并把所需的值写入内存。否则,预期值会被内存中实际的值覆盖更新,并返回失败。这在绝大多数情况下都是正确的,除了一个列外情况:CAS的weak版本即使是在内存的值与期望值相等的情况,也可能返回失败。在这种情况下,所需的值不会同步到内存当中。

伪失败(Spurious Failiure)

上述的例外情况是因为伪失败。在一些平台上面,CAS操作是用一个指令序列来实现的,不同与x86上的一个指令。在这些平台上,切换上下文,另外一个线程加载了同一个内存地址,种种情况都会导致一开始的CAS操作失败。称它是假的,是因为CAS失败并不是因为存储的值与期望的值不相等,而是时间调度的问题。CAS的strong版本的行为不同,它把这个问题包裹在其中,并防止了这种伪失败的发生。

为什么大多数情况要在循环中使用compare_exchange_weak()?

C++11 §29.6.5
A consequence of spurious failure is that nearly all uses of weak compare-and-exchange will be in a loop

典型示例A

你需要根据原子变量的值来实现原子变量的更新。更新失败意味着我们的期望值并不是原子变量的最新值,我们需要重试。注意,我们不关心失败是否是由伪失败或者并行写导致的。我们只关心是我们成功更新了原子变量的值。

在实际生产中的例子,几个线程同时并行地向同一个链表添加一个元素。每个线程首先获取头节点的指针,分配一个新的节点并把头结点指针赋值到新节点的next指针变量。最后,算法会尝试用新的节点更新为头指针。

另外一个例子就是用std::atomic<bool>来实现互斥锁。最多只有一个线程可以进入临界区,这取决于哪一个线程抢先把current值设置为true并退出CAS循环。

典型示例B

这个例子实际上是从Anthony的书中提到过的(C++ concurrency in Action). 与A的情况相反,你可能只希望原子变量更新一次,但你不关心是谁更新了它。只要变量没有更新,那么你才重试。这种情况经常使用在bool型变量中。比如,你需要为一个状态机的转移实现一个触发器,但是哪个线程触发的是不重要的。

注意,上面这种情况是不能拿来实现互斥锁的。因为多个线程可能同时进入临界区。

这就是说,在循环之外几乎绝不使用compare_exchange_weak()函数。因为有一个strong版本可以使用。例如

这里使用compare_exchange_weak()就不合适了,它会由于伪失败的原因返回false,而很可能并没有人占用临界区。

线程饥饿?

有一点值得提一下,伪失败是否会一直发生并让线程饿死,形成一个活锁?理论上这种情况是有可能发生的,一般是当compare_exchange_xxx()函数是用一个指令序列实现的,例如LL/SC. 频繁地访问同一个LL与SC之间的缓冲行会发生连续不断的伪失败。一个更切合实际的例子,是在线程调度中,所有的并发线程被调度成如下这种交错执行的模式。

上面的情况会发生吗?幸运的是,这不可能发生。C++11的标准保证了这一点。

§ 29.6.5
Implementations should ensure that weak compare-and-exchange operations do not consistently return false unless either the atomic object has value different from expected or there are concurrent modifications to the atomic object.

为什么要这样繁琐地使用compare_exchange_weak()并自己实现循环?为什么不使用compared_exchange_strong()?

这取决于具体的情况。

情况1:如果两种版本都在循环中使用,哪一个更好?

C++11标准中提到:

§ 29.6.5
When a compare-and-exchange is in a loop, the weak version will yield better performance on some platforms.

在x86平台(至少是到目前为止,也许将来的某一天,当更多的核心加入进来,出于效率目的改为LL/SC),weak和strong的两个版本本质上是一样的,因为他们都归结为一个cmpxchg指令。在其他的平台中,compare_exchange_xxx()的实现并不是原子的). Weak版本在循环中的性能会更好,因为strong版本会处理伪失败并在某些情况下重试。

但是

在极少数情况下,会是用strong版本来代替使用循环的weak版本。比如在我们获取原子变量的值与最后更新原子变量之间,有许多事情要做的情景。如果原子变量自身变化并不是很频繁,我们没有必要为每一次的伪失败做开销很大的计算。反而期望compare_exchange_strong()吸收这些失败,而仅在由于值的改变而失败的情况下做重试。

情况2:strong版本代替weak版本循环

C++11标准中提到:

§ 29.6.5
When a weak compare-and-exchange would require a loop and a strong one would not, the strong one is preferable.

这种情况是当你做循环只是为了排除伪失败。你可能在exchange操作成功或者因为值的修改而失败的情况下,不再重试了。

上面的代码充其量,是在重复造轮子而且行为跟compare_exchange_strong()一样。上面的代码段使用的方法,没有充分利用在硬件中的排除伪失败的compare-and-exchange的机制。

最后,如果你因为其他原因而循环重试(比如前面典型示例A),那么把strong版本放到循环可能效果也会更好,这就跟情况1类似了。

 

 

使用BOOST.SPIRIT.X3的RULE和ACTION进行复杂的语法制导过程

Preface

上一篇简述了boost.spirit.x3的基本使用方法。在四个简单的示例中,展示了如何使用x3组织构造一个语法产生式,与源码串匹配并生成一个综合属性。这些简单的示例中通过组合x3库中的基本语法单元,创建了一些复杂语法单元,也就是非终结符。但这些示例中的语法单元完成的事情还不够,它们只能配合phrase_parse函数告诉我们,与源码是否匹配;并且通过一个简单赋值操作返回一个综合属性。如果我想要在匹配成功的时候完成一些用户自定义的Action,如何完成这种需求?此外,仅使用基本语法单元的组合来实现一个比较复杂的DSL的时候,会让产生式变得非常复杂。这些问题都是鄙文将要解决的问题。

Semantic Action

Semantic Action,姑且翻译成语义作用,是x3提供的一个Unary Parser.它可以包装一个语法单元和一个泛型仿函数。当Action包装语法的单元匹配成功的时候会调用这个泛型的仿函数。首先来看一个例子。

x3::parser类模板重载了operator index. 当一个parser对象以一个泛型仿函数对象为实参,调用这个operator index,parser会返回一个对象。这个对象的类型就是x3::action根据parser和f的类型后实例化的类型。而x3::action内部在发现包装的parser匹配成功以后,就会调用这个泛型仿函数。

泛型仿函数(杜撰的),得满足一个条件。把条件写成一个普通的仿函数如下。

泛型仿函数必须要有一个,具有一个模板参数的operator call. x3中是不关心这个operator call的返回值,因此可有可无。形参类型是一个依赖模板参数的类型,可以有const限定,但会失去对ctx对象的写权限。C++14标准中的Generic Lambda正好可以满足需求,这里使用lambda非常方便。在boost::spirit::qi中使用了boost::pheonix库来实现Semantic Action,但是局限性很大,使用用户自定义的仿函数也需要一些额外的代码来适配,x3的设计要合理多了。

小生详细讨论这个模板参数Context. Context的类型是由parser的综合属性决定的。它本质上是一个tuple. 而我们在operator call中使用的_attr()函数,可以类比为std::get<I>()函数,来获取上下文中传递的数据。_attr()获取的就是包装的子parser的综合属性。这样的函数还有三个,_val()获取rule的综合属性,_where()获取源码匹配串的当前迭代器位置,_pass()获取匹配的结果。_val()与_attr()的细节,鄙文在介绍rule的时候会展开。这里先用一个简单示例展示_pass()的使用方法。

当attribute,在这里就是x3::int_的综合属性,大于100或者小于0的时候把匹配设置为失败。

Rule

x3::rule可以管理组合在一起的基本语法单元,成为一个更复杂的parser。通常在实践中,我们自己定义的DSL语法会很复杂,使用rule管理基本的parsers,就是使用自底向上的方法构建我们的语法产生式,使得层次更加的清晰。下面,依旧以C++ Identifier为示例。

x3::rule一般情况下要定义两个模板参数,第一个模板参数是一个ID,仅仅只是当做ID的参数,可以只是一个前向声明;第二个参数是这个rule的综合属性。第十七行代码中用一个字符串初始化这个rule,给这个rule一个名字,这个行为是可选的,rule保存的字符串可以在调试的时候起到一定的作用。同时,我们可以发现这个rule使用了const修饰符,因为我们的语法都是不变的。定义一个rule对象是申明一个语法,接下来我们要定义它,第十八行的代码就是定义它的方法。那么identifier与identifier_def是如何绑定到一起的?下面我们对x3的源码探究一下,浅尝辄止。

x3::phrase_parser作为整个解析的入口,这个函数会进入x3::phrase_parse_main这个函数。

phrase_parse_main会从这个用Expression Tetmplate构造的静态语法产生式的根节点开始,调用parser的parse方法。实际上rule是从parser使用CRTP模式派生出来的,rule也是一个parser,pharse_parse_main就会进入到rule的parse方法中。

rule的parse成员模板方法调用了一个重要的函数,parse_rule函数。这个函数本来可以用一个通用的模板函数处理所有通用的情况,但是x3并没有这么做。x3的设计是在这里希望用户自己实现一个parse_rule的重载函数。注意,parse_rule是一个非限定性名称(Unqualified Name),因此parse_rule的重载方法因ADL查找的机制,可以定义用户的命名空间下面,rule其实也是定义在用户的命名空间下面。从这里就能够看到x3良好设计的思想。

这里有一个问题,为何不把rule管理的语法单元包含的rule对象中?通过阅读rule的源码可以发现,其成员仅有一个string成员变量。如果大家熟悉Expression Template的设计原理,就可以知道identifier_def是带有复杂的类型信息的。如果我们在rule中包含这个identifier_def,我们只有两种选择。增加一个模板参数<typename RHS>,使用CRTP的方式再一次继承;或者使用一个抽象类型把分派交给运行期。第一种方法,定然会让用户定义rule的时候非常不方便,第二种方法显然也已经违背了x3设计的初衷。然而x3在这里来了一记金蝉脱壳!且看示例代码的第22行。x3使用了rule_defintion来真正管理复杂的Expression Template,它以静态对象的方式在用户命名空间下重载的parse_rule的scope中存在。ADL查找配合重载决议,解析rule的代码进入用户自定义的parse_rule函数中,并由rule_defintion的parse方法继续递归向下!x3此处的设计方法,非常惊艳!!

大部分情况下,我们重载的parse_rule的方法就只有这几行代码了,而且是重复的。x3为了减少大家重载函数的工作量,定义了一个宏BOOST_SPIRIT_DEFINE来完成这项工作。但是有一个约定,rule_definition的对象名只能是rule的对象名跟一个”_def”的后缀。BOOST_SPIRIT_DEFINE还是一个可变参数的宏,可以让我们只使用一个宏就能够定义出我们需要的全部工作。

Problems in MSVC

上午刚刚从群里面的伙伴得知vs2015 update 1已经部分支持Expression SFINAE的特性了,x3的代码是不是可以不用修改就能使用。此时我正在下载安装update 1,稍后验证一下,会在后面的文章给出测试结果。

上一篇中也有一些纰漏。x3在vs2015中不能使用而修改的SFINAE的实现方法有点问题,并不能正确traits出ID是否有on_error和on_success函数,正确的修改做法请参考这一篇博客。我写的SFINAE为什么没有生效,小生还需研究一下,还请知道的大神们不吝赐教。

再提一提BOOST_SPIRIT_DEFINE宏,上一篇的文章中,我们有修改这个宏。官方的示例是允许如下的使用方式的。

以上两种方式在vs2015中也不不能编译通过的,不过使用本文示例中的方法暂时能满足需求。我也会在update1中也验证一下,decltype的bug是不是修复了。

Ending

x3提供了Semantic Action给用户处理复杂的解析行为,还提供了rule给用户管理复杂的语法单元。但是x3并没有把复杂的问题交给用户,而是使用了精妙的设计来规避静态类型带来的问题。下一篇,小生会谈谈spirit的性能问题,如何高效使用spirit的注意事项;还会详细讲述x3的黑科技,自定义parser来扩展x3的功能。

在msvc中使用Boost.Spirit.X3

Preface

Examples of designs that meet most of the criteria for “goodness” (easy to understand, flexible, efficient) are a recursive-descent parser, which is traditional procedural code. Another example is the STL, which is a generic library of containers and algorithms depending crucially on both traditional procedural code and on parametric polymorphism.” Bjarne Stroustrup

先把Boost文档当中引用的Bj的名言搬过来镇楼。小生在这里斗胆也来一句。 Boost spirit is a recursive-descent parser, which is depending on traditional procedural code, static(parametric) polymorphism and expression template.  Procedural Code控制流程,Static Polymorphism实现模式匹配与分派,再加上使用Expression Template管理语法产生式,让spirit充满的魔力。

鄙文对Spirit的性能问题不作讨论,只介绍Spirit.X3的一些基本概念和简单的使用方法,并在最后给出一个简单的示例。后面的一两篇幅,会分析一些性能问题,并介绍如何扩展X3. 

Terminals & Nonterminals

终结符号在X3中代表了一些基本词法单元(parser)的集合,它们通常都是一元的(unary parser),在后面的篇幅中会剖析spirit的源码作详细解释。终结符号在展开语法生成式的时候,是最基本的单位。例如x3::char_匹配一个字符,x3::ascii::alpha匹配一个ascii码的一个字母,x3::float_匹配一个单精度浮点数等,匹配字符串使用了正则表达式引擎。详细请参考字符单元数字单元字符串单元等。

非终结符号通常是由终结符号按照一定的逻辑关系组成而来。非终结符号通过组合终结符号来生成定义复杂的语法生成式。例如x3::float_ >> x3::float与”16.0 1.2″匹配成功,>>表示一个顺序关系。*x3::char_与”asbcdf234″匹配成功,但同样也会与”assd  s  s ddd”匹配成功,在词法单元的世界中空格或者一些自定义的skipper(如注释)会被忽略跳过。详细的参考X3非终结符的文档。

上面我们看到在X3使用终结符与C++的operator来生成非终结符,那么非终结符到底是什么类型。实际上它是使用了expression template,创建了一个静态树形结构的语法产生式。那么展开产生式的过程,就是一个自顶向下的深度优先遍历,碰到非终结符号,x3会尝试匹配其子语法单元直到终结符。

Synthesized Attribute

无论是终结符还是非终结符,在匹配字符串成功以后,它们将字符串作为输入,总会输出的某一个类型的值。这个值就是这个语法单元的综合属性。例如x3::char_的综合属性是char类型的值,x3::float_对应float型数的值。非终结符的属性比较复杂,可以参考组合语法单元的综合属性

除了综合属性外,还有一个继承属性。继承属性同综合属性一样也是某一个类型的值,这个值可能来自于某个语法产生式其他节点的综合属性。例如xml的节点<Node></Node>,在解析</Node>的时候,需要与前面的匹配,这里就是使用继承属性的场景。可惜在x3中继承属性还没有实现,在boost::spirit::qi中有继承属性的实现。小生正在尝试实现继承属性,但是鄙文就不讨论继承属性了。

Start Rule

在编译解析源语言的开始,x3需要知道其语法产生式的起始语法,也就是语法产生式的静态树形数据结构的根节点。整个分析的流程就总根节点开始递归向下进行。而根节点的综合树形可以是代表这个源代码的抽象语法树。我们可以发现X3的词法分析与语法分析是被合并到一趟(One Pass)来完成了。当然,也可以在第一趟只做词法分析,将根节点的综合属性依旧为字符串,然后再做第二趟完成语法分析。

Simple Examples

1.解析”1.2, 1.3, 1.4, 1.5″

x3::float_ >> *(‘,’ >> x3::float_)表示一个float类型的数据后面紧跟若干个(‘,’ >> x3::float_)的组合。在尝试写组合语法产生式的时候,先考虑语法再考虑综合属性。那么这里就要探究一下,这个组合产生式的综合属性是什么。‘,’是一个字符常量,在x3的文档中可以知道,字符串常量x3::lit的综合属性是x3::unused,这意味着它只会消费(consume)源码的字符串而不会消费(consume)综合属性的占位。简而言之‘,’ >> x3::float_中的’,’可以忽略,则其综合属性就是float类型的值。那么整个产生式的综合属性就是std::vector<int>类型的值了,或者其类型与std::vector<int>兼容(fusion.adapt)。

x3::float_ >> *(‘,’ >> x3::float_)可以简化为x3::float_ % ‘,’.

2. 解析”1.2, Hello World”到一个用户自定的综合属性

借助Boost.Fusion库,我们可以把一个struct适配成一个tuple. 宏BOOST_FUSION_ADAPT_STRUCT就把struct user_defined适配成了boost::fusion::vector<float, std::string>.

x3::lexeme是一个词法探测器。词法探测器同样是一个parser,同样有综合属性。lexeme的综合属性是一个字符串值,但是它修改字符串迭代器的行为,在匹配的时候不跳过空格。如果是默认跳过空格的行为,那么*x3::char_会跳过字符串间的空格,匹配的结果将会是”HelloWorld”,这是一个错误的结果;而x3::lexeme[*x3::char_]匹配的结果是”Hello World”.

phrase_parse函数定义在boost::spirit::x3的命名空间下,在这里phrase_parse是一个非限定性名称(unqualified name),使用ADL查找就能正确找到函数的入口。

3. 解析C++的Identifier

C++的identifier要求第一个字符只能是字母或者下划线,而后面的字符可以是字母数字或者下划线;

第一种方法比较直观。x3::char_只匹配一个字符,x3::char_重载的operator call可以罗列其可以匹配的全部字符,别忘了使用lexeme不跳过空格。

第二种方法使用了x3中内置的charactor parser. x3::alpha是一个字母的parser而x3::alnum是字母和数字的parser.

这一种看似更简洁,但是它实际上是错误的。原因在于’_’是一个常量字符,x3::lit是没有综合属性的,所以当我们使用这个parser去解析一个identirier的时候,它会漏掉下划线。

这一个例子会让我们更深刻的理解匹配串与综合属性的关系。虽然x3::raw的重载的operator index中的表达式的综合属性会忽略下划线,但是它匹配的字符串没有忽略下划线!x3::raw探测器,是一个unary parser,其综合属性的类型是一个字符串。它忽略其operator index中parser的综合属性,以其匹配的串来代替!例如,”_foo_1″中x3::lexeme[(x3::alpha | ‘_’) >> *(x3::alnum | ‘_’)]匹配的串是”_foo_1″,其综合属性是”foo1″;identifier_def的综合属性就把”foo1″用匹配串”_foo_1″代替。

4. 解析C++的注释

C++中注释有两种”//”和”/**/”。”//”一直到本行结束都是注释;而”/*”与下一个”*/”之间的都是注释。

operator> 与operator>>都是顺序关系,但是前者比后者更严格。后者由operator>>顺序连接的parser不存在也是可以通过匹配的;但是前者有一个predicate的性质在其中,operator>连接的parser必须匹配才能成功。x3::eol与x3::eoi是两个charactor parser,分别表示文件的换行符与文件末尾符。我们值关心注释匹配的串,在真正的解析中会被忽略掉,而不关心注释语法单元的综合属性。x3::seek是另外一个词法探测器,它的综合属性依旧是一个字符串,它同x3::lexeme一样修改了迭代器的行为,匹配一个串直到出现一个指定的字符为止。

msvc中使用x3

x3使用了C++14标准的特性,如Expression SFINAE(基本上都是它的锅), Generic Lambda等。它使用的大部分C++14的特性在vs2015的编译器上暂时都有实现除了Expression SFINAE. 小生只过了X3官方的例子,发现只用把这些使用了Expression SFINAE的代码改成传统的SFINAE的方法。除此之外还有Boost.Preprocessor库与decltype一起使用的时候在msvc14.0的编译器下有bug的问题。顺便喷一下微软,msvc都开始实现C++17的提案了,竟然连C++11的标准都还没有全部搞定!

1.修改<boost/spirit/home/x3/nonterninal/detail/rule.hpp>中的代码

 2. 修改<boost/spirit/home/x3/support/utility/is_callable.hpp>中的代码

3. 修改<boost/spirit/home/x3/nonterninal/rule.hpp>中的宏BOOST_SPIRIT_DEFINE为如下实现


修改出1、2都是因为Expression SFINAE在msvc中还没有实现。而修改处3的原因是在使用BOOST_SPIRIT_DEFINE貌似与decltype有冲突,小生写了一些测试代码,最后把问题锁定在decltype(rule_name)作为形参类型的用法上。这里在gcc上编译是没有问题的,应该是msvc对decltype的支持还不完全。BOOST_SPIRIT_DEFINE涉及到x3::rule的使用,将在下一篇详细讲解使用方法。

Ending

Boost.Spirit乍看把C++语法弄得面目全非,其实在处理Expression Template的时候,重载operator是最优雅的做法。在UE4的UI框架,还有一些基于Expression Template的数学库中也大量使用了这种技巧。Recursive Descent – 迭代是人,递归是神;Static Polymorphism – 形散而神不散。而Expression Template应用在其中,就像是前面两者的躯骨框架。但是Expression Template如果构建特别复杂的语法产生式,也会使得编译器负担很重,降低编译速度,甚至导致类型标识符的长度大于4K!这些问题将在后面的篇幅同Spirit运行期的效率问题一同讨论。 总体而言,小生觉得Spirit依旧是优雅的。

对2015.05技术沙龙中江南群主“任性”故事的探讨

五月份技术沙龙第二场演讲中,江南群主讲述的第二个“任性”故事的一个细节引发了一些争议。经小生仔细观察,三位讲师都有使用到相同的技术,但是实现的方法都有所不同,本文特来对这一个问题做一次详细的研究。

众所周知,在C++中实现反射是一件很棘手的事情。但是在确保没有类型退化(decay)和没有隐式类型转换的干扰下,是用模板元编程的一些技巧可以帮助我们完成一些目标。比如判断某个类型中是否含有某个成员函数,本文中的类成员函数仅指非静态成员函数

现实的基本思想是“一瞥”( catch a glimps of )这个成员函数。一瞥实际上是编译期的某种计算,而不会生成实际的代码。例如非求值运算符( Unevaluated Operator ),重载解析模板特化。非求值运算符在C++98下只有sizeof,到了C++11标准又扩充了decltype,typeid和noexcept三个操作符。先来看看C++98的实现。

由于sizeof只能对类型大小求值,因此C++98的版本的基本思想就是利用SFINAE和重载决议,配合sizeof来计算函数返回类型的大小,而获知哪一个test函数是决议的结果。如果是返回One类型的test,那么可以判断出这个类型T含有命名为foo,返回类型为void且有一个形参为void的成员函数。

这里有两个问题。1. 是否含有成员函数foo,单单只知道成员函数名是不够的,还必须知道它的完整签名,如返回值(暂不考虑cv修饰符)。2. 重载解析的规则里面有讲,相同的形参和不同返回类型的重载函数是有歧义的。因此,我们只需要知道形参就足够了,而不需要知道其完整的签名。

问题一很好解决,就是啰嗦点,除了提供函数名称之外,所有的形参和返回值类型一并提供。在c++98中,想做到这一点更啰嗦。我们需要提供形参数目从1到N每种版本的实现,具体实现多少个N由类库作者自行估量。

第二个问题,我们要寻求其他的实现方法了。因为指向非静态成员函数的指针(pointer to non-static memeber function)的签名有返回值类型,还有cv修饰符。基本思路是,假装我们要调用这个成员函数。先看看实现。

sizeof(((T*)0)->foo()),这一句就是假装去调用这个函数并尝试去计算函数返回值的类型的大小。由于sizeof是非求值运算符,因此没有生成运行期的空指针调用foo的代码。从这里就能看出sizeof操作符已经心有余而力不足了。首先sizeof将类型映射到了类型大小,丢失了类型信息;其次sizeof无法对void求值,这也是这个实现版本的硬伤。总之小生受能力所限,一直无法在cpp98版本中寻求比较好的实现方法。拜求得道大神之不吝赐教。

到了c++11的时代,情况好了许多。decltype这个非求值运算符的出现,让C++98中实现has_member_foo的第二种思路得以实现。先看看实现代码。

基本思想同样是SFINAE和重载解析,配合非求值运算符。只不过换成了delctype运算符。相比于sizeof运算符,decltype保留了非求值表达返回类型的完整信息,更重要的是decltype也能对void计算,不会出现sizeof(void)的尴尬。

深入细节,我们来看看C++11的实现版本是如何一瞥foo的调用的。通常,我们在描述数学问题的时候,总是使用假设。这里类比之,“假设”有一个类型的实例,且“假设”有可列的实参的全部实例,“尝试”使用这些实例调用函数foo,让decltype演绎这次假设的返回值结果!由于decltype是非求值运算符,所以计算中对象不需要真正的实例,同样函数只需要声明而不需要函数体。std::declval就是这样的一个函数。在std命名空间中就是返一个universal reference,并没有函数体。std::decltype只能用于非求值的计算当中。小生认为这种实现是最为简单的,如果使用指向非静态成员函数的指针来实现还要考虑返回值和cv修饰符,而这一种是完全不用考虑的。

接下来扩展一下思路。

拓展思路-另外的实现方法。文章的开头提及到的非求值的编译期计算,除了非求值运算符和重载解析外,还有一个模板特化。那么是否可以通过模板特化来实现本文的需求呢?先来看看基本思路。has_member_foo的泛型实现,应当返回false,继承std::false_type即可。在某种情况下的特化继承std::true_type!听起来是不是很美好?!实现细节。首先,为了简化问题,先不考虑成员函数有形参的情况。元函数has_member_foo的第一个参数是T,要判断的类型,应该是雷打不动的。而我们需要额外的一个参数,为特化的实现所用。

先举一个例子。还记得元函数enable_if配合模板特化的技巧吗?元函数template <typename T> struct size_integral;只计算整形类型的大小,其他类型不做任何计算。看看实现的代码。

当编译器尝试使用某个类型T去实例化size_integral的时候,会实例化所有的特化版本,并决议最佳的匹配。如果T是一个整形,那么特化版本会选择;如果T不是整形,那么特化版本实例化替换失败,根据SFINAE,会匹配泛型的实例化版本。

现在的问题是,针对本文的需求,我们需要一个元函数工具,使得传递任意可列个C++参数类型给它,它始终导出一个void. 为了迎合上面给出的例子的形式,小生才选择void。于是我们构建一个这样的工具,其实现如下。

也有了本文需求的另外一个实现

如果decltype能够成功推导出voider_t中的类型,那么决议就会选择这个more specialized的版本;反之,就会选择泛化的版本。实现是不是更优雅了?使用模板偏特化减少了使用重载解析造成的额外代码,至少小生谨以为然。

只可惜目前的编译器都不支持这种实现,原因是因为voider元函数没有使用任何模板参数,而被编译期做了优化。C++委员会也有一个提案来解决这个问题,详见CWG 1558, treatment of unused arguments in an alias template specialization. 其中的原委,小生还不是很清楚,望闻得道大神指教。

拓展思路-易用性。江南群主在这个故事中也提到了,这个元函数只能针对某一个成员函数,换一个成员函数要重新实现一个,中间有重复代码。因此有了使用宏来生成代码的实现版本,详见江南群主ppt. 可是江南群主的版本必须“两步走”!先得使用宏声明,再使用。有没有什么方法可以使用一个宏就能搞定?经过小生的测试,仅在msvc平台下还有一个小坑,把宏写在函数体内似乎有点问题,始终都找不到这个模板,不知道其他平台如何。因此一定要把宏写在函数体以外。此外,还需要考虑命名空间的问题。其实易用性的实现就目前的C++标准还是有些不够。

鄙文先写到这里。对于C++1y技术感兴趣的同学请加入我们社区,加入QQ群296561497讨论,让C++的世界更美好。

Copy Protected by Chetan's WP-Copyprotect.