WilburDing's Blog

Keep track of my life

什么是变量

| Comments

当我们初学计算机语言的时候,就接触到了变量的概念,当然,那时候不可能给出精确的定义,很多书在讲的时候就像大家看到了变量这个词大概就能知道它是什么一样无需解释,比如《C语言程序设计》里直接就提到了变量的说明而没有说什么是变量。当我们带着这种模糊的感觉变成“有经验”的程序员时,似乎已经没人在意变量究竟是什么了。人世间的悲哀莫不如此……

Wikipedia里给的Variable的定义如下:

In computer programming, a variable is a storage location and an associated symbolic name (an identifier) which contains some known or unknown quantity or information, a value.

翻译下就是说,变量是一个存储位置和一个关联的符号名字,这个存储位置包含了一些已知或未知的量或者信息,即值。在C语言里,变量是如下三方面的统一体:

  1. 名字(运行时会变成数字化的名字,内存地址)
  2. 存储位置(某一位置开始的一定大小的存储空间)
  3. 该存储位置里内容的解释方式(即类型,整数、浮点数还是字符串?)

任意一部分单独都不是变量。当我们给一个变量a赋值另一个值时,改变的是a对应的存储位置里的内容,赋值前后是同一个a,因为1、2、3都没有变。

这个定义适用于C这种语言,它面向的是字节的世界。由于一个字节的表达能力有限,我们需要若干个字节来表达一些复杂的概念,所以一个变量需要确定它在内存地址中的位置、多大以及解释方式。而对于Python这种语言,它抽象的是对象的世界,没有更底层的字节这样的东西,那Python中的变量是什么呢?

如果我们把Python语言的内存空间视为对象的空间,即不象C语言那样内存地址指向的是字节而是Python对象,甚至这个地址也不会像C语言的那样是数字而可能就是源代码里的名字,那Python的对象就是如下两方面的统一体:

  1. 名字
  2. 存储位置(可以存放任意的对象)

所以,Python里给变量赋值就是把对象放到变量关联的存储位置上。如从CPython的实现角度讲,函数局部变量存储位置对应函数的f_locals数组下标,赋值就是把对应下标位置的元素指向新对象。

绕了一圈,发现Wikipedia里的定义算是普适的,只是“存储位置”的概念也要看成抽象的,而不是简单的C语言面对的内存位置。

C++11的Atomic和Memory Model的一点认识

| Comments

C++11已经出来好久了,最近才刚开始研究。。

我们知道,C++一般尽量使用库提供功能特性而不是从语言本身开刀(貌似python也是这么宣称的),但这次C++11标准带来了大量的语言特性,甚至可以当成一门新语言来学,哪怕你有C++基础,这其中包括重在提高运行时性能的右值引用,提高易用性的统一初始化、lambda、自动类型推断等,增强语言功能的变参模版、用户自定义字面常量等。随着现在多核的流行,C++终于在语言层面上支持了多线程编程,提供了线程类、同步原语、原子类型以及异步相关的类型和操作。你要问为什么要在语言层面上进行支持而不是只用库提供,毕竟现在已经有大量用C++加类库写成的多线程代码了,而且似乎都工作的很好,因为 Threads Cannot be Implemented as a Library.

Memory Order

查看STL提供的原子操作类型Atomic的接口(std::atomic)可以发现,几乎每个方法都有一个类型为memory_order的默认参数,默认值是std::memory_order_seq_cst。再翻翻,发现memory_order是个枚举类型,并且还有其他几个值memory_order_relaxed/memory_order_consume/memory_order_acquire/memory_order_release/memory_order_acq_rel,这是什么东东?看下边的解释貌似(memory_order)也不知道在说什么,于是猫就被害死了。。

Memory Model

Memory order具体是干嘛的呢,这要从memory model说起。不过memory model貌似有很多意思,比如我们知道的x86 cpu的段式存储就是一种memory model. 但是这里要说的是指线程间通过内存的交互以及它们之间共享数据的使用(wiki),这个主要与编译器有关了。

编译器从计算机的远古时代发展至今,已经不是简单的把我们写的代码一股脑翻译成机器码了,而是会进行非常多的优化,有的优化是单纯将我们写的糟糕代码换成更有效的代码,比如将循环内不变量提出,有的则是为了充分利用现代CPU的特性(乱序执行神马的),这种优化在普通人看来就很费解,比如我们写了

