分类 编程技术 中的文章

网络程序计时器通常用啥实现?

通常来讲,就是利用 select 的空余时间,来进行时钟检查,不管是 select / poll / epoll/ kevent,以下统称 select,它有一个等待时间作为参数,即没有事件时,最多 wait 多少时间,我们把这个作为网络库的基准频率,比如 10MS,或者 20MS, 25MS, 50MS,都是常用的几个值。

就是说网络库调用 select 等待事件时如果没有事件,那么最长等待 10MS 就返回了,这时再处理完所有网络事件后,就可以来处理时钟数据了。事件处理函数就是这样:

def update_events(milisec = 10):  
	result = selector.select(milisec)  
	for fd, event in result:  
		do something with socket event  
	current = time.time()  
	update_timer(current)

while 1:  
	WAIT_MILLISEC = 10  
	update_events(WAIT_MILLISEC)

关键就是这个两次 select 中间 update_timer 的任务:集合中检查需要唤醒的时钟,并且调用它们的回调函数,来驱动整个服务器的时钟运行,以最简单的扫描法为例:

def update_timer (current):  
	for timer in available_timers:  
	while current >= timer.expires:  
		timer.callback(current)  
		timer.expires += timer.period
……

阅读全文

C++的反思

最近两年 C++又有很多人出来追捧,并且追捧者充满了各种优越感,似乎不写 C++你就一辈子是低端程序员了,面对这种现象,要不要出来适时的黑一下 C++呢?呵呵呵。 咱们要有点娱乐精神,关于 C++的笑话数都数不清: 笑话:C++是一门不吉祥的语言,据说波音公司之前用ADA为飞机硬件编程,一直用的好好的,后来招聘了一伙大学生,学生们说我靠还在用这么落后的语言,然后换成C++重构后飞机就坠毁了。 笑话:什么是C++程序员呢?就是本来10行写得完的程序,他非要用30行来完成,并自称“封装”,但每每到第二个项目的时候却将80%打破重写,并美其名曰 “重构”。 笑话:C容易擦枪走火打到自己的脚,用C++虽然不容易,但一旦走火,就会把你整条腿给炸飞了。 笑话:同时学习两年 Java的程序员在一起讨论的是面向对象和设计模式,而同时学习两年 C++的程序员,在一起讨论的是 template和各种语言规范到底怎么回事情。 笑话:教别人学 C++的人都挣大钱了,而很多真正用 C++的人,都死的很惨。 笑话:C++有太多地方可以让一个人表现自己“很聪明”,所以使用C++越久的人,约觉得自己“很聪明”结果步入陷阱都不知道,掉坑里了还觉得估计是自己没学好 C++。 笑话:好多写了十多年 C++程序的人,至今说不清楚 C++到底有多少规范,至今仍然时不时的落入某些坑中。 笑话:很多认为 C++方便跨平台的人,实际编写跨平台代码时,都会发现自己难找到两个支持相同标准的 C++编译器。 -————– Q:那 C++为什么还能看到那么多粉丝呢? A:其实是因为 Windows,因为 Windows的兴起带动了 C++,C++本来就是一门只适合开发 GUI的语言。 Q:为何 C++只适合开发 GUI呢? A:你看 Unix下没有 GUI,为啥清一色的 C呀?所有的系统级问题都能在 C里找到成熟的解决方案,应用级问题都能用其他高级语言很好地解决,哪里有 C++什么事情呀? Q:你强词夺理,Unix下也有 C++的项目呀。 A:有,没错,你任然可以用任何语言编写任何糟糕的代码。 Q:别瞎扯了,你都在说些什么?连C++和 Windows 都扯到一起去了。 A:回想下当年的情景,一个大牛在教一群初学者如何编程。一边开发一边指着屏幕上说,你看,这是一个 Button,我们可以用一个对象来描述它,那是一个 panel我们也可以用一个对象来描述它,并且你们有没有发现,其实 Button和 Panel是有血缘关系的,你们看。。。这样就出来了。。。。下面的学生以前都是学着学校落后的教材,有些甚至还在用 turboc的 bgi库来画一些点和圆。哪里见过这么这么华丽的 Windows 界面呀。大牛说的话,象金科玉律一样的铭刻在自己幼小的心理。一边学着 Windows,一边发现,果然,他们都需要一个基类,果然,他们是兄弟关系,共同包含一些基本属性,可以放到基类去。他们越用越爽,潜意识里觉得因为 C++这么顺利的帮他们解决那么多界面问题,那看来 C++可以帮他们解决一切问题了。于是开发完界面以后,他们继续开发,当他们碰到各种设计问题时,反而认为肯定自己没有用好 C++。于是强迫自己用下去,然后就完蛋了。 (点击 more展开) -————– 关于 C++的笑话我有一箩筐,各位 C++粉用不着对号入座。言归正传,为什么要黑 C++呢?谈不上黑不黑,我从94年开始使用 C++(先前是 C 和 Pascal),一路看着 C++成长壮大,用 C++写过的代码,加起来应该超过 10MB了吧,C++的各种宝典我也都读过,一直到 2004年开始切回 C,主要原因是发现很多没法用 C++思路继续解决下去的问题,或者说用 C++思路解决下去会很糟糕的问题。 那时候(2004-2005)正是 C++满天飞的时候,言必称 C++,用必用模版,我跳出来说你们醒醒吧,别过火了,这个世界并不是都是抽象数据结构和算法就可以描述清楚的。于是很多人激动的跳出来说:“你没领会到 C++精髓,你根本都不会用 C++”。我问他们:“语言是用来解决问题的,如果一个语言学了三四年都会经常掉沟里,算好语言么?如果编写十多年 C++的程序员都很难掌握得了,这算好语言么”。他们又说:“语言是死的,人是活的”。 我记得当时一位国内 C++大牛,为了纠正我的 “错误观点”,给我看过他写的一套十分强大的库,我打开一看,倒吸了一口冷气,全部是 .h文件。我只能回他三个字:“你牛逼”。当然这是一个极端的例子,那家伙后来终于也开始把 .h里面的东西逐步挪到 .cpp里面了,这是好事。 当时和云风在一家公司,2004年新人培训时,他给新人布置了一个实现内存分配器的作业,批改作业的时候,他经常边看边问人家,“不够C++呀,你能不能百分之百OOP?”,“1%的 C都不要留”。我当时在公司内部邮件列表里面发过关于 C++的问题,大部分人都表示:“你看没有C++我们怎么写3D引擎呢?”。我跟他们讲:“John Carmack直到 Quake3都还在用着 ANSI C,后来因为不得不支持 D3D,改用 C++了。为啥 C不能写 3D引擎了?”。他们告诉我:“你看,Point,就是个对象,Matrix也是个对象,那么多 Vector的代数计算,用 C++的算术重载是多么美妙的事情,三维世界就是对象的世界。”。 确实当时客户端 GUI的话,只有 C++,图形引擎也只有 C++,这两个正是C++最强的地方,所以我也没和他们争辩,强迫他们承认 C也可以很漂亮的写图形,而且C写的可以写的很优雅。我又不是闲着没事情,何必去质疑人家的核心价值观呢,呵呵。当年我正在接手一个 C++项目,代码超过 800KB,每次崩溃都需要花费很长时间去定位,项目中大量的前后依赖,改一个地方,前后要看好几处,一处遗漏,整个系统就傻逼了。我开始重构后,画了两个星期,将性能敏感的核心部分剥离出来用 C实现(代码量仅 200KB),然后导出 Python接口,用Python来完成剩下的部分,整个脚本层代码量只有 150KB。整个世界清爽了,整个 C++项目原来的工期为 2个程序员四个月,我一个人重构的时间加起来就 1.5个月,而且代码量比远来少了两倍还多,各种奇特的 BUG也一扫而尽。我看看左边的 800KB一团乱麻的 C++代码,再看看右边整洁的 300多 KB 纯 C + Python,琢磨着,这个项目干嘛不一开始就这么做? 跨语言接口 现代项目开发,不但需要更高的性能,而且需要更强大的语言描述能力。而 C++正处在一个尴尬的地方,比底层,它不如 C能够精确的控制内存和硬件,各种隐式构造让你防不胜防;比描述能力,比快速业务开发和错误定位,它又赶不上 Python, Ruby, Lua等动态语言,处于东线和西线同时遭受挤压和蚕食的地步。 很快,2006-2007年左右,其他项目组各种滥用 C++的问题开始显现出来:当时脚本化已经在工程实践中获得极大的成功,然而某些项目一方面又要追求 100%的 C++,另一方面又需要对脚本导出接口,他们发现问题了,不知道该怎么把大量的 C++基础库和接口导给 Lua。 C的接口有各种方便的方式导给脚本,然而整个项目由一群从来就不消于使用脚本的cpp大牛开发出来,当他们要吧cpp类导出接口给脚本时,他们设计了一套牛逼的系统,lua自动生成机器码,去调用c++的各种类,没错,就是c++版本的cffi或者ctypes。他为调用vc的类写了一套机器码生产,又为调用gcc的类写了一套代码生成。那位cpp大牛写完后四处炫耀他的成果,后来他离职了,项目上线一而再再而三的出现无 可查证的问题,后来云风去支援那个项目组,这套盘根错节的c++项目,这套盘大的代码自生成系统深深的把他给恶心到了。后来众所周知云风开始反C++,倡导回归C了,不知道是否和这个项目有关系。 于是发现个有趣的现象,但凡善于使用脚本来提高工程效率的人,基本都是C加动态语言解决大部分问题(除了gui和图形),但凡认为c++统治宇宙的人很多都是从来没使用过脚本或者用了还不知道该怎样去用的人。 凭借这样的方法,我们的产品同竞争对手比拼时,同样一个功能,同样的人力配置,竞争对手用纯C++要开发三月,我们一个月就弄出来了,同样的时间,对手只能试错一次,我们可以试错三次。后来,据我们招聘过来的同事说,竞争对手也开始逐步降低 C++的比例,增加 java的比例了,这是好事,大家都在进步嘛。 ABI的尴尬 ABI级别的 C++接口从来没有标准化过,以类为接口会引入很多隐藏问题,比如内存问题,一个类在一个库里面实例化的,如果再另外一个库里面释放它们就有很多问题,因为两个动态库可能内存管理系统是不一样的。你用这里的 allocator分配一块内存,又用那里的 allocator去释放,不出问题才怪。很多解决方法是加一个 Release 方法(比如 DX),告诉外面的人,用完的时候不要去 delete,而是要调用 Release。 项目写大了各个模块隔离成动态库是很正常的,而各种第三方库和自己写的库为追求高性能引入特定的内存管理机制也是很正常的。很多人不注意该调用release的地方错写成delete就掉沟里去了。更有胜者跨 ABI定义了很多inline方法的类,结果各种隐式构造和析构其实在这个库里生成,那个库里被析构,乱成一团乱麻。C就清晰很多,构造你就调用fopen,析构你就fclose,没有任何歧义。其实C++的矛盾在于一方面承认作为系统级语言内存管理应该交给用户决定,一方面自己却又定义很多不受用户控制的内存操作行为。所以跨 ABI层的c++标准迟迟无法被定义出来,不是因为多态 abi复杂,而是因为语言逻辑出现了相互矛盾。为了弥补这个矛盾,C++引入了operator new,delete,这new/delete重载是一个补丁并没从逻辑上让语言变得完备,它的出现,进一步将使用者拖入bug的深渊。 其实今天我们回过头去看这个问题,能发现两个基本原则:跨abi的级别上引入不可控的内存机制从语言上是有问题的,只能要靠开发者约定各种灵巧的基类和约定开发规范来解决,这个问题在语言层是解决不了的;其次你既然定义了各种隐式构造和析构,就该像java或者动态语言一样彻底接管内存,不允许用户再自定义任何内存管理方法,而不是一方面作为系统极语言要给用户控制的自由,一方面自己又要抢着和用户一起控制。 因此对象层 ABI接口迟迟无法标准化。而纯 C的 ABI不但可以轻松的跨动态库还能轻松的和汇编及各类语言融合,不是因为C设计多好,而是C作为系统层语言没有去管它不该管的东西。当年讨论到这个话题时 C++大牛们又开始重复那几句金科玉律来反驳我:“语言只是招式,你把内功练好,就能做到无招胜有招,拿起草来都可以当剑使,C++虽然有很多坑,你把设计做好不那么用不就行了”。我说:本来应该在语言层解决好的事情 ,由于语言逻辑不完备,将大量问题抛给开发者去解决极大的增加了开发者的思维负担,就像破屋上表浆糊一样。你金庸看多了吧,武术再高,当你拿到一把枪发现子弹不一定往前射,偶尔还会往后射时,请问你是该专心打敌人呢?还是时刻要提防自己的子弹射向自己? 系统层的挫败 C++遭受挫败是进军嵌入式和操作系统这样靠近硬件层的东西。大家觉得宇宙级别的编程语言,自然能够胜任一切任务,很快发现几个问题: 无法分配内存:原来用 C可以完全不依赖内存分配,代码写几千行一个 malloc没有都行。嵌入式下处理器加电后,跳到特定地址(比如起始地址0),第一条指令一般用汇编来写,固定在0地址,就是简单初始化一下栈,然后跳转到 C语言的 start函数去,试想此时内存分配机制都还没有建立,你定义了两个类,怎么构造呀?资源有限的微处理器上大部分时候就是使用一块静态内存进行操作。C++写起来写爽了,各种隐式构造一出现,就傻了。 标准库依赖:在语言层面,C语言的所有特性都可以不用依赖任何库就运行,这为编写系统层和跨平台跨语言代码带来了很方便的特性。而C++就不行,我要构造呀,我要异常呀,你为啥不能给我强大的运行时呢?什么你还想用 stl?不看看那套库有多臃肿呀(内存占用,代码尺寸)。 异常处理问题:底层开发需要严格的处理所有错误返回,这一行调用,下一行就判断错误。而异常是一种松散的错误处理方式,应用层这么写没问题,系统层这么写就很狼狈了。每行调用都try一下和 C的调用后if判断结果有什么区别?C++的构造函数是没有返回值的,如果构造内部出错,就必须逼迫你catch构造函数的异常,即便你catch住了,构造异常的时候当然会自动触发相关内部对象的析构,但是有很多并没有析构的资源(比如系统资源,比如C接口的资源,他们都没有一个析构),整个过程是很难控制的,此时这个实例是一个半初始化实例,你该怎么处理它呢?于是有人把初始化代码移除构造函数,构造时只初始化一下变量,新增加一个带返回的init函数,这样的代码写的比C冗余很多。何况硬件中断发生时,在你不知道的情况下,同事调到一些第三方的库,你最外层没有把新的exception给 catch住,这个exception该往哪里抛呀?内存不够的时候你想抛出一个 OutOfMemoryException,可是内存已经不够了,此时完全无能力构造这个异常又该怎么办呢? 处理器兼容:C++的类依赖基地址+偏移地址的寻址方式,很多非 Intel系列的微处理器上只有简单的给定地址寻址,不支持这样一条语句实现BASE+OFFSET的寻址,很多C++代码编译出来需要更多的指令来运算地址,导致性能下降很多,得不偿失。 隐式操作问题:C的特点是简单直接,每行语句你都能清楚的知道会被翻译成什么样子,系统会严格按照你的代码去执行。而用C++,比如 str1 = str2 + “Hello” + str3; 这样的语句,没几个人真的说得清楚究竟有多少次构造和拷贝,这样的写法编写底层代码是很不负责任的,底层需要更为精细和严格的控制,用C语言控制力更强。 当然,说道这里很多人又说,“C++本来就是 C的超集,特定的地方你完全可以按照C的写法来做呀。没人强迫你构造类或者使用异常呀”,没错,按 Linus的说法:“想要用 C++写出系统级的优秀的可移植和高效的代码,最终还是会限于使用 C本身提供的功能,而这些功能 C都已经完美提供了,所以系统层使用 C的意义就在于在语言层排除 C++的其他特性的干扰”。……

