Archive for the ‘Develop’ Category

Hadoop 实战:谁是最倒霉的人?

Saturday, October 4th, 2008

hadoop-logo.gif

上一次介绍了 MapReduce 的工作方式以及 Hadoop 这个开源的 MapReduce 实现,这次尝试用 Hadoop 来写一个简单的应用。要解决的问题是这样的:现在我手里有大量的邮件数据,并且我知道每封邮件是正常邮件还是垃圾邮件,现在我想要找出收到的邮件中垃圾邮件最多的人,亦即找出“谁是最倒霉的人”。

首先是 Map 的过程,输入数据是一封一封的邮件,彼此之间没有任何关联,因此可以很自然地分组处理。Map 将邮件转化到以邮件的收件人进行分组,如果邮件是垃圾邮件,则映射到收件人的垃圾邮件数“+1”。Reduce 的过程就是将各个收件人的邮件数统计结果加起来。

Read the rest of this page »

public interface RequestProcessorFactoryFactory

Saturday, September 20th, 2008

beans曾经在 reddit 上看到这个 Apache 的 FactoryFactory ,觉得很好笑,只是想,大概这样的名字就是严格按照某些设计模式做出来的吧。不过笑过之后也并没有去细想。

最近自己开始用起 Java 来,因为以前学过这个语言,所以很容易就上手了,之后差不多很多东西都很自然,直到有一天我发现自己不小心做了一个叫做 FeatureCollectionFactory 的接口出来,才觉得似乎是该好好想一想了。

有一些东西,自己以前也时常听到或者看到,但是觉得太“企业级”了或者太“Java”了,并没有去关注。比如 Factory 这个东西,为什么会需要 Factory 呢?我觉得,主要就是因为 new 语句太“死板”了,比如:

Fruit fruit = new Fruit();

这里后面可以写 new Apple()new Pear() 或者是 new Grape() 什么的,但是无论是写任意一个,都必须要作为一个语句写死了,在编译的时候就完全确定了,但是有时候希望具体创建什么对象要等到运行时才能确定。于是就有了 Factory 。

Read the rest of this page »

程序优化中的测不准原理

Tuesday, September 2nd, 2008

optimize在《The Art of Computer Programming》一书中有这样一句话:

Premature optimization is the root of all evil in programming.

相信大家肯定都已经耳熟能详了,也大都清楚我在“Ruby: 提升性能的几点尝试”中提到的优化程序应该走的基本步骤。虽然如此,这样的情况还是时常发生:花力气把代码大改一番之后发现性能并没有得到什么提升的时候,才开始悔恨自己没有先跑一遍 profiler 。可是如果只是机械地去重复“找出程序热点”、“优化热点”的步骤的话,实际上并没有掌握优化的真谛。

例如下面是我用 Valgrind 分析程序得到的一个结果报告:

Read the rest of this page »

pymmseg-cpp: rmmseg-cpp with Python interface

Thursday, August 14th, 2008

以前为了提高 RMMSeg 的性能,我写了 rmmseg-cpp ,根据 JavaEye 一段时间的使用情况来看,似乎挺稳定的,性能也很不错。其实 rmmseg-cpp 虽然名字里面有一个 “r” 字,但是算法核心完全是用 C++ 做的,最后才加了一层 Ruby 的接口包装。正巧最近我又两个用 Python 的项目都要用到中文分词,便决定给 rmmseg-cpp 加一个 Python 的接口。

正如我在 On the Rubinius FFI 一文中描述的一样,做到 Native 模块的接口有两种方法,一种是我在 rmmseg-cpp 中用的写 C 代码来粘合二者。另一种则是直接用语言提供的 FFI 接口,写 Python 代码来粘合。也可以算是各有各的好处吧,不过这里用 FFI 有一个很吸引我的地方就是粘合代码不用进行编译。如果用 C 来写粘合代码的话,需要用编译 Python 解释器相同的编译环境下加上 Python 的源代码(至少是头文件)一起编译,在 Linux 下倒是挺方便的,但是在 Windows 下可以说是相当麻烦,这似乎也是 rmmseg-cpp 一直不支持 Windows 平台的原因。但是如果用 FFI 来写粘合代码的话,就只需要单独编译原本的 Native 模块。编译一个标准的 C/C++ 模块和编译一个依赖于 Python/Ruby 源代码/头文件的模块是不一样的,这样的任务即使在 Windows 下也可以很方便地完成。

Read the rest of this page »

Notes: How to make a patch

Friday, August 1st, 2008

虽然现在各种版本控制工具大行其道,但是有时候还是需要使用相对原始一些的办法提交补丁,制作补丁其实很简单,用 diff 命令,加上 -u 参数生成带有上下文的 unified 格式的 diff 文件,就是一个 patch 了。可是最容易忘记的地方就是后面的参数是先写未修改过的版本呢还是先写修改过的版本。我自己每次都记不住,要去查 man page 。正好今天收到一个 patch ,发现里面的修改都是反过来的,大概也是参数写反了吧。 ^_^ 所以我终于决定把正确的用法记下来:

diff -u original new > original.patch

希望自己能记住,就算记不住也能方便地在此查到。 :)

Read the rest of this page »

the compiler for skime — from bottom up

Wednesday, July 9th, 2008

最近有空的时候也都在折腾 skime 的 VM ,虽然主要集中在 VM 上,但是写测试代码十分麻烦,每次添加一些辅助功能,最后猛然发现一个编译器的原型已经完成了。我仍然在尝试这种编程方式——并非一开始就把所有的东西都设计好,而是对一些简单的 case ,采用最简单的方法构建出一个可以运行的原型,再通过原型进行扩充。到目前为止似乎都感觉挺好的,因为许多东西都是万事开头难,有了一个大致框架之后剩下的事情就要简单多了,而且原型作为一个快速的可行性尝试也是很不错的。

在刚做出一个 VM 样子的时候,要测试必须手工写字节码,全是数字,写起来非常麻烦,而且一开始指令集也时常有改动,指令的 opcode 也跟着变动,改起来非常麻烦,于是我写了一个简单的 encoder ,从 opcode 的名字到数值进行转换,也算是方便了一些,测试代码可以这样写了:

Read the rest of this page »

MSTC Staff 的睡眠趋势

Thursday, June 26th, 2008

大约是从去年寒假的时候开始,我就经常在 cc98 的 MSTC 版上发“晚安帖”,就是每天晚上睡觉的时候发一个帖子说一声晚安,后来版面上时常出现一大堆晚安帖的情况,遭到大家的抗议。 :p 后来只好集中到了一个帖子里面,养成了习惯大家也都时常来说晚安。

不管是早有预谋还是心血来潮,我对这个晚安贴的内容分析了一下,得到了类似于下面的结果:


plot_simple.jpg

其中横坐标是日期,纵坐标是睡觉时间,由于大家都睡得比较晚,所以把第二天凌晨的时间也记作当天晚上(如 25:00 就是第二天凌晨 1:00 )。每一条线就代表一个人的睡眠趋势了。由于并不是每个人每天都去那个晚安贴回帖的,所以每条线的横坐标分布并不是很均匀的。上面是只分析了最初几天的数据的情况,下面则是从今年 2 月 24 日到最近的完整数据分析的结果(点击查看原始大小的图片):

Read the rest of this page »

Introduction to direct threading, or computed goto

Saturday, June 14th, 2008

exec现在许多语言都是先把源代码编译成跨平台的字节码,然后通过解释字节码(或是对字节码进行 JIT)的方式执行程序。这比直接遍历 AST 的方式要高效许多。而现在许多虚拟机的字节码其实已经不是以字节 (byte) 为单位,而是以机器字 (word) 为单位(比如 Rubinius 和 Ruby 1.9 的虚拟机 YARV 都是如此),只是仍然沿用“字节码”这一称呼而已,这个原因我稍后会讲。

除此之外,虚拟机一般会分为两种:基于栈和基于寄存器的。虽然在现实的 CPU 上基于寄存器是理所当然的,但是在实现虚拟机的时候却不一样,基于栈的指令集能够让字节码跟紧凑,这样也可以提高 Cache 的利用率,而且实现起来也比基于寄存器的机器要简单。虽然有不少 paper (例如 The case for virtual register machinesVirtual machine showdown: Stack versus registers 等)对比了性能之后都得出基于寄存器的虚拟机“虽然代码大小有所增加,但是带来的性能提升更值”的结论,然而实际上除了 Perl 6 的虚拟机 Parrot 之外其他大部分虚拟机都是基于栈的。

扯了这么多,才要说到今天的正题。虚拟机的实现其实和一个真正的 CPU 差不多,大致有如下几个步骤:

  1. 取指令。在这里是字节码。
  2. 解码,在真实的 CPU 里这个过程会比较复杂,例如 x86 的指令集就是出奇的复杂。而在虚拟机里则不一样,一般 opcode 和 operand 是可以很简单地分开的。
  3. 执行。

如果学过体系结构相关的课程的话,应该了解一个简单的 CPU 大致是如何执行一条指令的,而在虚拟机中,则通常是针对每一个 opcode 会有一段代码完成相应的功能。

Read the rest of this page »

Rubyforge support git now

Wednesday, June 4th, 2008

不知道是不是我火星了,今天去 Rubyforge 注册 rmmseg-cpp 项目的时候发现在 SCM 那里可以选 git 了。不知道是什么时候加上的支持,这下应该会方便许多了。不过刚注册的项目还没有通过审核,到时候立即试用一下,这样在 github 和 Rubyforge 同时有一个 repo 应该也是能很方便地同步的了! :)

rmmseg-cpp: rmmseg in C++

Wednesday, May 21st, 2008

RMMSeg is an implementation of MMSEG Chinese word segmentation algorithm. It features full integration with Ferret. The original version is written in pure-Ruby, which includes two algorithms:

  • Complex Algorithm: Maximum matching with three-word chunk filtering. The accuracy is good. But the performance is very bad — it is very slow, consuming lots of memory and there even seems to be memory leaking.
  • Simple Algorithm: Simple maximum matching algorithm. The performance is relatively acceptable, the accuracy is also not too bad, but definitely not as good as the Complex Algorithm.

I tried various ways to improve the performance and achieved some improvements. But the result is not so good for real production. And there are also strange leaking. I tried various tools like ruby-prof and BleakHouse. They all showed that I’m not leaking, but the memory usage is definitely growing (linearly). I have to admit Ruby (MRI, currently) is very slow.

Then yesterday when reading Beautiful Code, and finding some beautiful C codes, I started to get enthusiastic. I got back after supper and started to implement RMMSeg in C++ — rmmseg-cpp.

Now I have something to show off:

rmmseg-cpp.png

With a simple Ruby wrapper, the interface of rmmseg-cpp is almost identical to the original rmmseg. Due to my simple test, it now runs roughly 40 times faster (though I had expected more) while consuming only 10% memory as before.

However, I’d also have to admit coding in C++ is more dangerous than in Ruby (or similar languages). I encountered several segment faults when writing rmmseg-cpp. And I’m still not very sure whether it is really bug-free (I used many tricky stuffs in order to make it faster and more compact. But in fact, no software is really bug-free :p ). Another drawback is that rmmseg-cpp is less (or difficult) extensible/customizable than rmmseg, because it is not very convenient to do such things.