Category Archives: 编程

std::inner_product的简单性能测试

最近团队产品中用到了一些机器学习方面的算法,涉及到求向量内积,采取的是最朴素的实现方式(元素乘积循环相加)。有一天路上想到 STL 提供了一个模板函数 std::inner_product ,就好奇 libstdc++ 实现上是否对该算法做了什么优化呢?

于是做了个简单的实验:1000 维 double 类型向量乘积,用 std::inner_product 和朴素方法分别计算10000次,g++ -O2优化。第一轮使用原生 double 类型数组,第二轮使用 vector<double> 容器,分别在三个机器环境下进行了计算。

// Processors | physical = 2, cores = 32, virtual = 12, hyperthreading = no
//     Speeds | 12x2400.186
//     Models | 12xIntel(R) Xeon(R) CPU E5645 @ 2.40GHz
//     Caches | 12x256 KB
//        GCC | version 3.4.5 20051201 (Red Hat 3.4.5-2)
	   
a*b     : std::inner_product(27.934ms), for loop(40.061ms)
a_v*b_v : std::inner_product(27.878ms), for loop(40.04ms)

// Processors | physical = 2, cores = 12, virtual = 12, hyperthreading = no
//     Speeds | 12x2100.173
//     Models | 12xAMD Opteron(tm) Processor 4170 HE
//     Caches | 12x512 KB
//        GCC | version 3.4.5 20051201 (Red Hat 3.4.5-2)

a*b     : std::inner_product(31.242ms), for loop(47.853ms)
a_v*b_v : std::inner_product(31.301ms), for loop(47.815ms)

// Processors | physical = 1, cores = 0, virtual = 1, hyperthreading = no
//     Speeds | 1x2572.652
//     Models | 1xIntel(R) Core(TM) i5-3320M CPU @ 2.60GHz
//     Caches | 1x6144 KB
//        GCC | version 4.7.2 (Ubuntu/Linaro 4.7.2-2ubuntu1)

a*b     : std::inner_product(41.76ms), for loop(33.165ms)
a_v*b_v : std::inner_product(35.913ms), for loop(32.881ms)

可以看出不同环境下 std::inner_product 的表现不尽相同,与朴素的方式相比有优有劣。瞄了一眼 gcc 4.8 的 libstdc++ 的代码,没有注意到 std::inner_product 对基本类型做什么 SSE 指令的优化。不过倒是有个并行计算的版本,可能对超大的向量计算有帮助。

虽然从性能上没有看到明显的优势,但毕竟 std::inner_product 可以简化一个循环的编码,至少可以少测一个分支嘛。而且配合重载函数的后两个 functor 参数,可以做一些有趣的事情,比如算一组数的平方和,比较两个字符串相同字符的数量等。以后呢可以多尝试一下用标准库的算法而不是自己写循环。

寻找最快的Python字符串插入方式

在 MapReduce 分布式计算时有这样一种场景:mapper 输入来自多个不同的数据源,共同点是每行记录第一列是作为 key 的 id 列,reducer 需要根据数据源的不同,进行相应的处理。由于数据到 reducer 阶段已经无法区分来自什么文件,所以一般采取的方法是 mapper 为数据记录打一个 TAG。为了便于使用,我习惯于把这个 TAG 打到数据的第二列(第一列为 id 列,作为 reduce/join 的 key),所以有这样的 mapper 函数:

def mapper1(line):
    l = line.split('\t', 1)
    return "%s\t%s\t%s" % (l[0], 'TAG', l[1])

这样给定输入:

s = "3001	VALUE"

mapper1(s) 的结果就是:

s = "3001	TAG	VALUE"

这是一个潜意识就想到的很直白的函数,但是我今天忽然脑子转筋,陷入了“这是最快的吗”思维怪圈里。于是我就想,还有什么其它方法呢?哦,格式化的表达式可以用 string 的 + 运算来表示:

def mapper2(line):
    l = line.split('\t', 1)
    return l[0] + '\t' + 'TAG' + '\t' + l[1]

上面是故意将 '\t' 分开写,因为一般 TAG 是以变量方式传入的。还有,都说 join 比 + 快,那么也可以这样:

def mapper3(line):
    l = line.split('\t', 1)
    l.insert(1, 'TAG')
    return '\t'.join(l)

split 可能要消耗额外的空间,那就换 find:

def mapper4(line):
    pos = line.find('\t')
    return "%s\t%s\t%s" % (line[0:pos], 'TAG', line[pos+1:])

变态一点儿,第一个数是整数嘛,换成整型输出:

def mapper5(line):
    pos = line.find('\t')
    pid = long(line[0:pos])
    return "%d\t%s\t%s" % (pid, 'TAG', line[pos+1:])

再换个思路,split 可以换成 partition:

def mapper6(line):
    (h,s,t) = line.partition('\t')
    return "%s\t%s\t%s" % (h, 'TAG', t)

或者干脆 ticky 一点儿,用 replace 替换第一个找到的制表符:

def mapper7(line):
    return line.replace('\t', '\t'+'TAG'+'\t', 1)

哇,看一下,原来可选的方法还真不少,而且我相信这肯定没有列举到所有的方法。看到这里,就这几个有限的算法,你猜一下哪个最快?最快的比最慢的快多少?

先把计时方法贴一下:

for i in range(1,8):
    f = 'mapper%d(s)' % i
    su = "from __main__ import mapper%d,s" % i
    print f, ':', timeit.Timer(f, setup=su).timeit()

下面是答案:

mapper1(s) : 1.32489800453
mapper2(s) : 1.2933549881
mapper3(s) : 1.65229916573
mapper4(s) : 1.22059297562
mapper5(s) : 2.60358095169
mapper6(s) : 0.956777095795
mapper7(s) : 0.726199865341

