双向链表的三种实现

这篇文章，其实很像是“茴字的四种写法”。这让人不由的想起来孔乙己。在我印象中，大多数人对孔乙己是持嘲讽态度的。 但是从技术上讲，我觉得”茴字的四种写法”在满足需求的前提下，有助于我们简化实现。 在我的历史经验中，我一共写过三种双向链表。 在最开始实现时，就是按算法导论最朴素的实现。 //算法1 struct node { struct node *prev; struct node *next; } struct node *head = NULL; void insert(struct node *n) { n->prev……

一次关于Cache的性能分析

Lua5.4-alpha-rc2 已经发布了好一段时间了, 一直没时间去跑跑看性能如何。最近刚好有空，就跑来看看。结果第一段测试代码就把我惊住了。 --a.lua collectgarbage("stop") local function foo() local a = 3 for i = 1, 64 * 1024 * 1024 do a = i end print(a) end foo() 在 Lua5.3.4 和 Lua5.4-alpha-rc2 上,这段代码运行时间分为0.55，0.42s。 通过`./luac -p -l ./lua ` 可以得知，上段这代码性能热点一定是OP_MOVE,和OP_FORLOOP。因此一定是这两个opco……

从CPU层面谈谈优化

大多数时间，大家都在从设计和算法上优化效率（这类优化往往效果比较明显，比如一个二分查找可以轻易将时间复杂度降低为lg(n))。但是在实现上，却很少有人注重实现效率，而理由是反正每年都会有更高频率的CPU出现，我何必花那个心思呢（Java程序员尤其擅长使用这个理由@_@)。 我个人不是完全同意上面的说辞，在不影响代码的可读性和花费不高的代价下，我习惯性的会写最我当前所知道的性能最高的写法。 在很早以前，我一度只有在编写汇编时才可以计算出汇编条数。随着代码量的增加，……

一次性能优化经历

自从上次修改backlog之后, Silly的IO能力，就一直以少量（约4~6K)的差距落后于redis，却一直找不到原因。 这次打算从头做一次profile来问题到底出在哪。 先用GNU提供的gprof分析一下C代码是否有值得优化的地方，结果发现CPU使用率最高的地方是luaVM内部和malloc/free。 我们所有的业务逻辑全在lua层做的，而IO线程与worker(lua)线程进行交互时是通过malloc来实现的。这几乎表明C代码几乎已经没有优化的余地了。 但是有个好消息，就是gprof不去profile系统调用和so，也许还有机会。 ……

关于CPU分支预测

由于很偶然的原因，这两天瞄了几眼”ZeroMQ”项目，发现项目中使用了’likely/unlikely’这种暗示编译器做分支预测优化的宏（这些宏只是gcc内建函数__builtin_expect的别名)。 其实早在看linux kernel源码时，就不止一次看到这组宏。但是，对此并没有放在心上。仅仅粗略搜了一下，得知‘likely/unlikely这组宏可以向编译器提供分支预测信息，以便编译器可以更好的安排指令顺序来提高效率’就没有再深入下去了。 因为我觉得，这种级别的优化估计能提高个千分之几就……

使用缓存优化数据请求

继上一篇场景之后，事情还没有完。 我有一堆struct obj对象（数量级可能为千级), 客户端需要频繁拉取这些信息中的一部分去显示（比如，当切换标签页时）。 由于这一操作可能会很频繁，而struct obj对象并不算小，如果每一次都重新拉取全部数据，有点让人不舒服，而且对流量也是一种很大的浪费。因此就琢磨着怎么去优化整个过程，以使在此过程中使数据传输量最小。 第一反应，肯定就是对整个列表加一个version字段，每当有obj对象改变时，version加1，当客户端进行拉取时，拿着他本地……

c语言部分的开销测试

最近在写c代码时底气越来越弱，原因在于某些调用的开销，我心里并不是十分明确。写起代码来由于纠结也就变的畏畏缩缩。 今天终于抽时间测了一下，仅测试了最近常遇到的一些调用的开销。 测试环境如下： CentOS release 6.7（Final） CPU：Intel（R）Xeon（R）CPU E3-1230 V2 @ 3.30GHz 采用gcc（glibc）编译，未开任何优化。 在测试时，大部分操作cache均会命中，因此如果cache经常命中失效，还需要另外考虑。 测试结果如下： 可以看出for循环是最廉价的。 malloc是开销最大的，这……

cache命中率对效率的影响

趁着去买菜的空档, 突然间想起来cache命中率失败的代价从来还没测过, 随后又想到网上很多人争论如果两个for循环嵌套, 到底是大循环放在外面效率高还是小循环放在外面效率高. 虽然有大牛说不同情况不同分析, 但到底为什么却没有分析. 于是就for循环与cache命中率写了一段测试代码访问1G的数据来测了一下性能, 竟然有1倍之多. 代码如下: #include <Windows.h> #include "assist.h" //cache line 64 byte //cache size 4Mbyte typedef unsigned char cache_line_t[64]; cache_li……

CheckSum计算的优化

　　最近在纠结于大数据的checksum的计算，算法如下： 1 unsigned long cs_cal(const unsigned char *buff, unsigned long size) 2 { 3 unsigned long cs; 4 5 cs = 0; 6 while (size--) 7 cs += buff[size]; 8 9 return cs; 10 } 　　当文件大于4G后这种计算的龟速就很明显了，在网上看到大牛说MMX指令对于数据计算相当不俗，于是改成下面代码（bug:不对齐部分没有处理，这部分消耗很小,对于效率影响不大）： 1 unsigned long cs_cal(const……

32位系统使用文件作为媒介来模拟大于4G内存访问

代码一篇，暂时没发现bug: 1 // vm_mgr.cpp : Defines the exported functions for the DLL application. 2 // 3 4 #include "stdafx.h" 5 6 #include <Windows.h> 7 #include <vector> 8 #include <assert.h> 9 #include <tchar.h> 10 #include "../common/assist.h" 11 #include"../error_no/error_no.h" 12 #include "../Log/log.h" 13 #include "vm_mgr.h" 14 15 #define VM_ADDR_GEN(addr, index) (assert……