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

从上一篇《PYTHON操作EXCEL》可以看到,Python 操作 Excel 已非常自如方便。但是 Python 和相关库毕竟是一个额外的依赖,若能从 Excel 自身解决此类问题,自然是更为易用。

1. VBA 中的哈希表

用 Python 的着眼点主要是 VLOOKUP 公式太慢了,所以关键是要找到一种更高效的算法或数据结构定位数据。VLOOKUP 要求对列进行排序,内部应该是对列内数据进行二分查找,算法上不好再优化了,那就只好更换一种数据结构。搜索了一下,VBA 提供了 Scripting.Dictionary 这一词典结构,而且有文章说内部是哈希表实现,那就正是我要的东西了。

这样,VLOOKUP(lookup_value,table_array,col_index_num,range_lookup) 这一公式就转为下面的词典查找方式来实现:

  • 使用要从中进行查找的 table_array 内容构建词典。用 table_array 第一列作为 key,table_array 第 col_index_num 列作为 value,插入 Dictionary 中:Dictionary.Add key, value;
  • 查找时只需直接取 Dictionary 内的值 Dictionary.Item(lookup_value),即可完成查找;

若是仅仅 VLOOKUP 一次,倒也不必费劲先建立起一个词典。但当使用同样 VLOOKUP 公式的单元格很多时(比如几万个),就显得其必要了。因为 Dictionary 只需要建立一次,就可以用 O(1) 的复杂度进行多次查找了。

2. VLOOKUP 慢,主要问题不在算法上

从算法角度,词典查找的确快于二分查找,但优势并不是那么明显。所以在具体执行时,我发现使用词典查找的 VBA 宏运行速度并不比 VLOOKUP 快多少,运行时 Excel 仍然会导致系统假死几个小时。按说如此简单的程序不应该那么慢,问题究竟在哪里呢?

经过一段摸索,我才发现问题的根源所在:

  • VBA 往 Excel 表格中填内容时,会引发表格中已有公式的自动计算,非常耗时;
  • Excel 表格内容更新时,会触发屏幕显示内容的自动刷新,代价也很高;

所以提高 VBA 脚本执行性能的关键点,在于计算时关掉公式自动计算和屏幕刷新,这也是我始料未及的。在 VBA 中实现这两点很容易,但由于 VLOOKUP 本身即是公式,我没能想通直接调用 VLOOKUP 时如何避免这两点带来的性能损失。

3. 示例 VBA 代码

在做了上面提到的两次优化之后,原来 VLOOKUP N 个小时才能完成的任务,只用了 7 秒钟就执行结束了。

下面是我写的一段示例代码。我不熟悉 VBA 语言,只是照葫芦画瓢。代码规范程度相差甚远,但题意应是体现其中了。有心的朋友可以用作参考。

Sub 在机器表上生成一级分中心()
'
' 在机器表上生成一级分中心 Macro
'
Application.Calculation = xlCalculationManual
Application.ScreenUpdating = False

t0 = Timer
' 词典
Set map_dict = CreateObject("Scripting.Dictionary")

' 打开分中心映射表
Set map_sheet = Worksheets("分中心映射表")
map_nrows = map_sheet.Range("A300").End(xlUp).Row
Set my_rows = map_sheet.Range("A2:B" & map_nrows).Rows

' 遍历分中心映射表,获得 分中心 对应的一级分中心,插入词典
For Each my_row In my_rows
   center = my_row.Cells(1, 1).Value
   city = my_row.Cells(1, 2).Value
   If Not map_dict.Exists(center) Then
       map_dict.Add center, city
   End If
Next my_row

' 打开机器表
Set dispatch_sheet = Worksheets("机器表")
dispatch_nrows = dispatch_sheet.Range("G99999").End(xlUp).Row
Set my_rows = dispatch_sheet.Range("K2:L" & dispatch_nrows).Rows

' 遍历开通表,通过词典获得 machine_id 对应的一级分中心,插入开通表
For Each o_row In my_rows
   center = o_row.Cells(1, 1).Value
   o_row.Cells(1, 2).Value = map_dict.Item(center)
Next o_row

MsgBox "在机器表上生成一级分中心。共处理 " & dispatch_nrows & " 条记录,总耗时" & Timer - t0 & "秒。"

