|
|
2008年3月19日
写了好几天的代码因为还有bug没de掉，没commit到svn上
然后不知怎么的在make的时候生成的kernel没变化，于是直接make world，然后发现linux kernel目录被清空了。。。
只能明天靠记忆慢慢补了，皑皑。
yifanw大牛半个月前发在c++版上的，怕以后忘了看先放在这备个忘吧
白话入门
http://www.newsmth.net/bbscon.php?bid=335&id=250203
白话解决方案
http://www.newsmth.net/bbscon.php?bid=335&id=250237
白话参考文献
http://www.newsmth.net/bbscon.php?bid=335&id=250260
最近有点忙，今天总算在某个课题deadline前把论文憋出来交上去了。跑这儿来推荐两篇上个月看到的比较有意思的paper，都比较偏理论，也很老。
今天写介绍下第一篇，剑桥大学的A Logic of Authentication，中了SOSP '89，整理后发在1990年的ACM Transactions on Computer Systems上。
http://www.csie.fju.edu.tw/~yeh/research/papers/os-reading-list/burrows-tocs90-logic.pdf
（另一篇是Safe Kernel Extensions Without Run-Time Checking，改天再写点介绍）
这篇paper的主要工作是通过构造一种多种类的模态逻辑(many-sorted model logic)，来检查网络中验证协议的安全性。
基础的逻辑分三部分：
原语，如验证双方A和B，以及服务器S，下文用P Q R泛指
密钥，如K_ab代表a和b之间的通讯密钥，K_a代表a的公钥，{K_a}^{-1}代表对应的私钥，下文用K泛指
公式（或者陈述），用N_a, N_b等表示，下文用X Y泛指
接下来定义以下约定（constructs）
P 信任 X: 原语P完全信任X
P 看到 X: 有人发送了一条包含X的信息给P，P可以阅读它或者重复它（当然通常是在做了解密操作后）
P 说了 X: 原语P发送过一条包含X的信息，同时也可以确定P是相信X的正确性的
P 控制 X: P可以判定X的正确与否。例如生成密钥的服务器通常被默认为拥有对密钥质量的审核权。
X 是新鲜的: 在此之前X没有被发送过。这个事实可以通过绑定一个时间戳或者其他只会使用一次的标记来证明。
P <-K-> Q: P和Q可以通过共享密钥K进行通讯，且这个K是好的，即不会被P Q不信任的原语知道。
K-> P: P拥有K这么一个公钥，且它对应的解密密钥K^{-1}不会被其他不被P信任的原语知道。
P <=X=> Q: X是一个只被P和Q或者P和Q共同信任的原语知道的陈述，只有P和Q可以通过X来相互证明它们各自的身份，X的一个例子就是密码。
{X}_K: X是一个被K加密了的陈述
<X>_Y: 陈述X被Y所绑定，Y可以用来证明发送X的人的身份
好了，总算把这些约定列完了，然后来看看通过这些约定能推出一些什么东东：
如果 P 相信 (P <-K-> Q), 且 P 看到 {X}_K，那么 P 相信 Q 说了 X。
这个例子很简单，既然P Q有安全的密钥K，那么P看到通过K加密后的X肯定认为就是Q发出的。
又比如，
如果 P 相信 Q 控制 X，P 相信 (Q 相信 X)，那么 P 相信 X
也很容易理解，既然 P 相信 Q 的判断，那么 Q 相信什么 P 自然也就相信了。
再举一个例子
如果 P 相信 Y 是新鲜的，那么 P 相信 (X, Y) 也是新鲜的。
这里(X, Y)表示 X 和 Y 的简单拼接，也很容易理解，既然 Y 之前没出现过，那么 X 和 Y 的组合自然也没出现过。
一个协议要被定义为安全，最起码要满足
A 相信 A <-K->B，B 相信 A <-K->B
即双方要互相信任密钥是安全的
再健壮一点的协议，还要满足
A 相信 (B 相信 (A 相信 A <-K->B))，反之一样
即A B不仅相信密钥，也相信对方相信自己对密钥的信任。
有了这些简单却强大的工具后，接下来这篇paper开始着手分析一些协议，包括Kerberos协议，Andrew Secure RPC 握手协议等，还指出了其中的一些问题和改进措施，例如CCITT X.509 协议中可以通过重复发送一条老的信息来模仿成加密双方中的一员。
具体的分析不贴上来了，一方面对于我这个不熟悉TeX的人来说码公式实在麻烦，另一方面我实在困死了 =_=
建议有兴趣的朋友好好看看这篇经典paper
Some notes on
lock-free and wait-free algorithms
http://www.audiomulch.com/~rossb/code/lockfree/
NOBLE
-
a library of non-blocking synchronization
protocols
http://www.cs.chalmers.se/~noble/
An
optimistic approach to lock-free FIFO queues
(Distributed Computing 2008)
http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf
High performance
dynamic lock-free hash tables and list-based sets
http://portal.acm.org/citation.cfm?id=564870.564881
Concurrent
Programming Without Locks
http://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf
Simple,
Fast, and Practical Non-Blocking and Blocking
Concurrent Queue Algorithms
http://www.research.ibm.com/people/m/michael/podc-1996.pdf
2009-01-08 以前碰到这个问题都得先重启PieTTY然后用screen -x恢复到原来的工作界面，今天不知怎么的emacs里C-x C-s按了就挂起，只能google。 传说中，早期的终端会遇到显示字符的速度慢于接收字符的速度，为了解决这个问题，C-s用于先挂起当前终端，在数据传输之后用C-q恢复显示。所以最简单的解决方法就是在挂起后按C-q。 不过我的WinXP中C-q已经和快速启动工具（寝室里是Turbo Launcher，实验室的是Launchy）绑定了，也懒得为了这么个问题改操作习惯，于是再次google，终于找到一个一劳永逸的方法，以bash为例，在~/.bashrc中加入一行 stty -ixoff -ixon 即可。另外这样设置后似乎恢复了C-s在bash中正向增量查找的功能。恩。
今年的ASPLOS '09上zhou yuanyuan也有一篇关于如何concurrent program中发现隐藏的atomicity violation bugs的paper，里面提到了这篇paper
2008-11-30
OSDI '08上MSR发的paper，针对并发编程中难以发现的bug问题。
paper的内容主要分两大块。
一是如何在发现bug的时候记录下线程的运行先后(thread
interleaving)，途径是在线程API和用户程序多写一层wrapper
functions，这里还有一些其他的问题，比如只记录下了thread interleaving的话出现data race怎么解决等。
另外一块内容是如何遍历出给定程序运行后所能产生的结果的集合，加入这个能实现的话那就能把所有隐藏的bug都找出来了。但是这个搜索空间很大，是
指数级的，的一个结论就是：给定一个程序有n个的线程，所有线程共完成k条指令，那么c次占先调度后线程的排列情况数的复杂度是 的，所以在实现遍历代码的时候必须有效的降低k和c的值。
问题现象：上校内、一些国内论坛时经常出现连接重置(Connect reset)错误，而上google baidu等网站却没什么问题。ping那些有问题的网站的结果很正常。
google了一堆关键词后终于发现问题出在MTU上，至少在偶的本本上运行
sudo ifconfig eth1 mtu 1412
就没问题了（eth1是无线网卡）
p.s 多谢万熊 XD
摘要: 发信人: linelf (水水), 信区: Real_Estate
标 题: 苏南经济模式兴衰亲历记zz
发信站: 日月光华 (2009年01月15日20:39:22 星期四)
阅读全文
Bruce Eckel的一篇日志建议把self从方法的参数列表中移除，并把它作为一个关键字使用。
http://www.artima.com/weblogs/viewpost.jsp?thread=239003
Guido的这篇日志说明了self作为参数是必不可少的。
http://neopythonic.blogspot.com/2008/10/why-explicit-self-has-to-stay.html
第一个原因是保证foo.meth(arg)和C.meth(foo, arg)这两种方法调用的等价（foo是C的一个实例)，关于后者可以参见Python Reference Manual 3.4.2.3。这个原因理论上的意义比较大。
第二个原因在于通过self参数我们可以动态修改一个类的行为：
#
Define an empty class:
class
C:
pass
#
Define a global function:
def
meth(myself, arg):
myself.val
=
arg
return
myself.val
#
Poke the method into the class:
C.meth
=
meth
这样类C就新增了一个meth方法，并且所有C的实例都可以通过c.meth(newval)调用这个方法。
前面两个原因或许都可以通过一些workaround使得不使用self参数时实现同样的效果，但是在存在decorator的代码中Bruce的方法存在致命的缺陷。(关于decorator的介绍可以参见http://www.python.org/dev/peps/pep-0318/)
根据修饰对象，decorator分两种，类方法和静态方法。两者在语法上没有什么区别，但前者需要self参数，后者不需要。而Python在实
现上也没有对这两种方法加以区分。Bruce日志评论中有一些试图解决decorator问题的方法，但这些方法都需要修改大量底层的实现。
最后提到了另一种语法糖实现，新增一个名为classmethod的decorator，为每个方法加上一个self参数，当然这种实现也没必要把self作为关键字使用了。不过我觉得这么做还不如每次写类方法时手工加个self =_=
2008年评出了1998年最具影响力的PLDI论文，获奖论文的作者将分摊1000美元的奖金（还没一等奖学金多 -_-b）
2008 (for 1998): The Implementation of the Cilk-5 Multithreaded Language, Matteo Frigo, Charles E. Leiserson, and Keith H. Randall
Citation
“The 1998 PLDI paper “Implementation of the Cilk-5 Multithreaded
Language” by Matteo Frigo, Charles E. Leiserson, and Keith H. Randall
introduced an efficient form of thread-local deques to control
scheduling of multithreaded programs. This innovation not only opened
the way to faster and simpler runtimes for fine-grained parallelism,
but also provided a basis for simpler parallel recursive programming
techniques that elegantly extend those of sequential programming. The
stack-like side of a deque acts just like a standard procedure stack,
while the queue side enables breadth-first work-stealing by other
threads. The work-stealing techniques introduced in this paper are
beginning to influence common practice, such as the Intel Threading
Building Blocks project, an upcoming standardized fork-join framework
for Java, and a variety of projects at Microsoft.”
另外前几年的获奖paper有：
2007 (for 1997): Exploiting Hardware Performance Counters with Flow and
Context Sensitive Profiling, Glenn Ammons, Thomas Ball, and James R.
Larus
2006 (for 1996): TIL: A Type-Directed Optimizing Compiler for ML,
David Tarditi, Greg Morrisett, Perry Cheng, Christopher Stone, Robert
Harper, and Peter Lee
2005 (for 1995): Selective Specialization for Object-Oriented Languages, Jeffrey Dean, Craig Chambers, and David Grove
2004 (for 1994): ATOM: a system for building customized program analysis tools, Amitabh Srivastava and Alan Eustace
2003 (for 1993): Space Efficient Conservative Garbage Collection, Hans Boehm
2002 (for 1992): Lazy Code Motion, Jens Knoop, Oliver Rüthing, Bernhard Steffen.
2001 (for 1991): A data locality optimizing algorithm, Michael E. Wolf and Monica S. Lam.
2000 (for 1990): Profile guided code positioning, Karl Pettis and Robert C. Hansen.
两者配合，更完美的知识管理方案
http://hi.baidu.com/qq303520912/blog/item/de5cba082db83e36e924889e.html
Endnote是目前国内科研人员使用最多的文献管理软件，功能最完备，各数据库或大学图书馆等和它的兼容也是最好。它的Filter和style
也最为丰富，而且可以自己创建修改。看看周围的人，大部分都是Endnote的用户。
Zotero作为一个新的文件管理系统，与Endnote相比还是稚嫩了些，特别对于国内数据库的支持不佳，更是限制了它的应用。
不过，Zotero作为Firefox浏览器的插件，还是有一些特别之处。
第一，便携。Firefox是有Portable版本的，当然Zotero也就是Portable了，也就是说可以把火狐和Zotero放到U盘里，在任何一台电脑上都可以 使用。而Endnote就没有这么方便了。
第二，便利。使用电脑时，我们使用浏览器的时间要大大多于Endnote的时间，遇到有用的文献、网页或者需要做笔记，直接使用Zotero更加省时省力。而且它自动收集网页中文献信息的功能也大大方便了操作。
第三，
分享。EndnoteX以后可以把一个library发送成一个档案文件(.enlx)，使得文献交换更为方便。不过有时我们只需要几条文献时，这样操作
就大动干戈了。当然Endnote也支持所选部分文献的导出，但这样有不能够导出附件，包括图片、PDF等(此处为个人经验，是否Endnote也能导出
附件来还望您不吝赐教)。而Zotero就可以实现某条文献所有内容(题录、笔记、附件)的全部导出，而且可以为另一Zotero用户所完整接受。
第四，跟踪文献的收集。很多数据都支持检索式或者引文的提醒，会随时把新的内容发送到邮箱或者以RSS的形式发布。一般来说，查看这些都需要浏览器。有了Zotero，我们可以在查看的同时收集下有用的文献信息。
Zotero更适合于在日常工作、学习甚至娱乐时使用，而Endnote更适合在有明确目的时使用。有人说Zotero更像“知识管理软件”，
而
Endnote就是为文献服务的。两者可以实现互补，在日常工作中使用Zotero收集零散的资料，积累一定量之后将文献信息导入到Endnote中，使
用Endnote管理、引用文献信息。至于PDF、图片等附件的管理，我还是建议使用Zotero，方便且可以完整导出。
下面谈一下Zotero和Endnote中文献的互相导入。
Zotero导入Endnote：
1 选定文献，右键点选”export selected items”；如果是导入整个Library或者cellection可在相应图标上右键点选；
2 在弹出的对话框中选择导出的格式为”Refer/BibIX”, 选择文件目录，保存文件，格式为.txt;
3 在Endnote中打开一个library，执行“files-import”；
4 在对话框中选择刚才的.txt文件, Impott Option选Refer/BibIX，Text Translation选Unicode(UTF-8)。点确定后即可导入。
Endnote导入Zotero：
1 选择文献后，执行“files-export”；
2 选择Output Style为Endnote Export，命名后导入，得到.txt文件。
3 在Zotero中执行“actions-import” ，选择得到的文件，点确定即可导入。
上述导入方式仅能实现文献题录的导入。
BBS上的一个帖子，问题是 def a():
def b():
x += 1
x = 1
print "a: ", x
b()
print "b: ", x
def c():
def d():
x[0] = [4]
x = [3]
print "c: ", x[0]
d()
print "d: ", x[0] 运行a()会报UnboundLocalError: local variable ‘x’ referenced before assignment
但是运行c()会正确地显示3和4。 原因在于原因在于CPython实现closure的方式和常见的functional language不同，采用了flat closures实现。 “If a name is bound anywhere within a code block, all uses of the
name within the block are treated as references to the current block.” 在第一个例子中，b函数x += 1对x进行赋值，rebind了这个对象，于是Python查找x的时候只会在local environment中搜索，于是就有了UnboundLocalError。 换句话说，如果没有修改这个值，比如b中仅仅简单的输出了x，程序是可以正常运行的，因为此时搜索的范围是nearest enclosing function region。 而d方法并没有rebind x变量，只是修改了x指向的对象的值而已。如果把赋值语句改成x = [4]，那么结果就和原来不一样了，因为此时发生了x的rebind。 所以Python中的closure可以理解为是只读的。 另外第二个例子也是这篇文章中提到的一种workaround：把要通过inner function修改的变量包装到数组里，然后在inner function中访问这个数组。 至于为什么Python中enclosed function不能修改enclosing function的binding，文中提到了主要原因还是在于Guido反对这么做。因为这样会导致本应该作为类的实例保存的对象被声明了本地变量。 参考网站：http://www.python.org/dev/peps/pep-0227/
acm queue 9月的杂志的主题是The Concurrency Problem，力推了Erlang这个语言，其中有篇文章简单的介绍了下这个message-oriented语言。 查了下这个名字的读法，正确的读法应该是air-lang，这里元音a的发音和bang中的a一样。 文章中的第一个程序就有点令人费解，主要原因在于Erlang的语法和一般的imperative language差别很大，和functional language比较类似，但是本质上也有很大的不同。 以Java的一个计数程序为例 // A shared counter.
public class Sequence {
private int nextVal = 0;
// Retrieve counter and increment.
public synchronized int getNext() {
return nextVal++;
}
// Re-initialize counter to zero.
public synchronized void reset() {
nextVal = 0;
}
} 这个程序的功能不用多说了，一个同步的计数程序。它的Erlang翻译版的代码为 -module(sequence1).
-export([make_sequence/0, get_next/1, reset/1]).
% Create a new shared counter.
make_sequence() ->
spawn(fun() -> sequence_loop(0)end).
sequence_loop(N) ->
receive
{From, get_next} ->
From!{self(), N},
sequence_loop(N + 1)<SEMI>
reset ->
sequence_loop(0)
end.
% Retrieve counter and increment.
get_next(Sequence) ->
Sequence!{self(), get_next},
receive
{Sequence, N} -> N
end.
% Re-initialize counter to zero.
reset(Sequence) ->
Sequence! reset. 初看这个程序自然是一头雾水，不过程序的函数式风格味还是很浓的。 前面提到，Erlang是基于message的，或者说message sending机制是包含在语言系统内部的，语法就是 pid ! message 接下来再来分析这个简单的程序。开头两行是模块和函数声明，略去。make_sequence开始这个进程，spawn/1内置函数创建一个新的进程，并返回pid到调用者。 初始时运行的函数是sequence_loop(0)，这个函数接收两种信息，用receive表达式声明：如果收到形式是{From,
get_next}的信息，就返回当前的N并调用sequence_loop(N+1)，这样下一次收到同样的信息时就能返回N+1了；reset则等价
于Java版本中的n=0语句。 get_next/1则是发送给pid为Sequence的进程 {self(), get_next}
这样一个信息，上面解释的sequence_loop/1函数收到这个信息后会返回一个 {self(), N}
的tuple给get_next/1，收到这个信息后get_next/1就能返回N这个值了。 最后reset/1函数则是发送给Sequence一个reset信息。 这个简单的程序里能大致窥见一些Erlang的特点，尤其是它基于信息发送的本质。
09月 18, 2008 第一个testkernel在Xen中的载入The Definitive Guide to Xen中第二章的例子，make成功后运行xen create domain_config，报错 Error: (2, ‘Invalid kernel’, ‘xc_dom_compat_check: guest type xen-3.0-x86_32 not supported by xen kernel, sorry\n’)
google之后发现是虚拟机类型设置的问题，运行xm info可以看到 xen_caps : xen-3.0-x86_32p
末尾的p表示Xen内核开启了PAE模式，所以载入的kernel也必须开启PAE，在bootstrap.x86_32.S中加入PAE=yes选项即可。 09月 25, 2008 DomainU中调用do_console_ioThe Definitive Guide to Xen第二章的Exercise，通过调用hypercall page中的console_io项输出Hello World。 void start_kernel(start_info_t * start_info)
{
HYPERVISOR_console_io(CONSOLEIO_write,12,"Hello World\n");
while(1);
} 但是默认选项编译和启动的Xen是不会保留DomainU中输出的信息。参考drivers/char/console.c，可以看到主要有两个选项控制了DomainU的do_console_io输出： #ifndef VERBOSE
/* Only domain 0 may access the emergency console. */
if ( current->domain->domain_id != 0 )
return -EPERM;
#endif
if ( opt_console_to_ring )
{
for ( kptr = kbuf; *kptr != '\0'; kptr++ )
putchar_console_ring(*kptr);
send_guest_global_virq(dom0, VIRQ_CON_RING);
} VERBOSE选项可以在编译Xen的时候开启debug选项，而opt_console_to_ring则是一个启动选项，在grub的启动选项中增加loglvl=all guest_loglvl=all console_to_ring即可。 重启Xen后就能通过xm dmesg看到Hello World了。 09月 25, 2008 Xen: Remove support for non-PAE 32-bit看来我还是用Xen 3.1吧 = = Subject: [Xen-devel] [PATCH] xen: remove support for non-PAE 32-bitLink to this message From: Jeremy Fitzhardinge (jer…@goop.org) Date: 05/09/2008 04:05:34 AM List: com.xensource.lists.xen-devel Non-PAE operation has been deprecated in Xen for a while, and is rarely tested or used. xen-unstable has now officially dropped non-PAE support. Since Xen/pvops’ non-PAE support has also been broken for a while, we may as well completely drop it altogether. 10月 07, 2008 IA-32 Memory Virtualizationhttp://www.intel.com/technology/itj/2006/v10i3/3-xen/4-extending-with-intel-vt.htm 上图为full virtulization的情况，即不修改Guest OS的行为时的解决方案。Xen为每个Guest OS维护了一张shadow page table，其中映射的地址为machine address。一种比较高效的方案是设置Guest OS的page table为只读，当Guest OS试图修改这个虚拟页表时，发生page fault被Xen截获，Xen修改shadow page table中相应的数据（把pseudo-physical address转化成machine address）。另外一个优化是guest page table被修改时不修改shadow page table，只是把它放到一个待更新列表中，等Guest OS执行了刷新tlb的指令后再一次性更新。 The Definitive Guide to Xen上还提到了另一种基于full paravirtulization和shadow page table之间的方案。Xen把Guest OS的page table置为只读，当Guest OS试图修改page table时，Xen捕获到page fault，把page directory中对应的入口置为无效，再把page table改成可写让Guest OS修改。由于page directory中对应的入口被设成无效了，下次访问该地址时还是会发生page fault，这时候Xen再修改page directory和page table的对应项就行了。 这种方法意味着Guest OS中内核管理模块直接和machine address打交道，而其他部分则仍然使用pseudo-physical address。另外这种情况下page directory不能被Guest OS修改。 另外Xen还用到了段机制，用来为Xen保留地址空间开始的64M内存。
好不容易找到的一个php，直接贴这儿了，方便其他网友。 wordpress的wp-syntax插件用的也是geshi，所以同样也适用于wp-syntax <?php
/*************************************************************************************
* erlang.php
* --------
* Author: Uwe Dauernheim (uwe@dauernheim.net)
* Copyright: (c) 2008 Uwe Dauernheim (http://www.kreisquadratur.de/)
* Release Version: 1\.0\.0
* Date Started: 2008-09-27
*
* Erlang language file for GeSHi.
*
* CHANGES
* -------
* 2008-09-27 (1.0.0)
* [ ] First Release
*
* 2008-09-28 (1.0.0.1)
* [!] Bug fixed with keyword module.
* [+] Added more function names
*
* TODO (updated 2008-09-27)
* -------------------------
* [!] Stop ';' from being transformed to '<SEMI>'
*
************************************************************************************/
$language_data = array (
'LANG_NAME' => 'Erlang',
'COMMENT_SINGLE' => array(1 => '%'),
'CASE_KEYWORDS' => GESHI_CAPS_NO_CHANGE,
'QUOTEMARKS' => array('"'),
'HARDQUOTE' => array("'", "'"),
'HARDESCAPE' => array('\\\'',),
'ESCAPE_CHAR' => '\\',
'KEYWORDS' => array(
1 => array(
'module', 'export', 'import', 'author', 'behaviour'
),
2 => array(
'case', 'of', 'if', 'end', 'receive', 'after'
),
3 => array(
// erlang
'set_cookie', 'get_cookie',
// io
'format', 'fwrite', 'fread',
// gen_tcp
'listen', 'accept', 'close',
// gen_server
'call', 'start_link'
)
),
'SYMBOLS' => array(
':', '=', '!', '|'
),
'CASE_SENSITIVE' => array(
GESHI_COMMENTS => false,
1 => true,
2 => true,
3 => true
),
'STYLES' => array(
'KEYWORDS' => array(
1 => 'color: #b1b100;',
2 => 'color: #b1b100;',
3 => 'color: #000066;'
),
'COMMENTS' => array(
1 => 'color: #666666; font-style: italic;',
2 => 'color: #009966; font-style: italic;',
3 => 'color: #0000ff;',
4 => 'color: #cc0000; font-style: italic;',
5 => 'color: #0000ff;',
'MULTI' => 'color: #666666; font-style: italic;'
),
'ESCAPE_CHAR' => array(
0 => 'color: #000099; font-weight: bold;',
'HARD' => 'color: #000099; font-weight: bold;'
),
'BRACKETS' => array(
0 => 'color: #009900;'
),
'STRINGS' => array(
0 => 'color: #ff0000;',
'HARD' => 'color: #ff0000;'
),
'NUMBERS' => array(
0 => 'color: #cc66cc;'
),
'METHODS' => array(
1 => 'color: #006600;',
2 => 'color: #006600;'
),
'SYMBOLS' => array(
0 => 'color: #339933;'
),
'REGEXPS' => array(
0 => 'color: #0000ff;',
4 => 'color: #009999;',
),
'SCRIPT' => array(
)
),
'URLS' => array(
1 => '',
2 => '',
3 => 'http://www.erlang.org/doc/man/{FNAMEL}.html'
),
'OOLANG' => true,
'OBJECT_SPLITTERS' => array(
1 => '->',
2 => ':'
),
'REGEXPS' => array(
// Variable
0 => '[A-Z][_a-zA-Z0-9]*',
// File Descriptor
4 => '<[a-zA-Z_][a-zA-Z0-9_]*>'
),
'STRICT_MODE_APPLIES' => GESHI_NEVER,
'TAB_WIDTH' => 4
);
?>
依然是内网日志的汇总
1. sysenter的介绍
http://www.codeguru.com/cpp/w-p/system/devicedriverdevelopment/article.php/c8223
System Call Optimization with the SYSENTER Instruction
by John Gulbrandsen
Windows下的
2. The SLUB allocator
slab的改进版本
http://lwn.net/Articles/229984/
http://lwn.net/Articles/229096/
Christoph’s response is the SLUB allocator, a drop-in replacement for the slab code. SLUB promises better performance and scalability by dropping most of the queues and related overhead and simplifying the slab structure in general, while retaining the current slab allocator interface.
Wider use may be in the cards: the SLUB allocator is in the -mm tree now and could hit the mainline as soon as 2.6.22. The simplified code is attractive, as is the claimed 5-10% performance increase. If merged, SLUB is likely to coexist with the current slab allocator (and the SLOB allocator intended for small systems) for some time. In the longer term, the current slab code may be approaching the end of its life.
3. Compilers and More: Parallel Programming Made Easy?
http://www.hpcwire.com/features/Compilers_and_More_Parallel_Programming_Made_Easy.html
by Michael Wolfe, Compiler Engineer, The Portland Group, Inc.
4. OpenCL slides, SIGGRAPH '08
发信人: jjgod (while(!asleep()) sheep++;), 信区: CSArch
标 题: SIGGRAPH 08 上的 OpenCL slides
发信站: 水木社区 (Mon Sep 15 01:32:03 2008), 站内
※ 来源:·水木社区 newsmth.net·[FROM: 125.33.176.*]
附件: munshi-opencl.pdf (1338 KB) 链接:
http://att.newsmth.net/att.php?p.272.35430.226.pdf
全文链接：http://www.newsmth.net/bbscon.php?bid=272&id=35430
5. linux-gate.so
http://www.trilithium.com/johan/2005/08/linux-gate/
linux下使用sysenter的机制
发信人: Zellux (null), 信区: Software_06 标 题: OSLab之中断处理 发信站: 日月光华 (2008年08月30日20:15:58 星期六), 站内信件 1. 准备工作 在开始分析Support Code之前，先配置下我们的Source Insight，使它能够支持.s文件的搜索。 在Options->Document Options->Document Types中选择x86 Asm Source File，在File fileter中增加一个*.s，变成*.asm;*.inc;*.s 然后在Project->Add and Remove Project Files中重新将整个oslab的目录加入，这样以后进行文本搜索时.s文件也不会漏掉了。 2. Source Insight使用 接下来简单分析下内核启动的过程，在浏览代码的过程中可以迅速的掌握Source Insight的使用技巧。 lib/multiboot /multiboot.s完成了初始化工作，可以看到其中一句call EXT(multiboot_main)调用了C函数multiboot_main，使用ctrl+/搜索包含multiboot_main的所有文件，最终base_multiboot_main.c中找到了它的定义。依次进行cpu、内存的初 始化，然后开启中断，跳转到kernel_main函数，也是Lab1中所要改写的函数之一。另外 在这里可以通过ctrl+单击或者ctrl+=跳转到相应的函数定义处，很方便。 3. irq处理初始化工作 来看下Lab 1的重点之一，irq的处理。跟踪multiboot_main->base_cpu_setup->base_cp u_init->base_irq_init，可以看到这行代码 gate_init(base_idt, base_irq_inittab, KERNEL_CS); 继续使用ctrl+/找到base_irq_inittab的藏身之处：base_irq_inittab.s 4. base_irq_inittab.s 这个汇编文件做了不少重复性工作，方便我们在c语言级别实现各种handler。 GATE_INITTAB_BEGIN(base_irq_inittab) /* irq处理函数表的起始，还记得jump table 吗？ */ MASTER(0, 0) /* irq0 对应的函数 */ 来看看这个MASTER(0, 0)宏展开后是什么样子： #define MASTER(irq, num) \ GATE_ENTRY(BASE_IRQ_MASTER_BASE + (num), 0f, ACC_PL_K|ACC_INTR_GATE) ;\ P2ALIGN(TEXT_ALIGN) ;\ 0: ;\ pushl $(irq) /* error code = irq vector */ ;\ pushl $BASE_IRQ_MASTER_BASE + (num) /* trap number */ ;\ pusha /* save general registers */ ;\ movl $(irq),%ecx /* irq vector number */ ;\ movb $1 << num,%dl /* pic mask for this irq */ ;\ jmp master_ints 依次push irq号，trap号（0x20+irq号），通用寄存器（eax ecx等）入栈，把irq号保 存到ecx寄存器，然后跳转到master_ints，master_ints是所有master interrupts公用 的代码。 跳过master_ints的前几行，从第七行开始 /* Acknowledge the interrupt */ movb $0x20,%al outb %al,$0x20 /* Save the rest of the standard trap frame (oskit/x86/base_trap.h). */ pushl %ds pushl %es pushl %fs pushl %gs /* Load the kernel's segment registers. */ movw %ss,%dx movw %dx,%ds movw %dx,%es /* Increment the hardware interrupt nesting counter */ incb EXT(base_irq_nest) /* Load the handler vector */ movl EXT(base_irq_handlers)(,%ecx,4),%esi 注释写得很详细，首先发送0x20到0x20端口，也就是Lab1文档上所说的发送INT_CTL_DON E到INT_CTL_REG，看来这一步support code已经替我们完成了。接下来保存四个段寄存 器ds es fs gs，并读入kernel态的段寄存器信息。 最后一句很关键，把base_irq_handlers + %ecx * 4这个值保存到了esi寄存器中，%ecx 中保存了irq号，而*4则是一个函数指针的大小，那么base_irq_handlers是什么呢？继 续用ctrl+/搜索，可以在base_irq.c中找到这个数组的定义 unsigned int (*base_irq_handlers[BASE_IRQ_COUNT])(struct trap_state *ts) 且初始时这个数组的每一项都是base_irq_default_handler 看来这句汇编代码的功能是把处理irq对应的函数地址保存到了esi寄存器中。 为了证实这一点，继续看base_irq_inittab.s的代码： #else /* Call the interrupt handler with the trap frame as a parameter */ pushl %esp call *%esi popl %edx #endif 果然，在保存了esp值后，紧接着就调用了esi指向的那个函数。而从那个函数返回后， 之前在栈上保存的相关信息都被恢复了： /* blah blah blah */ /* Return from the interrupt */ popl %gs popl %fs popl %es popl %ds popa addl $4*2,%esp /* Pop trap number and error code */ iret 这样就恢复到了进入这个irq处理单元前的状态，文档中所要求的保存通用寄存器这一步 其实在这里也已经完成了，不需要我们自己写代码。 好了，这样一分析后，我们要做的事情就很简单，就是把base_irq_handlers数组中的对 应项改成相应的handler函数就行了。 注意index是相应的idt_entry号减去BASE_IRQ_SLAVE_BASE，或者直接使用IRQ号。 另外这个数组的初始值都是base_irq_default_handler，用ctrl+左键跳到这个函数的定 义，可以看到这个函数只有一句简单的输出语句： printf("Unexpected interrupt %d\n", ts->err); 而这就是没有注册handler前我们所看到的那句Unexpected interrupt 0的来源了。 5. struct trap_state *ts 所有的handler函数的参数都是一个struct trap_state *ts，这个参数是哪来的呢？ 注意call *%esi的前一行 /* Call the interrupt handler with the trap frame as a parameter */ pushl %esp 这里把当前的esp当作指向ts的指针传给了handler，列一下从esp指向的地址开始的内容 ，也就是在此之前push入栈的内容： pushl $(irq) /* error code = irq vector */ ;\ pushl $BASE_IRQ_MASTER_BASE + (num) /* trap number */ ;\ pusha /* save general registers */ ;\ pushl %ds pushl %es pushl %fs pushl %gs 再看一下trap_state的定义，你会发现正好和push的顺序相反： /* Saved segment registers */ unsigned int gs; unsigned int fs; unsigned int es; unsigned int ds; /* PUSHA register state frame */ unsigned int edi; unsigned int esi; unsigned int ebp; unsigned int cr2; /* we save cr2 over esp for page faults */ unsigned int ebx; unsigned int edx; unsigned int ecx; unsigned int eax; /* Processor trap number, 0-31. */ unsigned int trapno; /* Error code pushed by the processor, 0 if none. */ unsigned int err; 而这个定义后面的 /* Processor state frame */ unsigned int eip; unsigned int cs; unsigned int eflags; unsigned int esp; unsigned int ss; 则是发生interrupt时硬件自动push的五个数据（参见Understand the Linux Kernel） 也就是说，ts指针指向的是调用当前handler前的寄存器状态，也是当前handler结束后 用来恢复的寄存器状态，了解这一点对以后的几个lab帮助很大。 p.s. 另外提一句和这个lab无关的话，非vm86模式下栈上是不会有v86_es等四个寄存器 信息的，所以以后根据task_struct指针计算*ts的地址时使用的偏移量不应该是sizeof( struct trap_state) 6. The End 这样差不多就把support code中处理interrupt的方法过了一遍（另外还有base_trap_in ittab.s，不过和irq的处理很相似） 了解这些后Lab1就比较简单了，不需要任何内嵌汇编代码即可完成。
摘要: 美国为什么需要这么多大学生，而中国培育出这么多优秀大学生为什么失业？难道是我们学生程度不够？难道是我们同学不够用功？难道是我们同学专业不对口？那我告诉所有读者，为什么大学生就业难…… 阅读全文
用ctags -R或者ctags * -R的时候只能生成当前目录下的tag，检查了半天发现原来这个版本的ctags的参数顺序只能老老实实的来：ctags -R *
太囧了，总归要bs下的，虽说也有那么一点点可能是bash解析参数时的问题，不过我猜问题来源还是这个低版本的ctags = =
话说我也挺圡的，不习惯用source insight，还是喜欢用vim写代码
没心思看离散，也不准备坚持看没有荷兰的欧洲杯决赛。闲着点好友的Q-Zone，原来Q-Zone首先会判断你的浏览器，如果是Firefox它会重定向到RSS阅读界面。
安然在开学后2个月写的一篇日志，“记忆里的名单”，惊喜的看到有我。也列出了一张属于我的名单。好，等待时间的遴选。
“于是想 如果有个妹妹 我要告诉她 好好放肆猖狂 做不可思议的事情 为友情和少年青涩的爱情花心思 做只是喜欢没有功利目的的事情 这么好的年华 就是用来这样浪费 和珍惜的~”
可惜我只保持了四五个月的这种疯狂，现在依然纠结于功利的选择。有时候曾想，或许那次失败更适合我，或许我终将把这么一条平淡无奇的路走到尽头。“表面强者”，或许还是很有道理的。
看到fofo的博的文字，“我要去杭州，把所有的事情抛掉，不管后果。这个地方太让人压抑，尽管有很玩得来的室友，有很好的足球队的队友，可以看很多以前爸妈不让看的喜欢的书还有过米的比赛，吃的东西也都很习惯，还是会在天气很好的星期天下午突然想起曾经在冬日的阳光照射下一家人在阳台上围着一张桌子吃饭的情景，还是会在一个人骑在去计算机协会的路上很难过地想着再也不会有那么四个或者五个人在一起吃完小炒放肆地在铺满夕阳的校园小路上勾肩搭背地行走了，还是会在一百多个人的课堂上怀念起那些艰苦却简单的日子里所有的笑声，还是会在网吧包夜的时候想起初中时捏着饭钱偷偷摸摸地去电脑房玩星际……想找找朋友们，调整一下自己的心情。”
真的找不回来了。在写这篇博文时也找不到以前写字的感觉了。
明天离散考试，某个记录或许将要因此打破。
摘要: 一篇关于函数式编程的介绍，在水木Java版引起了热烈讨论。 阅读全文
1. framwork/policies/Singleton.h Singleton模式，可以指定相应的线程模型、创建策略和生命期控制策略。 对于全局范围的Singleton实例，定义了若干个宏便于访问，例如  #define sLog MaNGOS::Singleton<Log>::Instance()
#define sMaster MaNGOS::Singleton<Master>::Instance()
Singleton的定义：  
namespace MaNGOS
{
template
<
typename T,
class ThreadingModel = MaNGOS::SingleThreaded<T>,
class CreatePolicy = MaNGOS::OperatorNew<T>,
class LifeTimePolicy = MaNGOS::ObjectLifeTime<T>
>
class MANGOS_DLL_DECL Singleton
{
public:
static T& Instance();
protected:
Singleton() {};
private:
// Prohibited actions this does not prevent hijacking.
Singleton(const Singleton &);
Singleton& operator=(const Singleton &);
// Singleton Helpers
static void DestroySingleton();
// data structure
typedef typename ThreadingModel::Lock Guard;
static T *si_instance;
static bool si_destroyed;
};
}
#endif
不知道这里的注释Prohibited actions...this does not prevent hijacking.是什么意思，copy constructor和hijacking有什么关系呢？
另外注意这行typedef typename ThreadingModel::Lock Guard;，原来typedef还可以用在函数上。
Singleton的Instance方法用的是标准的double-checked lock方法，关于DCL可以参考这篇博文http://www.blogjava.net/zellux/archive/2008/04/07/191365.html
2. Explicit Constructors
game/WorkPacket.h中看到的语法，防止构造函数中参数的隐式转型
比如explicit String(int n); 用String('c')声明时就会报错
一套基于文件系统的安全方案，主要通过隔离运行不可信任的程序、taint记录、事故恢复。
我的presentation：
http://docs.google.com/Presentation?id=dcjk4xx7_473cv5ddgc8
出于时间考虑没有提到paper中进程间通信的解决方法
摘要: 一篇介绍一种全新的Web架构，另一篇介绍虚拟机的探测方法 阅读全文
摘要: 发信人: NetMD (C++), 信区: CPlusPlus
标 题: [FAQ] C/C++中的序列点
发信站: 水木社区 (Wed Feb 7 01:13:41 2007), 站内 阅读全文
VIM Calender是个很好用的写日记的插件( http://www.vim.org/scripts/script.php?script_id=52) 水木上的rmrf写了一个同步VIM Calender和Google Calender的脚本( http://code.google.com/p/diaryvgc/downloads/list) 想到blogger.com支持通过发送邮件发布日志，于是我也写了个把VIM Calender中的日记发布到blogger.com的脚本。 这个脚本把发布情况记录在diary/poster.log中，以后每次执行只会发布最新的日志，同时考虑到当天的日记可能会被修改（blogger.com似乎不支持通过email修改日志），所以当天的日记不会被发布。 使用的时候修改开头几行的配置信息即可 #!/usr/bin/python
# A script for posting diaries created by VIM Calender to blogger.com
# Author: Wang Yuanxuan <zellux@gmail.com>
import smtplib, os, re, datetime
from email.mime.text import MIMEText
fromaddr = xxxxx@fudan.edu.cn'
toaddr = xxxx.xxxx@blogger.com'
smtpserver = 'mail.fudan.edu.cn'
diarydir = '/home/user_name/diary'
username = 'xxxxxx'
password = 'xxxxxx'
logpath = diarydir + '/poster.log'
def PostMail(title, content):
msg = MIMEText(content + '\r\n#end\r\n')
msg['Subject'] = title
msg['From'] = fromaddr
msg['To'] = toaddr
server = smtplib.SMTP(smtpserver)
server.login(username, password)
# server.set_debuglevel(1)
server.sendmail(fromaddr, [toaddr], msg.as_string())
server.quit()
# Load log file. Create a new one if not exist.
posted = []
if os.path.isfile(logpath):
temp = open(logpath, 'r')
posted = [line[:-1] for line in temp.readlines()]
log = open(logpath, 'a')
else:
print "A new poster log has been created at " + logpath
log = open(logpath, 'w')
pattern = r'(\d{4})/(\d{1,2})/(\d{1,2}).cal$'
scanner = re.compile(pattern)
for (top, dirname, filenames) in os.walk(diarydir):
for filename in filenames:
fullpath = os.path.join(top, filename)
if scanner.search(fullpath):
(year, month, day) = scanner.search(fullpath).groups()
filedate = datetime.date(int(year), int(month), int(day))
title = filedate.isoformat()
if filedate == datetime.date.today():
continue
if fullpath not in posted:
log.write(fullpath + '\n')
text = open(fullpath).read()
PostMail(title, text)
print 'The diary ' + title + ' has been posted'
log.close()
这书的数学分析方面有点过于简单了，连绝对值、二维坐标系是个什么东东都会给你解释一下，所以看起来很快。
第一章 经济学十大原理
第二章 像经济学家一样思考
生产可能性边界(production possibilites frontier)通常是凹向原点的形状。
实证表述(positive statements)：企图描述世界是什么的观点。经济学的许多内容是实证的。
规范表述(normative statements)：企图描述世界应该是什么的观点。
第三章 相互依赖性与贸易的好处
机会成本与比较优势
第四章 供给与需求的市场力量
第五章 弹性及其应用
需求价格弹性 = 需求量变动百分比 / 价格变动百分比
供给价格弹性 = 供给变动百分比 / 价格变动百分比
例：由于毒品的需求缺乏弹性，禁毒引起的毒品价格提高的比例大于毒品使用减少的比例，因此禁毒会增加与毒品相关的犯罪。（短期）
第六章 供给、需求与政府政策
限制性价格上限导致短缺，限制性价格下限导致过剩。
例：最低工资法导致失业。
一旦市场达到新均衡，无论向谁征税，都是买者与卖者分摊税收负担。
例：由于劳动的供给远比劳动的需求缺乏弹性，是工人而不是企业承担了大部分工薪税的负担。
发信人: bluegene (蓝色基因||多看paper才是王道), 信区: Quant
标 题: 美国次贷危机之通俗演义 zz (转载)
发信站: BBS 未名空间站 (Fri Mar 21 01:24:10 2008)
【 以下文字转载自 ChinaNews 讨论区 】
发信人: chaoz (饭局局长), 信区: ChinaNews
标 题: 美国次贷危机之通俗演义 zz
发信站: BBS 未名空间站 (Thu Mar 20 23:49:57 2008)
在美国，贷款是非常普遍的现象，从房子到汽车，从信用卡到电话账单，贷款无处不在。当地人很少全款买房，通常都是长时间贷款。可是我们也知道，在这里失业
和再就业是很常见的现象。这些收入并不稳定甚至根本没有收入的人，他们怎么买房呢？因为信用等级达不到标准，他们就被定义为次级贷款者。
大约从10年前开始，那个时候贷款公司漫天的广告就出现在电视上、报纸上、街头，抑或在你的信箱里塞满诱人的传单：
“你想过中产阶级的生活吗？买房吧！”
“积蓄不够吗？贷款吧！”
“没有收入吗？找阿牛贷款公司吧！”
“首付也付不起？我们提供零首付！”
“担心利息太高？头两年我们提供3％的优惠利率！”
“每个月还是付不起？没关系，头24个月你只需要支付利息，贷款的本金可以两年后再付！想想看，两年后你肯定已经找到工作或者被提升为经理了，到时候还怕付不起！”
“担心两年后还是还不起？哎呀，你也真是太小心了，看看现在的房子比两年前涨了多少，到时候你转手卖给别人啊，不仅白住两年，还可能赚一笔呢！再说了，又不用你出钱，我都相信你一定行的，难道我敢贷，你还不敢借？”
在这样的诱惑下，无数美国市民毫不犹豫地选择了贷款买房。（你替他们担心两年后的债务？向来自我感觉良好的美国市民会告诉你，演电影的都能当上州长，两年后说不定我还能竞选总统呢。）
阿牛贷款公司短短几个月就取得了惊人的业绩，可是钱都贷出去了，能不能收回来呢？公司的董事长——阿牛先生，那也是熟读美国经济史的人物，不可能不知道房
地产市场也是有风险的，所以这笔收益看来不能独吞，要找个合伙人分担风险才行。于是阿牛找到美国经济界的带头大哥——投行。这些家伙可都是名字响当当的主
儿（美林、高盛、摩根），他们每天做什么呢？就是吃饱了闲着也是闲着，于是找来诺贝尔经济学家，找来哈佛教授，用上最新的经济数据模型，一番鼓捣之后，弄
出几份分析报告，从而评价一下某某股票是否值得买进，某某国家的股市已经有泡沫了，一群在风险评估市场里面骗吃骗喝的主儿，你说他们看到这里面有风险没？
用脚都看得到！可是有利润啊，那还犹豫什么，接手搞吧！于是经济学家、大学教授以数据模型、老三样评估之后，重新包装一下，就弄出了新产品——CDO
（注： Collateralized Debt
Obligation，债务抵押债券），说穿了就是债券，通过发行和销售这个CDO债券，让债券的持有人来分担房屋贷款的风险。
光这样卖，风险太高还是没人买啊，假设原来的债券风险等级是6，属于中等偏高。于是投行把它分成高级和普通CDO两个部分，发生债务危机时，高级CDO享
有优先赔付的权利。这样两部分的风险等级分别变成了4和8，总风险不变，但是前者就属于中低风险债券了，凭投行三寸不烂“金”舌，当然卖了个满堂彩！可是
剩下的风险等级8的高风险债券怎么办呢？
于是投行找到了对冲基金，对冲基金又是什么人，那可是在全世界金融界买空卖多、呼风唤雨的角色，过的就是刀口舔血的日子，这点风险小意思！于是凭借着老关
系，在世界范围内找利率最低的银行借来钱，然后大举买入这部分普通CDO债券，2006年以前，日本央行贷款利率仅为1．5％；普通CDO利率可能达到
12％，所以光靠利息差对冲基金就赚得盆满钵满了。
这样一来，奇妙的事情发生了，2001年末，美国的房地产一路飙升，短短几年就翻了一倍多，这样一来就如同阿牛贷款公司开头的广告一样，根本不会出现还不
起房款的事情，就算没钱还，把房子一卖还可以赚一笔钱。结果是从贷款买房的人，到阿牛贷款公司，到各大投行，到各个银行，到对冲基金人人都赚钱，但是投行
却不太高兴了！当初是觉得普通CDO风险太高，才扔给对冲基金的，没想到这帮家伙比自己赚的还多，净值一个劲地涨，早知道自己留着玩了，于是投行也开始买
入对冲基金，打算分一杯羹了。这就好像“老黑”家里有馊了的饭菜，正巧看见隔壁邻居那只讨厌的小花狗，本来打算毒它一把，没想到小花狗吃了不但没事，反而
还越长越壮了，“老黑”这下可蒙了，难道馊了的饭菜营养更好，于是自己也开始吃了！
这下又把对冲基金乐坏了，他们是什么人，手里有1块钱，就能想办法借10块钱来玩的土匪啊，现在拿着抢手的CDO还能老实？于是他们又把手里的CDO债券
抵押给银行，换得10倍的贷款，然后继续追着投行买普通CDO。嘿，当初可是签了协议，这些CDO都归我们的！！！投行心里那个不爽啊，除了继续闷声买对
冲基金之外，他们又想出了一个新产品，就叫CDS （注：Credit Default
Swap，信用违约交换）好了，华尔街就是这些天才产品的温床：不是都觉得原来的CDO风险高吗，那我投保好了，每年从CDO里面拿出一部分钱作为保金，
白送给保险公司，但是将来出了风险，大家一起承担。
保险公司想，不错啊，眼下CDO这么赚钱，1分钱都不用出就分利润，这不是每年白送钱给我们吗？干了！
对冲基金想，不错啊，已经赚了几年了，以后风险越来越大，光是分一部分利润出去，就有保险公司承担一半风险，干了！
于是再次皆大欢喜，CDS也卖火了！但是事情到这里还没有结束：因为“聪明”的华尔街人又想出了基于CDS的创新产品！我们假设CDS已经为我们带来了
50亿元的收益，现在我新发行一个“三毛”基金，这个基金是专门投资买入CDS的，显然这个建立在之前一系列产品之上的基金的风险是很高的，但是我把之前
已经赚的50亿元投入作为保证金，如果这个基金发生亏损，那么先用这50亿元垫付，只有这50亿元亏完了，你投资的本金才会开始亏损，而在这之前你是可以
提前赎回的，首发规模500亿元。天哪，还有比这个还爽的基金吗？1元面值买入的基金，亏到0．90元都不会亏自己的钱，赚了却每分钱都是自己的！评级机
构看到这个天才设想，简直是毫不犹豫：给予AAA评级！
结果这个“三毛”可卖疯了，各种养老基金、教育基金、理财产品，甚至其他国家的银行也纷纷买入。虽然首发规模是原定的500亿元，可是后续发行了多少亿，
简直已经无法估算了，但是保证金50亿元却没有变。如果现有规模5000亿元，那保证金就只能保证在基金净值不低于0．99元时，你不会亏钱了。
当时间走到了2006年年底，风光了整整5年的美国房地产终于从顶峰重重摔了下来，这条食物链也终于开始断裂。因为房价下跌，优惠贷款利率的时限到了之
后，先是普通民众无法偿还贷款，然后阿牛贷款公司倒闭，对冲基金大幅亏损，继而连累保险公司和贷款的银行，花旗、摩根相继发布巨额亏损报告，同时投资对冲
基金的各大投行也纷纷亏损，然后股市大跌，民众普遍亏钱，无法偿还房贷的民众继续增多……最终，美国次贷危机爆发。(屈直言)
次贷危机是否会酿成全球危机?
--
只要功夫深, 一夜夫妻百日恩.
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 141.219.]
摘要: 一种利用虚拟机进行的攻击手段(下篇) 阅读全文
Fight Club
1. 不能谈论斗阵俱乐部。 2. 不能谈论斗阵俱乐部。 3. 只要有人喊停，或者受伤，快累死了，打斗就得停。 4. 一次只能两人打 5. 一次一场 6. 脱掉衬衫和鞋子 7. 打斗没有时限 8. 只要你是初次参加，就一定得打。 太混乱了
秒速5センチメートル
“樱花飘落的速度，是每秒5厘米。” 凄美无奈的故事，有点像村上的《国境以南》，只是主人公最后仍然在寻找着对方。 新海诚的动画色彩很斑斓，很华丽。 写到这里，千千静听里正好随机播放到了那首One More Time, One More Chance，几百分之一的概率，呵呵。 晚上看风格截然不同的National Trasure: Book of Secrets
在机房电脑的Arch Linux上搭了个MediaWiki，作为自己的知识库。
前几天在水木上看到的想法，觉得这样很有成就感，尽管现在还没学多少东西。
一步一个脚印，慢慢扩充。
Mika的歌还真是好听。
Problem
Every bus in the Ekaterinburg city has a special man (or woman) called
conductor. When you ride the bus, you have to give money to the conductor.
We know that there are more then P% conductors and less then Q% conductors.
Your task is to determine a minimal possible number of Ekaterinburg citizens.
我只能说太挫了。。。精度问题搞了半天，看来浮点还是要尽量化成整型再算啊。
1 #include <iostream>
2 #include <cmath>
3
4 using namespace std;
5
6 int main()
7 {
8 double dp, dq;
9 cin >> dp >> dq;
10 int p = floor(dp * 100 + 0.5);
11 int q = floor(dq * 100 + 0.5);
12 for (int i = 1; ; i++) {
13 int a = p * i / 10000;
14 int b = q * i / 10000;
15 if ((a < b) && (q * i % 10000 > 0)) {
16 cout << i << endl;
17 return 0;
18 }
19 }
20 return 0;
21 }
22 还有个问题就是q*i是开区间还是闭区间，总之Wrong Answer了无数次后总算过了。。。
摘要: 算法导论第27章，在并行处理的条件下高效的排序算法。 阅读全文
因为MSN一开始会尝试连接crl.microsoft.com，把这个网站屏蔽了就行。
在hosts文件中加入
127.0.0.1 crl.microsoft.com
~/.vim/ftplugin/ 下有c.vim和cpp.vim
但是vim打开cpp和c文件时使用的配置都是c.vim中指定的
使用vim xxx.cpp -V跟踪了打开的配置列表，发现有这么一段
line 17: sourcing "/usr/share/vim/ftplugin/cpp.vim"
Searching for "ftplugin/c.vim ftplugin/c_*.vim ftplugin/c/*.vim" in "/home/wyx/.vim,/usr/share/vim,/usr/share/vim,
/usr/share/vim/after,/home/wyx/.vim/after"
Searching for "/home/wyx/.vim/ftplugin/c.vim"
line 12: sourcing "/home/wyx/.vim/ftplugin/c.vim"
原来/usr/share/vim/ftplugin/cpp.vim中直接调用了c.vim
runtime! ftplugin/c.vim ftplugin/c_*.vim ftplugin/c/*.vim
把这行注释掉，问题解决
要提高效率果然得远离网络，躺床上看paper理解起来快多了
总算把晚上要讲的ppt做出来了，囧
下午打球直到体力极限，一路淋雨跑回寝室，洗澡，感冒，低落。想回家。
有时候会想，几年后，真的就要在上海这个地方工作立足吗？
我想看一堆电影 想读一堆书 想学C# Lisp Python 想上ACM OJ网站切题 想参加一次TopCoder比赛 想学埙 想学钢琴 想睡觉 想看微经 想练英语 想看内核 想到处旅游
终会和现实冲突。于是我想退实验室。几个小时后又放弃这个决定。
终究是怕这怕那保守着缓慢前进的人。
计算机科学论坛最近举办了一个阅读样章，提交书评的活动，具体内容请见http://www.ieee.org.cn/dispbbs.asp?boardID=42&ID=61162。
这里我想针对样章上的一个问题谈谈自己的理解。
问题很简单，求二进制中1的个数。对于一个字节（8bit）的变量，求其二进制表示中"1"的个数，要求算法的执行效率尽可能的高。
先来看看样章上给出的几个算法：
解法一，每次除二，看是否为奇数，是的话就累计加一，最后这个结果就是二进制表示中1的个数。
解法二，同样用到一个循环，只是里面的操作用位移操作简化了。
1: int Count(int v)
2: {
3: int num = 0;
4: while (v) {
5: num += v & 0x01;
6: v >>= 1;
7: }
8: return num;
9: }
解法三，用到一个巧妙的与操作，v & (v -1 )每次能消去二进制表示中最后一位1，利用这个技巧可以减少一定的循环次数。
解法四，查表法，因为只有数据8bit，直接建一张表，包含各个数中1的个数，然后查表就行。复杂度O(1)。
1: int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };
2:
3: int Count(int v) {
4: return countTable[v];
5: }
好了，这就是样章上给出的四种方案，下面谈谈我的看法。
首先是对算法的衡量上，复杂度真的是唯一的标准吗？尤其对于这种数据规模给定，而且很小的情况下，复杂度其实是个比较次要的因素。
查表法的复杂度为O(1)，我用解法一，循环八次固定，复杂度也是O(1)。至于数据规模变大，变成32位整型，那查表法自然也不合适了。
其次，我觉得既然是这样一个很小的操作，衡量的尺度也必然要小，CPU时钟周期可以作为一个参考。
解法一里有若干次整数加法，若干次整数除法（一般的编译器都能把它优化成位移），还有几个循环分支判断，几个奇偶性判断（这个比较耗时间，根据CSAPP上的数据，一般一个branch penalty得耗掉14个左右的cycle），加起来大概几十个cycle吧。
再看解法四，查表法看似一次地址计算就能解决，但实际上这里用到一个访存操作，而且第一次访存的时候很有可能那个数组不在cache里，这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle（因为要访问内存）。所以对于这种“小操作”，这个算法的性能其实是很差的。
这里我再推荐几个解决这个问题的算法，以32位无符号整型为例。
1: int Count(unsigned x) {
2: x = x - ((x >> 1) & 0x55555555);
3: x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
4: x = (x + (x >> 4)) & 0x0F0F0F0F;
5: x = x + (x >> 8);
6: x = x + (x >> 16);
7: return x & 0x0000003F;
8: }
这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。
还有一个更巧妙的HAKMEM算法
1: int Count(unsigned x) {
2: unsigned n;
3:
4: n = (x >> 1) & 033333333333;
5: x = x - n;
6: n = (n >> 1) & 033333333333;
7: x = x - n;
8: x = (x + (x >> 3)) & 030707070707;
9: x = modu(x, 63);
10: return x;
11: }
首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。
因为2^6 = 64，也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，这里的等号表示同余。
这个程序只需要十条左右指令，而且不访存，速度很快。
由此可见，衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。
关于后面的两道扩展问题，问题一是问32位整型如何处理，这个上面已经讲了。
问题二是给定两个整数A和B，问A和B有多少位是不同的。
这个问题其实就是数1问题多了一个步骤，只要先算出A和B的异或结果，然后求这个值中1的个数就行了。
总体看来这本书还是很不错的，比较喜欢里面针对一个问题提出不同算法并不断改进的风格。这里提出一点个人的理解，望大家指正 ;-)
(by ZelluX http://www.blogjava.net/zellux)
摘要: 以下简单的整理来自游侠 netshow论坛的帖子 部分补充 阅读全文
摘要: 问题：
给定n个32位无符号整数，求出其中异或结果最大的两个整数。 阅读全文
转载请注明 作者 ZelluX
http://www.blogjava.net/zellux
看OOP教材时，提到了一个双检测锁定(Double-Checked Lock, DCL)的问题，但是书上没有多介绍，只是说这是一个和底层内存机制有关的漏洞。查阅了下相关资料，对这个问题大致有了点了解。
从头开始说吧。
在多线程的情况下Singleton模式会遇到不少问题，一个简单的例子
1: class Singleton {
2: private static Singleton instance = null;
3:
4: public static Singleton instance() {
5: if (instance == null) {
6: instance = new Singleton();
7: }
8: return instance;
9: }
10: }
假设这样一个场景，有两个线程调用Singleton.instance()，首先线程一判断instance是否等于null，判断完后一瞬间虚拟机把线程二调度为运行线程，线程二再次判断instance是否为null，然后创建一个Singleton实例，线程二的时间片用完后，线程一被唤醒，接下来它执行的代码依然是instance = new Singleton();
两次调用返回了不同的对象，出现问题了。
最简单的方法自然是在类被载入时就初始化这个对象：private static Singleton instance = new Singleton();
JLS(Java Language Specification)中规定了一个类只会被初始化一次，所以这样做肯定是没问题的。
但是如果要实现延迟初始化(Lazy initialization)，比如这个实例初始化时的参数要在运行期才能确定，应该怎么做呢？
依然有最简单的方法：使用synchronized关键字修饰初始化方法：
public synchronized static Singleton instance() {
if (instance == null) {
instance = new Singleton();
}
return instance;
}
这里有一个性能问题：多个线程同时访问这个方法时，会因为同步而导致每次只有一个线程运行，影响程序性能。而事实上初始化完毕后只需要简单的返回instance的引用就行了。
DCL是一个“看似”有效的解决方法，先把对应代码放上来吧：
1 : class Singleton {
2 : private static Singleton instance = null ;
3 :
4 : public static Singleton instance() {
5 : if (instance == null ) {
6 : synchronized (this) {
7 : if (instance == null)
8 : instance = new Singleton();
9 : }
10 : }
11 : return instance;
12 : }
13 : }
用JavaWorld上对应文章的标题来评论这种做法就是smart, but broken。来看原因：
Java编译器为了提高程序性能会进行指令调度，CPU在执行指令时同样出于性能会乱序执行（至少现在用的大多数通用处理器都是out-of-order的），另外cache的存在也会改变数据回写内存时的顺序[2]。JMM(Java Memory Model, 见[1])指出所有的这些优化都是允许的，只要运行结果和严格按顺序执行所得的结果一样即可。
Java假设每个线程都跑在自己的处理器上，享有自己的内存，和共享的主存交互。注意即使在单核上这种模型也是有意义的，考虑到cache和寄存器会保存部分临时变量。理论上每个线程修改自己的内存后，必须立即更新对应的主存内容。但是Java设计师们认为这种约束会影响程序性能，他们试着创造了一套让程序跑得更快、但又保证线程之间的交互与预期一致的内存模型。
synchronized关键字便是其中一把利器。事实上，synchronized块的实现和Linux中的信号量(semaphore)还是有区别的，前者过程中锁的获得和释放都会都会引发一次Memory Barrier来强制线程本地内存和主存之间的同步。通过这个机制，Java中的同步机制保证了synchronized块中指令的原子性(atomic)。
好了，回过头来看DCL问题。看起来访问一个未同步的instance字段不会产生什么问题，我们再次来假设一个场景：
线程一进入同步块，执行instance = new Singleton(); 线程二刚开始执行getResource();
按照顺序的话，接下来应该执行的步骤是 1) 分配新的Singleton对象的内存 2) 调用Singleton的构造器，初始化成员字段 3) instance被赋为指向新的对象的引用。
前面说过，编译器或处理器都为了提高性能都有可能进行指令的乱序执行，线程一的真正执行步骤可能是1) 分配内存 2) instance指向新对象 3) 初始化新实例。如果线程二在2完成后3执行前被唤醒，它看到了一个不为null的instance，跳出方法体走了，带着一个还没初始化的Singleton对象。
错误发生的一种情形就是这样，关于更详细的编译器指令调度导致的问题，可以参看这个网页 [4]。
[3] 中提供了一个编译器指令调度的证据
instance = new Singleton(); 这条命令在Symantec JIT中被编译成
0206106A mov eax,0F97E78h
0206106F call 01F6B210 ; 分配空间
02061074 mov dword ptr [ebp],eax ; EBP中保存了instance的地址
02061077 mov ecx,dword ptr [eax] ; 解引用，获得新的指针地址
02061079 mov dword ptr [ecx],100h ; 接下来四行是inline后的构造器
0206107F mov dword ptr [ecx+4],200h
02061086 mov dword ptr [ecx+8],400h
0206108D mov dword ptr [ecx+0Ch],0F84030h
可以看到，赋值完成在初始化之前，而这是JLS允许的。
另一种情形是，假设线程一安稳地完成Singleton对象的初始化，退出了同步块，并同步了和本地内存和主存。线程二来了，看到一个非空的引用，拿走。注意线程二没有执行一个Read Barrier，因为它根本就没进后面的同步块。所以很有可能此时它看到的数据是陈旧的。
还有很多人根据已知的几种提出了一个又一个fix的方法，但最终还是出现了更多的问题。可以参阅[3]中的介绍。
[5]中还说明了即使把instance字段声明为volatile还是无法避免错误的原因。
由此可见，安全的Singleton的构造一般只有两种方法，一是在类载入时就创建该实例，二是使用性能较差的synchronized方法。
(by ZelluX http://www.blogjava.net/zellux )
参考资料：
[1] Java Language Specification, Second Edition, 第17章介绍了Java中线程和内存交互关系的具体细节。
[2] out-of-order与cache的介绍可以参阅Computer System, A Programmer's Perspective的第四、五章。
[3] The "Double-Checked Locking is Broken" Declaration, http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[4] Synchronization and the Java Memory Model, http://gee.cs.oswego.edu/dl/cpj/jmm.html
[5] Double-checked locking: Clever, but broken, http://www.javaworld.com/javaworld/jw-02-2001/jw-0209-double.html?page=1
[6] Holub on Patterns, Learning Design Patterns by Looking at Code
感冒发烧。
把不应该存在的博文全删了。
我知道我在和自己赌气。
那又如何。
回过头来，这两年我所得到的，不过是可以随手扔掉的东西。
最后，acm的那些人们加油。
翘课大半，作业一半不交一半抄，总之太不像学生了。
搞得现在Super Scalar都只知道个大概，tableaux也知其然而不知所以然。
下星期好好参与一次，上课、作业一个都不能少，恩。
至于之后么，再说咯。
这语言真不错，不像Java那么呆，可惜不开源。 入门看的书是CLR via C#中文版，翻译质量不错，起码到现在还没觉得有必要翻一翻原版（不过为什么中文书都喜欢把“栈”叫成“堆栈”呢）。 前面几章粗略看了下，从第四章类型基础开始重点阅读。 继续漫无目的的学习感兴趣的东西，学习之中经常会惊喜的发现，自己看问题的角度已经不同于之前了。 1. 类的new操作会递归调用该类的所有父类构造器，直到System.Object，后者的构造器只是简单返回，用ILDasm查看MSCorLib.dll可以证实这一点。
.method public hidebysig specialname rtspecialname
instance void .ctor() cil managed
{
 .custom instance void System.Runtime.ConstrainedExecution.ReliabilityContractAttribute::.ctor(valuetype System.Runtime.ConstrainedExecution.Consistency,
valuetype System.Runtime.ConstrainedExecution.Cer) = ( 01 00 03 00 00 00 01 00 00 00 00 00 )
// Code size 1 (0x1)
.maxstack 8
IL_0000: ret
 } // end of method Object::.ctor
2. is和as操作符，is类似于Java中的instanceof，as会先检查类型，如果兼容返回该对象的引用，反之返回null。 Emplooee e = o as Employee;
if (e != null) {
// blah
} 利用as可以做到只检验一次对象类型，提高程序性能。这本书的很多地方都提到了性能因素。 3. 方法调用和x86上汇编语言调用机制很类似。先是参数入栈，接着返回地址入栈，返回的时候也差不多。 不知道x64等寄存器较多的架构上会不会使用寄存器传参呢，呵呵。
4. 作为方法的prologue的一部分，CLR会自动将所有局部变量初始化为null或0。 感觉这个自动初始化没什么必要，在第五章可以看到。 SomeVal v1;
SomeVal v1 = new SomeVal(); 这里的SomeVal都是值类型，CLR都会将它们初始化为0。区别在于C#认为前者没有初始化，直接使用这个值会报错；而后者在不赋值的情况下使用这个值。 可能这是CLR和C#之间不统一导致的冗余步骤吧。 5. CLR开始在一个进程中运行时，会给System.Type类型创建一个实例，每个类都会包含指向System.Type类型的指针。 6. CLR提供了执行溢出检查的计算指令，例如add.ovf对应add，mul.ovf对应mul。C#中默认关闭溢出检查。 可以使用checked关键字使用溢出检查。一般情况下，对预计可能发生溢出的代码放到checked块中，对允许溢出的代码(比如计算hash值)放到一个unchecked块中，其他情况，Debug时打开编译器的/checked+开关，Release版本关闭。 7. 所有的值类型都是从System.ValueType继承的。后者重写了Equals方法，比较两个值对象是否完全相等。 8. boxing和unboxing。 boxing：托管堆中分配内存，复制值类型，然后返回对象地址。 unboxing：相当于一个通过指针取值的过程，不过这个指针是已装箱部分中的实际值部分。 9. FCL(Framework Class Library)中包含了支持值类型的泛型容器类，不需要对容器中的元素进行boxing/unboxing处理。 不过这里就有个问题了，值类型的话是放在栈上的，生命周期小于容器的，这个怎么处理呢？第16章才详细解释泛型，先把这个问题留着吧 =,= 10. 依然是性能问题。有时候编译器会反复对一个值类型boxing，此时手动boxing会提高一些性能。 Int32 v = 5;
// 需三次boxing
Console.WriteLine("{0}, {1}, {2}", v, v, v);
// 只需一次boxing
Object o = v;
Console.WriteLine("{0}, {1}, {2}", o, o, o);
接下来书上举了个很搞的例子说明boxing和unboxing的各种情况，其实也很容易理解。
火车缓缓地开着，混杂的人群。此时的我不属于两边世界中的任何一个，孤立于这种空间和从属感的交界处。理下思路，趁着记忆的新鲜，在手机上敲下这四天的感受，以弥补将来的某天可能发生的对这次旅行的淡忘。
Zijingang Campus: A Fudaner's Perspective
1. Abstract
一次课堂电影(话剧《暗恋桃花源》[5])
旁听两节课，图形学和线性代数。图形学课上回答一次问题 =_=
一场越剧，小百花越剧团的《春琴传》
一场话剧，黑白剧社[1]的《我在天堂等你》[2]
半天图书馆自修，读了半章SICP[4]和一篇paper
半天机房灌水，水木C版版主上任后的第一个操作居然是在浙大完成的
半天在“风雨操场”打球
一晚上在浙大战网打了十盘星际，九胜一负
2. Introduction
K900到车管所，一站的路程后到达正门。紫金港的正门没有试图制造一种空间隔离感，宽敞的道路上横躺着一块刻有“浙江大学”的石块，构成了形式上的正门。步行百余部后，回头才意识到原来百余步前的所处位置竟是一个入口。
这个入口给人一种宽广、松驰的感觉，与复旦的正门放置伟人像不同，紫金港的封面很平坦。除了草坪就无其他，可以望到天际。整个紫金港都给我这样的感觉：草坪、树、湖的世界中，点缀着几幢风格各异的建筑。
3. Details
3.1 上课
其实到浙大吃完饭后做的第一件事就是旁听了一节数媒专业的图形学，上的是三维空间的坐标变换。老师上课进度偏慢，绝大部分学生上课都很认真。感到那么一点点的压力 >,<
3.2 图书馆
一直觉得图书馆是大学的灵魂组成部分之一。甚至大一的时候觉得有个好的图书馆和一套优秀的借阅制度就足以成为一个好的大学了。也因此新到一个大学后总是特别关注那里的图书馆。
紫金港图书馆依傍在高耸的行政楼旁，可以把它比成计算中心，行政楼对应于光华主楼，较之后者它们靠得更紧密些。浙大同学说外校同学来看图书馆时，第一反应总是误把行政楼当图书馆。喜欢图书馆的这种低调。
图书馆的书架分类很笼统，所有的理工类书橱都被贴上了“自然科学”的标签，恐怕找书的时候要很依赖电脑。抽样调查了计算机类书籍，书目较小，重复率较大，甚至会有十几册同本书罢占一层书架的情况。阅读环境很不错，落地窗，明亮。窗外便是那片湖，一如图书馆般地平静。若是把座椅换成摇椅，再加上一杯咖啡，最愉悦的享受莫过于此。
离开图书馆时还让同学代借了本SICP[4]，本想带回上海以此要胁该同学五一来复旦，到时候再还的。无奈多带本书太麻烦，回来之前还是还掉了。
3.3 付费
住宿楼旁有几家小吃店，其中不少店都是设置了一个单独的付费窗，而这个付费机制里没有任何凭证，或者说点了吃的却不付钱是很容易做到。别的不多说，这样一种店与客之间的信任给人一种亲切感。当然这也和紫金港地理位置较偏远，外人较少有关。
3.4 话剧
看了黑白剧社[1]的《我在天堂等你》[2]。话剧在一个可容纳百人左右的小书屋里进行。由于一个月前刚看过人艺的《榆树下的欲望》[3]，相比之下学生的功底自然略逊一筹，尤其是对老年人的刻划上。不过总体还是很不错的。
记忆最深的是社员的那份激情，话剧结束后，演员和工作人员挨个自我介绍完毕，然后跑出书屋，站在门口等待出来的观众，齐喊“再见”“谢谢”。下楼走出百余米后，听到后面三声击掌，接着是社员们高喊“谢谢你们”，如此重复几遍，一阵高过一阵。被这种热情所震撼。
3.5 肆
一位同学的寝室门口贴着一张记录着这个班级同学的奋斗目标之类的墙纸，中间是一个硕大的草体“肆”。奋斗目标都很直接，譬如要被Stanford商学院录取，要进入某某大公司云云。不怎么喜欢这种过于外露的上进心，更欣赏复旦略带散漫的风格。
3.6 还是课
浙大课比较多。上下午各5节，每节45分钟，中间休息5/15分。同时周末有课也是很常见的现象，为了提高绩点而重修的同学通常周末的课表也很满。个人不喜欢这种课多的生活，喜欢兴趣驱动的学习，不喜欢自己的学习方向太受外力的牵引。
4. The End
总是有一种声音提醒自己，我不属于这里，注定不属于。太多的不应该出现的巧合，太多的主观的或是客观的借口。我有自己的天地，那里与浙大没有交集，即便我希望会有。
5. Acknowledgements
感谢浙大那些被我折腾、蹭吃蹭喝的同学。
感谢版主的m或b。
6. References
[1] 黑白剧社 http://www.qsc.zju.edu.cn/heibai/
[2] 我在天堂等你 http://www.douban.com/subject/1310322/
[3] 榆树下的欲望 Desire Under the Elms, http://www.douban.com/subject/1297393/
[4] Structure and Interpretation of Computer Programs, http://www.douban.com/subject/1451622/
[5] 暗恋桃花源，富含搞笑因素却又错综复杂值得深深体味的一部话剧，推荐一看 http://www.douban.com/subject/1299889/
[6] 春琴传，较传统的日本爱情故事 http://www.douban.com/subject/1949657/
其实理解了 Regular Expression -> NFA -> DFA 这个过程，大致的复杂度确定也不难
发信人: styc (styc), 信区: Algorithm
标 题: Re: 请问一下大家正则表达式的时间复杂度
发信站: 水木社区 (Wed Mar 26 20:37:02 2008), 站内
NFA构造O(n)，匹配O(nm)
DFA构造O(2^n)，最小化O(kn'logn')（N'=O(2^n)），匹配O(m)
n=regex长度，m=串长，k=字母表大小，n'=原始的dfa大小
大概是这样子吧
一个用Lattice Boltzmann Method模拟三维空间中不可压缩流体的程序，示意图见底部。 转这个程序实在是太耗体力了 -_-b Brook本身的不少缺陷、bug，加上不习惯科学计算程序的代码风格，导致大多数时间都在fix bug。 其中de掉以后最有快感的一个bug：（只能这么形容了 >,<） 每个cell都有一个flag值，尽管类型是double，但是程序中是用一个MAGIC_CAST宏把它当作整型处理的。 初始情况，每个cell的flag都为~f，也就是一个1~28位都是1，29~32位为0的double型浮点。根据IEEE标准，应该是个NaN。 CPU上没有问题，放到GPU上问题就出来了，GPU不支持这种转型操作，在对这个double型进行运算操作的时候，所有结果都会变成NaN。 解决方法： 在把数据传给GPU之前可以先把这些flag值转换为GPU可以操作的double型，最简单的方法就是都先转成int（会有truncating），然后取反，再传给GPU。 
看来这年头Stream Programming要越来越热哈，恩，期待~~
发信人: freelife (陪你一起老), 信区: METech
标 题: Intel披露CPU/GPU混合芯片细节和时间 zz
发信站: 水木社区 (Tue Mar 18 22:54:49 2008), 站内
估计AMD和NV要急了~~
3月18日消息，英特尔2008年春季开发商论坛会议下个月将在中国上海召开。英特尔在会前的新闻发布会上简单地介绍了英特尔即将推出的图形芯片内核“Larrabee”的状况。
“Larrabee”与AMD的Radeon和NVIDIA的GeForce处理器有很大区别。“Larrabee”是以中央处理器架构中使用的 x86指令集为基础的。英特尔副总裁Steve Smith强调说，
“Larrabee”不仅是一个图形处理器，而且是能够完成任何流处理任务的多核芯片。
Smith没有详细说明“Larrabee”芯片中有多少个内核，不过，英特尔2006年披露的早期方案是采用16个内核。每个内核的运行速度都超过2GHz。
“Larrabee”芯片显然能够升级到数千个内核，共享与英特尔的Tera级计划相同的研究成果。除了x86的方式之外，英特尔将很快发布一个名为 “Advanced Vector
Extensions”（高级矢量扩展）的另一种像SSE扩展那样的扩展集。这些扩展可能把“Larrabee”芯片的x86指令集与Core 2 Duo和Phenom处理器的x86指令区别开来。Smith说，
“Larrabee”将支持OpenGL、 DirectX控件和光跟踪指令。
英特尔把处理器与图形处理器混合在一起的芯片将有两种版本。这两种版本都采用Nehalem处理器架构。第一种版本代号为“Havendale”，是一种台式电脑芯片，第二种版
本代号为“Auburndale”，是一种笔记本电脑芯片。
“Auburndale”和“Havendale”这两种芯片将采用两个Nehalem内核和一个图形子系统。两个内核共享4MB二级缓存和一个集成的双通道内存控制器，支持内存配置最高可
达DDR3-1333。
图形子系统最初是采用英特尔G45集成图形芯片。这表明上述两种芯片都没有强大的图形处理能力，只不过是集成图形芯片的替代品。
事实上，这两种图形芯片内核都省略了支持DirectX 9和DirectX 10的关键功能。这个基于G45图形芯片的内核最终将被高级的“Larrabee”图形处理器所取代。
根据英特尔的产品路线图，这种新的处理器预计将在2009年上半年进入市场。这将早于AMD Fusion处理器预计推出的时间。Fusion处理器计划在2009年下半年推出。
Smith许诺说，“Larrabee”芯片最终推出的时候将比Radeon和GeForce芯片更有竞争力。
|