Mar 21
After wasting over 45 minutes on moving database out of the default "/var/lib/mysql" on Ubuntu, I think this crazy problem should be written down, in case someone get confused by the same problem again.

I thought this problem to be very simple: go to /etc/mysql/, edit my.cnf, change the "datadir = /var/lib/mysql" to a new place, say, /home/mysql, and run "service mysql restart". But mysqld just refused to start, it says something like this:
引用
/usr/sbin/mysqld: Can't find file: './mysql/plugin.frm' (errno: 13)
130321 22:48:26 [ERROR] Can't open the mysql.plugin table. Please run mysql_upgrade to create it.
130321 22:48:26 [Note] Server hostname (bind-address): '127.0.0.1'; port: 3306
130321 22:48:26 [Note]  - '127.0.0.1' resolves to '127.0.0.1';
130321 22:48:26 [Note] Server socket created on IP: '127.0.0.1'.
130321 22:48:26 [ERROR] /usr/sbin/mysqld: Can't find file: './mysql/host.frm' (errno: 13)
130321 22:48:26 [ERROR] Fatal error: Can't open and lock privilege tables: Can't find file: './mysql/host.frm' (errno: 13)

I'm very sure I've done chmod/chgrp to "/home/mysql", so it won't be file permission problem. It occurred to me that the original database 'mysql' may contain some path information, since it's a newly installation, so I backed up the mysql directory, tried to run "mysql_install_db --user=mysql --datadir=/home/mysql", and failed again:
引用
$ mysql_install_db --user=mysql --datadir=/home/mysql/
Installing MySQL system tables...
130321 23:18:17 [Warning] Can't create test file /home/mysql/localhost.lower-test
130321 23:18:17 [Warning] Can't create test file /home/mysql/localhost.lower-test

Installation of system tables failed!  Examine the logs in/home/mysql/ for more information.

and two more lines were added to the error.log:
引用
ERROR: 1005  Can't create table 'db' (errno: 13)
130321 23:06:48 [ERROR] Aborting

That was weird. I used bash -x to run mysql_install_db again (it's a bash script) and found out that It started mysqld with some certain parameters which printed the Warning message shown above. So the problem went back to mysqld. A forum thread somewhere also noticed the problem but didn't come up with a solution.

With no choice, I went through the manual of mysql_install_db, and fortunately found a comment at the end of the page:
引用
Ubuntu 9.10
Moving the database from /var/lib/mysql to /data/databases/mysql

You'll get errors when running mysql_install_db until you go into /etc/apparmor.d, update the usr.sbin.mysql file, and run /etc/init.d/apparmor restart

You may also get an error when running /etc/init.d/mysql start:

Access denied for user debian-sys-maint at localhost

Check /etc/mysql/debian.cnf for the account information.

You'll need to run mysql, add the grant tables, and then restart mysql.

As the 'usr.sbin.mysql' requests, I added two lines to the end of "/etc/apparmor.d/local/user.sbin.mysql" and restarted apparmor(/etc/init.d/apparmor restart), thus fixed the problem.
引用
  /home/mysql/ r,
  /home/mysql/** rwk,
Mar 18

模重复平方算法 不指定

felix021 @ 2013-3-18 15:20 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(13311) | Via 本站原创
在RSA算法里头经常要用到“求x的n次方模m”这样的过程,通常使用O(log(n))的模重复平方算法来实现,提高效率。

其实这是大二学的《信息安全数学基础》里面的内容,那时为了考试需要(手算+写出很罗嗦的过程),还专门写了代码放在Blog空间里考试的时候用—……

同样O(log(n))的递归算法其实很容易理解:
/* C */
int square(int x) { return x * x; } /* 这里可不能用宏哟 */
int fast_mod(int x, int n, int m)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        return square(fast_mod(x, n / 2, m)) % m;
    else
        return x * fast_mod(x, n - 1, m) % m;
}

#Python
fast_mod = lambda x, n, m: 1 if n == 0 else fast_mod(x, n / 2, m) ** 2 % m if n % 2 == 0 else x * fast_mod(x, n - 1, m) % m

;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast x n m)
    (define (square x) (* x x))
    (cond ((= n 0) 1)
          ((even? n) (remainder (square (mod-fast x (/ n 2) m)) m))
          (else (remainder (* x (mod-fast x (- n 1) m)) m))))