阅读全文

如何实现移动设备的通用手势识别?

移动设备多用手势进行输入,用户通过手指在屏幕上画出一个特定符号,计算机识别出来后给予响应的反应,要比让用户点击繁琐的按钮为直接和有趣,而如果为每种手势编写一段识别代码的话是件得不偿失的事情。如何设计一种通用的手势识别算法来完成上面的事情呢? 我们可以模仿笔记识别方法,实现一个简单的笔画识别模块,流程如下:

第一步:手势归一化

1. 手指按下时开始记录轨迹点,每划过一个新的点就记录到手势描述数组guesture中,直到手指离开屏幕。 2. 将gesture数组里每个点的x,y坐标最大值与最小值求出中上下左右的边缘,求出该手势路径点的覆盖面积。 3. 手势坐标归一化:以手势中心点为原点,将gesture里顶点归一化到 -1<=x<=1, -1<=y<=1空间中。 4. 数组长度归一化:将手势路径按照长度均匀划分成32段,用共32个新顶点替换guestue里的老顶点。

第二步:手势相似度

1. 手势点乘:

g1 * g2 = g1.x1*g2.x1 + g1.y1*g2.y1 + … + g1.x32*g2.x32 + g1.y32*g2.y32 

2. 手势相似:

相似度(g1, g2) = g1 * g2 / sqrt(g1 * g1 + g2 * g2)

