Brainfuck JIT Compiler in Rust

Hello JIT


JIT不是一个神秘的玩意。

—— Tondbal ik Ni

我们都知道,对于解释型的语言实现来说,性能是大家关注的焦点。比如,这位 Tondbal ik Ni 曾经还说过:

P*没上JIT,慢的一逼!

—— Tondbal ik Ni

似乎这句话总是隐含着另一层意思:实现JIT,难!而当我们再一联想到JVM这种庞然大东西的时候,很自然的就

然而!JIT原理并不复杂,做出一个玩具JIT Compiler更是非常轻松。之所以JVMs那么庞大而复杂,原因之一在于它们做了大大大量的优化工作。

我们今天就要来看看JIT究竟是个什么东西!

Just-in-Time Compiler


JIT Compiler,究其根本还是一个Compiler。一个Ahead-of-Time Compiler的编译过程往往会有这些(既不充分也不必要的)步骤:

  • 词法分析
  • 语法分析
  • 语法制导定义或翻译
  • 中间代码生成
  • 代码优化
  • 目标代码生成

对于解释器来说,往往将编译工作进行到中间某一步后就直接进行解释执行了,并不生成目标代码。而JIT Compiler却是要生成目标代码的,最终执行的是编译好后的Native Code。只不过,它将目标代码生成的部分推迟到了执行期才进行。这样的好处有:

  • 无需重新编译就可以实现跨平台
    参考Java,它将平台差异隔离在了中间代码部分(指Java ByteCode)。
  • 运行时优化
    当年大欢还在用Gentoo的时候曾经开过嘲讽:本地编译,优化开的细,比你Arch强多了(然而后来还是倒戈到了Arch 666666)而一个JIT Compiler不仅知道目标平台的信息,更知道程序的运行时信息,因此往往可以有更多的优化。
  • 解释/编译混合
    这其实也可以看作是一种优化措施,即执行次数多的代码JIT编译后执行,执行次数少的代码解释执行。因为JIT还是需要一步编译的过程,如果代码执行次数少,很可能抵消不了编译过程带来的时间开销。

所以,其实优化是JIT Compiler中相当重要的一部分。如果我们不要优化,那可是简单了很多哟。

Core of JIT


如果你能看懂这段代码,那就说明你已经掌握了JIT的精髓了:

#include <stdio.h> 
#include <string.h>
#include <sys/mman.h> 

char f[] = {0x48, 0xC7, 0xC0, 0x00, 0x00, 0x00, 0x00, 0xC3}; 

int main(){  
    int a = 5; memcpy(&f[3], &a, 4); 
    char* mem = mmap(NULL, sizeof(f), PROT_WRITE | PROT_EXEC, MAP_ANON | MAP_PRIVATE, -1, 0); 
    memcpy(mem, f, sizeof(f)); 
    printf("%dn", ((int (*)())mem)()); munmap(mem, sizeof(f)); 
    return 0;
 }

其中mmap的作用是申请按照PageSize对齐的内存,并可以修改页面保护属性。

所以一个JIT Compiler编译的主要步骤就是:

  • 申请一块可写、并且将来可以改成可执行的内存。
  • 生成机器代码,写入内存。
  • 修改内存页面属性,Call it!

So easy,下面进入脑残环节。

An interpreter for Brainf*ck


我们将实现一个Brainfuck的解释器,随后再实现一个JIT编译器。之所以选择Brainfuck,自然是因为它相当简单,完全可以当做中间代码进行处理,省去了词法语法分析、中间代码生成等与编译原理直接相关的部分。