(mod-fast 79 24 33)
;16

但是SICP要求写一个迭代版的。印象中我是记得可以把 n 写成二进制(比如n=13, 1101),然后一位一位地推。

试推了一下从高位到低位,倒是挺简单的,记B[i]为第 i 位的值,通过A[i] = A[i+1]^2 * x^B[i] 从高到低计算出A[0],就得到结果了。但是问题是,为了从高到低计算,又得一次递归,似乎不能满足要求。

于是只好反过来,从低位往高位推。这个过程其实也挺简单的,举例来说:

当n=13,即二进制的 1101 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0时,最终结果

ans = x^n % m
    = x^(1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0) % m
    = [x^(1 * 2^3)] * [x^(1 * 2^2)] * [(x ^ (0 * 2^1)] * [x ^ (1 * 2^0)] % m

也就是说,从低到高,在第 i 位的时候,将 x^(Bit[i] * 2^i) % m 乘到结果中即可。这里可以稍微变换一下:仅当Bit[i] == 1的时候,将x^(2^i) % m乘进去即可。所以这里可以用一个辅助的变量 b 来保存 x^(2^i) % m,在每次迭代的过程中 b = b^2 % m 。

于是实现就容易了:
/* C */
int fast_mod_iter(int x, int n, int m)
{
    int a = 1, b = x; //i=0的时候b = x^(2^0) = x
    while (n)
    {
        if (n % 2 == 1)
            a = a * b % m;
        b = b * b % m;
        n /= 2;
    }
    return a;
}

#Python
def fast_mod(x, n, m):
    a = 1
    b = x
    while True:
        if n == 0:
            return a
        if n % 2 == 1:
            a = a * b % m
        b = b * b % m
        n /= 2

;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast-iter x n m)
    (define (iter a b n)
        (cond ((= n 0) a)
              ((even? n)
                (iter a (remainder (* b b) m) (/ n 2)))
              (else
                (iter (remainder (* a b) m) (* b b) (/ (- n 1) 2)))))
    (iter 1 x n))

(mod-fast-iter 79 24 33)
;16


//网上搜了下模重复平方算法,居然没有靠谱的算法解释,看来可能还是这个算法太简单了吧。。。
Mar 18

fibonacci 的进化 不指定

felix021 @ 2013-3-18 01:06 [IT » 程序设计] 评论(4) , 引用(0) , 阅读(14505) | Via 本站原创
最近在看SICP,抛弃旧的世界观和方法论压力很大,不过还是很有收获的,比如学习了个O(log(n))的fibonacci算法,大涨姿势啊。

想起前几天看到的某个笔试题,说是用最快的办法计算fibonacci数列的第n项。虽然我知道它是有个通项公式的,但是不适用于精确计算,因此写了个迭代的算法,自以为已经很好了,现在看了真是too simple sometimes naive了。

众所皆知 fibonacci 的定义是f(n) = f(n - 1) + f(n - 2); f(1) = f(2) = 1(从f(1)=1开始算起)
#Python版:
fibonacci = lambda n: 1 if n <= 2 else fibonacci(n - 1) + fibonacci(n - 2)

/* C版 */
int fibonacci(int n) {
    return n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}