' 销毁建立的词典
Set map_dict = Nothing

' 打开自动计算和屏幕刷新
Application.Calculation = xlCalculationAutomatic
Application.ScreenUpdating = True
'
End Sub

最后补充一点:我先实现的词典查找,后发现性能问题根源,所以未能去比较 VLOOKUP 与词典查找两种方式的具体性能差异。我想如果差异可以忍受,那么直接在 VBA 中调用 VLOOKUP 公式或许是一种更为简单的实现。

Python操作Excel

老婆单位有时候有一些很大的 Excel 统计报表需要处理,其中最恶心的是跨表的 JOIN 查询。他们通常采取的做法是,把多个 Excel 工作簿合成一个工作簿的多个表格,然后再跑函数(VLOOKUP之类)去查。因为用的函数效率很低,在 CPU 打满的情况下还要跑几个小时。

然后我就看不过去了,我也不懂 Excel,不知道如何优化,但我想用 Python+SQLite 总归是能够实现的。于是就尝试了一把,效果还不错,一分钟以内完成统计很轻松,其中大部分时间主要花在读 Excel 内容上。

1. Python 操作 Excel 的函数库

我主要尝试了 3 种读写 Excel 的方法:

1> xlrd, xlwt, xlutils: 这三个库的好处是不需要其它支持,在任何操作系统上都可以使用。xlrd 可以读取 .xls, .xlsx 文件,非常好用;但因为 xlwt 不能直接修改 Excel 文档,必须得复制一份然后另存为其它文件,而且据说写复杂格式的 Excel 文件会出现问题,所以我没有选它来写 Excel 文件。

2> openpyxl: 这个库也是不需要其它支持的,而且据说对 Office 2007 格式支持得更好。遗憾地是,我经过测试,发现它加载 Excel 文件的效率比 xlrd 慢 3 倍以上,内存使用在 10 倍以上,于是就放弃了。

3> win32com: Python Win32 扩展,这个库需要运行环境为 Windows+Office 对应版本。由于 Python Win32 扩展只是把 COM 接口包装了一下,可以视为与 VBA 完全相同,不会有读写格式上的问题。尝试了一下用 win32com 读取 Excel 文件,效率还是比 xlrd 慢一些。

由于读取效率上 xlrd > win32com > openpyxl,所以我自然选择了 xlrd 用来读取统计报表;而最终输出的报表格式较复杂,所以选择了 win32com 直接操作 Excel 文件。

2. Python 里的关系型数据库

SQLite 是一个非常轻量级的关系型数据库,很多语言和平台都内置 SQLite 支持,也是 iOS 和 Android 上的默认数据库。Python 的标准库里也包含了 sqlite3 库,用起来非常方便。

3. 用 xlrd 读取 Excel 并插入数据库样例

如果数据量不大,直接用 Python 内部数据结构如 dict, list 就够了。但如果读取的几张表数据量都较大,增加个将数据插入数据库的预处理过程就有很大好处。一是避免每次调试都要进行耗时较长的 Excel 文件载入过程;二是能充分利用数据库的索引和 SQL 语句强大功能进行快速数据分析。

#!/usr/bin/python
# -*- coding: gbk -*-

import xlrd
import sqlite3

# 打开数据库文件
device_city_db = sqlite3.connect('device_city.db')
cursor = device_city_db.cursor()

# 建表
cursor.execute('DROP TABLE IF EXISTS device_city')
cursor.execute('CREATE TABLE device_city (device_id char(16) PRIMARY KEY, city varchar(16))')
 
# 打开 device 相关输入 Excel 文件
device_workbook = xlrd.open_workbook('输入.xlsx')
device_sheet = device_workbook.sheet_by_name('设备表')

# 逐行读取 device-城市 映射文件,并将指定的列插入数据库
for row in range(1, device_sheet.nrows):
   device_id = device_sheet.cell(row, 6).value
   if len(device_id) > 16:
       device_id = device_id[0:16]
   if len(device_id) == 0:
       continue
   city = device_sheet.cell(row, 10).value
   # 避免插入重复记录
   cursor.execute('SELECT * FROM device_city WHERE device_id=?', (device_id,))
   res = cursor.fetchone()
   if res == None:
       cursor.execute('INSERT INTO device_city (device_id, city) VALUES (?, ?)',
                      (device_id, city))
   else:
       if res[1] != city:
           print '%s, %s, %s, %s' % (device_id, city, res[0], res[1])
