Liuw's Thinkpad

我们的项目需要改Xen用户空间的工具。Xen用户空间的工具是用Python写的，代码量还不小，用人肉方法去跟踪执行路径那是很笨的办法。我们需要trace调用，又不能改变函数原来的行为，那么最好的办法就是用decorator了。上网找一下，已经有人做过这样的工作了，我综合一下，改成下面的样子。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Decorators used to trace function/method calls
# derive from:
# http://wordaligned.org/svn/etc/echo/echo.py
# http://svn.osafoundation.org/chandler/trunk/chandler/util/autolog.py
#
# liuw
# 2010-5-27

import types

# Should use python log facility?
def do_log(s):
    print s

def _format_arg_value(arg_val):
    arg, val = arg_val
    return '%s=%r' % (arg, val)

def log_wrapper(fn, display_name=None):
    import functools
    if not display_name: display_name = fn.__name__

    code = fn.func_code
    arg_count = code.co_argcount
    arg_names = code.co_varnames[:arg_count]
    fn_defaults = fn.func_defaults or list()
    arg_defs = dict(zip(arg_names[-len(fn_defaults):], fn_defaults))

    @functools.wraps(fn)
    def wrapped(*v, **k):
        global indent

        positional = map(_format_arg_value, zip(arg_names, v))
        defaulted = [_format_arg_value((a, arg_defs[a]))
                     for a in arg_names[len(v):] if a not in k]
        nameless = map(repr, v[arg_count:])
        keyword = map(_format_arg_value, k.items())

        args = positional + defaulted + nameless + keyword

        do_log('%s(%s)' % (display_name, ', '.join(args)))
        return fn(*v, **k)
    return wrapped

def log_class(cls, methodAsFunction=False):
    """Python does not support class decorator, use it this way:
        class ClassName:
            ...
        ClassName = log_class(ClassName)
    """
    # disallow ALL builtin functions/methods
    allow = lambda s: not (s.startswith('__') and s.endswith('__'))

    names = cls.__dict__.keys()

    for name in names:
        if not allow(name): continue

        value = getattr(cls, name)

        if methodAsFunction and callable(value):
            setattr(cls, name, log_wrapper(value))
        elif isinstance(value, types.MethodType):
            # a normal instance method
            if value.im_self == None:
                setattr(cls, name, log_wrapper(value))

            # class and static method are more complex
            # class method
            elif value.im_self == cls:
                w = log_wrapper(value.im_func,
                               display_name='%s.%s' % (cls.__name__,
                                                       value.__name__))
                setattr(cls, name, classmethod(w))
            else:
                assert False

        # static method
        elif isinstance(value, types.FunctionType):
            w = log_wrapper(value,
                            display_name='%s.%s' % (cls.__name__,
                                                    value.__name__))
            setattr(cls, name, staticmethod(w))
    return cls

def log_module(m):
    # import m if m hasn't been imported
    if isinstance(m, str):
        d = {}
        exec 'import %s' % m in d
        import sys
        m = sys.modules[m]

    names = m.__dict__.keys()
    for name in names:
        value = getattr(m, name)
        if isinstance(value, type):
            setattr(m, name, log_class(value))
        elif isinstance(value, types.FunctionType):
            setattr(m, name, log_wrapper(value))

# ------------------------------TEST----------------------------------
class C1:
    @classmethod
    def f1(self, a, b=1, c=2):
        """f1"""
        pass

    @staticmethod
    def f2(d , e=3, f=4):
        """f2"""
        pass

    def f3(self, g):
        """f3"""
        pass
C1 = log_class(C1)

@log_wrapper
def test(x):
    pass

if __name__ == '__main__':
    inst = C1()
    inst.f1(10)
    inst.f2(20)
    inst.f3(1000)
    test(321)

functools.wraps这个decorator可以保证被修饰函数/方法的其他attribute与被wrap之前无异。比较让我感慨的是，我参考的有一部分是Chandler的代码，这个项目现在仍健在，实在不易。

看到很多散列表（hash table）的实现中，长度都是一个素数。至于为什么一定要用素数，一下子也没想出所以然来。上网搜索了一下相关的文章，发现很多人也在讨论这个问题。

http://www.cs.unm.edu/~saia/numtheory.html

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth-2

http://blog.csdn.net/ilibaba/archive/2009/03/05/3960142.aspx

长度是否要是素数，能不能是合数，这个问题大家的意见得不到统一。支持用素数的人的理由是，素数可以使得散列的分布更加均匀。

自己总结一下看这些文章的心得。一个散列运算可以等价如下式：

hash(k) = mix(k) mod m

散列计算中，求余往往是最后一步，因为没有机器拥有无限的内存，所以必须把结果放入到有限的桶（bucket）中。求余前的运算，假如混淆（mix）得比较好的话，那么m使用素数还是合数，分布是一样的。假如混淆（mix）得不够好的话，那么一个素数可以把一些common pattern加以区别。至于什么样的数据混淆用什么样的mix算法比较好，这个得经统计才可以得出结论。总的来讲，使用一个素数总没有错，虽然运行慢了点，却可以得到相对较好的统计特性。个人看法。

Knuth的The Art of Computer Programming中，也用的是一样的理由推荐用素数的m。手上没有书，他应该没有提到合数的问题。上面也仅仅是我个人的一些想法，没有经过严格的证明，我也没有能力去证明。当然，很欢迎有人来指正我的错误。

手上有《算法导论》，第十一章散列表，对这个问题也没有给出严格的证明。但是它提到这样的一个问题，若m=2^p-1，则所有以2^p为基数的解释的字符串，无论字符位置怎么变化，得出的散列值都是一样的。这个证明比较简单，用同余的性质就可以证明，最后的值，其实是各个字符值的和再对m取余，所以散列值不会随字符的位置发生变化。

UPDATE：

StackOverflow上也有对这个问题的讨论。

http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus

上面的文章的观点和我总结出来的基本一致。

“零拷贝”这个词也听到不少了，据说是可以明显提高性能。网上找到好文一篇。

Zero Copy I: User-Mode perspective

在一些程序，比如说HTTP服务器，需要向用户发送文件，有一部分是图片、静态网页之类不需要处理就可以直接发送的文件。土一点的做法无非是：

read(file_fd, buf, len);
write(socket_fd, buf, len);

实际上，read(2)这个操作，是首先把文件内容读入到内核缓冲区中去，然后再把文件内容从内核缓冲区拷贝到用户缓冲区；而write(2)这个操作，需要把用户缓冲区的内容拷贝到内核缓冲区。我们不需要对文件内容进行处理的情况下，却多用了一道拷贝工序，直接造成的开销有多了一次的上下文切换，以及浪费了缓冲区的内存。

为什么不把拷贝到用户空间的这一道工序去掉了，内核的两个缓冲区直接拷贝就好了。目前流行的做法是用sendfile(2)，在Linux里面的作用是把数据从一个文件描述符直接拷贝到别一个文件描述符。但是sendfile(2)的实现，好像是各个系统都有差异，使用的时候需要注意一下，在使用的时候最好先查一下手册。

但是从内核缓冲区到内核缓冲区的“零拷贝”，还不算真的完全没有拷贝。真正的“零拷贝”需要硬件支持。在具备Gather操作的DMA硬件支持下，内核只需要修改内部文件描述符的指向，然后等待硬件自动执行Gather操作，把数据取走。

有个小计划，就是尽量能做到每日抽出一段时间来读点有趣的文章，把链接放在这，然后再记一下自己的想法。

其实前面也有写，比如说公众演说技巧和Memory Barriers的一些小结，应该都算是这类文章。但是直到今天，才真正萌发起这样的想法，能否把这个事情做得系统点，坚持下来，对自己也有好处。假如能做到有周期有规律，那自然是最好的，但是目前的情况是比较难实现的了，只能说有看就写了。

今天看的是Eric Steven Raymond写的How To Become A Hacker。

简要摘录一下，Hacker应有的态度是：1. 世界上有大量有趣的问题是等待解决的；2. 没有人应该需要解决同样的问题两次；3. 拒绝沉闷的事情；4. 自由；5. 信念不能代替能力。

ESR还提到Hacker的基本技能自然是过硬的编程能力、基本功等等。

个人觉得后面对于社区的讨论也比较有价值。在有了前面的基本能力之后，就必须要融入社区之中，从社区获取，也为社区作贡献。个人觉得，这是Hacker和一般程序员的最大的区别。在我的印象中，Hacker们总是热衷于各种各样的争吵，呵呵。

小胖提到的一个问题：有两个已经排序好的URL文件a和b，想要求出b中与a不同的行数。

太久没有写Shell了，还想了一阵用哪个命令好。

expr `wc -l b` - `comm -1 -2 a b | wc -l`

有更好的方法请指教。

五一期间看了一篇文章，Memory Barriers: a Hardware View for Software Hackers，对于Memory Barriers得到了更加深入的理解。

Cache本身的更新是遵守MESI（Modified，Exclusive，Shared，Invalid）协议的。CPU之间的Cache信息更新通过消息传递来完成。

但是现在CPU的设计中，在Cache之外加入了Store Buffer和Invalidate Queue。Store Buffer的加入，使得CPU对某内存单元的更新不能马上反映到Cache中；Invalidate Queue的存在，使得其他CPU对Cache的invalidate操作不能马上反映到Cache中。Store Buffer和Invalidate Queue提高了性能，但是也就导致了Cache的不一致。

因此需要引入Memory Barriers。Store Buffer和Invalidate Queue应该分别对应使用wmb和rmb。当然直接使用通用mb也是可以的。

Roughly speaking, a “rmb” marks only the invalidate queue and a “wmb” marks only the store buffer, while a “mb” does both.

一般来说，Memory Barriers应该配对使用，比如说一方使用了rmb另外一方对应使用wmb。在Linux内核中，还存在着Data Dependence Memory Barrier，这是一个较弱的rmb。具体见Linux内核代码的Documentation/memory-barriers.txt。

把《演说之禅》草草看了一遍，小总结一下。

Made To Stick提到的演说六原则是：简单（Simplicity）、意外（Unexpectedness）、具体（Concreteness）、可信（Credibility）、情感（Emotions）、故事（Story），SUCCESs。满足这六个原则，可以做出令人印象深刻的公众演说。

某一领域的专家对公众介绍本领域的知识时，一定要注意避免“知识祸根”。所谓“知识祸根”就是说演讲者可能会错误估计受众对专业知识的了解程度和自己一样好，然后采用过于专业的方式去演说。正确的做法，应该是以直观、显浅的语言去进行介绍。

要做好一个公众演说，前期的设计是必不可少了。为了完成这个设计，我们需要准备一叠纸，一些彩笔，一块白板，一个安静的地方，一个好的图片库，还有一个好用的slideware。初期阶段应离开电脑，而在纸上设计。适当的头脑风暴，可以丰富内容，但是在选择内容时，不要犹豫，该砍掉的就要砍掉。

Steve Jobs的Keynote值得学习，他的演说技巧还是很符合Made To Stick六原则的。