关于圣诞节

不知道为什么今天心情真的不好,今天唯一的收获是学会了弹奏《you are my sunshine》,但是真的不适合在今天弹这么欢快的歌曲。感谢朋友的邀请,但是真的不想出去玩。晚上一个人去街上走了走,本来想一个人练下台球,好久没打了。怎么说呢,还是算了,本来平安夜那天决定以后认真去做心里决定的事情,但是这个愿望还是被一下子浇灭了,我太傻了。恩,就这样吧。lonely Christmas.
-
-
-
但是呢,我可以有更多时间去达成另一个目标,我要去我想去的那个地方。它一定会被实现。

Shortest Palindrome

leetcode的一道题
题意:给出一个字符串,只能在首部加上字符使其成为回文串,求所加字符数最少的方案。
这题以前搞acm的时候碰到过,如果是以前,就直接上KMP了。但是前面有道题是用manacher算法求字符串的最长回文子串。突然发现这题也可以用manacher来做,时间复杂度也是O(n)。
manacher确实是一种思路巧妙,代码简短的算法。
https://leetcode.com/problems/shortest-palindrome/

char str[1000010],ans[1000010];
int r[1000010];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
char* shortestPalindrome(char* s) {
    int i,j,k,cnt;
    int len=strlen(s);
    if(len<=1)  return s;
    r[0]=0;
    str[0]='?';
    for(i=0;i<=len;i++)
    {
        str[(i<<1)+1]=s[i];
        str[(i<<1)+2]='*';
    }
    str[len<<1]='#';str[(len<<1)+1]='\0';
    i=1;j=0;
    while(i<=(len<<1))
    {
        while(str[i-j-1]==str[i+j+1]) j++;
        r[i]=j;
        for(k=1;k<=j;k++)
            if(r[i]-k!=r[i-k]) r[i+k]=min(r[i]-k,r[i-k]);
            else break;
        j=max(0,r[i]-k);
        i+=k;
    }
    for(i=(len<<1);i>=1;i--)
    {
        if(i-r[i]==1) break;
    }
    i=(i+r[i])/2;
    cnt=0;
    for(j=len-1;j>=i+1;j--) ans[cnt++]=s[j];
    for(j=0;j<=len-1;j++) ans[cnt++]=s[j];
    ans[cnt++]='\0';
    return ans;
}

pmfs+nvm与ext4+pmbd+nvm性能比较

这周开始做nvm相关的一个性能测试。nvm是非易失性内存,是一类比较新的存储硬件的总称,其读写速率比DRAM慢,比ssd快。之前看了一些相关的论文,nvm的应用大概分这么几种:

1.用来完全替代DRAM作为主存.(并用DRAM做cache)

2.和DRAM一起构成一个混合的内存模型

3.作为块设备。

4.作为其他块设备的cache(如ssd)

这里把nvm作为块设备。

实验用dram模拟nvm,试验机总共8g内存,前4g仍作为dram使用,后4g作为nvm。

现在存在两种方案来使用它。

一是用新的filesystem来管理,这里使用pmfs这个文件系统.

pmfs项目的github:https://github.com/linux-pmfs/pmfs

二是在现有filesystem的基础上加上一层转换层,使得能够用现有的filesystem,如ext4来管理nvm。

这个中间层在这里是pmbd:https://github.com/linux-pmbd/pmbd

这两种方案下的体系结构图大概如下:

pmbd是作为内核模块启动的,可以按照README进行

pmfs对内核改动比较大,因此github给出的是修改后的整个内核。需要下载后重新编译内核。

注意不要下载zip文件然后解压,会导致文件不全。请用git clone到试验机。

对内核进行编译,请参照:http://zjuedward.blog.51cto.com/1445231/461376

make menuconfig时记得选上File sytems->Miscellaneous filesystems->Persistent and Protected PM file system support

这里声明一点:由于pmfs是基于内核3.11,而pmbd只能运行在3.2.1的内核上,所以我们只能在不同的内核下进行测验,但是内核版本的不同对实验结果影响不大,内存那块的差异非常小。

 
实验主要测试io带宽。使用的benchmark是fio-2.1.10
由于需要多次测试取平均值,并且生成的结果需要以特定格式导入到excel中生成图表,所以我写了个脚本来进行测试(只列举了针对pmbd的测试,pmfs的测试时类似的),如下:

import commands
io_type=["read","write","randread","randwrite"];
blocksize=["1KB","2KB","4KB","8KB"];
job_num=["1","2","4","8"];
result='type-job';
for num in range(1,4):
	for i in blocksize:
		result+="	"+i;
	result+="\n";
	for iotype in io_type:
		for job in job_num:
			result+=iotype+'-'+job;
			for bs in blocksize:
#				commands.getstatusoutput('touch /mnt/1.txt');
				cmd='fio -filename=/dev/pma -direct=1 -iodepth 1 -thread -rw='+iotype+' -ioengine=psync -bs='+bs+' -size=8G -numjobs='+job+' -runtime=30 -group_reporting -name=mytest';
				print str(iotype)+"  "+str(bs)+"  "+str(job)+"  begin\n";
				(status,output)=commands.getstatusoutput(cmd);
				word=output.split();
				bw_val=0.0;
				for i in word:
					if i.startswith('bw='):
						i=i.lstrip('bw=');
						if i.endswith('KB/s,'):
							bw_val=float(i.rstrip('KB/s,'))/1024.0;
							bw_val=float('%0.3f' %bw_val);
							bw_val=str(bw_val);
						else:bw_val=i.rstrip('MB/s,');
						break;
				result+="	"+str(bw_val);
				print str(iotype)+"  "+str(bs)+"  "+str(job)+"\t"+str(bw_val)+"  end\n";
				tmp_result=str(iotype)+"  "+str(bs)+"  "+str(job)+"\t"+str(bw_val)+"  end\n";
				ret1="echo '"+tmp_result+"' >>tmp_fio_log.txt";
				commands.getstatusoutput(ret1);
			result+="\n";
	ret="echo '"+result+"' >>resultlog.txt";
	commands.getstatusoutput(ret);
	result='type-job';

最终得到如下性能:


注意两个图纵坐标的不同,初步的比较可知使用pmfs对nvm进行管理的性能更好。
job=4比job=8性能更好是因为实验机为四核,用8个线程去跑反而增加切换的开销。
顺序读比随机读性能稍好可能是因为预取和cache的原因,我们的nvm实际上是DRAM模拟的,所以cache对其是有影响的
顺序写比随机写性能稍好也可能是cache的原因。
目前进行的是没有虚拟化的情况下的性能比较,后期还要加入kvm,在kvm下进行性能测试,io栈大致如下: