w.rdc.sae.sina.com.cn:3307|nj41yyozkz|nj41yyozkz SAE云计算
Twitter FaceBook
Home
Sina App Engine
Posted by kobe, and filed under 计算机应用

一,框架性开发

分布式程序设计或者并行程序设计,往往需要将大量的精力花在如何制定通信协议、如何进行机器管理、如何进行共享存储、如何进行数据传输等方面,而这些工作对于每一个具体的分布式计算任务都是通用的,为了减少工作量,将分布式设计中通用的部分尽量设计为底层框架,这样在以后的应用中,只需要将精力集中在单机算法的设计中就可以轻松完成整个分布式程序设计。

google的mapreduce就是一种著名的分布式程序设计框架,根据google的说明,使用该框架,程序设计者不需用分布式程序设计经验,只要像原来写单机程序一样编写,就可以享受到上千台机器运算带来的巨大便利,而这种便利背后隐藏的技术细节都是由mapreduce提供的。

和mapreduce一样,SINA DCF也致力于提供分布式计算的底层框架,使用本框架,设计者不需要关心复杂的通信协调、容灾处理、任务分发等环节,只需要将精力集中在单笔任务处理的设计上,从而加快了分布式程序设计二次开发的问题。

二,基本流程

SINA DCF基本由三个环节组成:

1,任务分发:DCF使用者(程序员)根据规定的接口设计单笔任务执行模块,然后DCF负责将执行模块分配到各台机器上。

2,数据分发:DCF使用者(程序员)根据规定的接口设计原始数据分割模块,DCF将使用者分散好的数据分配到空闲的机器上。

3,指令分发:DCF根据协议,在各个阶段负责向每台机器发送相关指令,并接收从每台机器返回的指令,包括查询状态指令、运算状况指令、存活指令、错误发送指令、状态变更指令等。

总的流程是:

原始任务经过用户定义的MapDLL模块,分散到一个个小任务,小任务在DCF的协调下,会自动寻找空闲的存活机器节点,并传输到该机器上。同时,对于单笔小任务计算的执行由用户定义的TaskDLL模块规定,由DCF分配到每一台存活机器。根据任务和数据发送状态,主机(master)开启计算开关,启动某些台机器的计算线程。master定时维护从所有存活机器返回的信息,并更新机器状态和运算状态,对于down掉的机器或者运算出错的机器,按照调度算法重新加入等候机器列表,并将该任务视为重做。某一笔任务完成后,slave机器会将结果发送到reducer(结果合并机),由reducer合并结果。所有任务都运算完成后,master会通知用户计算完成,并生成统计报告,汇报计算情况耗费时间等等。

http://www.rayfile.com/files/7545ce26-470f-11df-b4d3-0015c55db73d/

13th 四 2010
Tags:
Posted by kobe, and filed under 计算机应用

JavascriptDevelopmentEnvironment,简称JSDE,是一套面向特殊需求的JS开发部署环境,对于JS的开发人员,它支持扩展JS语法、分析JS工程、分析CSS工程、整合JS代码、分析JS工程、除错等功能,是一套基于linux平台的,面向RIA开发人员的开发环境。

需求来源

JSDE的需求最早来源自RIA组的JS开发实际环境,JS开发需要两套系统:开发模式和线上模式。开发模式为人为编写的代码,线上模式为经过除注释、整合、混淆后的代码。可以近似的理解为开发模式对应源代码,而线上模式对应包含、link后的目标代码。
以linux下GCC编译环境为例,需要makefile的依赖分析, gcc的预编译、编译、链接等环境,最终形成从源代码.c文件到线上部署的可执行程序的转变。不像成熟的编译语言,JS语言没有统一、商业化的线上部署的环境支持,正基于此,为了提高整个RIA的开发效率、线上部署效率,一套灵活、具体的可靠的JSDE就显得尤为重要。

 

功能

