写出形似QML的C++代码

最开始想出的标题是《Declarative C++ GUI库》,但太标题党了。只写了两行代码,连Demo都算不上,怎么能叫库呢……后来想换掉“库”这个字,但始终找不到合适词来替换。最后还是起了个low一点的名字,贱名好养活啊!

这篇文章的目的是介绍如何用C++写出带有Declarative风格的代码。有一些GUI库需要额外的预处理过程(比如qt),还有一些也支持XML格式的GUI声明,但需要运行时Parse那个XML(比如wxWidgets)。能不能只用一个C++编译器、不要运行时Parse新语言来搞定这个问题?

直观地看上去,QML语法跟C++好像还有几分像,就选择QML进行借(chao)鉴(xi)吧。
最终的代码放在了 https://github.com/dontpanic92/yz ,代码与文章一同食用味道更佳。

Continue reading “写出形似QML的C++代码”

编辑器背后的数据结构

大约刚上大二的时候,想做一个编辑器控件。不是一个用Scintilla套上外壳的编辑器,而是一个能被套上外壳的控件。当然它最后也成为了我众多流产了的练手项目中的一员,不过人人黑历史里还留存着当时的一张截图

那段时间也对编辑器所使用的数据结构非常感兴趣。我们需要一种数据结构,能够支持字符串高效地索引、遍历、插入和删除。当时找的一些论文和书还躺在硬盘里一直没删,如今拿出来再嚼一嚼。下面介绍几种在编辑器中常见的数据结构。

Continue reading “编辑器背后的数据结构”

贝叶斯分类器

这是3月25日我在TM组机器学习讨论会上的分享。

Content


  1. 贝叶斯决策论
  2. 朴素贝叶斯分类器
  3. 半朴素贝叶斯分类器
  4. 贝叶斯网络

1. 贝叶斯决策论


贝叶斯决策论是一种基于概率的决策理论。当所有相关的概率都已知的理想情况下,贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。

Example

哈工大与哈师大的同学举办大型联♂谊♀会,两个学校分别有500人参与。在联谊会上随机找到一个同学,请猜测他是那个学校的学生?

如果我们一点额外信息都不知道的话,只能随机猜测给出答案。如果我们能够提前知道一点点信息的话,就能够更大程度地猜中正确答案。比如,性别信息:

 

如此的话,假若这个同学是男生,我们肯定会猜测他是哈工大的学生。而从贝叶斯决策论的角度来看,我们需要比较以下两个概率大小:

  • P(工大学生=是 | 性别 = X)
  • P(师大学生=是 | 性别 = X)

上述两个概率被称作后验概率。后验概率往往难以直接获得,我们需要采用一定的手段进行计算。一些算法采用直接对后验概率进行建模的方法,例如SVM、决策树等,这些模型称为判别式模型。而先对联合概率进行建模、进而计算后验概率的模型,称为生成式模型

\(P(c|\boldsymbol{x})=\frac{P(\boldsymbol{x}, c)}{P(\boldsymbol{x})}=\frac{P(c)P(\boldsymbol{x}|c)}{P(\boldsymbol{x})}\)

由此可以计算得到,P(工大学生=是 | 性别 = 男)为4/5,P(师大学生=是 | 性别 = 男)为1/5.

在上面的例子中,我们直接使用了后验概率对类别进行估计。实际问题中,如果将某一类估计错误的代价比较大的话,可以选择在后验概率前乘以一个系数,变为期望损失。分类也从最小化分类错误率变为最小化期望损失。

在上面的式子中,\(P(c)\)代表的是类先验概率。在样本足够大的情况下,直接使用频率即可作为这一概率;\(P(\boldsymbol{x}|c)\)叫做类条件概率,它跟属性x的联合概率有关。上面的例子中,x只有一维,而在实际问题中,往往会选择很多个Feature。此时他们的联合概率就变得难以计算,因此我们需要一些手段对它们进行估计。

Continue reading “贝叶斯分类器”

Goodbye WordPress

花了点时间把博客从Wordpress换到了Ghost上。一是觉得Wordpress有点慢,TTFB(Time To First Byte)常年在1s左右,状态不好能到几秒十几秒。换到Ghost之后,基本稳定在400毫秒。要是把服务器换回旧金山应该还会更好一点。二是我基本上就用Markdown随便写一写,有高亮有公式就够了,Ghost后台也足够简洁,自己把Prism.js代码高亮和MathJax公式加上就好。

不过迁移的时候,导出插件把我的代码全都弄乱了……还需要人工调教,甚至每段代码中<<之后的代码全部丢失!!如果你也打算从Wordpress导出Ghost格式的数据,一定要记得备份代码!

再就是基本找不到称心的主题,还是先用默认的Casper吧,加了个封面之后感觉倒是好了很多。

站在镜像源背后的男人

@雨翌 说想知道镜像源是如何工作的,我们就来说一说这个。其实要做一个镜像源,需要搞定的有两件事:一是如何向广大用户提供下载服务,一条httpd start就搞定了;二是如何与上游同步,然而这种东西也一条rsync就搞定了:joy:

关于rsync

rsync提供了一种快速的文件同步的机制。一般的diff算法需要分别遍历两个文件,然而这种功能并不适用于远程传输:如果我能够同时获得需要同步的两个文件,再diff他们就没什么意义了。rsync使用的算法并不是特别复杂,可以Google The rsync algorithm 搜到Andrew Tridgell在1996年的论文,man rsync可以得到使用说明。

Continue reading “站在镜像源背后的男人”

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