由此我们可以根据两个手势的相似度算成一个分数score。用户输入了一个手势g,我们回合手势样本中的所有样本g1-gn打一次相似度分数,然后求出相似度最大的那个样本gm并且该分数大于某个特定阀值(比如0.8),即可以判断用户输入g相似于手势样本 gm !

……

阅读全文

快速可靠协议-KCP

简介

KCP是一个快速可靠协议,能以比 TCP浪费10%-20%的带宽的代价,换取平均延迟降低 30%-40%,且最大延迟降低三倍的传输效果。纯算法实现,并不负责底层协议(如UDP)的收发,需要使用者自己定义下层数据包的发送方式,以 callback的方式提供给 KCP。 连时钟都需要外部传递进来,内部不会有任何一次系统调用。

整个协议只有 ikcp.h, ikcp.c两个源文件,可以方便的集成到用户自己的协议栈中。也许你实现了一个P2P,或者某个基于 UDP的协议,而缺乏一套完善的ARQ可靠协议实现,那么简单的拷贝这两个文件到现有项目中,稍微编写两行代码,即可使用。

技术特性

TCP是为流量设计的(每秒内可以传输多少KB的数据),讲究的是充分利用带宽。而 KCP是为流速设计的(单个数据包从一端发送到一端需要多少时间),以10%-20%带宽浪费的代价换取了比 TCP快30%-40%的传输速度。TCP信道是一条流速很慢,但每秒流量很大的大运河,而KCP是水流湍急的小激流。KCP有正常模式和快速模式两种,通过以下策略达到提高流速的结果:

RTO翻倍vs不翻倍:

TCP超时计算是RTOx2,这样连续丢三次包就变成RTOx8了,十分恐怖,而KCP启动快速模式后不x2,只是x1.5(实验证明1.5这个值相对比较好),提高了传输速度。

选择性重传 vs 全部重传:

TCP丢包时会全部重传从丢的那个包开始以后的数据,KCP是选择性重传,只重传真正丢失的数据包。

快速重传:

发送端发送了1,2,3,4,5几个包,然后收到远端的ACK: 1, 3, 4, 5,当收到ACK3时,KCP知道2被跳过1次,收到ACK4时,知道2被跳过了2次,此时可以认为2号丢失,不用等超时,直接重传2号包,大大改善了丢包时的传输速度。

延迟ACK vs 非延迟ACK:

TCP为了充分利用带宽,延迟发送ACK(NODELAY都没用),这样超时计算会算出较大 RTT时间,延长了丢包时的判断过程。KCP的ACK是否延迟发送可以调节。

UNA vs ACK+UNA:

ARQ模型响应有两种,UNA(此编号前所有包已收到,如TCP)和ACK(该编号包已收到),光用UNA将导致全部重传,光用ACK则丢失成本太高,以往协议都是二选其一,而 KCP协议中,除去单独的 ACK包外,所有包都有UNA信息。