1
2
a = 1
b = some_old_variable

编译器可能就会转换成‘

1
2
b = some_old_variable
a = 1

如果跟踪过-O2或者更高优化级别的代码运行肯定会深有体会,代码的执行不再是按照我们写的顺序来,而是忽上忽下的,查看变量时调试器还经常告诉你变量已经被优化掉了。至于为什么要调换代码的执行顺序,可能是编译器觉得现代CPU的store操作比load操作代价大,所以先执行load再来store吧。

优化虽好,可不是没有坏处。当然不好调试算一个,但致命问题是,这些优化都是建立在程序是在一个线程中执行的。调整语句顺序也好,调整嵌套循环的嵌套关系也好,还是把循环用变量一直放到寄存器直到循环结束才写回内存,编译器都会保证不会破坏程序的语义(当然不排除聪明过头的情况),使得优化后的程序执行结果和程序员原始代码一致。一旦多线程运行,平时默默无闻的优化就露出了马脚,比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int sum;

void f1()
{
  wait_for_some_condition();
  for(int i = 0; i < 100; ++i)
  {
      sum += i;
      std::this_thread::sleep_for(std::chrono::microseconds(1));
  }
}

void f2()
{
  wait_for_some_condition();
  for(int i = 0; i < 100; ++i)
  {
      cout << sum;
      std::this_thread::sleep_for(std::chrono::microseconds(1));
  }
}

假如f1和f2各在一个线程中运行,f2能打印出来sum的计算过程吗,即使不是完全的?答案只能是不一定,如果f1执行时sum一直在寄存器里,那f2只能看到f1执行完后的sum,中间过程根本看不到。那么为了多线程程序的正确执行,是不是只要禁了编译器的优化就可以了呢?答案是不能,就算能,你愿意接受运行缓慢的程序,那编译器作者也不乐意,那么多年心血就付诸东流了,CPU也更欲哭无泪。

为什么禁了编译器优化也不能正确运行呢,因为。。。现代CPU速度非常快,频率都在2GHz上下甚至3GHz还多,以前Pentium4都有超频到8GHz左右的,按2GHz算,一个周期就是0.5ns;而它的搭档内存又“非常慢”,核心频率大概在200MHz上下(神马,我的DDR3不是都1600Mhz吗,额,那是数据传输频率,大概就是核心频率一下可以吐8个bit而不是1个,换算回来核心频率还是200MHz,单论反应速度不比当年的SDRAM好多少),然后还有反应延迟,CPU说要某个地址的数据了,内存要慢悠悠转上几个周期先,然后才能拿到数据往CPU送,所以内存引用一次就要消耗大概100ns。CPU执行计算肯定要使用内存的数据,要是这么等内存,那太伤CPU感情了,白跑那么快,全浪费在等内存上了,所以根据程序的局部性原理(Locality of Reference),在CPU和内存之间加上一个比内存小点但快很多的cache来保存可能要用到的数据,然后我们就获得了一个比cache略慢但是和主内存一样大的内存;内存也不甘寂寞,通过pipeline的方式使自己忙起来,尽力一次多传点数据。有了这些机制也不意味着CPU就能直接从中完全受益,还需要CPU进行很多的配合以充分利用,比如一旦cache命中失败,CPU可以执行后边的指令而不是干等,这样就有了乱序执行,这种内存操作的性质称为Memory Ordering.而且有了cache,CPU往内存写数据也要多考虑点,是直接连cache带内存都写呢还是先写cache一会再写到内存呢,如果其他cpu的cache里也有相同数据怎么办呢。这样,当多个线程同时执行时,彼此都可以看到对方的执行样子,这么赤裸裸的,怎么会不出问题呢。

到了这份田地,正确的多线程程序该怎么写呢?于是编译器说,我知道你的程序在单线程里的情况,但是我不知道哪些数据是线程间共享的,所以,你来告诉我吧!这样,我可以在必要的时候保守的优化,一般情况下全力优化,并且只要你保证你的程序是正确同步的,那我保证程序执行时就是你要的那个样子。这样一个在程序员和语言间的约定,就是Memory Model。

Ordering

刚开始提到的memory_order那几个枚举就是告知编译器数据是在线程间共享的,并且是怎样共享的。memory_order_acquire和memory_order_release的关系大概就像mutex的acquire(lock)和release(unlock)。mutex使线程间串行执行,并且上一个线程unlock后另一个线程lock进入,保证可以看到上一个线程的所有数据修改(或曰side effect)而不会有读写操作被reorder后出问题的情况。同样的,一个atomic a变量,一个线程t1 release(一般是store操作, a.store(memory_order_release))后,另一个线程t2 acquire(一般是load操作, a.load(memory_order_acquire)),那t2可以看到上个release线程的所有修改(不管是不是atomic的变量),但这不是说a.load的时候会一直等另一个线程的a.store,他们只是在执行时间上有个happen-before的关系,即t1的a.store发生在t2的a.load之前,如果他们同时发生,那就说明你的代码没有正确同步,只能自求多福了。比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::atomic<int> flag = ATOMIC_VAR_INIT(0)
int data = 0;

void thread_1()
{
  data = 1;
  flag.store(1, std::memory_order_release);
}

void thread_2()
{
  while(flag.load(std::memory_order_acquire) == 0)
      ;
  assert(data == 1);
}

thread_2通过不断循环保证自己最后读到flag不为0时发生在t1的flag.store之后(因果关系)。从这里也可以看出,atomic的acquire/release时更多的是在起同步作用。

为了达到acquire/release的要求,编译器会对这样的操作比较小心。release时,编译器保证不会把写操作移到它后边,否则其他线程就看不到这个修改了;acquire时,不会把其后的读操作移到它前面,否则读到的就是旧数据。剩下的情况,编译器就可以自由移动读写操作了。除了编译器,有时也需要CPU的配合,因为它执行的时候也会reorder指令,所幸的是x86/x64平台上,mov指令是具有acquire/release语义的,所以我们基本没有什么性能损失。

除此之外还有几个其他的memory_order枚举。

  • memory_order_relaxed说明这个操作除了是原子的外,周围的操作随便移动,比较适合做计数器。
  • memory_order_acq_rel基本是memory_order_acquire和memory_order_release的合体。
  • memory_order_scq_cst是memory_order_acq_rel的加强版,除了有acq_rel语义,还保证是sequencially-consistent(人家Lamport同学70年代就在研究这个了。。)的,这是atomic各种操作的默认memory_order,也是执行代价最大的。选memory_order_scq_cst做默认参数是因为它是最容易用的memory_order,并且性能要比用mutex好点,如果性能的确成为瓶颈可以换其他memory_order慢慢调优,具体可以看这个paper
  • memory_order_consume是memory_order_acquire的弱化版,它只保证不把跟当前load的变量有依赖的变量reorder,没依赖关系的随便移动。比如上边的代码中,data对flag没有依赖,所以thread_2里flag.load换成memory_order_consume后,读到的data就不能保证是1了。但是经常有一些情况是比较合适的,比如通过指针传递一些数据的情况。

当然,你知道了这些memory_order后,也不一定意味着能用它们写出来正确的代码,因为你在reason代码的时候基本是在考虑各种代码reorder的排列组合,当然也可能是我比较stupid的。。但是人家Herb Sutter至少把memory_order_consume列成了C++语言的专家级特性呢。。

Finally

因为我并没有太多的多线程并发开发经验,所以不知道以上有多少是在胡扯,不过我尽力保证是正确的,如果哪位发现有不对的地方,还请多谢指正。。

最后推荐下Herb Sutter的这个talk,Atomic Weapons 1 Atomic Weapon 2,这篇blog大多也是参考这个talk的slides写的。

关于设计的一点思考

| Comments

现在游戏里有类似于红警的建筑列表面板的那种需求,简单说就是有一个面板,里面可以显示若干个按钮,每个按钮有一个图标,鼠标指上去后会显示tip,左键点击按钮就会灰化同时进入建造该建筑的状态(此时当鼠标在场景内移动时就会有一个虚的建筑跟着移动)。UI同学三下五除二给了套这样的API:

1
2
3
4
5
class BuildingPanel(Panel):
  def setIconList(self, iconList)
  def setBtnEnable(self, index, enabled)
  def asOnGetTip(self, index)   鼠标悬停时的回调,请求tip内容
  def asOnBtnClicked(self, index)  # 鼠标点击的回调

当然,这套API也能够完成任务,但是确提供了一套很别扭的语义(先不说命名问题)。一般我们会按照一个面板包含很多按钮,每个按钮可以有icon有tip这样层次化的去理解这个东西,但是,这套API带来的语义确是这个面板有一列icon,你可以设某个位置的按钮的使能。如果用数据库表来类比的话,那么这套API就是以表的每一列来向你讲述这个表而不是表有很多行,每行表示一个按钮。例如,如果初始化这个面板的时候要有一些按钮默认置灰,那么代码可能就得这么写

1
2
3
4
5
6
7
8
9
10
allBuildingTypes = ..
icons = getAllBuildingIcons(allBuildingTypes)
enableStates = calcEnableStates(allBuildingTypes, otherArgs)

\# assume buildingPanel is the panel
buildingPanel.setIconList(icons)

for index, enabled in enumerate(enableStates):
  buildingPanel.setBtnEnable(index, enabled)
  

这样的代码就很难是自解释的了,它淹没在具体的实现细节里了。另外,为实现asOnGetTip/asOnBtnClicked,BuildingPanel需要保存一个管理器类的对象,并调用其相关的函数,这引入了一些依赖。而管理器类也需要自己维护一个按钮索引到建筑类型的一个映射,以在处理tip或者点击时知道是哪个建筑,多了一些负担。

如果我们直接将文章开头的描述转换成代码,那首先需要抽象一个按钮:

1
2
3
4
5
6
class ButtonData(object):
  def __init__(self, icon, callback, enabled, tip)
      self.icon = icon
      self.callback = callback  # called when clicked
      self.enabled = enabled
      self.tip = tip

这样BuildingPanel就管理一些ButtonData就可以了:

1
2
3
class BuildingPanel(Panel):
  def __init__(self):
      self.buttons = []  # [ButtonData]

之前提到的初始化代码会变成这样子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
allBuildingTypes = ..

def onClicked(buildingType, index)
  doSomething(buildingType)
  buildingPanel.setBtnEnable(index, False)

buttons = []
for buildingType in allBuildingTypes:
  buttons.append(ButtonData(
      buildingType.icon,
      functools.partial(onClicked, buildingType),
      buildingType.enabled,
      buildingType.tip
  ))
  
buildingPanel.setButtons(buttons)

(一些命名还比较蛋疼,先忍着)这样子,代码的实现算是层次比较分明了,也更具有自解释性。所以,API的设计,或者代码的每个层次,应该尽量提供一个比较自然的语义,而不是一些看起来能完成功能的随机产生物。同时,借助于直接的回调机制,管理类现在不需要去维护一个按钮索引和实际建筑的关系,BuildingPanel也不需要依赖管理类来处理鼠标点击或者tip显示问题,完全通过self.buttons自给自足,大家各自独立,不需要多知道彼此一点点。

我觉得,以callable(functions/callable class instance/closure/partial(bind))为基础建立起来的回调机制,是使得模块划分清晰的有力武器,主动通知方不需要了解被通知方的任何性质,被通知方也不需要按照某种硬性interface规格来使自己适应,而且callable本身就包含了足够的信息进行处理(closure或者bind或者callable class instance的形式保存),各自可以说井水不犯河水。用duck type的意思来说,在主动通知方看来,你看起来是我要的callback,那你就是我要的callback,不管你是function还是closure还是instance还是什么。在Python里,我们可以轻松的用lambda或者functools.partial,或者复杂点自己写个定义了call的类。在最新的CPP11里,也融合了大量的函数式编程的内容,包括lambda/std::function/std::bind,让我们活得轻松点。据说java8里也有lambda什么的了,但是看起来笨笨的,没那么duck typing。。

Python实现简单的Monad

| Comments

今天看了一篇讲Ruby实现的Monad的文章(这里),所以一时兴起就也想用Python写一个。So,心动不如行动。。

在Haskell里,Monad就是用来把带有context的值应用到接受普通值并返回带context的值的函数的,用Learn You a Haskell话说就是