JSDE具有以下12点功能:
1,致力于为RIA打造基于linux平台的JS开发部署环境:
基于通用框架,面向特定需求
2,具有支持类如自定义函数等扩展JS语法功能:
开发人员可以自形扩展javascript的语法,以达到方便工程的目的,扩展的语法由JSDE负责进行解释和转义
3,具有检查JS语法错误功能
可以检查代码的语法正确性
4,具有去除注释功能
可以去除代码的各种注释说明,以达到代码瘦身的目的
5,具有去除冗余代码功能
可以去除代码中的冗余部分,比如多余的分号、空格等,以达到代码瘦身的目的
6,具有整合代码功能
可以通过预编译,实现解释语言的include
7,具有依赖关系分析功能
类似Makefile,分析工程中的文件、函数等依赖关系,给出结构图,方便调试
8,具有编码检查功能
可以针对实际线上环境,检查工程文件编码格式,并提出警报
9,具有include once和检查功能
实现#pragam once等宏定义,保证依赖文件关系保持拓扑性(无环)
10,具有整合CSS功能
根据CSS语法和依赖关系,整合CSS代码
11,具有发布工程的功能
按工程配置,发布工程,完成开发模式到线上模式的转换
12,具有代码混淆功能
混淆代码,实现霍夫曼编码,达到代码瘦身的目的

http://www.rayfile.com/files/691976d9-75a4-11de-82fa-0014221b798a/

13th 四 2010
Tags:
Posted by kobe, and filed under 计算机理论

    前段时间给N年前的一些代码code review,其中涉及到了一个人机博弈的程序。人机博弈中有一个很重要的结构,就是优先队列,其作用的是能够随机的insert一些数据,并保证随时能获得最小(大)的点,其实该结构在大部分的图算法中(包括寻路问题)也很常用。我原来的代码使用heap实现的,不过最近看了一篇paper,是描述《帝国时代》游戏中寻路算法的数据结构的,很是新颖,其用线性表+缓存的结构就可以达到相当快的速度,于是想拿它来试试,看看它和堆哪个快。结果很失望,还是堆快,而且快的不是一星半点,当然也许在特定领域会有不同的表现。
    为了完善该paper的思想,我决定对这个结构进行改进,看看能不能接近或者超过堆。先看看堆的优先队列是如何实现的,我这里使用STL里面的结构:
class PriorityQueueHeap
{
private:
  vector<int> vec;
public:
  int ExtractMin();
  void Insert(const int value);
  void Display(){}
  bool IsEmpty(){return vec.empty();}
};
void PriorityQueueHeap::Insert(const int value)
{
vec.push_back(value);
push_heap(vec.begin(),vec.end(),greater<int>());
}
int PriorityQueueHeap::ExtractMin()
{
pop_heap(vec.begin(),vec.end(),greater<int>());
int min=vec.back();
vec.pop_back();
return min;
}
    接下来,我开始对线性表的结构进行改进,首先将固定缓存进行扩展,变成了动态缓存,在做了这个改进后,发现性能有显著提高,大约相当于STL Heap版的60%,这当然是不令人满意的;而后,利用桶排序的思想分割线性表并结合动态缓存修改算法,经过一系列精心的优化(比如减少函数调用次数,利用内联等等)后,惊人的效果出现了,测试表示改进后的时间比STL要快了将近30%,测试程序如下:
srand((unsigned)time(NULL));
for(int k=0;k<1;k++){
 KobePriorityQueue pq1; (PriorityQueueHeap pq1;)
     for(int i=0;i<=100000000;i++){
     int value=rand()%16777216;
     pq1.Insert(value);
     if(!pq1.IsEmpty()&&rand()%8==1)
        pq1.ExtractMin();
     }//end for i
}//end for k
    KobePriorityQueue是经过我改进后的结构,PriorityQueueHeap是STL最小堆实现,测试程序会不停的插入节点,并随机取最小点,随机数1/8的来源是因为大多数寻路问题(棋盘问题)新增节点和删除节点的比是8。测试结果如下(linux 4核,4G内存):