device_city_db.commit()

4. 将结果写入 Excel 文件样例

使用 win32com 写入 Excel 的时候要注意,一定要记得退出 Excel,否则下次运行会出错。这需要增加异常处理语句,我这里偷了个懒,出了异常后要手动杀死任务管理器中的 excel 进程。至于 win32com 中类的接口,可以从 MSDN 网站查阅。

import win32com.client as win32
import os
excel = win32.gencache.EnsureDispatch('Excel.Application')
excel.Visible = False
# 貌似这里只能接受全路径
workbook = excel.Workbooks.Open(os.path.join(os.getcwd(), '输出.xlsx'))
month_sheet = workbook.Worksheets(1)
# 计算文件中实际有内容的行数
nrows = month_sheet.Range('A65536').End(win32.constants.xlUp).Row
# 操作 Excel 单元格的值
for row in range(5, nrows-4):
   month_sheet.Cells(row, 1).Value += something
# 保存工作簿
workbook.Save()
# 退出 Excel
excel.Application.Quit()

Python JSON模块解码中文的BUG

很多语言或协议选择使用 ASCII 字符 “\”(backslash,0x5c) 作为字符串的转义符,包括 JSON 中的字符串。一般来说,使用 Python 中的 JSON 模块编码英文,不会存在转义符的问题。但如果使用 JSON 模块编解码中文,就可能面临着中文字符包含转义符带来的 bug。本篇文章给出了一个 badcase。

中文解码错误

测试用例文件里面包含繁体的“運動”二字,使用 GB18030 编码。使用 json 解码的错误如下:

$ cat decode.dat
{"a":"運動"}
$ python
>>> import json
>>> fp=open('decode.dat', 'r')
>>> json.load(fp, encoding='gb18030')
Traceback (most recent call last):
  File "", line 1, in 
  File "/home/yangwb/local/lib/python2.7/json/__init__.py", line 278, in load
    **kw)
  File "/home/yangwb/local/lib/python2.7/json/__init__.py", line 339, in loads
    return cls(encoding=encoding, **kw).decode(s)
  File "/home/yangwb/local/lib/python2.7/json/decoder.py", line 360, in decode
    obj, end = self.raw_decode(s, idx=_w(s, 0).end())
  File "/home/yangwb/local/lib/python2.7/json/decoder.py", line 376, in raw_decode
    obj, end = self.scan_once(s, idx)
UnicodeDecodeError: 'gb18030' codec can't decode byte 0xdf in position 0: incomplete
multibyte sequence

发生这个问题的原因,就存在于“運”字的编码之中。“運”的 GB18030 编码是 0xdf5c,由于第二个字符与转义符 “\” 编码相同,所以剩下的这个 0xdf 就被认为是一个 incomplete multibyte sequence。

我本来认为,既然已经提供了编码,json 模块就能够区分汉字与转义符(所以我觉得这应该是 json 的一个 bug)。但从实验来看,并非如此。对于一些不需提供字符编码的 JSON 解码器来说,我们倒可以用一种比较 tricky 的方法绕过上面这个问题,即在“運”字后面加一个额外的转义符:

{"a":"運\動"}

遗憾的是,这种方法对 Python 的 json 模块不适用。我仍不知道该如何解决这个解码问题。

中文编码——没错误!

对于相同的 case,Python 倒是能够编码成功:

$ cat in.dat
運動
$ python
>>> import json
>>> in_str = open('in.dat', 'r').read()
>>> out_f = open('out.dat', 'w', 0)
>>> dump_str = json.dumps({'a': in_str}, ensure_ascii=False, encoding='gb18030')
>>> out_f.write(dump_str.encode('gb18030'))
$ cat out.dat
{"a": "運動"}

所以这件事情就把我给搞糊涂了,Python 的 json 模块不能解码自己编码的 json 串。所以我觉得这可能是一个 bug,或者至少是 2.7.1 版本的 bug。

