Apr 282011
 

云风的buzz中提到了coolshell.cn的一篇文章Linux 2.6.39-rc3的一个插曲有感,看过之后,有两个感受:
(1)Linus 提出的 ‘think and analyze’的解决方式。
对于bug,从我解读Linus和Cloud的buzz回复来看,他们对于bug的方式都是知其然也知其所以然,即要么不去改bug,要么就把bug想清楚了从系统上改好。就像给一个人看病,要是治胃疼,不是说你少吃点,或者是来几片止疼药,而是调查清楚为什么得了胃病。要是长期不规律吃饭得的胃病,恐怕最好的解决方法是养成按时吃饭的习惯。这样做会增加改一个bug的时间。但从长远来看,我们有可能节省时间。比如:如果我们引入magic number之后,一个星期之后,又有类似的bug发现了,如果我们每个bug都是通过仔细思考,而且系统构建有足够的正交性的话,我们会很自然的想到,这个bug肯定发生在其他部位,而不太可能是刚修复bug的变体,这就减少了解决问题时的思考路径,节省了时间。这个时候,我们应该对自己说Good job,给自己多一点鼓励。
而有时,我们可能在别人的代码里发现了bug,这种情况下同样适用Linus的建议,即‘think and analyze’或者是’years and years of testing on thousands of machines’。要不能通过思考和分析解决问题,要么就用历史证明过的已经work的代码。这样即使不能fix 这个bug,也不会造成fix bug的假象,从而避免以后有的版本work,有的版本不work的现象。读通别人的代码并不简单,这个’think and analyze‘的过程也许要很多天,因为这个过程强迫我们用别人的思维结果来思考,而我们很难知道为什么别人这样做。个人认为,如果有足够的单元测试和高质量的文档,这个思考分析的时间并不是浪费,而是学习其他人编程思路和技巧的机会。同时,我们应该让老板知道,我们需要时间来读代码,我们在解决问题,但是的确需要时间。如果一个系统的核心部分很难读懂,而bug并不关键,不妨告诉自己不要太完美主义(想想iphone,没有多任务,电池续航有限,价格高,但仍然一个好产品)。

总而言之,Linus的观点就是每看到一个bug,问一下你确实了解这个bug的原理么?
如果Yes: (think and analyze之后),准备重组的理由,用别人可以理解的方式改(少用magic number)。
如果No: (‘years and years of testing on thousands of machines’) 回到以前测试好的版本,并且注明这个bug没有被fix。
这就是Linus认为的: It really is that simple. It’s _always_ that simple.

(2)对Yinghai Lu的评价
首先Yinghai Lu是一个kernel开发者,我认为他是有足够的相关经验的:很快发现了问题,提出了一种解决方法
陈皓认为“我没有想到Linux 内核组会有像Yinghai这样工作的方式,毕竟这是一个黑客级的开发团队。” 我认为言之过甚。
Yinghai 的 email 中说:” can you try following change ? it will push gart to 0x80000000″ (你能不能试试这个?)
而陈皓说“给出了个fix”,他认为Yinghai提出的是会加入到kernel code中的patch,我想这不一定是Yinghai的本意。

以我的理解来看,Linus一直负责code review,他希望code的质量高,有注释,不能随意fix bug (改一两个数)。因此他非常反感code中的magic number,以及只改code不管背后的逻辑;而Yinghai Lu做为开发者,首先想到的是找到问题的原因。他自己的电脑里没法重复这个bug,因此他需要把patch交给别人来测试。在不同的立场下,Linus生气 和 Yinghai的解释 就容易理解了。

我不清楚kernel开发的具体流程是怎样的。但我认为Yinghai 试图做的是在top down这个框架下做修补,他不想或者不能够对整个top down的机制做出修补,特别是这个机制下已经有垃圾代码的情况下(见HPA的回信)。在Linus看来,他是不希望看到top down这种新尝试(相对于bottom up)缺乏足够的调研支持的。至于未来Linux kernel的采用机制,将要由kernel 开发者们和Code reviewer之间做出协调,也要和以往的低质量代码做出协调。我会拭目以待。

Mar 082011
 

Learning and applying coding style from Google (in Emacs)

今天李开复的博客转发了一条围脖,大意是:Google C++ Coding Style是最好的Coding Style,没有之一。
以前虽然经Paul提示过,但当时的我并没有提起足够的重视,现在重新看了一下,受益匪浅。
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml Google C++ Style Guide

这个Style Guide不仅提示并规定了如何格式化代码,还对C++中的特性做了对比和使用建议。例如:
(1) 对于引用(reference)的参数,应该尽量使用const来做修饰,否则我们不知道程序中修改的值会不会有超出该函数的作用;
(2) 对于要修改值的参数,则提倡使用指针。
(3) 还有,对于构造函数Constructor,Google 认为应使用explicit关键字来修饰,这样防止编译器做隐式的类型转换,同时构造函数必须明确的写出来,即使是与default的形式是相同的。
(4) 对于头文件的引用,Google 建议使用Forward declaration(提前声明)来减少包含过多的文件次数

在这个Style Guide之中,还提到了一个有用的工具cpplint.py, 这个Python工具可以对照Google Style Guide去检查你的代码是否符合规范。我是一个Emacs fans,那么如何把Google Style Guide 和 我们的.emacs配置结合起来呢?
首先你需要下载这个文件: google-c-style.el
之后考虑到我所在的小组要求Tab-indent是4个空格,并且要求用空格替代Tab,那么我们的.emacs配置如下:

(require 'cc-mode)
(require 'google-c-style)
(defun my-build-tab-stop-list (width)
  (let ((num-tab-stops (/ 80 width))
	(counter 1)
	(ls nil))
    (while (<= counter num-tab-stops)
      (setq ls (cons (* width counter) ls))
      (setq counter (1+ counter)))
    (set (make-local-variable 'tab-stop-list) (nreverse ls))))
(defun my-c-mode-common-hook ()
  (c-set-style "google")
  (setq tab-width 4) ;; change this to taste, this is what K&R uses 🙂
  (my-build-tab-stop-list tab-width)
  (setq c-basic-offset tab-width)
  (setq indent-tabs-mode nil) ;; force only spaces for indentation
  (local-set-key "\C-o" 'ff-get-other-file)
  (c-set-offset 'substatement-open 0)
  (c-set-offset 'arglist-intro c-lineup-arglist-intro-after-paren)
  )
;; google sytle is defined in above function
(add-hook 'c-mode-common-hook 'my-c-mode-common-hook)
(add-hook 'c++-mode-common-hook 'my-c-mode-common-hook)

如何配置.emacs里并加入cpplint功能呢?只需在.emacs里加入如下代码:

(defun cpplint ()
  "check source code format according to Google Style Guide"
  (interactive)
  (compilation-start (concat "python ~/bin/cpplint.py " (buffer-file-name))))

我们只需要执行M-x cpplint就可以得到格式检查的结果。用C-x `,或者M-g n, M-g p可以上下切换。

另一个常用的功能是如何将多个源文件通过Emacs来调整格式的(batch indent source code)?
参考 Batch Indentation with Emacs,文中提到的方法可以用默认的代码风格来格式化源文件。
但我们的目标是用Google风格来格式话代码,那么只需要稍作改变:
~/bin/emacs-format-function

;;; File: emacs-format-file
;;; Stan Warford
;;; 17 May 2006
;; from: http://www.cslab.pepperdine.edu/warford/BatchIndentationEmacs.html

;; Adopt by Xiaowei Zhan 2011 from .emacs
(require 'google-c-style)
(defun emacs-format-function ()
  "Format the whole buffer."
  (setq tab-width 4) ;; change this to taste, this is what K&R uses 🙂
  (setq c-basic-offset tab-width)
  (c-set-offset 'substatement-open 0)
  ;; next line is strange, I copied it from .emacs, but it cannot find c-lineup-arglist-intro-after-paren
  ;; however, disable this line seems working as well.
  ;;(c-set-offset 'arglist-intro c-lineup-arglist-intro-after-paren) 
  (indent-region (point-min) (point-max) nil)
  (untabify (point-min) (point-max))
  (save-buffer)
  )

~/bin/my-indent

#!/bin/bash
# File: my-indent
# Opens a set of files in emacs and executes the emacs-format-function.
# Assumes the function named emacs-format-function is defined in the
# file named emacs-format-file.

if [ $# == 0 ]
then
   echo "my-indent requires at least one argument." 1>&2
   echo "Usage: my-indent files-to-indent" 1>&2
   exit 1
fi
while [ $# -ge 1 ]
do
   if [ -d $1 ]
   then
      echo "Argument of my-indent $1 cannot be a directory." 1>&2
      exit 1
   fi
   # Check for existence of file:
   ls $1 2> /dev/null | grep $1 > /dev/null
   if [ $? != 0 ]
   then
      echo "my-indent: $1 not found." 1>&2
      exit 1
   fi
   echo "Indenting $1 with emacs in batch mode"
   emacs -batch $1 -l ~/emacs/google-c-style.el -l ~/bin/emacs-format-file -f emacs-format-function
   echo
   shift 1
done
exit 0

#from http://www.cslab.pepperdine.edu/warford/BatchIndentationEmacs.html

值得注意的是Google除了C++ Style Guide, 还提供JavaScript Style Guide, Objective-C Style Guide, and Python Style Guide。对这些语言感兴趣的朋友可以到Google Style Guide发掘。

Jan 312011
 

为了利用OpenMP来加速C/Fortran程序,我记录一些阅读OpenMP API Version 3.0 Specification (May 2008)的经验。另外,这篇文章主要关注C语言中OpenMP的使用经验。

本文包括 摘要、经验和其他注意事项、参考 三部分。

摘要 (按照Specification的顺序)

(1)第一章是Glossary, 定义了各种OpenMP使用的名词(terms),例如:construct, directive, clause, task, tied task … 这个可以在看不懂的时候返回来查询。其中有一个被多次使用的名词是sentinel,这似乎是Fortran中使用OpenMP时应该使用的名词,和C并没有关系。

(2)2.2:  _OPEN 这个macro 被定义成yyyymm形式,表示OpenMP API的版本

(3) parallel construct:表示紧挨着的程序可以parallel运行。用#pragma omp parallel 来使用,当程序遇到parallel construct之后,会用固定个数的threads形成一个team去完成work。至于有多少个threads,这不一定,可参考2.4.1中决定threads number的算法。注意,当parallel里一个thread结束的时候,其他的threads都会被结束 (If execution of a thread terminates while inside a parallel region, execution of all threads in all teams terminates. If execution of a thread terminates while inside a parallel region, execution of allthreads in all teams terminates.)

(4) worksharing construct:有4类:loop;sections constructs;single construct;workshare construct

对于worksharing loop construct来说,有5种scheduling,即安排工作,的方式。static(静态分配), dynamic(每一个thread动态要求一个chunk of iterations), guided(execution thread负责给其他threads分配chunks), auto(根据compiler和system的情况决定), runtime(运行期决定)。2.5.1.1给出了一个决定scheduling的流程图

四种类型的区别:

loop:在C中紧接着一个for循环

section:与loop类似,不必要是for循环,只要是structure block就行

single:只能由一个thread执行(不一定是master thread)

worshare:只有Fortran中出现,是把structure block分成若干份,每一份由一个thread执行

(5)2.6节讲了结合parallel construct 和worksharing construct,就是这两个construct可以合在一起用。然后分3个小节介绍了parallel loop construct (相当于loop construct 后直接用parallel construct),parallel section construct(相当于section construct 后直接用parallel construct)和parallel workshare construct(相当于worshare construct 后直接用parallel construct)。

(6)2.7节是task construct,这定义了一个task。当一个thread碰到task construct的时候会立刻产生一个task,并按照data-share attribute的指示准备相应的数据环境(data environment)。这个task可能被立刻执行,也可能被延后执行。

注意当task construct带有if clause (if 从句)的时候,当前的 thread会暂停(suspend)当前的task,并切换到刚刚生成的task。这里的if clause中的变量对于task construct后的structure block是引用型的(不是传值,是传引用)。默认的task是tied task (这个task被某个thread suspend后,只能由这个thread来resume)

task scheduling point 是指在这一点可以改变task的状态(如可以被suspended),或是task 结束的位置。包括task construct开始的地方;taskwait construct开始的地方;遇到barrier directive;隐含的barrier 区域; 在tied task region的末尾。

(7)2.8节介绍了master and synchronization constructs,包括master constructs(只有master thread可以执行), critical constructs(同一时间只能有一个thread来执行。可以给critical constructs起名字), barrier constructs(指定一个明确的barrier,举例:在parallel region的explicit tasks必须在barrier之前都完成,之后的程序才能继续执行。注:在C语言中使用有一定限制。), taskwait constructs(等待当前task生成的子程序全部完成), atomic constructs(原子语句,注:只支持+,-,*,/,++,–,|, &,+=,-=,*=等简单运算,原子性只是保证赋值的那一步), flush constructs(保证thread view里的数据和memory的数据相吻合,另外需考虑不同thread执行flush的order,见74页的范例), ordered constructs(保证按照loop region指定的顺序来运行thread).

(8)2.9节是Data Environment数据环境,即并行计算时不同thread间的变量是如何影响的。

construct里变量的数据共享属性(Data-sharing Attribute):提前决定的(private:用threadpriviate声明的,在construct里声明的,for construct里的循环变量;shared:在heap上的,static的变量),显示决定的(在construct上指明的),隐示决定的(default clause可以指定的;如果default clause没有指定,则比较复杂,例如parallel construct中是shared,全部规则见79页)。额外的不能由上面隐式规则推出的可以见92页。 (我认为如果数据共享属性已经复杂到不好看出,那是不是这个程序本身写的太不清晰了!)

不在construct里而是在region里的数据共享属性(Data-sharing Attribute),见2.9.1.1

threadprivate见2.9.2

default的数据共享属性见2.9.3 。包括shared, private,firstprivate(private,且给变量赋初值),lastprivate(private,在task结束后会改变原始变量的值),reduction(做functional programming里的reduction,需要提供运算符。先使用private copy,然后用初始值做reduce,最后更新原始的变量)

数据拷贝从句(Data Copy Clause),见2.9.4

(9)第3章是运行库里的子程序

3.1 所有函数的原型在omp.h中,都是用C做链接(link)的。

3.2 控制执行环境的函数,包括设置/取得线程数,得到最多的支持的线程数,设置线程数的上限等等。

3.3 Lock程序,这是为了给线程加锁而提供的函数,分简单锁(simple lock)和级联锁(nested lock,区别是可以set多次)

3.4 时间程序。只有两个:omp_get_wtime() 返回double型的时间 和omp_get_wtick()返回1秒等于多少个时钟的tick

(10)第4章讲环境变量,可以通过设置环境变量来改变调度方式(schedule type)OMP_SCHEDULE,线程数OMP_NUM_THREADS ,最多的线程数OMP_THREAD_LIMIT等等

(11)第5章有各种各样的样例程序。这样当我们不清楚概念的时候,都可以快速的查看,例如如何使用lock,如何用reduction……

经验其他注意事项:

这个Specification里很有结构化,对于各种construct都给出了Summary,Syntax,Binding(使用范围), Description,Restriction。

网上一些程序中常常显示指明shared variable,这样做可能是为了减少不必要的数据拷贝。

对于多重循环,只对外层循环并行化处理不一定能达到负载均衡。解决方法可以用,把多重循环合并成一层循环,见【4】

参考:

【1】OpenMP Specification Version 3.0 Complete Specifications – (May, 2008). (PDF)

【2】OpenMP C/C++ Summary Card http://www.openmp.org/mp-documents/OpenMP3.0-SummarySpec.pdf

【3】Wikipedia (其中介绍OpenMP语言架构的图很不错)http://en.wikipedia.org/wiki/OpenMP

【4】对多重循环的优化 http://blog.csdn.net/drzhouweiming/archive/2008/05/23/2472454.aspx

【5】OpenMP 编程指南 http://blog.csdn.net/drzhouweiming/archive/2009/04/20/4093624.aspx

Jan 282011
 

Reason:

I used strtod() function in C, forgot to set errno to 0, then after calling strtod(), the value of errno is unpredictable.

When found the bug:

I tried to use Ptyhon ctypes module. In script mode, python pyCtypes.py always crash but in command line mode, the code becomes all right. It’s mysterious running Python in different ways turns out to give different results.

First, I thought it is clear that Python has some bug, otherwise the same Python code should give the same result.

Then I realized my Python code use a DLL routine using C language, and I recalled in the man page of “strtod”, it says we need to initialize errno value to zero every time before calling.

Example code:
Line 1 should be added to ensure correctness.

        errno = 0;
        vec->value[vec->len++] = strtod(temp, NULL);
        //vector_print(vec);
        if (errno != 0) {
            perror("strtod");
            fprintf(stderr, "%s\n", temp);
            exit(EXIT_FAILURE);
        }

Note:

WordPress supports syntax highlight.

I am using SyntaxHighlighter Evolved http://wordpress.org/extend/plugins/syntaxhighlighter/.

Official documentation mentions another way: http://en.support.wordpress.com/code/posting-source-code/.