非退让流控:

KCP正常模式同TCP一样使用公平退让法则,即发送窗口大小由:发送缓存大小、接收端剩余接收缓存大小、丢包退让及慢启动这四要素决定。但传送及时性要求很高的小数据时,可选择通过配置跳过后两步,仅用前两项来控制发送频率。以牺牲部分公平性及带宽利用率之代价,换取了开着BT都能流畅传输的效果。

基本使用

……

阅读全文

【原创】快速除以255的方法

经过若干次试验修改,研究出下面这个快速/255的宏,可以在 X属于[0,65536]的范围内误差为零:

#define div_255_fast(x)    (((x) + (((x) + 257) >> 8)) >> 8)

传统来说,人们习惯于将 /255改为 >> 8,但是这样误差挺大的,比如先乘以255再除以255,连续做十次,如果用>>8来代替除法,那么十次之后,误差为10. 另外一种常见的近似法是((x) + 255) >> 8,这种累积误差也挺厉害的。 因此>>8代替/255结果是比较粗糙的。而这个宏的开销比起>>8来说成本大12%。 经过测试65536000次计算中,使用/255的时间是325ms, 使用div_255_fast的时间是70ms,使用>>8的时间是62ms,div_255_fast的时间代价属于可以接受的范围。 下面是测试程序