PS: 要仔细看文档

20120516:经网友 TreapDB 提醒,加载字符串时自己做 Unicode 转换,貌似能够解决这个问题。

$ cat decode.dat
{"a":"運動"}
$ python
>>> import json
>>> in_str = open('decode.dat', 'r').read().decode('gb18030')
>>> json.loads(in_str)

回头仔细看了一下 json 的文档,其中有这么一段:

Encodings that are not ASCII based (such as UCS-2) are not allowed, and should be wrapped with codecs.getreader(encoding)(fp), or simply decoded to a unicode object and passed to loads().

已经注明了 encoding 不支持非 ASCII-based 编码的参数,所以应该使用 getreader 进行转码,而不是让 json 模块去转码。看来是我没读懂文档,大惊小怪了,回家面壁去!

>>> json.load(codecs.getreader('gb18030')(fp))

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

做后台系统比做客户端软件的辛苦的地方,就是不能让程序轻易地挂掉。因为在生产环境中无法容易地复现或调试 bug,很多时候需要程序日志提供足够的信息,所以一个后台系统的程序员必须要明白该如何打日志(logging)。

很多语言都有自己现成的 logging 库,比如 Python 标准库中的 logging 模块,Apache 的 log4cxx(C++), log4j(Java)。如果你愿意找,很容易能找到基本满足自己需求的日志程序库。当然,自己实现一个也不是很困难。难点不在于写这些库,而是如何去使用它们。

大部分情况下,我们关注的都是日志的级别和内容。即哪些情况下,该打哪个级别的日志,日志语句中,该怎么写。

在程序开发的过程中,我们需要很多的日志协助分析程序问题;但在生产环境中,我们没有那么多的空间存储丰富的日志,而且日志量太大对于问题排查反而是累赘。有些人使用预处理解决这个问题,在 debug 版本和 release 版本中编译进不同的日志语句。这样能够解决一些问题,但却使得在生产环境中无法轻易地打印更多的日志。大部分人更接受的做法是,使用配置(参数)控制日志的打印级别,在需要更多日志的时候,可以随时打开它们。为了实现日志“少但是足够”的目标,开发人员必须明白日志信息的价值,即哪些日志应该属于哪个级别。

日志的作用是提供信息,但不同的日志语句,提供的信息量却是不一样的。有的日志里会写“Failed to get sth..”,但却忘记加上失败调用的返回值。同程序一样,日志语句中有的是变量(某个变量内容),有的是常量(提示信息)。常量你总能从程序源代码中获得,但变量不行。所以在一条日志中,信息量最大的是变量,是函数返回值/字符串内容/错误码,因而变量应该尽量放在靠前的位置。常量也不是一点价值没有,写得好的提示语句,会使问题一目了然,可以免去你到代码中 grep,然后重读代码的麻烦。

上面这两点,几乎所有知道 logging 重要性的同学都会了解。但关于 logging 对性能的影响,很多人没有足够的警惕心。例如有人会在一个按行解析文件的函数中写下这样的日志:

int parseline(...)
{
log_trace("Enter parseline with ...");
DO_SOMETHING;
log_trace("Exit parseline with ...");
return 0;
}

乍一看,由于 log_trace 级别不高,在生产环境中肯定会关闭,那么这样做看起来对性能没太大影响。但实际上 log_trace 可能是这样实现的:

#define log_trace(fmt, arg...) \
    xx_log(LVL_TRACE, "[%s:%d][time:%uus]" fmt, __FILE__, __LINE__,\
           log_getussecond(), ## arg)
#endif

可以看到 log_trace 宏中自动添加了很多信息,值得注意的是时间参数 log_getussecond()。大家都知道统计时间需要系统调用,那么无论 log_getussecond() 函数是如何实现的,它的代价肯定是高于一般的简单函数。

我们本以为 log_trace 在 LVL_TRACE 级别被关闭的情况下,消耗的代价仅仅是一个函数调用和分支判断,却没有发现宏参数中还隐藏着一个需要调用系统调用的函数。当文件不大是还算能够忍受,但当这个文件是一个数据库,扫描每一行都要执行两次 log_trace() 时,它对系统性能的影响就绝不可忽视了。

所以,最佳的做法还是,在性能攸关的代码中,使用可被预处理掉的 logging 语句,仅仅在 debug 发布中才能见到这些日志,release 版本中不把它们编译进来。

此外,上面这个 log_trace,是一个糟糕的设计。logging 模块只应该干 logging 的事情,开发人员需要时间统计时会自己完成。

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

exVim 是一个非常优秀的 Vim 环境,通过它能够省去很多 Vim 插件的配置工作。自从使用上 exVim 后,我基本没有再自定义 Vim 插件,完全依赖 exVim 打包的辅助功能。

最近让我略有不爽的使用问题是:exVim 默认的 file filter 和 dir filter 都是匹配通过的,即“匹配 filter 过滤条件的目录和文件被通过,列入项目目录、文件列表中”。

exVim 的 dir filter

对于文件来说,设置匹配通过毫无问题。因为我也想要项目中仅包含 “.cpp,.c,.h,.py” 这样的源代码文件,选出来匹配这些模式的文件就是我希望的结果。

但是对于目录来说,设置匹配通过就与我通常的需求相悖了。一般情况下,项目目录下的所有目录都是程序需要的。但是一些专门存放测试程序、测试框架、输出文件的目录,我其实不希望显示在我的项目中。而且 exVim 中的目录过滤貌似仅限在项目顶层目录中,过滤的意义不大。

所以我修改了一下 exVim 的代码,将默认的 dir filter 含义修改为匹配拒绝,即:“匹配 dir filter 的目录被拒绝(被过滤掉),无论它在哪一级。"例如,我将 dir filter 设置为 “test,output”,那么我项目目录下所有叫做 test 或者 output 的子目录都不会显示到项目目录列表中,而不妨碍其它名称目录的通过。

可以想见两个 filter 采用不同的通过逻辑并不是 exVim 开发者希望看到的,所以我想这个修改也没必要提交给开发者。不过我仍然觉得这是很有用的一个修改,所以拿出来分享一下。修改的补丁文件见:http://share.solrex.org/ibuild/exvim-dir_filter-8.05_b2.patch

PS: patch 文件中还有一个改动是将 quick_gen_project_PROJECT_autogen.sh 文件从项目目录下,移动到项目目录下的 .vimfiles.PROJECT/ 目录中,原因是看起来碍眼 :)

std::sort 的仿函数参数

因为习惯了 qsort 的函数指针参数,以前用 std::sort 的时候一般也是传函数指针而不是仿函数(functor)。从很多示例程序来看,貌似没有什么大的不同。但是直到今天我才醒悟,原来是示例太简单了啊!

具体来说,我今天遇到了一个问题:要对一个表进行排序,每个字段可能是升序,可能是降序,也有不同的类型,所以排序的时候需要根据这些信息进行比较。比较函数不能是类成员函数,但我又的确要用到类成员的信息,函数接口又不能变,着实发愁。愁了就只能 Google,发现原来仿函数可以轻松地搞定这件事情。

// 来自 http://stackoverflow.com/a/1902360
class MyClass{

   // ...
   struct doCompare
   {
       doCompare( const MyClass& info ) : m_info(info) { } // only if you really need the object state
       const MyClass& m_info;

       bool operator()( const int & i1, const int & i2  )
       {
            // comparison code using m_info
       }
   };

    doSort()
    { std::sort( arr, arr+someSize, doCompare(*this) ); }
};

简单点儿说,因为仿函数是个类,也可以有成员变量,构造的时候可以传参进去初始化,这样就能实现更灵活的比较方法。这么简单的道理,为什么之前我就是想不到呢?

此外值得一提的是,std::sort 要求比较的结果是 strict weak order,就是说要严格小于才返回 true。这就意味着,仅仅对比较结果取反,是无法实现逆序的。因为小于的取反不是大于,而是大于等于。

我们有过经验,如果相等的时候也返回 true,可能会导致某些标准库实现的 sort 函数指针越界,导致程序出错。所以要千万避免犯这个错误。

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

在编译 Levedb 时,我遇到了这个错误:

g++ -c -I. -I./include -fno-builtin-memcmp -DLEVELDB_PLATFORM_POSIX -pthread -DOS_LINUX -O2 -DNDEBUG db/version_set.cc -o db/version_set.o
db/version_set.cc: In member function `void leveldb::VersionSet::Builder::Apply(leveldb::VersionEdit*)':
./db/version_edit.h:100: error: `std::vector, std::allocator > > leveldb::VersionEdit::compact_pointers_' is private
db/version_set.cc:461: error: within this context
...

在网上容易搜到解决方案,由于归根结底是访问控制问题,方法是把所有涉及到的的 private 变量或类型修改为 public。由于不是所有的编译器都会报错,我就很好奇产生这个错误的根本原因。

BTW: 一种不修改代码的 work around 方法是,在编译这个文件时加上 -fno-access-control 参数,这样 g++ 就不会进行访问控制检查,自然也就没问题了。这个参数同样可以用于对 private 成员函数进行单元测试。

简单地分析一下这个错误。发生错误的地方是在 VersionSet::Builder 这个类的成员函数中,而错误则是其成员函数无法访问 VersionEdit 和 Version 类的私有成员变量。VersionSet 是 VersionEdit 和 Version 类的友元类,Builder 是 VersionSet 的嵌套类。简化一下,代码如下所示:

class VersionSet;

class VersionEdit {
    friend class VersionSet;
    static int compact_pointers_;
};

class VersionSet {
    class Builder {
        int foo()
        {  
            return VersionEdit::compact_pointers_;
        }  
    }; 
};

把这段代码拿给编译器去编译,g++ 3.4.4/5 会报类似的 `int VersionEdit::compact_pointers_' is private 错误,但是 g++ 4.5.3 则能够编译通过。

由于 VersionSet 是 VersionEdit 的友元类,那么 VersionSet 是能够访问 VersionEdit 私有成员的,这样问题就集中在 Builder 是否能够获得与 VersionEdit 的友元关系。如果语法规定嵌套类 Builder 能够从 VersionSet “获得”友元关系,那么 Builder就能够访问 VersionEdit::compact_pointers_,反之就不能访问。

在 C++98 标准中,关于嵌套类的权限有如下描述:

$11.8/1 [class.access.nest],

The members of a nested class have no special access to members of an enclosing class, nor to classes or functions that have granted friendship to an enclosing class; the usual access rules (clause 11) shall be obeyed. The members of an enclosing class have no special access to members of a nested class; the usual access rules (clause 11) shall be obeyed.

Example:

class E {
    int x;
    class B { };
    class I {
        B b;                 // error: E::B is private
        int y;
        void f(E* p, int i) {
           p->x = i;         // error: E::x is private
        }
   };
   int g(I* p)
   {
       return p->y;          // error: I::y is private
   }
};

但是在 C++11 中,这段描述变更为:

$11.7/1 Nested classes [class.access.nest]

A nested class is a member and as such has the same access rights as any other member. The members of an enclosing class have no special access to members of a nested class; the usual access rules (Clause 11) shall be obeyed.

Example:

class E {
    int x;
    class B { };
    class I {
        B b;                  // OK: E::I can access E::B
        int y;
        void f(E* p, int i) {
            p->x = i;         // OK: E::I can access E::x
        }  
    }; 
    int g(I* p) {
        return p->y;          // error: I::y is private
    }  
};

从上面的描述和示例代码对比中我们可以明显看出,在旧标准中嵌套类和“被嵌套类”没有什么特殊的关系,就像两个普通类一样;但是在新标准中嵌套类已经完全视为“被嵌套类”的成员,那么自然也获得了“被嵌套类”成员应该有的访问控制权限。这也就意味着“被嵌套类”的普通成员拥有的访问“被友元类”私有成员变量的权限,嵌套类也能够获得,那么 Leveldb 在新版本的编译器下能够编译通过也不足为奇了。

不过 gcc3.4 的编译错误问题还不能单单归究于标准的变化。因为 gcc3.4 已经能够支持嵌套类访问“被嵌套类”的私有成员(因为在很早以前这就被确认为一个缺陷),只是不能够支持友元关系到嵌套类的传递。友元关系的传递可能是在 4.1 或者 4.2 版本中实现的,应该属于上述标准变化的衍生特性。