Scale Loop STL HeapPQ(average sec) KobePQ(average sec) KobePQ(best sec) percentage comparison
1000 10000 1.222 2.79 1.221 -0.08%
10000 1000 1.298 1.406 1.261 2.93%
100000 100 1.433 1.192 1.159 23.64%
1000000 10 1.535 1.214 1.214 26.44%
10000000 1 1.652 1.293 1.265 30.6%

    可见,在缺省参数下,十万级以上KobePriorityQueue比STL版本要快了25%,在10万级以下应用,通过调整参数也可以获得和STL相当的效率。当然这里的弱点就是在某些应用时,需要调节算法参数,使得其不像STL那样稳定通用(毕竟堆的操作效率基本都是logN,使得其时间消耗很稳定快速)。另,根据CLRS,有一种叫FIB heap的结构在插入时可以比最小堆更快,平摊获得O(1)的效率,根据其wiki链接,也下了一份其实现做比较,但结果很令人遗憾,其方法的速度比heap和KobePQ要慢了好几个数量级,当然不排重是代码编写的问题。
    总之,和C++和Java都采用的以堆实现的优先队列算法比较,KobePriorityQueue基本表现得略胜一筹,在某些特定要求速度的领域,可以代替STL Heap。当然在要求稳定性的领域,还是用STL更安全些。

前段时间给N年前的一些代码code review,其中涉及到了一个人机博弈的程序。人机博弈中有一个很重要的结构,就是优先队列,其作用的是能够随机的insert一些数据,并保证随时能获得最小(大)的点,其实该结构在大部分的图算法中(包括寻路问题)也很常用。我原来的代码使用heap实现的,不过最近看了一篇paper,是描述《帝国时代》游戏中寻路算法的数据结构的,很是新颖,其用线性表+缓存的结构就可以达到相当快的速度,于是想拿它来试试,看看它和堆哪个快。结果很失望,还是堆快,而且快的不是一星半点,当然也许在特定领域会有不同的表现。
    为了完善该paper的思想,我决定对这个结构进行改进,看看能不能接近或者超过堆。先看看堆的优先队列是如何实现的,我这里使用STL里面的结构:
class PriorityQueueHeap
{
private:
  vector<int> vec;
public:
  int ExtractMin();
  void Insert(const int value);
  void Display(){}
  bool IsEmpty(){return vec.empty();}
};
void PriorityQueueHeap::Insert(const int value)
{
vec.push_back(value);
push_heap(vec.begin(),vec.end(),greater<int>());
}
int PriorityQueueHeap::ExtractMin()
{
pop_heap(vec.begin(),vec.end(),greater<int>());
int min=vec.back();
vec.pop_back();
return min;
}
    接下来,我开始对线性表的结构进行改进,首先将固定缓存进行扩展,变成了动态缓存,在做了这个改进后,发现性能有显著提高,大约相当于STL Heap版的60%,这当然是不令人满意的;而后,利用桶排序的思想分割线性表并结合动态缓存修改算法,经过一系列精心的优化(比如减少函数调用次数,利用内联等等)后,惊人的效果出现了,测试表示改进后的时间比STL要快了将近30%,测试程序如下:
srand((unsigned)time(NULL));
for(int k=0;k<1;k++){
 KobePriorityQueue pq1; (PriorityQueueHeap pq1;)
     for(int i=0;i<=100000000;i++){
     int value=rand()%16777216;
     pq1.Insert(value);
     if(!pq1.IsEmpty()&&rand()%8==1)
        pq1.ExtractMin();
     }//end for i
}//end for k
    KobePriorityQueue是经过我改进后的结构,PriorityQueueHeap是STL最小堆实现,测试程序会不停的插入节点,并随机取最小点,随机数1/8的来源是因为大多数寻路问题(棋盘问题)新增节点和删除节点的比是8。测试结果如下(linux 4核,4G内存):