If we have a fancy value and a function that takes a normal value but returns a fancy value, how do we feed that fancy value into the function?

简单说,我们的目标就是Monad的两个主要的函数:

  1. return,把值放到最小化的context中
  2. >>=(bind),把作为左操作数的Monadic值应用到作为右操作数的函数上,这个函数接受一个普通的值并返回Monadic值

首先,我们需要一个作为Monad的数据类型,这里简单用了一个继承自list的类MonadList,当然也可以自己造一个Maybe什么的。这样,return操作就是把值放到list里,不过Python已经把这个名字给占用了,所以只好取另一个名字wrap; 而bind就是把list里的元素逐一应用到给定的函数上(aka. map!),不过>>=在Python里是赋值语句,只能用个类似的>>了(不同于Haskell的Monad的>>)。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/python

class MonadList(list):

    @staticmethod
    def wrap(value):
        return MonadList([value])

    def bind(self, f):
        return reduce(lambda acc, element: acc.extend(element) or acc,
                      map(f, self),
                      MonadList())

    def __rshift__(self, f):
        return self.bind(f)

    def __str__(self):
        return 'MonadList: ' + super(MonadList, self).__str__()


print MonadList([1, 2, 3, 4]) >> \
        (lambda x: MonadList.wrap(x ** 2)) \
        >> (lambda x: MonadList.wrap(x + 1))

代码的作用很简单,就是把数组的元素先平方再加1 。。

另外,在写这篇文章的时候还发现了另一个blog,比较详细的讲了一个要产品化的代码里使用的Python的Monad,嗯哼。。

Python的is和==操作符用法

| Comments

我只是想说下今天代码检查中遇到的一个问题,不做详细的说明。代码里有这种用法:

1
2
3
4
5
if someVar is []:
    blah

if anotherVar is 1:
    blah

很明显这么用是错的,判断空链表应该用隐式转换,值是否为1用==。当然为了说明清楚问题,稍微研究了一下。控制台里进行了这样的测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> 1 == 1
True
>>> n = 1
>>> n is 1
True
>>> a = 1000
>>> a is 1000
False
>>> [] is []
False
>>> [] == []
True
>>>

n is 1返回True是由于Python对于小整数的优化(小整数都是预先创建好的,需要时直接使用),a is 1000返回False是因为一般的整数都是需要时直接创建的对象并且就算之前有相同的值的对象也不会复用。不过如果写1000 is 1000是会返回True的,因为这俩字面常量实际上引用了一个对象,这应该是编译器的优化吧。[] is []返回False就显而易见了,因为每个list都是全新的对象,不会复用已有的对象。

手工安装OSX上的支付宝插件

| Comments

支付宝在OSX里的插件一直安装不能,因为一个”empty alias”的问题。本来想等着支付宝能哪天更新下解决的,结果等到现在也不行,无奈只好自己手动装了。 虽然没仔细研究过OSX上的软件安装流程,但大概是直接把.application那个文件夹拖到目标目录就可以了。所以需要先知道那个”empty alias”原来要指到哪里的。google了一番,找到了google earth还有一些其他插件的说明文档,说放到 /Library/Internet Plug-ins 里。一开始脑袋短路了,在~/下面找那个目录,结果没找到自己新建了个,加上搜索的时候出现了好几个目录名(Internet Plugins/Internet Plugin/Internet Plug-ins什么的),试了半天无果。最后终于找到了正确位置,发现已经有好几个插件了,然后把wkaliedit.dmg里的aliedit.plugin直接拽过去,当然要提下权限。 这么拽过去的插件还是不能用的,因为里面的文件的权限只对root开了rwx,而且还有apple的扩展属性xattr什么的需要清掉。大概的命令是:

1
2
3
4
5
6
7
cd /Library/Internet\ Plug-Ins
sudo chmod a+rx aliedit.plugin
sudo xattr -c -r aliedit.plugin
cd aliedit.plugin
find . -type d| sudo xargs chmod a+rw
find . -type f| sudo xargs chmod a+r
sudo chmod a+x Contents/MacOS/aliedit

这么搞之后,重启下浏览器,登陆alipay.com的时候的密码框应该就能用了。不过后来发现里面的支付密码框还是不能用的,暂时没弄清楚还,有了解的麻烦告知下,thx。