;Scheme版
(define (fibonacci n) (if (<= n 2) 1 (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

不幸的是这样树形展开效率太低了,当n=42的时候,C语言需要的时间已经超过1s了。

因此需要改成迭代版,使用 (a, b) <- (a + b, a) 这样的方式。
#Python版
def fibonacci(n):
    a = 1; b = 0;
    for i in range(n):
        a, b = a + b, a
    return b

/* C版 */
int fibonacci(int n) {
    int a = 1, b = 0, c;
    while (n--) {
        c = a;
        a = a + b;
        b = c;
    }
    return b;
}

;Scheme版
(define (fibonacci n)
  (define (iter n a b)
    (if (= n 0) b (iter (- n 1) (+ a b) a)))
  (iter n 1 0))

虽然O(n)的效率已经有显著的提升,但是由于这个数列的增长超过了2^n,所以当对于稍大的n,就需要使用大整数的运算,效率很低。python版的代码,当n=300,000的时候,需要超过1s才能得出结果;Scheme版则需要大约9s。

SICP的练习1-19里面则提到一个O(log(n))的巧妙算法:将计算fibonacci的每次迭代 (a, b) <- (a + b, a) 表示为一个变换T[p=0, q=1],具体表示为(似乎是用矩阵乘法倒推过来的)
引用
T[pq](a, b) = (a(p+q) + bq, aq + bp)


通过计算 T[pq](T[pq](a, b)) (即对(a, b)进行两次T[pq]变换),可以得到
引用
(a((pp+qq) + (2pq+qq)) + b(2pq+qq), a(2pq+qq) + b(pp+qq))

记 p' = pp + qq, q' = 2pq+qq 则有
T[p'q'](a, b) = T[pq](T[pq](a, b)) = (a(p' + q') + bq', aq' + bp')

于是
f(n+1) = T[pq]n(f(1))

也就是说——可以通过类似分治计算 《a的n次方模b》 的算法来计算fibonacci了!

给出了算法以后,代码就容易写了:
#Python版
def fibonacci(n):
    def iter(a, b, p, q, n):
        if n == 0:
            return b
        elif n % 2 == 0:
            return iter(a, b, p * p + q * q, 2 * p * q + q * q, n / 2)
        else:
            return iter(a * (p + q) + b * q, a * q + b * p, p, q, n - 1)
    return iter(1, 0, 0, 1, n)

/* C版 */
typedef unsigned long long ull;
ull fibo_iter(ull a, ull b, ull p, ull q, int n) {
    if (n == 0)
        return b;
    else if (n % 2 == 0)
        return fibo_iter(a, b, p *p + q * q, 2 * p * q + q * q, n / 2);
    else
        return fibo_iter(a * (p + q) + b * q, a * q + b * p, p, q, n - 1);
}

ull fibonacci(int n) {
    return fibo_iter(1, 0, 0, 1, n);
}

/* Scheme版 */
(define (even? n) (= (remainder n 2) 0))
(define (fibonacci n)
    (define (iter a b p q n)
        (cond ((= n 0) b)
              ((even? n)
                (iter
                    a
                    b
                    (+ (* p p) (* q q))
                    (+ (* 2 p q) (* q q))
                    (/ n 2)))
              (else
                (iter
                    (+ (* a (+ p q)) (* b q))
                    (+ (* a q) (* b p))
                    p
                    q
                    (- n 1)))))
    (iter 1 0 0 1 n))

经过这样的优化以后,效率显著,对于n=300,000,python版仅需要不到0.04s,而Scheme版也仅需要0.12s即可得出结果。

p.s. 以上代码均经过测试。
Mar 8

test和bash的小坑 不指定

felix021 @ 2013-3-8 12:57 [IT » 软件] 评论(0) , 引用(0) , 阅读(3821) | Via 本站原创
昨天黄老湿问了我个问题, [ -e ] 是true还是false?为什么?

==== 啦啦啦啦啦的分割线,猜猜吧 ====

这种坑题显然只能实践出真知:
引用
$ [ -e ] && echo yes || echo no 
yes

果然坑了。

仔细想想,这个问题其实还是来源于实践的,比如一个很有可能会出现的写法是:
引用
[ -e $somefile ] && do_sth || do_sth_else

显然,在这个情况下,如果$somefile意外地是一个空串的话,bash实际上执行的就是 [ -e ] (这个可以很容易地验证),于是返回了 true。

简单过了一下源码(coreutils/src/test.c),可以看到执行流是
value = posixtest(argc - 1 <as> nargs);
    switch(nargs)
        case 1: //只有一个参数
            return one_argument();
                return argv[pos++][0] != '\0';  //检查不为空串
        case 2: //只有俩参数
            return two_arguments();
                if (argv[pos] 是 - 开头 <且> 只有俩字符 <且> 是unary_operator)
                    return unary_operator()
                        switch(argv[pos][1]):
                            case 'e':
                                unary_advance() //里面pos加了2
                                return stat(argv[pos-1], &stat_buf) == 0;
        case .. //更多参数
test_exit(value ? TEST_TRUE : TEST_FALSE);

也就是说对于只有一个参数的情况下,test只是简单地判断这个参数是否为空(无论是不是它支持的操作符),有两个参数的情况,才会去判断是否是合法操作符,再执行相应的检测。

然后才想起来,原来我还可以看manual啊,泪流满面。。。man test,果然看到这几行:
引用
-n STRING
      the length of STRING is nonzero

STRING equivalent to -n STRING

也就是说 test STRING 等于 test -n STRING ,检查非空串,于是 [ -e ] 就等于 test -n "-e",自然就是true了。。。

对于上面提到的情况来说,解决办法是在引用变量的时候,记得加上双引号,这样test就会收到2个参数,其中第二个参数是空串,stat出错,于是就可以得到(可能原先)期望的结果了:
引用
$ [ -e "$somefile" ] && echo yes || echo no
no

不过话说回来,bash脚本中引用不存在的变量这件事情本来就不应该发生,类似 rm -rf $some_path/ 这样的悲剧也不是没有发生过,但是bash又没有一个 explicit 模式,所以只能自己在使用之前检测了。

通常检测一个变量是否为空,用上面的 test -n "$VAR" 或者 test -z "$VAR" 即可(注意引号),但是如果要检测某个变量是否根本不存在,BASH却没有内建方法,只能通过这种看起来很奇怪的方式(出自stack overflow):
if [ -z "${VAR+xxx}" ]; then echo VAR is not set at all; fi

//本博客3月份真高产。。。
Mar 7

Python int缓存的那点事[续] 不指定

felix021 @ 2013-3-7 02:57 [IT » Python] 评论(0) , 引用(0) , 阅读(2707) | Via 本站原创
上一篇 说到,对于这样的一段代码:
a = 257
b = 0x101
print a is b

Python解释器会为 a 和 b 各 创建一个 PyIntObject (通过修改PyInt_FromLong打印int的id可以看出来),但是在实际的执行中,a和b却指向了同一个PyIntObject。也就是说,在执行之前,a和b已经被映射到了同一个PyIntObject。

前面说了,Python的解释执行是由以下调用链组成的:
引用

PyRun_FileExFlags()
    mod_ty *mod = PyParser_ASTFromFile() //把py源码转换成AST(Abstract Syntax Tree)
    run_mod(mod, ...) //执行AST
        co = PyAST_Compile(mod, ...) //将AST转换成CFG(Control Flow Graph) bytecode
            PySymtable_Build() //创建符号表
            co = compiler_mod() //编译ast为bytecode
        PyEval_EvalCode(co, ...) //执行bytecode
            PyEval_EvalCodeEx()

由于没有编译原理的基础,只能从全局上看出这些代码都做了什么,但是却很难从细节上去追查。通过修改源码我尽可能了解了 PyParser 将Python源码转换成AST的运行机制(虽然还是没有看懂tokens->cst的转换),但是run_mod的细节实在是看不懂了。于是我在StackOverflow上面提了一个问题,@Bakuriu大牛给了个hint,说是PyCompiler在处理lambda的时候,使用 compiler_add_o() 来将lambda对应的函数的__doc__设置为 PyNone:
/* Make None the first constant, so the lambda can't have a
  docstring. */
if (compiler_add_o(c, c->u->u_consts, Py_None) < 0)
    return 0;

这里头PyNone是常量,而且又出现了 c->u->u_consts ,大有看头。

有了线索以后,突然一切都变得清晰了,简单加了些代码追,可以发现对于上面给出的代码, compiler_mod 是这样处理mod_ty *mod(也就是那棵AST)的:

引用
compiler_mod(compiler *c, mod_ty *mod)
    case Module_kind: //mod->kind = 1
        compiler_body(c, mod->v.Module.body <as> stmts)
            for (i = 0; i < asdl_seq_LEN(stmts); i++) //循环3次,因为有3个stmt
                VISIT(c, stmt, asdl_seq_GET(stmts, i)) //宏展开到compiler_visit_stmt
                    compiler_visit_stmt(c, asdl_seq_GET(stmts,i) <as> s)//访问每个stmt
                        case Assign_kind: //第一个stmt的kind = 5,表示一个赋值操作
                            //赋值操作允许 a = b = 1 所以看起来有点罗嗦,
                            //它会被解析成如下AST:
                            //Assign([AssName('a', 'OP_ASSIGN'),
                            //      AssName('b', 'OP_ASSIGN')], Const(1))
                            n = asdl_seq_LEN(s->v.Assign.targets);
                            VISIT(c, expr, s->v.Assign.value);
                            for (i = 0; i < n; i++) {
                                if (i < n - 1)
                                    ADDOP(c, DUP_TOP);
                                VISIT(c, expr, asdl_seq_GET(s->v.Assign.targets, i));
                            }

简单解释下Assign操作的代码:
    1. 获得赋值目标的数量(比如a=b=1,就是2个)
    2. "VISIT"要赋的值
    3. 挨个ADDOP(c, DUP_TOP)是告诉编译器,增加一个OPCODE=DUP_TOP

DUP_TOP 是 Duplicates the reference on top of the stack 的简写,意思是取得上次计算的值(比如对于b,就是int(1)的reference,而对于a,就是b=1的返回值,也就是b的reference)加入stack_top,这样正好把多个赋值操作串起来。

不过我关注的主要是第二条,对应的代码就是:

引用
VISIT(c, expr, s->v.Assign.value); //宏展开到compiler_visit_expr
    compiler_visit_expr(c, s->v.Assign.value <as> e)
        case Num_kind: //e->kind = 16
            ADDOP_O(c, LOAD_CONST, e->v.Num.n, consts) //宏展开到compiler_addop_o
                //这里e->v.Num.n是在CST->AST的过程中生成的PyIntObject
                //下面的c->u->u_consts是一个PyDictObject,用来保存常量对象
                compiler_addop_o(c, LOAD_CONST <as> opcode,
                                c->u->u_consts <as> dict, e->v.Num.n <as> o)
                    arg = compiler_addop_o(c, dict, o)//塞入dict
                    compiler_addop_i(c, opcode, arg) //将插入顺序作为opcode的oparg


这个compiler_add_o(struct compiler *c, PyObject *dict, PyObject *o)的作用是将一个变量o及其type组成的tuple(o, o->ob_type)塞入到dict中。但是并不是简单暴力地直接插入,它的源码大约是这样的:

static int
compiler_add_o(struct compiler *c, PyObject *dict, PyObject *o)
{
    PyObject *t, *v;
    Py_ssize_t arg;

    if (PyFloat_Check(o)) {
        //省略部分与int无关的代码
    }
    else {
        t = PyTuple_Pack(2, o, o->ob_type); //t = tuple(o, type(o))
    }

    if (t == NULL)
        return -1;

    v = PyDict_GetItem(dict, t); //看看t是否已经在dict中出现过
    if (!v) { //如果没有
        arg = PyDict_Size(dict); //获取dict的当前大小(PyIntObject)
        v = PyInt_FromLong(arg);
        if (!v) {
            Py_DECREF(t);
            return -1;
        }
        if (PyDict_SetItem(dict, t, v) < 0) { //dict[(o, type(o))] = v
            Py_DECREF(t);
            Py_DECREF(v);
            return -1;
        }
        Py_DECREF(v);
    }
    else
        arg = PyInt_AsLong(v); //如果出现过,取得之前设置的v
    Py_DECREF(t);
    return arg;
}


这个代码乍看挺诡异的,因为还与后续编译成字节码的部分有所耦合,这里大致解释一下:

(1) 对于LOAD_CONSTS, 在compiler_visit_expr里面已将dict指定为c->u->u_consts,也就是专门用来存放常量的dict
(2) 所有常量都是用 (o, type(o)) 作为 key 存进去的,并返回顺序递增的编号v,表示o是第v个存进去的常量
(3) dict是个hash表,所以往dict里面塞东西时要计算key的hash
(4) tuple的hash值是将每个元素的hash值组合起来哈希(详见tuplehash函数),类似于sdbmhash或者jshash
(5) int对象的哈希是针对int的值,int对象比较时仅比较它们的值

    尽管 a 和 b 对应的key (a, int)和(b, int)虽然不是同一个对象,但是它们的哈希值是一样的!并且!PyDict_GetItem()查找到某个slot去比较key的时候,递归地去比较key的每一个元素,而两个int的比较,“正好”是比较它们的值是否相等!

    所以,在遍历AST生成bytecode之前,两个相同的const只会在c->u->u_consts中出现1次。

    在compiler_mod函数的末尾有一个assemble(c, addNone),它是将前面生成好的opcode等数据转换成最终的bytecode,其中一些代码逻辑是这样的

        assemble(c, addNone)
            struct assembler a;
            完成一些初始化
            makecode(c, &a);
                PyObject *tmp = dict_keys_inorder(c->u->u_consts, 0); //convert to Tuple
                consts = PySequence_List(tmp); //convert to List
                ...
                PyCodeObject *co = PyCode_New(..., consts, ...);
                    co->co_consts = consts


    也就是说,这里把保存所有常量的 c->u->u_consts 按照插入元素的顺序将所有塞进来的PyObject逐个插入到 consts 里,并最后赋值给PyCodeObject的PyListObject *co_consts。而在最最后的eval环节,LOAD_CONST这个opcode会将它的oparg(就是前面 compiler_addop_i 塞进去的值,也就是compiler_addop_o返回的值)作为索引,从co_consts里取出来,PUSH到栈顶(参见Python/ceval.c +1123行),供下一个指令读取。

    于是int常量整个python的解释执行所经历的步骤都完整地串起来了。

    泪流满面,居然看懂了。
Mar 5

记坑 不指定

felix021 @ 2013-3-5 15:39 [IT » 其他] 评论(4) , 引用(0) , 阅读(6809) | Via 本站原创
1. Python的除法

线上有一个简单的函数,运行一年多了,作用是把"分"表示的字符串转成"元":
def fen_to_yuan(str_fen):
    fen = int(str_fen)
    return '%d.%02d' % (int(fen / 100) , fen % 100)

看起来也的确是没有什么问题,但是就这么简单的一点代码,它还是错了,原因是fen_to_yuan("-270")居然返回了"-3.30"!坑爹啊。简单测试一下,原来是这样:
引用
>>> -270/100
-3
>>> -270%100
30

所以只好蛋疼地修改成这样:
def fen_to_yuan(str_fen):
    fen = int(str_fen)
    sign, fen = fen < 0 and ('-', -fen) or ('', fen)
    return sign + '%d.%02d' % (int(fen / 100) , fen % 100)


2. 线上有一个脚本,要得到上个月的月份,bash的实现就是
引用
date -d "-1 month $date" +%m

看起来也的确是没有什么问题,但是就这么简单的一点代码,它还是错了,原因是对于10月31号居然返回了10!坑爹啊。简单测试一下,原来是这样:
引用
$ date -d "-1 month 20121031" +%Y-%m-%d
20121001
$  date -d "-1 month 20130331" +%Y-%m-%d
20130303

也就是说,先把月份减一,然后检查日期,超过当前月,再向上修正月份,再向上修正年份。

所以只好蛋疼地修改成这样:
引用
date -d "-1 month ${date:0:6}01" +%m

#update: @whusnoopy补充说 向后查看1个月也会有这样的情况,总之记得用月来算是有坑的,千万注意。

3. crontab的小坑

crontab默认是不会读取.bashrc,需要自己去source一下.bashrc,并且不支持像bash一样用反引号来启动一个子命令(这个结论是错的,是因为%前面忘了加斜杠)。这个不展开细说了,有兴趣的试试吧。
Mar 3

常用find + grep查找封装 不指定

felix021 @ 2013-3-3 23:45 [IT » 其他] 评论(0) , 引用(0) , 阅读(2022) | Via 本站原创
看源码的时候经常要在某一类文件里面grep一些内容,用标准的find + grep写起来很辛苦:

$ find -name "*.c" -exec grep {} -Hne "hello world" \;

所以简单封装了下,保存成 ~/bin/xgrep 然后把 ~/bin 加入到 PATH 里去,以后就只需要

$ xgrep \*.c "hello world"    #注意这个 \*.c 里可以用的是*和?的通配符,不是正则

#!/bin/bash

if [ -z "$1" -o -z "$2" ]; then
    echo "Usage: xgrep FilePattern WordPattern"
    exit
fi

filepat="$1"
greppat="$2"

shift
shift

set -x

find -name "$filepat" -exec grep {} -Hne "$greppat" $* \;

#后来才想起grep其实有个--exclude=PATTERN(可以去掉find),但是已经这么用了挺久,习惯了。。。
Mar 3

Yet Another False-Sharing Test 不指定

felix021 @ 2013-3-3 23:31 [IT » 硬件] 评论(0) , 引用(0) , 阅读(2982) | Via 本站原创
前天在 coolshell 里看到 并发框架Disruptor译文 以后 ,才感慨了CPU娘的傲娇,没一会儿就看到 Dutor 同学的 A False-Sharing Test ,发现差距好大(4线程4倍- ,16线程8倍+ ,我用dutor的代码实测16线程性能差距接近20倍),于是也写了段小代码来测试它。跟dutor同学不一样,我用的是 c 实现的,看起来可能没那么易读。

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>
#include <limits.h>

void *tester(void *arg)
{
    long *nloop = (long *)arg; //这里之前笔误写成int了。
    while ( (*nloop)-- );
    return NULL;
}

int driver(int nthread, int nloop, int npad)
{
    size_t size = npad + sizeof(long); //每个线程占用sizeof(long) + npad的空间
    char buff[size * nthread];
    pthread_t th[nthread];

    struct timeval s, e;
    gettimeofday(&s, NULL);

    for (int i = 0; i < nthread; i++) {
        int *arg = (int *)(buff + size * i);
        *arg = nloop;
        pthread_create(&th[i], NULL, tester, (void *)arg);
    }

    void *pret;
    for (int i = 0; i < nthread; i++)
        pthread_join(th[i], &pret);

    gettimeofday(&e, NULL);

    return (e.tv_sec - s.tv_sec) * 1000000 + e.tv_usec - s.tv_usec;
}

int main()
{
    int nloop = 1024 * 1024 * 128, nthread = 16, npad, best_padding = 0, best_usage = INT_MAX;
    printf("nloop = %d, nthread = %d\n\n", nloop, nthread);
    for (npad = 64; npad >= 0; npad -= 8) { //之所以步长为8是为了避免非8字节对齐long可能有的性能损失
        int i, usage = 0;;
        for (i = 0; i < 3; i++)
            usage += driver(nthread, nloop, npad);
        usage /= 3;
        if (usage < best_usage) {
            best_usage = usage;
            best_padding = npad;
        }
        printf("padding: %2d, time usage: %12d\n", npad, usage);
    }
    printf("\nbest padding: %2d, time usage: %12d\n", best_padding, best_usage);
    return 0;
}

引用
$ gcc false_sharing.c -lpthread -std=c99
$ ./a.out
nloop = 134217728, nthread = 16

padding: 64, time usage:      491395
padding: 56, time usage:      477760
padding: 48, time usage:      853594
padding: 40, time usage:      834318
padding: 32, time usage:      905200
padding: 24, time usage:      940989
padding: 16, time usage:      991595
padding:  8, time usage:      1040412
padding:  0, time usage:      1112716

best padding: 56, time usage:      477760

该机器使用的是4颗4核8线程的Xeon E7520@1.87GHz (16个物理核心32个逻辑核心),64GB RAM,/proc/cpuinfo里的cache_alignment是64

可以看出来,padding=56(也就是正好对齐到一个cache行)的时候效率最高,是没有填充时的2倍+的效率,虽然明显,但是显著地没有dutor的测试那么夸张。

把dutor的代码稍微改了下,s[ith].n = NLOOP,且pthread_create的时候传入的参数改成 (void *)&(s[ith].n),然后hook程序改成
size_t *n = (size_t *)args;
while ( (*n)-- );
return NULL;

其运行效率提升显著,padding=56的时候能快10%左右,而padding=0的时候能快达7倍之巨,最终的性能差距大约可以降至 3 倍的差距。这说明dutor的测试方法并不是测试裸的性能差距,带来的了一定的误差。

由于现在多数CPU都已经有了共享的L2或者L3 Cache,Cache Line失效的问题得到了相当的改善,不过不同物理CPU上仍然需要注意这个问题。

然而有一点我不能理解,这个修改对两种情况的影响竟相差这么大,这里头又有什么玄机呢...... #UPDATE: 后根据dutor的测试,我去掉了 for 循环中用到的循环变量 i 之后,性能差距立即将至2倍左右,修改循环的方向或者将for改成while则无效,因此这很可能是分支预测失效带来的问题了。
分页: 8/94 第一页 上页 3 4 5 6 7 8 9 10 11 12 下页 最后页 [ 显示模式: 摘要 | 列表 ]