Scale Loop STL HeapPQ(average sec) KobePQ(average sec) KobePQ(best sec) percentage comparison
1000 10000 1.222 2.79 1.221 -0.08%
10000 1000 1.298 1.406 1.261 2.93%
100000 100 1.433 1.192 1.159 23.64%
1000000 10 1.535 1.214 1.214 26.44%
10000000 1 1.652 1.293 1.265 30.6%

    可见,在缺省参数下,十万级以上KobePriorityQueue比STL版本要快了25%,在10万级以下应用,通过调整参数也可以获得和STL相当的效率。当然这里的弱点就是在某些应用时,需要调节算法参数,使得其不像STL那样稳定通用(毕竟堆的操作效率基本都是logN,使得其时间消耗很稳定快速)。另,根据CLRS,有一种叫FIB heap的结构在插入时可以比最小堆更快,平摊获得O(1)的效率,根据其wiki链接,也下了一份其实现做比较,但结果很令人遗憾,其方法的速度比heap和KobePQ要慢了好几个数量级,当然不排重是代码编写的问题。
    总之,和C++和Java都采用的以堆实现的优先队列算法比较,KobePriorityQueue基本表现得略胜一筹,在某些特定要求速度的领域,可以代替STL Heap。当然在要求稳定性的领域,还是用STL更安全些。

13th 四 2010
Posted by kobe, and filed under 计算机应用

根据我上篇提到的boost::object_pool的一些问题,我试着把object_pool做了一些改进,改进完的性能测试如下(测试环境linux服务器,4G内存,4核CPU(3052MHz))
#include “kobe_object_pool.hpp”
using namespace std;
using namespace boost;
//————————————————————–
class SS
{
public:
int value;
float value2;
SS(){}
};
//————————————————————–
int main(int agrc,char** argv)
{
boost::kobe_object_pool<SS,boost::default_user_allocator_new_delete> my_pool;
int test_range=10000000;
for(int i=0;i<test_range;i++)
    {
     SS* p=my_pool.construct();
     my_pool.destroy(p);
    }
real    0m0.049s
user    0m0.040s
sys     0m0.000s
//————————————————————–
boost::object_pool<SS> my_pool;
for(int i=0;i<test_range;i++)
    {
     SS* p=my_pool.construct();
     my_pool.destroy(p);
    }
real    0m0.125s
user    0m0.120s
sys     0m0.000s

//————————————————————–
for(int i=0;i<test_range;i++)
    {
     SS* p=new SS();
     delete p;
    }
real    0m0.695s
user    0m0.690s
sys     0m0.000s

//————————————————————–
return 0;
}

可以看见,使用我的kobe_object_pool要比boost_object_pool快了1倍多,比常规的内存分配快了一个数量级。这里有一个说明:
kobe_object_pool要求使用者调用完construct后一定要调用destroy,以保证对象的析构可以被正常唤起,否则将会有隐患的资源泄漏;而boost::object_pool则不然,它可以在pool析构时释放用户所遗留析构的object。这也是boost::object_pool的一个优点吧,但如果用户可以保证唤起析构,那么使用kobe_object_pool还是有性能优势的。

13th 四 2010
Tags: ,
Posted by kobe, and filed under 计算机应用

boost::object_pool绝对是一个超失败的设计!该内存池模块,基于sss(simple segregated storage),以32为长为block大小,成倍增长,本来挺好的设计思想,利用了chunks空间存free list既节省了overhead空间又节省free list空间,还包装了对象构造和析构,但就是毁在了它的释放操作。真是不看代码不知道,一看吓一跳,它的释放效率居然是O(N),原因在于它的free list不同于boost::pool的free list,它的free list是有序的,我理解设计者的目的,因为有序的free list可以保证在最终垃圾回收时的效率保持在O(N)(否则是O(N*N)),但设计者难道不知道释放chunk的使用频率远远大于最终回收时的一次吗?鬼才会使它呢,真是失败中的失败。。。遗憾啊
    补救的方法一个是使pool代替(但这样就会丧失面向对象操作的遍历,比如需要自己调用构造析构等),或者自己写一个object_pool的版本。
PS:顺便搜了一下,拍的人还不少,http://lists.boost.org/boost-users/2007/03/25888.php

13th 四 2010
Tags: ,
illuminati
illuminati
 
Designed by