最后胜出的是 mapper7 (tricky 的 replace 方法),最慢的是 mapper5 (蛋疼的 id 转数字方法),最慢的耗时是最慢的约 3.6 倍。最早想到的 mapper1 方法在 7 种方法中排名——第 5!耗时是最快方法的 1.8 倍。考虑到 mapper 足够简单,这个将近一倍的开销还是有一点点意义的。

最后,欢迎回复给出更快的方法!

那些害人的编码“神谕”

同其它领域一样,计算机科学和工程领域也是群星璀璨,有些耀眼的星光甚至刺得我们无法直视,只能匍匐在地上聆听神谕。也正如其它领域一样,虽然大家听到的是同样的话,却有各式各样不同的理解。我这里想讲的,就是我观察到的不同理解引发的现象。

“过早优化是万恶之源。” 这是 Donald Knuth 的一句名言。虽然大部分人都不知道,或者会忘掉前面半句:“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.” Knuth 说出这句话时,可能想不到这句话会多么地流行,多么根植在很多人心中,以至于成为程序员偷懒的借口,阻碍进步的动力。因为有了这句话,在你指出别人代码中可以优化的问题时,还必须浪费口舌来解释这样的优化是必要的,不是过早优化或者过度优化。

就我的观察而言,对很多程序员来说,其能力还远远达不到过早优化的地步。但他感觉自己受到了 Knuth 的神启,仿佛具有了某种魔力,不优化代码反而成了一种优越感!关于大多数人是否具备过早优化代码的能力,我可以举几个至今我还觉得神奇的例子。

我供职的公司内部有这样一个模块,隔一两个星期总会挂掉几台服务器,现象是内存占满导致服务器假死或者宕机,但事实上根据请求推算根本不会同时使用那么多内存。最后的排查结果发现,每个线程都有这样一个数据结构,它的内存是只增不减的。当你调用它的 clear 接口,它只会把所有的内存还回自己的内存池里,而不是还给系统。这就导致可供分配的内存越来越少、越来越少...

还是这个模块里,仅仅加载一个几 K 的配置文件,就能够占用超过 1G 的内存。为什么呢?因为它用 char str[MAX_CONF_LEN] 保存配置字符串,用 struct xx_t xx[MAX_XX_NUM] 读取配置,而且这个 struct 中还有嵌套的 struct yy_t y[MAX_YY_NUM] 数组。

该模块是个个例吗?还是这家公司,一个全公司使用的公共日志库,LOGGING 宏定义中直接传一个需要系统调用的函数作为参数,导致无论关不关该级别日志都要进行一次系统调用

这家公司好歹也位列国内顶尖的互联网公司之一,工程师的招聘要求也是极其高的,还会普遍出现这种肆意浪费资源的情况。那么我想对于大部分工程师来说,谈避免“过早优化”、“过度优化”,还为时尚早。

还有一句名言“好代码本身就是最好的文档。当你需要添加一个注释时,你应该考虑如何修改代码才能不需要注释。” 这是 Steve McConnell 说的。同样,大部分人都不知道,或者忘掉后面半句:Good code is its own best documentation. As you're about to add a comment, ask yourself, "How can I improve the code so that this comment isn't needed?" Improve the code and then document it to make it even clearer. 如果你是程序员,回想一下多少次跟别人讨论代码是不是必须要注释时,这句话被引用到;有很多次在写代码时喜爱这句话,又多少次改别人的代码时痛恨这句话。

还是从我个人的观察来看,对很多程序员来说,其编码能力还不足以达到“代码本身就是最好的文档”的地步,包括我自己。敝司招聘过很多顶尖的工程师,有传说中的各种杰出前辈,可能在各种学校、公司内部事迹广为流传。但若是你哪天继承了他的代码遗产,就会发现很多传说中的明星跌落凡尘。成百上千行没有注释,使用一个公共库函数时要么接口就根本没注释只能基本靠猜,要么即使注释也语焉不详让你踩到未注明的大坑。每到这个时候你心里总会暗暗骂娘,后面别人再谈到他的光辉事迹时,你跟随讪笑时心中暗自腹诽:“牛逼个锤子!”

但我想很多人争论的焦点是:“注释是不是不可省略的、要强制执行的?”即使个别人能力真能达到“代码本身就是最好的文档”的地步(我还没见过),我也不建议在团队中传播“注释可以省略”这一想法。因为如果你说“注释可以省略”,可能你会发现大家都理解和实践成“终于可以不写注释了”。如果一个刚刚大学毕业、脑袋里从来没有过 documentation 概念、从来没写过注释的新人进入公司,就“终于可以不写注释了”,那么我想他的代码会很难达到“代码本身就是最好的文档”这个级别。因为他根本没有机会懂得什么叫做 documentation。

在公司里,代码注释深远地影响着团队合作的每个人,以及软件生存期里所有的维护者,甚至会影响自己的职业声誉。所以无论别人怎么想,我对注释这个问题的答案始终是:“注释是不可省略的,越完善越好的,甚至强制执行矫枉过正也没关系的!”

用词典查找代替VLOOKUP

从上一篇《PYT … Continue reading

Python操作Excel

老婆单位有时候有 … Continue reading

Python JSON模块解码中文的BUG

很多语言或协议选 … Continue reading

警惕程序日志对性能的影响

做后台系统比做客 … Continue reading

修改exvim目录过滤逻辑为匹配拒绝

exVim 是一 … Continue reading

std::sort 的仿函数参数

因为习惯了 qs … Continue reading

Leveldb 编译错误背后的C++标准变化

在编译 Leve … Continue reading

Page 1 of 812345...Last »