解释器写起来就太简单了。Brainfuck预设我们有一块无限大的内存,初值均为0。数据指针指向第一个字节。它支持8种操作:

  • >
    数据指针右移一格
  • <
    数据指针左移一格
  • +
    数据指针指向的内存内容+1
  • -
    数据指针指向的内存内容-1
  • .
    putchar
  • ,
    getchar
  • [
    如果当前内存内容 == 0,则向后跳转至对应的]
  • ]
    如果当前内存内容 != 0,则向前跳转至对应的[

翻译器部分可以作为大一的C语言实验哈哈哈哈

A JIT Compiler for Brainf*ck


如果要手撸JIT Compiler,则需要对目标平台有一定的了解。我们这里的目标平台是x86_64,这个网址 可以在线将汇编生成为x86或x64的机器代码。

第一步:申请PageSize对齐的内存
这一步除了使用mmap,还可以使用posix_memalign。

第二步:生成函数框架
在这里我们将一整个Brainfuck程序编译成一个函数。这个函数接受一个参数,即我们事先申请好的一块内存作为数据区域。对于x64来说,Linux等类Unix系统遵循的调用约定是System V AMD64 ABI,函数的第一个参数由Rdi传递。因此我们生成的函数的开始与结束部分如下:

pub fn compile_and_run(&mut self, code: &str) {  
    self.jit_code.emit_push_r(Reg::Rbp); 
    self.jit_code.emit_mov_rr(Reg::Rbp, Reg::Rsp); 
    self.emit_push_regs(); //Save regs 
    self.jit_code.emit_mov_ri(Reg::Rbx, 0); //Rbx = data_pointer 
    self.jit_code.emit_mov_rr(Reg::Rdx, Reg::Rdi); //Rdx = memory_base 

    //more code here... 

    self.emit_pop_regs(); //Load regs that saved before 
    self.jit_code.emit_mov_rr(Reg::Rsp, Reg::Rbp);
    self.jit_code.emit_pop_r(Reg::Rbp);     self.jit_code.emit_ret(); 
}

上面的代码中,各个emit函数的作用是生成相应的机器代码,放入内存中。例如emit_push_r(Reg::Rbp)将生成机器码0x55,它对应的汇编为push rbp

接下来就是根据Brainfuck各个操作生成机器码了。例如>操作:

self.jit_code.emit_inc_r(Reg::Rbx);  

So easy. 需要额外说明的只有两点:

一是我们可能需要重定位操作。当我们的buffer空间不够的时候,需要对其进行扩大,这样的话我们代码所在的 地址就会变动。而有一些指令(比如Relative跳转、RelativeCall等)它的操作数是当前RIP(即程序计数器PC)与目标地址的 Offset,这就需要当我们最终结束生成这个函数时,再对这些指令的操作数进行计算。

二是对于[操作来说,需要一个patch back的过程。当我们在编译过程中遇到它的时候,我们并不知道跳转的目的地址是哪里。只有在遇到对应的]时,才能更新它的跳转地址。

第三步:Call it!

let mut memory: Vec<u8>= vec![0; 10000];  
let func: extern "C" fn(*mut u8) = unsafe { mem::transmute(self.jit_code.function()) };  
func(memory.as_mut_ptr());  

Performance Comparison


我找了一个用Brainfuck写的Mendelbrot程序进行测试,它会在控制台输出Mendelbrot的ASCII图(大神请受我一拜 )。除了上面自己实现的解释器和JIT编译器外,我还找了一个Brainfuck的编译器bfc进行测试。

测试结果大致如下:

Interpreter: ~1min
JIT: ~4.31s
bfc: ~4.21s

代码请参 https://github.com/dontpanic92/rainfuck

最后,由于将汇编翻译为机器码是一件体力活,我们还可以使用一些现成的工具。例如DynASM,通过预处理的方式将C + ASM混合代码处理为C语言代码(即省去了我们显示emit的部分)。或者,也可以考虑使用LibJIT或LibGCCJIT等库。

Reference


  1. http://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html
  2. http://www.hydrocodedesign.com/2014/01/17/jit-just-in-time-compiler-rust/
  3. http://www.jonathanturner.org/2015/12/building-a-simple-jit-in-rust.html

使用Reflexil修改Unity3D游戏逻辑

曾经有个游戏叫做《新剑侠传奇》,曾经停留在一个尴尬的版本1.0.7。作为一名抠脚大汉,自然要坐在在电脑前为广大玩家发福利!

故事背景

游戏发售之后出现了一些Bug,官方在更新至1.0.7版本后决定回炉。然而这一版本依然有一些玩家比较需要的Feature没有实现。在长达两周多的回炉阶段,我的补丁横空出现啦!

技术背景

MSIL可以较为轻易地反编译回C#/VB代码,如果不做代码混淆的话,可读性非常高。目前很多国产单机游戏都选择Unity 3D做为引擎:scream: ,并使用C#作为主要逻辑的实现语言。这为我们修改游戏逻辑创造了相当好的条件。

实现功能

  • 打击感增强
    通过在命中目标后停顿画面0.1秒实现。
  • 新增操作模式
    《新》是一个具备跟随视角的3D游戏,鼠标旋转视角,鼠标点击怪物为普攻,感觉略坑爹。新增操作模式采用类似龙之谷的方式:默认隐藏鼠标,鼠标移动旋转视角,鼠标点击为普攻,ctrl键呼出鼠标。
  • 摄像机位置记忆
    每次剧情之后摄像机都会回到初始位置,不会记忆上次用户调整的摄像机与人物的距离。
  • 暂停游戏
    进入战斗或者开始剧情之后,终于可以随意去上厕所了……
  • 跳过开始动画
    打开游戏时无需强制观看片头。
  • 画面改善:对比度增强、Bloom、HDR
    使用Unity内置Shader实现。

工具准备

  1. .NET Reflector
    我们用 .NET Reflector 来对 .NET Managed DLL 进行反编译工作。对于没有进行混淆或加密操作的程序,可以得到可读性很高的代码。
    0<em>1448775094110</em>1.png
  2. Reflexil
    Reflexil 可以在已经编译好的Managed DLL中插入MSIL代码。它提供了.NET Relfector的插件,安装好后即可直接插入IL代码。
  3. XamarinStudio (MonoStudio)
    其实这个有无皆可。但是如果不想所有代码全部使用IL手写的话,还是搞一个比较好。

代码修改

拿打击感增强作为一个例子,我们来看一下如何修改。Unity 3D游戏的主体逻辑都在/xxxx_Data/Managed/Assembly-CSharp.dll中。这个游戏的逻辑由几百个类/枚举构成,如果游戏大量使用了Unity插件(比如可视化编程:see<em>no</em>evil: ),可能还会更多。

增强打击感的方法是在玩家命中敌人后画面停顿0.1秒。所以我们需要在命中时记录当前时间、停顿画面,然后在0.1秒后取消停顿。

经过浏览代码,发现负责进行攻击的逻辑集中在Fighter类中。我们需要修改的有两个函数:一个是CalcHurt,发生在玩家已经命中怪物之 后,用于计算伤害;另一个是Update,每次迭代更新逻辑时都会调用这个函数。我们还需要一个Field用于记录停顿时间,可以直接在类上右击通过 Reflexil添加。

打开CalcHurt方法,在Reflexil中添加IL代码。IL代码非常简单易懂,而且我们并不需要掌握所有的IL指令。简介可以参考Introduction to IL Assembly Language,或者在Common Language Infrastructure (CLI) | ECMA-335中有所有指令的列表。

在修改完IL代码后,.NET Reflector会重新加载并反编译代码。如果指令有错误,.NET Reflector会无法反汇编成功。

停顿功能使用了Unity提供的Time.settimeScale函数,获取时间使用Time.getrealtimeSinceStartup。这些函数可以参考Unity 3D Manual

举例来说,

Time.set_timeScale(0.001f); InjectedField = Time.get_realtimeSinceStartup + 0.1;  

的IL代码如下:

ldc.r4 0.0001 call Time.set_timeScale call Time.get_realtimeSinceStartup ldc.rc 0.1 add stsfld InjectedField #InjectedFiled为静态成员  

就是这么简单啦。

使用XamarinStudio

如果不想所有代码全部手写,可以使用XamarinStudio新写一个Class,将所有新的逻辑放在这里。然后再修改原来的Assembly-CSharp.dll时,所有位置都变成函数调用就行了。

在编写新Class时,需要把游戏的Managed目录中的相关DLL作为引用添加进我们的工程里。对于这个游戏来说,我们主要用到了 UnityEngine、Assembly-CSharp、Assembly-CSharp-firstpass、Assembly- UnityScript-firstpass。

写好Class后,可以使用Reflexil将改Class添加进Assemby-CSharp的引用中。
0<em>1448778641887</em>3.png

请原谅时间久远电脑上已经没有XamarinStudio了:joy:

替换原始文件

没什么问题之后,就可以去论坛或者贴吧收获一番经验了~

关于Intel超线程技术

原回答自知乎:奔腾四和SNB之后的超线程技术一样吗?

1.Pentium 4 HT(NetBurst)和Core i7(Nehalem)中的超线程技术一样吗?

Intel的超线程技术在2002年2月发布的志强处理器中首次出现,并在同年12月发布的Pentium 4 HT中同样加入了这一技术[1]。关于此时的Intel的超线程技术的论文比较多,比如(Deborah T. Marr et al, 2002)[2]。论文中提到,architecture state在各个逻辑线程中是独立存在的,而其余几乎所有资源都是共享的。Architecture state主要包括的是各种寄存器,例如通用寄存器、控制寄存器CR以及APIC寄存器等;而共享的包括缓存、执行部件、分支预测、控制逻辑以及总线。

而后来在Nehalem核心(Core i7)中重新回归的超线程技术,我没有找到官方详细的论文。不过找到了一个德克萨斯A&M大学博士生的论文,关于Nahalem核心的[3]。文中同样提到:对于同一个物理核上的逻辑核心,它们之间

  • 独立:寄存器状态、返回栈缓冲(用于预测函数返回指令)、指令TLB(用于加速虚拟地址与物理地址的转换)
  • 分隔(静态划分):各种缓冲
  • 竞争共享:分为SMT-sensitive 和SMT-insensitive。保留栈(用于实现乱序执行)、数据TLB、二级TLB等属于SMT-sensitive,所有执行单元均为SMT-insensitive。

以及共享Cache。

所以结构上看,基本一致。

两篇论文中都有提到CPU的Pipeline(流水线结构)。当Nehalem开启超线程时,将从两个线程中取指令,之后送入后端乱序执行引擎执 行。而[1]中提到得Pentium 4在开启超线程后的做法则更为详细:两套指针分别记录两个线程的PC,解码后存入Execution Trace Cache(其为一级指令缓存的主要部分)。两个线程再按照时钟周期依次访问这个Cache。如果有一个线程stall住了,则另一个随意用。

大致来看,主要步骤基本相同。不过细节不太清楚。

2.什么是超线程?

超线程(即Simultaneous multithreading[4])属于线程级并行方法。在说超线程技术(多线程技术)之前,我们先来看一下超标量技术。

超标量技术是一种指令级并行技术,具备超标量特性的CPU具有同时发射多条指令的能力,这样CPU就可以充分利用各种执行部件。举例来说,如果单发 射一条加法指令,那么在执行过程中只有加法部件(或算数计算部件)被利用起来;如果我有两条指令:add R1, R2; shr R3, 3(加法和右移),如果两条指令同时执行,那么加法部件和移位部件就同时利用起来了。

然而能够同时执行的前提是:两条指令之间不能有相关性。例如第一条指令需要写R1,第二条指令需要读R1,那么这两条指令无法同时执行。由此即诞生出了乱序执行(Out of Order)技术:如果第三条指令与前两条指令没有相关性,则可以先执行第三条指令。

超线程技术则可以更加充分地利用执行部件:同时执行两条线程,进一步降低了指令之间的相关性。同时,如果一个线程需要访存(意味着大量的时钟周期可能被浪费)、或是分支预测失败(意味着需要清空流水线),超线程的优势就更明显了。

然而对于超线程技术的优劣则有激烈的讨论,主要集中在性能的提升的同时芯片面积与功耗等也在增加,这样的trade-off是否合适。

3.关于超线程技术消失又重现

Pentium Pro、Pentium 2、Pentium 3所使用的架构均为P6架构,Pentium 4使用Netburst架构,后续的Core 2使用的是Core架构,从Core i系列开始进入Nehalem/Sandy Bridge架构等[5]。

然而,NetBurst是相对独立的一个架构,让人记忆深刻的就是超长的流水线和相当高的频率。而Core架构是基于P6的变种Pentium M的架构改进而来的。在Intel的一个Slides中也可以得知,NetBurst和P6的Pipeline差异较大,Nehalem的基础需要在二者 中做出选择。而最后做出让多线程回归的决定,也是一种“抉择”[6]。

Reference

  1. Hyper-threading
  2. Marr D, Binns F, Hill D L, et al. Hyper-Threading Technology Architecture and Microarchitecture[J]. Intel Technology Journal, 2002, 6(1):1.
    http://www.cs.sfu.ca/~fedorova/Teaching/CMPT886/Spring2007/papers/hyper-threading.pdf
  3. Thomadakis M E. The Architecture of the Nehalem Processor and Nehalem-EP SMP Platforms[J]. Jfe Technical Report, 2011.
    http://sc.tamu.edu/systems/eos/nehalem.pdf
  4. Simultaneous multithreading
  5. Nehalem (microarchitecture) P6 (microarchitecture) Intel Core (microarchitecture)
  6. http://web.stanford.edu/class/ee380/Abstracts/100217-slides.pdf

深度学习简介及单词的向量化表示

Content

  • 深度学习简介
  • NLP与深度学习
  • 单词的向量化表示

1. 深度学习简介

首先应当明确的是,深度学习是机器学习中的一个领域。然而与传统机器学习所不同的是,传统的机器学习的重点在于特征的设计。在设计过特征之后,就变成了研究如何调整权重、优化参数来得到一个最优的结果。

图片1

然而特征设计所涉及的知识、经验的储备往往只有博士级别的研究人员才能够得心应手,而且特征设计的优劣往往直接影响最终的分类结果。与之相反,深度学习应用的是多层特征学习,其中特征学习指的是计算机能够自动地学习到特征的表示,这就解决了手工选择特征局限性较大的问题。深度学习提供了一个近乎统一的框架。它够表达各种信息,能够自动学习,并且非常灵活。这个框架也同样支持监督学习与非监督学习两种学习方式。

除此之外,深度学习还具备以下特点:

  1. 数据量增大时,深度学习的获益更多;
  2. 能够利用多核CPU、GPU加速
  3. 不断涌出的新模型、新算法
  4. 最终性能的提升

2. NLP与深度学习

事实上,在NLP领域,深度学习已经开始展现它的威力了。在应用方面,机器翻译、情感分析、问答系统等都依靠深度学习取得了重大的进步;而在NLP的各个层次上,例如语音识别、形态分析、句法分析、语义解释等,深度学习也发挥了重要的作用。接下来

选区_006

语音

在语音层面,传统的表示形式采用了表格的形式来表示每一个音素。而在深度学习中,将每一个音素表示为向量。

字形

对于一个单词来说,传统的表示形式将词根、前缀和后缀分开表示,例如un-interest-ed。而在深度学习中,往往将一个词素表示为一个向量。

图片3

句法

传统的表示方法会显示地标注出每一个短语的具体类别,例如VP、NP等。而在深度学习中,会将一个词或短语均表示为向量。

语义

lambda演算是一种在语义层面的传统表示方式。例如,将likes视作接受两个参数的函数,每一次合并都相当于柯里化的过程:

图片4

而在深度学习中,仍然将语义表示为向量的合并。

可以看出,向量形式是NLP中所有层次的表达形式。


3. 文本的向量化表示

意义

语言文字或一些符号具备一定的意义。例如,苹果和apple所指代的意义相同。而对于一个外星人来讲,■△▲〓※↓↑〓↓说不定就代表“苹果”。因此,如果想要让计算机理解这一层意义,那么它也需要一种表示;反之,如果我们认为某种表示是计算机所理解的“苹果”,那么即便我们无法阅读(例如■△▲〓※↓↑〓↓),这也是在合理范围之中的。

意义在计算机中的表示

一种表达意义的方式是利用同义词和上位词。例如,熊猫属于动物一类,我们可以用“动物”来表达熊猫的某些方面的意义。再比如,good和well有时意义相近,那么我们可以用well来代表good的某些方面的意义。

然而,这样的表示的问题在于:

  • 缺乏语义差别的信息
  • 难以适应新词
  • 主观
  • 需要人工标注
  • 相似度难以计算

究其根本原因,在于这种方式将单词视为了一种原子符号。或者说,如果在向量空间中对其进行表示的话,我们把它叫做one-hot:

选区_007

one-hot的问题在于,无法表示单词之间的意义相近的关系。例如,hotel和motel两个词,如果利用one-hot形式来表示的话:

hotel  = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

motel = [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

我们无法使用向量运算来获得它们之间意义上的相似度。

You shall know a word by the company it keeps.

–J.R.Firth

J.R.Firth是50年代著名的语言学家,他的这句话被誉为当代NLP领域中最成功的思想之一。对于一个单词的意义,较好的方式是考虑它的上下文。

图片5

而这个“上下文”,则有不同的范围可以选择:其一是将整个文档作为上下文,另一种是选择一个较小的固定的窗口作为上下文。对于“全文档共现”来说,单词向量的维数是文档的个数,如果这一单词在某一篇文档中出现,则该维置1。全文档共现的方式能够挖掘单词的隐含语义。例如,对于“足球”和“教练”来说,它们很有可能在多篇文档中共同出现,则它们的向量也有多维同为1;如果取and的话,就可以获得它们之间的相似程度。

而对于基于窗口的共现来说,其能够同时获得语法与语义的信息。下面我们通过一个例子来看一下基于窗口共现方式的词向量学习过程。

我们选取三句话:

  • I like deep learning.
  • I like NLP.
  • I enjoy flying.

窗口大小取为1,即向前看1一个词、向后看1个词,窗口中一共3个词。通过对共现次数的计数,可以得到以下的矩阵:

图片6

我们可以发现,这个矩阵有这样的几个问题。一是维度过高,它与整个vocabulary相关,因此维度也会随着词汇量的增加而增加;而是矩阵十分稀疏,这将导致难以训练出有效的模型。我们可以通过两种方法来降低词向量的维度:一是用数学方法对这个矩阵进行降维(如SVD奇异值分解);或是不通过这个矩阵,而是直接估计出词向量。

SVD奇异值分解

通过SVD分解,可以将一个mxn的矩阵分解为3个维度分别为rxn、rxr、mxr的矩阵。我们所需要的词向量信息都存储在第一个rxn的矩阵当中。第二个rxr的矩阵是一个对角矩阵,通过调整对角线上的数值可以对第一个rxn矩阵的列进行排序,从而让比较重要的维排在前面。

图片7

使用numpy可以很容易地进行SVD分解计算:

U, s, Vh = numpy.linalg.svd(X, full_matrices=False)

下图是取前两维生成的plot:

图片1

可以看出,相对相近的单词距离更近。

使用SVD方法时,可以进行一些hack,例如通过阈值或过滤的方法对停用词进行处理、添加权重、使用Pearson相关系数代替count等。

图片2

然而,SVD奇异值分解有一些弊端。例如,计算复杂度与m×n相关、难以加入新的单词等。最后,它与深度学习的审美不同:深度学习通常追求从某一个例子中学习一些东西然后再移动到下一个,而SVD方法却需要对所有语料进行整体地处理。

直接学习低维向量

除了利用SVD方法把高维矩阵降维处理外,还可以直接学习低维向量。例如word2vec,他直接预测每个单词相邻单词的概率。除了word2vec,2014年出现了Glove: Global Vectors for Word Representation. Pennington et al. (2014)。它们可以向语料库中不断添加新词。

word2vec的核心思想是:当窗口长度为c时,预测与中心词共现的单词。其目标函数为:

图片3

其中p为

图片4

然而当单词量增大后,其计算将会变得缓慢。因此,我们可以通过采取采样、简化概率函数等方式进行近似。

  基于频数的方法 直接预测方法
优势 训练速度快充分利用了统计信息

性能更好可以获得到比单词相似性更复杂的信息

劣势 主要用来获得单词之间的相似度当频数较少时,获得的比重不合适

与语料库的大小有关没有利用统计信息

 

Reference

http://cs224d.stanford.edu/

Jump Out of C++:面向对象编程探索(二)

这次是这一个系列技术分享的第二部分,主要介绍的是C++对象模型。这里所讲的对象模型,是指如何在内存中(空间上)表达对象的性质和特征,以及如何在运行时(时间上)提供完成面向对象系统中的必要操作的能力。

Table of Content


C++并不是天生地庞大而迟缓

—— Stanley B. Lippman

  1. 概述
  2. 对象的内存布局
  3. 运行期环境

1. 概述


对于传统的C语言程序来讲,数据与算法是分离的:

struct Circle  
{ 
int x, y;  
int radius;  
}; 

Circle MakeCircle(int x, int y, int radius) { //.... } void DrawCircle(Circle c) { //.... }  

在C++中,将这样的与传统C语言结构体内存布局兼容的对象叫做Plain Old Data(POD)。

此外,我们还可以将数据和算法整合在一起:

class Circle  
{ 
public:  
    Circle(int x, int y, int radius); 
    void Draw(); 
private:  
    int x, y; 
    int radius; 
};

对于这样的代码,在时空上是否增加了什么负担?同时,C++还支持继承、多重继承等很多机制,它们呢?

class Point {  
public:  
    Point(int x, int y); 
private:  
    int x, y; 
}; 
class Circle : public Point { //... };  

我们先从最朴素的模型开始,看一看如何来安排对象的内存空间:

  • 简单对象模型

在简单对象模型中,对象中只存储指向成员(包括数据成员和方法成员)的指针,所有操作均通过指针索引来完成。

  • (双)表格驱动模型

双表格驱动模型是指在对象中仅存储两个指针:一个指向数据成员table的指针,一个指向方法成员table的指针。这种模型的优点在于所有对象的内存空间占用及内存布局均完全一致。早期的某款C++编译器采用了这一种模型。

以上两种模型都是可以在一定程度上满足需求的,但并未被大多数编译器所采用。目前主流的模型如下:

  • 非静态数据存放于对象内部
  • 静态数据、非virtual函数存放于对象之外
  • 每一个class至少有一张虚函数表
  • 每一个object中包含一个指向该表的指针

1

本文将探讨在单继承、多继承、虚拟继承下C++对象模型是如何应对的。

2. 对象的内存布局


 2.1 类

对于如下的代码来说:

class Circle  
{ 
public:  
    Circle(int x, int y, int radius); 
    void Draw(); 
    static void Print(); 
private:  
    int x, y; 
    int radius; 
    static int count;
};

根据前述的对象模型,其其布局与在C语言中使用结构体时是一致的:

circle

同时C++标准保证,在同一个权限声明块中(即同一个public、protected或private块中),后声明的成员在内存中位于高地址(更靠后)。但并没有规定其一定紧邻,其间可以插入其他编译器所需的数据。

 2.2 不包含虚函数的单继承

而对于单继承来说:

class Point  
{ 
public:  
    Point(int x, int y); 
protected:  
    int x, y; 
}; 
class Circle : public Point { protected: int radius; };  

其内存布局如下:

绘图7

可以看出,其占用内存的成本并没有增加。然而是否一定不会增加呢?如果我们有如下代码:

class Point {  
public:  
    //... 
protected:  
    int x, y; 
    char c1, c2; 
}; 
class Circle : public Point {  
public:  
//... 
protected:  
    char c3, c4; 
    int radius; 
};

此时的内存布局将为:

绘图7_

由于需要对其内存,编译器很可能会插入padding字节。这时,继承的内存占用将会比数据全部在同一个类中的时候大。不过,我们是否可以取消掉padding呢?

答案自然是否定的。取消padding后,Point对象和Circle对象中Point部分在内存中占用的大小将会不同,此时如果存在以下代码:

void some_func(Point* point) { Point a; *point = a; }  

由于Circle和Point存在继承关系,我们不能在编译期确定代码中point的真实类型是什么。如果point一旦为Circle类型,那么在执行到*point=a这一句代码时,将会多覆盖两个字节的内存,即c3和c4将被内容不确定的内存覆盖。

2.3 包含虚函数的单继承

对于包含虚函数的单继承来说,其内存中将会增加一个指向虚表的指针。

class Point {  
public:  
    virtual void Print(); 
protected:  
    int x, y; 
}; 
class Circle {  
public:  
    virtual void Print();
protected:  
   int radius; 
};

circle<em data-recalc-dims=withpoly” title=”” />

需要说明的是,虚表指针_vptr可以在Point中的任意位置。上图中其位于Point对象的末尾,也可以位于最前,甚至在中间也可以。在末尾的好处在于其前面的部分仍然与C语言结构体兼容,在最前的好处是可以省去一步计算过程(对象的地址即为虚表指针的位置,不需要额外的计算)。而一般来讲没有编译器选择在中间位置插入虚表指针。

对于一个Point对象来讲,其vptr将指向Point类的虚表;而对于一个Circle对象来讲,虽然图中标明了vptr在Point部分中,但这仅表明它是由Point继承而来,其仍将指向Circle类的虚表,如下图所示:

circle<em data-recalc-dims=withpoly_2″ title=”” />

2.4 包含虚函数的多重继承

假如有如下代码:

class Point {  
public:  
    virtual void Print();
protected:  
    int x, y; 
}; 
class Text {  
public:  
    virtual void OutputText(); 
protected:  
    char buffer[4]; 
}; 
class Circle : public Point { protected: int radius; };  
class CircleWithText : public Circle, public Text  
{ protected: int text_x, text_y; };

在多重继承中,标准并未要求在内存中多个父类之间的顺序。一种可能的内存布局如下:

绘图1

从上图可以看出,此时CircleWithText中将存在两个虚表指针,分别从两条继承线路中继承而来。也就是说,此时CircleWithText类将包含两张虚表,一张中存放由Circle带来的虚函数,一张存放由Text带来的虚函数。假如CircleWithText自己还有新的虚函数,则可以择一存放。

与单继承相比,多重继承除了内存布局的复杂程度增加了之外,在几种情况下运行时的指针运算同样非常重要:

  • 指针的类型转换
  • 通过子类调用由第二个父类(内存中靠后的父类)继承而来的虚函数
  • 通过指向第二个父类(内存中靠后的父类)的指针调用被子类覆盖的虚函数

让我们逐一观察这几种情况。

1. 指针类型转换

CircleWithText cwt;  
Circle *pCircle = &cwt;  
Point *pPoint = &cwt; 

Text *pText = &cwt;  
//pText = (Text*)((char*)&cwt + sizeof(Circle));

对于前两条赋值语句来说,不需要额外的计算,因为在CircleWithText对象中,Circle部分和Point部分的起始地址与cwt一样。而如果要转换为第二个父类的指针,则需要一定的计算。在计算中应当对NULL进行判断,如果需要转换的指针是空指针的话,转换后的指针也应该为空指针。

2. 通过子类调用由第二个父类(内存中靠后的父类)继承而来的虚函数

CircleWithText cwt;  
CircleWithText *pcwt = &cwt;  
pcwt->OuputText();  

上述代码中,使用了子类指针pcwt调用了由Text父类继承而来的虚函数OutputText。由于我们需要传入this指针,这个指针不应当传入pcwt,而是pcwt中Text部分的起始地址。可是很可惜,这只是一种情况;我们无法在编译期确定究竟需要传入哪个this,因为很有可能存在第三种情况:

 3. 通过指向第二个父类(内存中靠后的父类)的指针调用被子类覆盖的虚函数

class CircleWithText : public Circle, public Text  
{ 
public:  
 virtual void OutputText(); 
}; 

CircleWithText cwt;  
Text *pText = &cwt;  
pText->OutputText();  

我们首先需要注意这一段代码与上段代码的不同。这段代码中CircleWithText覆盖了Text中的OutputText函数。此时在pText->OutputText()这一调用中,传入的应为cwt的起始地址。

关键的问题终于出现了:第一:如何确定应当传入哪一个this指针?第二,假设已经确定应当传入CircleWithText的起始地址,那么如何从pText指针重新找到CircleWithText的起始地址呢?在编译期,我们无法知晓这些问题,就如我们不知道下面代码中p的真实类型是什么:

void some_func(Text* p) { p->OutputText(); }  

因此,我们只能通过一定的运行时机制来解决这个问题。下面介绍两种可以解决这一问题的方法。

方案一:在虚函数表中同时存储函数地址和this指针的偏移

示例图如下:

mb_vftable

此时在虚表中同时存储函数地址和所需的this指针偏移(注意,是偏移而不是地址)。因为this指针的“地址”是跟每个对象相关的,而每一个类只有一张vtable。不过偏移却是对于一个类的所有对象都适用的(比如,在一个CircleWithText对象中,想把Text部分的起始地址转换为CircleWithText对象的起始地址所需的偏移是一定的)。这种方法的弊端在于增加了单继承时虚表的成本。

方案二:为函数添加thunk入口

mb_thunk

这种方法不改变虚表的结构,而是将原本指向成员函数的指针改为指向一段由编译器自动生成的thunk代码的地址。在这一小段代码中,对指针进行调整,然后再跳转到真正的函数中去。

2.5 虚拟继承

虚拟继承所要解决的问题时在继承树中同一个父类出现多次的情况。有时我们仅需要一个基类,这就需要虚拟继承来解决:

class Drawable { public: virtual void Draw(); };  
class Point : virtual public Drawable;  
class Text : virtual public Drawable;  

图片1

实现虚拟继承的难度在于,如何将两个Drawable对象变为一个,同时要解决指针计算的相关问题。下面介绍几种方案:

方案一:虚基类指针

在虚拟继承的子类中,额外存储一个指针用于指向直接虚继承的父类:

绘图2

然而这一方案的问题在于,如果有多层的虚拟继承,其间接访问的时间成本也将增加。如果存在多个虚继承父类,则需要多个指针。

方案二:对象的虚基类指针表

对于方案一的一种改进是将这些指针都存放在一张表里,通过一个指针来访问:

vbtable

这一方案解决了方案一中的问题。然而正如之前所说,“地址”是与对象相关的,如果采用了方案二,就是说每一个CircleWithText对象都需要两张虚基类的指针table。

方案三:在虚函数表的负索引处存放偏移

为了解决方案二中的弊端,可以考虑使用偏移,这样的话就不必为每一个对象都生成几个虚基类表了。同时,鉴于虚函数表的负索引还没有被利用,我们可以在这里存放虚基类的偏移。

vb_vftable

3. 运行时环境


3.1 运行时类型识别

在虚函数表的第0项中,并不存储函数指针,而是运行时类型信息type_info。dynamic_cast和typeid是与运行时类型相关的操作。

一个典型的type_info 类可能定义如下:

图片2

3.2 异常

对于如下代码,我们如何判断应当析构哪些对象?

图片3

一种方法是根据程序计数器PC,然而这可能与特定平台相关。另一种方案是使用一个标识变量step,在每一个对象构建或析构之后将step加1。同时存放一张表,用于查询当step为n时应当析构哪些对象。

2.3 C++与动态链接库

对于某一种C++编译器编译产生的动态链接库,将很难其与其他编译器一同使用。原因在于C++标准并没有规定在二进制上的实现方式,编译器在名称改编、成员布局以及异常等机制上均存在着差异。不过,使用抽象类可以一定程度上解决这个问题,详情可以参考一些面向对象系统的实现,例如COM。

感知器算法

这是我之前在实验室的机器学习讨论会上的分享。


Table of Contents

  • 人脑的启示
  • 感知器算法
  • 双层感知器
  • 反向传播算法
  • 应用

人脑的启示


人的神经是由一个个神经元组成的,包括树突、轴突、胞体等。

Picture1

人脑具有以下特征:

  • 超过100亿个神经元
  • 神经元响应时间:约1毫秒
  • 人脸识别:约0.1secs
  • 平均每个神经元与1000个神经元相连
  • 计算高度并行

人脑擅长于模式识别、联想,并可以容忍噪声;电脑则擅长于计算,罗辑清晰。人脑的操作速度很慢,并且运算的结果不可靠,但其可以大规模地并行计算;而电脑的运算速度相当快,并且结果非常可靠。

模拟神经元的结构和工作方式,是感知器算法的主要机制。例如,刺激程度决定了这个神经元的兴奋程度,并且与其他神经元连接紧密时,信号强度大;连接疏松时,信号强度弱。

感知器算法


感知器算法的原理非常简单:

感知器算法

首先对输入信号的求和,当超过阈值时即使感知器兴奋。算法描述如下(from A Course in Machine Learning):

感知器算法

从算法描述可以看出,学习的意义在于向正确的结果靠拢。两组同样的数据,第一次分错了,第二次将会更加接近正确结果。

MaxIter是需要人工指定的参数,如果MaxItger 过大,容易发生过拟合;过小则容易学不到什么东西 。

同时,整个学习的过程就是在一个平面上寻找判别边界。为了简化问题,假设有一个线性可分问题,b=0,则感知器算法即在寻找分界面B:

snapshot7

B就是虚线,而由wd组成的向量w垂直于B:

snapshot8

由此也可以得出,w的绝对大小并不重要。

感知器算法的特点有:

  1. 在线学习,不需要一次性考虑整个数据集

  2. 错误驱动,当分类正确时,不进行学习操作

  3. 对训练集的输入顺序敏感。例如,有10000条训练数据,前9000条数据在默认的参数上就分类正确,则此次迭代只有最后1000条数据得到了训练。因此,不断地调整训练数据的顺序将有助于加快训练速度:

Picture4

朴素的感知器算法仍然存在一定的缺陷,例如后训练的数据会更加重要。参考上面举得例子,如果有10000条训练数据,前100条数据已经训练出足够好的分类器,一直到最后一条之前全部分类正确。最后一条数据就会掉了一个在99.9%的数据上工作得都非常好的分类器。

从以上的分析也可以看出,单层的感知器算法只能用于解决线性可分的问题。

算法改进

投票感知器算法

投票感知器算法会在训练时记录每一个分类器的存活时间,在最终预测时根据权重进行投票。

Picture5

但是由于需要保存每一个超平面,并且预测时需要使用每一个分类器进行预测,时空开销将非常大。

平均感知器算法

平均感知器算法仅记录加权平均后的分类器:

Picture6

除此之外,还有像信任权感知器、被动主动感知器、权表决感知器等。信任权感知器通过对输入添加信任权重的概率分布,使得信任度大的输入会得到更大幅度的修正;被动主动感知器可以主动修正学习速率;权表决感知器会为每一维输入产生一个分类器,最终由虽有分类器结果汇总投票产生,并对错误的分类器予以惩罚。

双层感知器


 snapshot9

在双层感知器中,将有两层感知器需要训练。除此之外,在单层感知器中,我们使用的是线性函数来计算感知器是否被激活;这种用于判断感知器是否激活的函数叫做激活函数(link function)。双层感知器中,隐含层通常采用非线性的sigmoid(tanh)函数来作激活函数。

对于双层感知器来说,它可以模拟任意连续函数;隐含层节点越多,函数越复杂。如果隐含层层数再增加,则可以模拟任意函数。

反向传播算法


对于感知器计算输出的过程来说,相当于正向传播;而通过计算结果反馈给隐含层和输出层来调整参数,则属于反向传播。例如:

Picture1

我们可以通过输出结果与标准值的误差,来修正向量v和矩阵w。常用的方法是梯度下降法,目标函数为结果误差的几何均值。通过对目标函数f求w和v的偏导,就可以求出v和w的梯度。

目标函数:

Picture5

计算结果:

Picture3

Picture4

总结


优势

  • 数学基础 如果有线性解则可以找到(单层)
  • 可以容忍噪声
  • 可以处理任意连续/非连续函数(多层)
  • 可以学到复杂的输入输出映射关系

劣势

  • 知识表示不易解释
  • 依赖于hidden层激励函数
  • 输入输出的设计对结果具有影响
  • 参数较多(神经元数目、层数、学习速率等)
  • 可能需要使用者的经验
  • 训练时间长
  • 过拟合

Jump Out of C++:面向对象编程探索(一)

这是今年3月29号在IBM俱乐部做的技术分享的文字整理版。


 ppt_cover

这次的系列分享叫做“Jump out of C++:面向对象编程探索”,标题可以分为两部分:一个是关于C++的,一部分是关于面向对象编程的。其实我本来并没有想将太多关于C++的东西,才起名叫“Out of C++”,不过大家一致希望听一些,就把它单独拿出来分享一次。面向对象编程探索的“探索”两个字,其实也有两方面的含义。一个是面向对象编程的发展,另一个就是我自己对它的探索了。

整个讲座大概分为三个部分:第一部分主要介绍C++,以及C++ 11新引进的一些特性。其实C++在语法方面并没有太多想要说的,大家已经都已经很熟悉了;只是有一些不是那么常见、但还比较有用的东西,跟大家分享一下。介绍过了这个之后,我们可以有从两方面继续进行探索:一方面是更加具体:C++的一些运行时机制是如何实现的?另一方面是更加抽象:面向对象编程语言有哪些共同的特性?可以将它们分类吗?这两个方面将分别在第二部分和第三部分中介绍。

Table of Content


  1.  C++是如何诞生的?
  2. 面向过程:C语言兼容性与扩展
  3. 面向对象
  4. 模板与泛型编程
  5. C++ 11 新特性 

1. C++ 是如何诞生的?


  • 具有Simula那样的对程序组织的支持
  • 运行得像BCPL一样快
  • 高度可移植的实现

—— Bjarne Stroustrup

B.Stroustrup在《C++语言的设计和演化》一书中曾提到,上面这三点是他在创造C++时希望这一门语言所拥有的特点。这三点也指导了他整个语言的设计过程。

他是在读博士的时候产生了对C语言进行改进的想法的。他希望编写一个模拟程序,模拟分布式程序的执行。最初使用了Simula进行编写,编写的过程很愉快;可是运行时却不尽人意。Simula的优点在于可以使用类对数据和方法进行管理,同时还支持协程,可以很好地进行并发运算;可是缺点也很明显:编译效率低、运行效率也很低。B.S分析后认为,Simula的垃圾收集机制、运行时类型检查、变量初始化检查是拖慢运行时效率的罪魁祸首之三。

随后他用BCPL语言重新编写了模拟器,运行效率极佳;然而编写的过程却极为痛苦:没有类型检查,运行时的支持也几近为零。

这使他下定决心:如果没有好用的工具,是不会进行下一步工作的。

为什么是C?

C语言有着这些优点:灵活、高效、常用、可移植。灵活高效不必多说,常用是指当时几乎每一台机器上都有较为成熟的C语言编译器和运行环境;可移植更是正中B.S的初衷之一。

然而,C语言也同样有着一些缺点,比如安全性的缺失、以及古怪的声明语法。

比如:

int* v[10];

int (*p)[10];

typedef int DtoI(double);

typedef DtoI *V10[10];

V10* f(char);

我们无法按照正常的习惯从左到右读下去,复杂的声明要借助typedef才能获得一定的可读性。

他曾设想一种新的声明方式,类似如下这种:

v: [10]->int;

p: ->[10];

int f(char)->[10]->(double)->;

可惜的是,貌似是他最开始的时候忘记了;而后又已经无法将其加入语言当中了。

2. 面向过程:C语言兼容性与扩展


隐含的int类型

在C语言中,如果不加类型进行声明,默认即为int。比如

f();

static a;

void f(const T);

由于C++支持了模版机制,对于第三种声明来讲,将对编译器造成极大困惑:T是一种类型,还是类型为const int的变量?

最终废除隐含的int类型终于进入了C++标准。而为了这一结果,花费了整整十年的时间。在最初C++对C语言改革的最大阻力,不是来自B.S,不是来自开发者,不是来自标准委员会,而是C语言的用户。

结构标志与类型名

struct S a;

S a;

在C语言中,只有第一种变量声明是合法的;C++中第二种同样合法。这使得用户自定义类型的地位有所提高。

然而,事情并不是这么简单:

struct

对于C语言来讲,struct S中的符号S与int S中的符号S并不在一个名称空间中;而对于C++来讲,只有一个全局名称空间。这也就意味着,在遇到S时,C++会产生冲突:究竟是类型名还是变量名呢?

最终的选择是当冲突发生时,默认为变量名。原因在于当时有相当多的程序是有着上面左图那样的写法的,而最关键的在于Unix头文件中同样有很多类似的写法。兼容性的需求最终取胜。

全局变量的初始化

在C语言中,全局变量的初始化只能用稍微扩展一点的常量表达式来进行。这使得编译器可以在编译期求值,即不需要在运行时动态初始化。而C++则不同,如果要支持用户自定义类型的全局变量,则动态初始化是不可避免的。也因此支持了内置类型变量的动态初始化。

double p = 10.0 / 3;  //ok in C

double q = sqrt(10.0); //error in C, ok in C++ (Cfront >= 2.0)

class Double;

Double d = sqrt(10.0); //ok in C++

声明语句

支持了任意位置声明,以及在if/for中的声明语句。

其他不兼容的情况

  • 全局名称局部于文件,除非显式引出
  • 默认进行静态类型检查,除非显式抑制
  • 一个类代表一个作用域

在C语言中,void f();表示的是函数f可以接受任意参数。对于调用f(1, 2, 3);来说,C语言中是合法的。同样还有一些隐式类型转换,在C++中都有了更加严格的限制。

同时,在C语言中,结构体对内部的结构体并不起到对作用域的限制:

struct outer{

    struct inner{

        int a;

    };

};

struct inner in = {1};

C++修改了这一特性。

3. 面向对象


说到面向对象,大概就这几个方面:封装、继承、多态、抽象。我们从继承中的多重继承开始说起。

多重继承

多重继承是在Cfront release 2.0引入的。原因大概有这么几点:一个是能够使得设计进一步的推进,而且并不需要太多的扩充即可实现。当然,还有一点“主观因素”:一些人认为实现多重继承比实现参数化类型(即C++模板)更难,甚至有人在自己的书中谈到想要给C++添加多重继承是不可能的。B.S当时也是年少方刚正值气盛,当然要做来给他们看看了。他在之前很早就开始构想了多重继承的实现方式,并且已经想到了一个很好的实现。

对于多重继承,有一些人尚有争论。比如用处不大、增加负担、机制太弱、增加代码复杂程度……

但B.S的态度是:它(实现、运行起来)很便宜,又能解决关键问题,何乐而不为呢?

多重继承带来的典型问题是菱形继承问题。

菱形继承问题

对于多重继承来说,如果父类们有着相同的基类,那么在子类中将有祖父类的多份拷贝。有些时候这并不合理,我们希望子类中只有一个祖父类。C++引入了虚基类来解决这个问题:

虚基类

 事实上,继承也是一种封装:当我们使用父类时,它将子类的信息进行了隐藏。

多态

C++中,多态是利用虚函数实现的。想要表现出多态的效果,需要使用父类的指针或引用。

同时,dynamic_cast动态类型转换也必须对在具有虚函数的类型使用。这是因为他所依赖的运行时类型信息(RunTime Type Information, RTTI)是保存在虚表中的。

抽象类

带有纯虚函数的类叫做抽象类。纯虚函数允许没有函数实体,抽象类不能实例化。

抽象类的作用:

  1. 避免了无意义的对象产生

  2. 抽象类可以用来做界面(接口)

在很多语言中,接口是有单独的关键字来表示的,比如interface之类。C++中,抽象类就可以充当接口的作用:只提供使用方式,而将实现细节完全隐藏。

这样做的好处在于能够使得接口与实现相互分离,用户不需要清楚实现,更不需要显式地依赖具体实现。这也限制了修改后重新编译的范围,降低了耦合度。

4. 模板与泛型编程


 C++的模板支持模板参数的自动推断,以及非类型的参数。比如

template<int b, class T>  
T add(T a) {  
    return a + b;
}
int a = add(1); //a == 3  

同时,C++的模板并没有对类型进行显式限制的功能,例如必须继承自某个类,或是必须有那些方法才可以。C++模板对类型的限制是在使用上,比如 T a; a.print(); 如果类型T没有print方法,则在编译器会报错。

有时候我们需要对模板进行特化。即定义一个特定类型参数的版本,以处理一些特殊的情况。例如

template <class T>  
bool equal(T a, T b) {  
    return a == b;
}

template <>  
bool equal(const char* a, const char*b) {  
    return !strcmp(a, b);
}

同时模板还支持偏特化,即部分特化。例如多个类型参数,只特化其中一部分;或将其不完全特化,例如将普适的类型特化为指针类型。

模板元编程

C++的模板是图灵完备的。也就是说,理论上它可以执行任何计算任务。但由于模板是由编译器在编译期进行计算,受到编译器的限制。

模板元编程与函数式编程语言很像:没有可变变量,所有“函数”都没有副作用。例如下面是在编译期计算斐波那契数列:

template <int n>  
struct Fib {  
    enum {
        Result = Fib<n - 1>::Result + Fib<n - 2>::Result
    };
};

template <>  
struct Fib<1> { enum { Result = 1 }; };

template <>  
struct Fib<0> { enum { Result = 0 }; };

int main() {  
    int i = Fib<5>::Result;
    std::cout << i << std::endl;
    return 0;
}

模板在最初设计的时候只是为了参数化容器而设计的,最终能够用来进行元编程是一种“意外”,因此从语法上来说也并不是很舒服。

5. C++ 11 带来了什么?


  • 更优雅的初始化
  • 更优雅的委托
  • 更优雅的RAII
  • 更高的效率
  • 更强大的模板

更优雅的初始化

更优雅的初始化方式包括初始化列表、新增的类成员初始化方式、代理构造函数以及统一的初始化语法等。例如:

class IntArray {  
public:  
    IntArray(int s) : size(s) { ptr = new int[s]; } 
    IntArray() : IntArray(50){}     
    IntArray(std::initializer_list<int> list) : 
    IntArray(list.size()) { //... } 
private:  
    unsigned size = 0; 
    int* ptr = nullptr; 
}; 
IntArray intArray = { 1, 2, 3 };  

 上例中,使用std::initializer_list将可以接受类似数组方式定义的初始化成员值;在第三个接受初始化列表的构造函数中,其调用了第一个只接受整型长度的构造函数;而在类的内部,则可以直接使用赋值语法对成员进行初始化。如果在构造函数的成员初始化列表(冒号之后的列表,不是initializer_list)中没有对相应成员进行初始化,则使用在类中声明的值用作初始化。

同时,C++ 11还统一了初始化的语法。任何类型均可以使用大括号进行成员的初始化,例如:

class Test {  
public:  
    Test(int a, int b){} 
    virtual ~Test(){} 
}; 

int main() {  
    Test t{1, 2}; 
    Test t2 = {1, 2}; 
    int t3 = {1}; 
    int t4{1}; 
}

 上述代码中,四条初始化语句都是正确的。当存在接受initializer_list作为参数的构造函数时,大括号将会被解释为initializer_list(例如之前的IntArray)。

更优雅的委托

什么是委托?

class A {  
public:  
    void p(); 
}; 

class B {  
    A a; 
public:  
    void p(){ a.p(); } 
};

 当B有一件事情,转交给A去做的情况,就叫做委托。事实上,委托也可以用来实现继承;而在C++的早期,B.S也曾经设想过使用委托来实现继承,但最终放弃了这一想法。对于近几年新出炉的Go语言来说,自动委托是用来实现类似于继承思想的一种方式。

对于稍微复杂一点的委托,例如B希望A能够执行一些自己设定的任务(比如回调),则稍稍有些麻烦。在C语言中,函数指针经常用来承担这种任务:

typedef void (*FUNC)();  
class A {  
public:  
    void q(FUNC func) (func();) 
}; 
void f() {/*...*/}  
int main() {  
    A a; 
    A.q(f); 
    return 0; 
}

 然而,上述代码对于类的成员函数则不适用。对于以下三个f函数来说,他们的类型是不同的:

class B {void f();};  
// void B::(*)(); 

class C {void f();};  
// void C::(*)(); 

void f();  
// void (*)();

底层的原因则在于B和C有着一个不同类型的隐含参数:this指针。因此,这三个f函数,只有最后一个能够传给A.q作为委托的任务。

一个典型面向对象解决方案可以统一B和C参数不同的问题。使用一个Listener纯虚类作为接口,类A接受一个Listener作为参数,而B和C均继承自Listener:

class Listener {  
public:  
    virtual void f() = 0; 
}; 

class A {  
public:  
    void q(Listener *listener){listener->f();} 
};

class B : public Listener {  
public:  
    void f(){} 
}; 

class C : public Listener {  
public:  
    void f(){} 
}; 

int main() {  
    A a; 
    B b; 
    C c; 
    a.q(&b);
    a.q(&c); 
    return 0; 
}

 这种方式在Java中非常常见。然而,这种方法使用了面向对象的方式仅仅解决了面向对象那一部分的问题——A仍然无法接受不属于任何类的f()。

 C++ 11新引入了多态函数对象包装器std::function,可以很好地解决这个问题。

class A {  
public:  
    void q(function<void> f){f();} 
}; 

class B {  
public:  
    void Callback() {} 
}; 

void normalFunc(){} 

int main() {  
    A a; 
    B b; 
    a.q(bind(&B::Callback, &b)); 
    a.q(normalFunc); 
    return 0; 
}

实际上,藉由std::function,C++ 11还提供了闭包的功能,并引入了匿名函数来简化语法:

void someFunc(function<void> q){q();}  
int main() {  
    int a = 2, b = 3; 
    auto f = [=]() -> void { //[&a, &b] 
        cout << a + b << endl;
    };
    someFunc(f);
    return 0;
}; 

 更优雅的RAII

RAII(资源获取即初始化)是C++中对于资源管理比较重要的一个概念,最初由B.S在他的The C++ Programming Language中提到。在C语言中,一个常见的资源管理策略是:谁申请,谁释放。“谁”可以指函数,也可以指模块。

谁申请,谁释放

举例来说,例如一个负责字符串编码转换的函数:

bool Charset1ToCharset2( const char* input, unsigned input_size, char* output, unsigned output_size ) {  
    //Convert charset return true; 
}

显然,根据谁申请、谁释放的原则,这个函数不应该在函数内部申请内存,而应当由外部调用者申请好资源后传入。可是调用者如何知道最终转换后的字符串需要多大的空间呢?

因此,将函数修改如下:

bool Charset1ToCharset2( const char* input, unsigned input_size, char* output, unsigned output_size, unsigned* output_needed ) {  
    *output_needed = calc_output_size(); 
    if (output_size < *output_needed)
        return false;

    //Convert charset
    return true;
}

此时在func1中需要调用两次Charset1ToCharset2,第一次用以查询需要多少空间;第二次真正接收字符串编码转换的结果。这种方式在Windows API中也非常常见。

然而,这种方式在有很多分支、很多资源需要申请时,资源释放是一件相当繁琐的事情。尤其在C++支持了异常之后,很有可能会出现资源没有释放,函数就返回的情况。

RAII就是为了解决这一问题而产生的管理方式。它通过对象的生命周期来管理资源,当对象的生命周期结束时,自动释放所持有的资源:

class FileRAII {  
public:  
    FileRAII(const char* n, const char* m) 
    { /*fp = fopen(n, m); */} 

    FileRAII(FILE* p) { fp = p; }

    ~FileRAII() { fclose(fp); } 

    operator FILE*() { return fp; } 
private:  
    FILE* fp; 
}; 

bool func() {  
    FileRAII fp(fopen("1.txt", "r")); 
    if (fp == NULL) 
        return false; 
    //Use fp... 
    return true; 
}

不论func正常退出,或是在使用fp时触发了C++异常而导致异常退出,fp都会被析构,即fclose(fp)都会被执行。

在C++ 11 之前,实现一个通用的RAII类是比较复杂的。然而,当匿名函数和闭包被引入了之后,它变得十分简单:

class ScopeGuard {  
public:  
    ScopeGuard(function<void> on_exit) : _on_exit(on_exit){} 
    ~ScopeGuard() { _on_exit(); } 
    ScopeGuard(const ScopeGuard&) = delete; 
    ScopeGuard & operator=(const ScopeGuard&) = delete; private: 
    function<void> _on_exit; 
}; 

void func5() {  
    FILE* fp = fopen("1.txt", "r"); 
    ScopeGuard s([=] {fclose(fp); }); 
}

 垃圾收集:为什么不支持?

  1.  不适合低层次的工作
  2. 效率
  3. C语言兼容性
  4. 对象布局、创建的限制
  5. 不确定状态

  6. 很多GC算法在运行时要求暂时中断程序的运行。对于很多程序来讲,这可能并不是太大的问题;但是,这将使得C++不再适用于低层次的工作。在当时,C++已经被广泛地用于各种实时系统、嵌入式系统中,他们对这个问题实在是太过敏感。

  7. 时空开销。对于今天的硬件发展来说,这个问题小了很多,但弊端同上一点。如果真的要支持GC,提供一个开关也是比较合理的考虑。

  8. C语言支持一些底层的功能,比如指针运算、联合、强制类型转换等,还有不加检查的数组、不加检查的函数参数等等对于GC算法的设计非常不利的功能。比如,当用户申请了一块堆内存时,如何判断用户已经不再需要这块内存了呢?由于C语言支持指针运算,用户可以轻易地将指针算走之后再算回来。

  9. 垃圾收集同样将导致与其他语言的接口变得复杂。

  10. 用户难以知道某一块内存是否被释放了,它的状态是不确定的。

更高的效率

C++ 11中引入了右值引用、move语义和常量表达式来实现效率的提升。

“值”是指无法被进一步求值的表达式。对于“值”来说,通常我们分为左值和右值。一开始,左值被定义为“赋值号左面的值”,右值相反。可是,这种定义明显不再适用于C++。C++ 11中,明确定义了3种值类型:

左值:可以取地址的值

临终值:生命期即将结束,但其值尚未被取走。例如返回右值引用的函数的返回值,或是强制转换后的右值。

纯右值:不具有标志,可以移动。

广义的左值是指左值+临终值,他们可以表现多态;广义的右值指纯右值+临终值,他们不能被取地址。

在C++ 11之前,“引用”可以引用左值,“常量引用”可以引用左值+右值,然而缺乏一种方式只能引用右值。例如,在C++ 11之前,当一个函数返回一个对象时,将会有临时对象被创建。此时临时对象的构造将会增加程序运行的成本。

class IntArray  
{
public:  
    IntArray(int s) : size(s)
    {
        ptr = new int[s];
        cout << "constructor" << endl;
    }
    IntArray(const IntArray& a)
    {
        delete[] ptr;
        size = a.size();
        ptr = new int[size];
        memcpy(ptr, a.ptr, sizeof(int) * size);
        cout << "copy constructor" << endl;
    }

    IntArray& operator=(const IntArray& a)
    {
        //......
        cout << "assgin operator" << endl;
        return *this;
    }
private:  
    unsigned size = 0;
    int* ptr = nullptr;
};

在VS中的测试结果是:未优化版本将有一次构造、一次拷贝和一次赋值;优化版本将有一次构造和一次赋值。Move语义在这里就派上了用场,它与Copy不同之处在于:

Move语义Copy语义 

当Object1对象是右值时,通过Move方式得到资源将会省去一次拷贝的过程。反正Object1也即将被释放,倒不如把资源送给Object2。

class IntArray  
{
public:  
    IntArray(const IntArray&& a)
    {
        delete[] ptr;
        size = a.size();
        ptr = a.ptr;
        a.ptr = nullptr;
        cout << "move constructor" << endl;
    }

    IntArray& operator=(const IntArray&& a)
    {
        //......
        cout << "move assign operator" << endl;
        return *this;
    }
};

constexpr关键字代表了新的常量表达式,它将在编译期被求值。例如:

constexpr int GetValue() {  
    return 5;
} 

int main() {  
    int a[GetValue() + 1];
    return 0; 
}

`
 在constexpr出现之前,这是不能编译通过的。带有constexpr修饰的语句将会在编译期被求值,如果无法求值的话将会出现编译错误。

常量表达式可以替代部分宏函数的功能,比如

enum Flags { good=0, fail=1, bad=2, eof=4 }; 

constexpr int operator|(Flags f1, Flags f2) {  
    return Flags(int(f1)|int(f2)); 
} 

void f(Flags x) {  
    switch (x) { 
    case bad: break; 
    case eof: break; 
    case bad|eof: break; 
    default: break; 
    } 
}

还有一些情况,是曾经无法支持的。例如,对于一个字符串常量来说,它其中的每一个字符也应当可以在编译器求值。但在constexpr出现之前,我们必须在运行时计算地址,然后取值;现在则不同:

constexpr char* str = "Hello World";  
int main() {  
    constexpr char a = str[1]; 
    cout << a << endl;
    return 0;
}

a将在编译期被取值。同样,我们也可以在编译期求值很多东西,它可以替代一部分模板的功能:

constexpr int exp(int a, int b) {  
    return (b == 0) ? 1 : a * exp(a, b - 1); 
} 
constexpr int a = exp(2, 10);  

 一个函数能否在编译期被求值是有要求的,例如不能有循环语句等。

更强大的模板

C++ 11 加强了模板的功能:模板不定参数、完美转发、编译期Assert、模板别名、返回类型后置(用来进行类型推导)等。

其他常见C++ 11特性

  • Range-based for
  • 强类型枚举
  • 新字符串字面值
  • thread
  • long long int
  • STL:tuple/unordered_map/regex/….

C语言中模拟/GS编译选项实现栈溢出检测

这其实是我在大二的时候给微软俱乐部捉虫大赛出的题目之一。代码基本上是写好了的,故意留出了一些bug,只可惜没人尝试来做。

关于/GS编译选项

VS在某一个版本之后添加了/GS编译选项,增强了对溢出检测的能力。随后对Windows XP进行了全面的重新编译,发布了SP2,安全性大大提高。

/GS的原理其实比较简单:

  1. 程序开始时,在堆的某个位置初始化一个security cookie。cookie的位置是不固定的。
  2. 存放cookie地址的指针大概在PEB之后的某个位置,地址也不固定,但是有一定的范围。对于这一点的记忆有点模糊了,手头也没有当时看的资料,网上也没搜到……确切查到了如果不对再来更新。
  3. 构建栈帧时,在所有的局部变量之前压入一个security cookie的副本。
  4. 函数返回时,检查栈中的security cookie副本与全局的security cookie是否一致,如果不一致则判定为栈溢出,执行相应的动作。

这些步骤之中很多自然需要由编译器来做,不过我们同样可以在源代码的层面模拟此类动作。当然,实际应用的价值也许并不大。

 在C语言中模拟/GS编译选项

下面的模拟与VS的/GS编译选项稍有不同。我们在栈中并不保存security cookie,而是保存cookie与当前栈帧中的ebp(即上一个栈帧的栈底)的异或值。由于当前ebp寄存器中保存的是当前栈帧栈底的地址,因此需要间访一次。在函数退出的时候,检查异或值即可。

采用这种机制的原因是,我们没有办法保证security cookie在所有临时变量之下,因此只好变通一下,跟ebp取个异或。

代码中对return做了define,因此所有函数的返回都必须以return的形式显示返回。没想到C语言里面怎么实现ScopeGuard,只能在return上下手了。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <string.h> 
/*
* A SIMPLE Security Cookie Example
* To Examine the Stack Overflow
*/
#define DEFALUT_SECURITY_COOKIE 0xE8CFF7E8 
int __security_cookie = DEFALUT_SECURITY_COOKIE;  
int __assistant_flag = 0;  
int cookie = 0, *ebp = 0;  
void __security_init_cookie()  
{
    __security_cookie ^= time(NULL);
}
void __security_check_fail()  
{
    printf("Stack Overflow!!n");
    exit(0);
}
#define __mainStartup (main) 
#define main() _main(int argc, char** argv) 
#define ENABLE_SECURITY_CHECK \
int cookie, *ebp, __assistant_flag;   \
__asm__("movl %%ebp, %0;":"=g"(ebp));   \
cookie = __security_cookie ^ *ebp;   \
__assistant_flag = 1; 

#define return if(__assistant_flag){ \
__asm__(" movl %%ebp, %0;":"=g"(ebp));   \
if((cookie ^ (*ebp)) != __security_cookie)   \
__security_check_fail(); }   \
return 

/**
* =======================================
* DO NOT CHANGE THE CODE FROM HERE
*/
int main();  
int __mainStartup(int argc, char** argv)  
{
    __security_init_cookie();
    return _main(argc, argv);
}
/* End of Security Cookie Example */

/* ---------------------------------------------
* User Code Begin
* Now Let's See How to Use Our Security Check
* Functions with ENABLE_SECURITY_CHECK MUST use return-statement to return
* DO NOT CHANGE THE CODE
*/
int main()  
{
    char s[5];
    ENABLE_SECURITY_CHECK
    strcpy(s, "Welcome to 5th Debug Contest!n");
    /* What a Stupid Overflow Example */
    return 0;
}

`

上面的代码中main和mainStartup的宏定义只是为了替换掉入口函数。

在不希望使用栈溢出检测的函数中,不添加ENABLE_SECURITY_CHECK即可。为了保证能够正常编译运行,定义了三个同样名称的全局变量。

不足之处

上面的代码如果在溢出时恰好将__assistant_flag设置为0了,也可以绕过后面的检测。这是不足之一;

security cookie的地址固定,不足之二;

重新定义了return,因此所有函数返回的地方需要显示return,不足之三。