……

阅读全文

内存拷贝优化(1)-小内存拷贝优化

相信大家代码里有很多地方用到memcpy这个函数,相信这个函数的占用是不小的,有时优化了memcpy,能使整个项目的运行效率提升。通过适当的编码技巧,让我们的内存拷贝速度超过memcpy两倍,是可以实现的。 有人说memcpy还能优化么?不就是rep movsd么?CPU和内存之间的带宽是固定的,怎么可能优化呢?其实是普通的内存拷贝并没有发挥全部的带宽,很多被浪费掉了,比如要等到数据完全读取成功后再去写入,然后要写入成功后再去读取新的。而优化本身就是使这两者尽量的并行,发挥最大的带宽。

现代的内存拷贝都需要判断内存大小,并按照大小选择不同策略进行拷贝,比如大内存拷贝(超过cache大小),那么最好使用并行若干读取指令和写入指令,然后再并行写入,使得CPU前后结果依赖得以大大降低,并且使用缓冲预取,再CPU处理数据之前,就把数据放到离CPU最近的CACHE。这样已经可以比memcpy快很多了,如果再加上一些新指令的帮助,大内存拷贝会大大提速。

但是用同样的代码去拷贝小内存,因为额外的开销,难对齐的内存,准备工作一大堆,如果实际要拷贝的内存很小的话,这样的工作开销还比直接按照 dword复制慢很多。在VC10的memcpy实现中将内存按照128个字节大小进行区分,小于该大小的使用普通拷贝,大于该大小的使用普通SSE指令拷贝,而现在我们就要来挑战VC10的memcpy,本篇先叙述小内存拷贝部分。

适合拷贝64字节以内的数据量。原理很简单,LOOP UNROLL。rep movsb/movsd是靠不住的,小内存拷贝还是得展开循环。

废话不多说,代码贴上:

……

阅读全文