Mar
18
在RSA算法里头经常要用到“求x的n次方模m”这样的过程，通常使用O(log(n))的模重复平方算法来实现，提高效率。
其实这是大二学的《信息安全数学基础》里面的内容，那时为了考试需要（手算+写出很罗嗦的过程），还专门写了代码放在Blog空间里考试的时候用—……
同样O(log(n))的递归算法其实很容易理解：
但是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 。
于是实现就容易了：
//网上搜了下模重复平方算法，居然没有靠谱的算法解释，看来可能还是这个算法太简单了吧。。。
其实这是大二学的《信息安全数学基础》里面的内容，那时为了考试需要（手算+写出很罗嗦的过程），还专门写了代码放在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
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
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
最近在看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开始算起）
不幸的是这样树形展开效率太低了，当n=42的时候，C语言需要的时间已经超过1s了。
因此需要改成迭代版，使用 (a, b) <- (a + b, a) 这样的方式。
虽然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](T[pq](a, b)) （即对(a, b)进行两次T[pq]变换），可以得到
也就是说——可以通过类似分治计算 《a的n次方模b》 的算法来计算fibonacci了！
给出了算法以后，代码就容易写了：
经过这样的优化以后，效率显著，对于n=300,000，python版仅需要不到0.04s，而Scheme版也仅需要0.12s即可得出结果。
p.s. 以上代码均经过测试。
想起前几天看到的某个笔试题，说是用最快的办法计算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)))))
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))
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))
记 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))
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
昨天黄老湿问了我个问题， [ -e ] 是true还是false？为什么？
==== 啦啦啦啦啦的分割线，猜猜吧 ====
这种坑题显然只能实践出真知：
果然坑了。
仔细想想，这个问题其实还是来源于实践的，比如一个很有可能会出现的写法是：
显然，在这个情况下，如果$somefile意外地是一个空串的话，bash实际上执行的就是 [ -e ] （这个可以很容易地验证），于是返回了 true。
简单过了一下源码(coreutils/src/test.c)，可以看到执行流是
也就是说对于只有一个参数的情况下，test只是简单地判断这个参数是否为空（无论是不是它支持的操作符），有两个参数的情况，才会去判断是否是合法操作符，再执行相应的检测。
然后才想起来，原来我还可以看manual啊，泪流满面。。。man test，果然看到这几行：
也就是说 test STRING 等于 test -n STRING ，检查非空串，于是 [ -e ] 就等于 test -n "-e"，自然就是true了。。。
对于上面提到的情况来说，解决办法是在引用变量的时候，记得加上双引号，这样test就会收到2个参数，其中第二个参数是空串，stat出错，于是就可以得到（可能原先）期望的结果了：
不过话说回来，bash脚本中引用不存在的变量这件事情本来就不应该发生，类似 rm -rf $some_path/ 这样的悲剧也不是没有发生过，但是bash又没有一个 explicit 模式，所以只能自己在使用之前检测了。
通常检测一个变量是否为空，用上面的 test -n "$VAR" 或者 test -z "$VAR" 即可(注意引号)，但是如果要检测某个变量是否根本不存在，BASH却没有内建方法，只能通过这种看起来很奇怪的方式（出自stack overflow)：
//本博客3月份真高产。。。
==== 啦啦啦啦啦的分割线，猜猜吧 ====
这种坑题显然只能实践出真知：
引用
$ [ -e ] && echo yes || echo no
yes
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);
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
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
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解释器会为 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:
这里头PyNone是常量，而且又出现了 c->u->u_consts ，大有看头。
有了线索以后，突然一切都变得清晰了，简单加了些代码追，可以发现对于上面给出的代码， compiler_mod 是这样处理mod_ty *mod(也就是那棵AST)的：
简单解释下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，这样正好把多个赋值操作串起来。
不过我关注的主要是第二条，对应的代码就是:
这个compiler_add_o(struct compiler *c, PyObject *dict, PyObject *o)的作用是将一个变量o及其type组成的tuple(o, o->ob_type)塞入到dict中。但是并不是简单暴力地直接插入，它的源码大约是这样的：
这个代码乍看挺诡异的，因为还与后续编译成字节码的部分有所耦合，这里大致解释一下：
(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，其中一些代码逻辑是这样的
也就是说，这里把保存所有常量的 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的解释执行所经历的步骤都完整地串起来了。
泪流满面，居然看懂了。
a = 257
b = 0x101
print a is b
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;
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));
}
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_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;
}
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
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
1. Python的除法
线上有一个简单的函数，运行一年多了，作用是把"分"表示的字符串转成"元"：
看起来也的确是没有什么问题，但是就这么简单的一点代码，它还是错了，原因是fen_to_yuan("-270")居然返回了"-3.30"！坑爹啊。简单测试一下，原来是这样：
所以只好蛋疼地修改成这样：
2. 线上有一个脚本，要得到上个月的月份，bash的实现就是
看起来也的确是没有什么问题，但是就这么简单的一点代码，它还是错了，原因是对于10月31号居然返回了10！坑爹啊。简单测试一下，原来是这样：
也就是说，先把月份减一，然后检查日期，超过当前月，再向上修正月份，再向上修正年份。
所以只好蛋疼地修改成这样：
#update: @whusnoopy补充说 向后查看1个月也会有这样的情况，总之记得用月来算是有坑的，千万注意。
3. crontab的小坑
crontab默认是不会读取.bashrc，需要自己去source一下.bashrc，并且不支持像bash一样用反引号来启动一个子命令（这个结论是错的，是因为%前面忘了加斜杠）。这个不展开细说了，有兴趣的试试吧。
线上有一个简单的函数，运行一年多了，作用是把"分"表示的字符串转成"元"：
def fen_to_yuan(str_fen):
fen = int(str_fen)
return '%d.%02d' % (int(fen / 100) , fen % 100)
fen = int(str_fen)
return '%d.%02d' % (int(fen / 100) , fen % 100)
看起来也的确是没有什么问题，但是就这么简单的一点代码，它还是错了，原因是fen_to_yuan("-270")居然返回了"-3.30"！坑爹啊。简单测试一下，原来是这样：
引用
>>> -270/100
-3
>>> -270%100
30
-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)
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
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，
Mar
3
看源码的时候经常要在某一类文件里面grep一些内容，用标准的find + grep写起来很辛苦：
$ find -name "*.c" -exec grep {} -Hne "hello world" \;
所以简单封装了下，保存成 ~/bin/xgrep 然后把 ~/bin 加入到 PATH 里去，以后就只需要
$ xgrep \*.c "hello world" #注意这个 \*.c 里可以用的是*和?的通配符，不是正则
#后来才想起grep其实有个--exclude=PATTERN（可以去掉find），但是已经这么用了挺久，习惯了。。。
$ 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" $* \;
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
前天在 coolshell 里看到 并发框架Disruptor译文 以后 ，才感慨了CPU娘的傲娇，没一会儿就看到 Dutor 同学的 A False-Sharing Test ，发现差距好大（4线程4倍- ，16线程8倍+ ，我用dutor的代码实测16线程性能差距接近20倍），于是也写了段小代码来测试它。跟dutor同学不一样，我用的是 c 实现的，看起来可能没那么易读。
该机器使用的是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程序改成
其运行效率提升显著，padding=56的时候能快10%左右，而padding=0的时候能快达7倍之巨，最终的性能差距大约可以降至 3 倍的差距。这说明dutor的测试方法并不是测试裸的性能差距，带来的了一定的误差。
由于现在多数CPU都已经有了共享的L2或者L3 Cache，Cache Line失效的问题得到了相当的改善，不过不同物理CPU上仍然需要注意这个问题。
然而有一点我不能理解，这个修改对两种情况的影响竟相差这么大，这里头又有什么玄机呢...... #UPDATE: 后根据dutor的测试，我去掉了 for 循环中用到的循环变量 i 之后，性能差距立即将至2倍左右，修改循环的方向或者将for改成while则无效，因此这很可能是分支预测失效带来的问题了。
#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;
}
#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
$ ./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;
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则无效，因此这很可能是分支预测失效带来的问题了。
Mar
3
早先翻python代码的时候是有注意到 intobject 里有缓存这档事，不过没细看。昨天有人在sf问起为什么有如下现象：
于是又翻开python的源码 python2.6.8/Objects/intobject.c ，可以看到这些代码(略做简化)：
而PyFloat_Object并没有（也不适合）实现这样的缓存，所以就可以解释上面的情况了。
更进一步，可以用257来验证一下，的确是超出了缓存的范围：
然后手贱做了另一个测试，蛋疼了：
也就是说如果让解释器一次执行的话，解释器又会再优化它，让a、b引用同一个对象。//注：这里对于float和str类型的常量效果是一样的。
为了搞清楚解释器到底是怎么实现这一点的，又把代码翻出来。之前翻的时候对解释器的执行流程已经有大致的了解了。make得到的python解释器是从 Module/python.c 里的 main() 函数开始的，调用链大约是这样：
从 PyRun_FileExFlags 开始，才能看到底层代码正式登场：
注：更详细的Python编译解释流程可参见这一系列： http://blog.csdn.net/atfield/article/category/256448
通过加入一些调试代码，可以窥探到内部的执行流。例如，在PyParser_AddToken中输出token的名称和类型编码；在PyParser_ParseFileFlagsEx()之后调用PyNode_ListTree()，可以看到生成的CST树（修改list1node()可以让它打印出更容易阅读的版本）；修改PyInt_FromLong()，让它在ival=257的时候输出创建的object的id（CPython实现中 id 其实就是指针的值）。加上一些代码以后，编译python，执行test.py可以看到如下输出：
从输出可以看到，解析源码生成CST的时候（输出的CST已经滤掉了非TERMINAL的node），每个token还保留着原始的字符串（例如0x101和257），而在CST到AST的转换过程中（PyAST_FromNode），解释器为每一个NUMBER都创建了一个PyIntObject。然而在程序运行的最终结果里可以看到，a is b的结果是True，也就是说，从AST转换到CFG并执行(run_mod)的过程中，解释器做了适量的优化，将 a 和 b 都指向了同一个 int 对象。
由于对CFG不熟，相应的代码还不太看得懂，所以暂时只能烂尾了，如果以后看懂了，再来补充。
续集：Python int缓存的那点事[续]
引用
>>> a = 1.0
>>> b = 1.0
>>> a is b
False
>>> a = 1
>>> b = 1
>>> a is b
True
>>> b = 1.0
>>> a is b
False
>>> a = 1
>>> b = 1
>>> a is b
True
于是又翻开python的源码 python2.6.8/Objects/intobject.c ，可以看到这些代码(略做简化)：
#define NSMALLPOSINTS 257
#define NSMALLNEGINTS 5
/* References to small integers are saved in this array so that they
can be shared.
The integers that are saved are those in the range
-NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
PyObject *
PyInt_FromLong(long ival)
{
register PyIntObject *v;
//如果 -5 <= ival && ival < 257, 命中缓存~
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
v = small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
return (PyObject *) v;
}
if (free_list == NULL) { //这个是另一个优化，相当于内存池，用链表实现
if ((free_list = fill_free_list()) == NULL)
return NULL;
}
/* Inline PyObject_New */
v = free_list;
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject *) v;
}
#define NSMALLNEGINTS 5
/* References to small integers are saved in this array so that they
can be shared.
The integers that are saved are those in the range
-NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
PyObject *
PyInt_FromLong(long ival)
{
register PyIntObject *v;
//如果 -5 <= ival && ival < 257, 命中缓存~
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
v = small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
return (PyObject *) v;
}
if (free_list == NULL) { //这个是另一个优化，相当于内存池，用链表实现
if ((free_list = fill_free_list()) == NULL)
return NULL;
}
/* Inline PyObject_New */
v = free_list;
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject *) v;
}
而PyFloat_Object并没有（也不适合）实现这样的缓存，所以就可以解释上面的情况了。
更进一步，可以用257来验证一下，的确是超出了缓存的范围：
引用
>>> a = 257
>>> b = 257
>>> a is b
False
>>> b = 257
>>> a is b
False
然后手贱做了另一个测试，蛋疼了：
引用
>>> a = 257; b = 257; a is b
True
True
也就是说如果让解释器一次执行的话，解释器又会再优化它，让a、b引用同一个对象。//注：这里对于float和str类型的常量效果是一样的。
为了搞清楚解释器到底是怎么实现这一点的，又把代码翻出来。之前翻的时候对解释器的执行流程已经有大致的了解了。make得到的python解释器是从 Module/python.c 里的 main() 函数开始的，调用链大约是这样：
引用
main() @Modules/python.c
Py_Main() @Modules/main.c
PyRun_AnyFileExFlags() @Python/pythonrun.c
PyRun_SimpleFileExFlags
PyRun_FileExFlags()
Py_Main() @Modules/main.c
PyRun_AnyFileExFlags() @Python/pythonrun.c
PyRun_SimpleFileExFlags
PyRun_FileExFlags()
从 PyRun_FileExFlags 开始，才能看到底层代码正式登场：
引用
PyRun_FileExFlags()
mod_ty *mod = PyParser_ASTFromFile() //把文件转换成AST(Abstract Syntax Tree)
node *n = PyParser_ParseFileFlagsEx() //生成CST(Concrete Syntax Tree)
parsetoke() //逐个解析token
ps = PyParser_New()
for (;;)
PyTokenizer_Get() //获取下一个token
PyParser_AddToken(ps, ...) //将token加入到CST中
mod = PyAST_FromNode(n, ...) //将CST转换成AST
递归调用 ast_for_xxx 生成AST，同时过滤CST中的冗余信息
其中ast_for_atom中调用了parsenumber, 它调用PyInt_FromLong()
run_mod(mod, ...) //执行AST
co = PyAST_Compile(mod, ...) //将AST转换成CFG(Control Flow Graph) bytecode
PyFuture_FromAST()
PySymtable_Build() //创建符号表
co = compiler_mod() //编译ast为bytecode
PyEval_EvalCode(co, ...) //执行bytecode
PyEval_EvalCodeEx()
mod_ty *mod = PyParser_ASTFromFile() //把文件转换成AST(Abstract Syntax Tree)
node *n = PyParser_ParseFileFlagsEx() //生成CST(Concrete Syntax Tree)
parsetoke() //逐个解析token
ps = PyParser_New()
for (;;)
PyTokenizer_Get() //获取下一个token
PyParser_AddToken(ps, ...) //将token加入到CST中
mod = PyAST_FromNode(n, ...) //将CST转换成AST
递归调用 ast_for_xxx 生成AST，同时过滤CST中的冗余信息
其中ast_for_atom中调用了parsenumber, 它调用PyInt_FromLong()
run_mod(mod, ...) //执行AST
co = PyAST_Compile(mod, ...) //将AST转换成CFG(Control Flow Graph) bytecode
PyFuture_FromAST()
PySymtable_Build() //创建符号表
co = compiler_mod() //编译ast为bytecode
PyEval_EvalCode(co, ...) //执行bytecode
PyEval_EvalCodeEx()
注：更详细的Python编译解释流程可参见这一系列： http://blog.csdn.net/atfield/article/category/256448
通过加入一些调试代码，可以窥探到内部的执行流。例如，在PyParser_AddToken中输出token的名称和类型编码；在PyParser_ParseFileFlagsEx()之后调用PyNode_ListTree()，可以看到生成的CST树（修改list1node()可以让它打印出更容易阅读的版本）；修改PyInt_FromLong()，让它在ival=257的时候输出创建的object的id（CPython实现中 id 其实就是指针的值）。加上一些代码以后，编译python，执行test.py可以看到如下输出：
引用
felix021@ubuntu-server:~/src/python2.7-2.7.3$ cat test.py
a = 257
b = 0x101
print a is b
felix021@ubuntu-server:~/src/python2.7-2.7.3$ ./python -d test.py
PyParser_ParseFileFlagsEx
type = 1, token: [a]
type = 22, token: [=]
type = 2, token: [257]
type = 4, token: []
type = 1, token: [b]
type = 22, token: [=]
type = 2, token: [0x101]
type = 4, token: []
type = 1, token: [print]
type = 1, token: [a]
type = 1, token: [is]
type = 1, token: [b]
type = 4, token: []
type = 4, token: []
type = 0, token: []
PyNode_ListTree:
<1>a //type=1表示是NAME
<22>=
<2>257 //type=2表示是NUMBER
<4> //这是NEWLINE
<1>b
<22>=
<2>0x101
<4>
<1>print
<1>a
<1>is
<1>b
<4>
<4>
<0> //这是ENDMARKER
Before PyAST_FromNode
name = a
ival = 257, id = 22699048 //注意这个id和下一个id不一样
name = b
ival = 257, id = 22698784
name = b
name = a
After PyAST_FromNode
True #这一行是print a is b的输出
a = 257
b = 0x101
print a is b
felix021@ubuntu-server:~/src/python2.7-2.7.3$ ./python -d test.py
PyParser_ParseFileFlagsEx
type = 1, token: [a]
type = 22, token: [=]
type = 2, token: [257]
type = 4, token: []
type = 1, token: [b]
type = 22, token: [=]
type = 2, token: [0x101]
type = 4, token: []
type = 1, token: [print]
type = 1, token: [a]
type = 1, token: [is]
type = 1, token: [b]
type = 4, token: []
type = 4, token: []
type = 0, token: []
PyNode_ListTree:
<1>a //type=1表示是NAME
<22>=
<2>257 //type=2表示是NUMBER
<4> //这是NEWLINE
<1>b
<22>=
<2>0x101
<4>
<1>print
<1>a
<1>is
<1>b
<4>
<4>
<0> //这是ENDMARKER
Before PyAST_FromNode
name = a
ival = 257, id = 22699048 //注意这个id和下一个id不一样
name = b
ival = 257, id = 22698784
name = b
name = a
After PyAST_FromNode
True #这一行是print a is b的输出
从输出可以看到，解析源码生成CST的时候（输出的CST已经滤掉了非TERMINAL的node），每个token还保留着原始的字符串（例如0x101和257），而在CST到AST的转换过程中（PyAST_FromNode），解释器为每一个NUMBER都创建了一个PyIntObject。然而在程序运行的最终结果里可以看到，a is b的结果是True，也就是说，从AST转换到CFG并执行(run_mod)的过程中，解释器做了适量的优化，将 a 和 b 都指向了同一个 int 对象。
由于对CFG不熟，相应的代码还不太看得懂，所以暂时只能烂尾了，如果以后看懂了，再来补充。
续集：Python int缓存的那点事[续]
