FastHashPage

kenmark · 发表于 2012-2-10 15:02:40

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

记得以前比赛大数库基本函数的时候有办过比赛写ZeroPage(void *addr); ，这次提出比赛写FastHashPage，具体问题是这样的：
很多时候操作系统需要对一个内存页（只考虑小页4096字节）进行Hash，从而确认其内容的唯一性。
这里我们就要写一个DWORD FashHashPage(void *addr); // assume addr is aligned to PAGE boundary
首先，当然是选取hash函数，这个比较灵活，只要最后hash结果reasonable即可，但却是主要影响性能的因素；
然后实现上，配合SSE之类的指令以及巧妙的hash函数特性当然可以更快
其他需要考虑的暂时还没有想到
没有抛砖，只等引玉

sielw · 发表于 2012-2-13 10:04:23

本帖最后由 sielw 于 2012-2-13 10:06 编辑

如果硬件不支持，那只能选择实现一个比较快速的hash函数。但是不明白验证内存的内容唯一性的目的何在？如果验证内容不多，应该对系统效率影响不大，如果太频繁则没必要。

G-Spider · 发表于 2012-2-13 17:19:06

hash 函数比较多，hash在比较方面有个问题，一是速度，二是有碰撞，两者通常排斥。
判断一个页是否被修改，一可只读，写异常；二可粗糙些CRC，若用md5 也不反对^_^.；还可以分段校验。

kenmark · 发表于 2012-2-14 13:01:11

应用场景有：
1）当一台机器上有多个相似的虚拟机时（运行相同操作系统和应用），通过建立这么一张表来找到identical content的内存页，从而用copy-on-write的方式只保留相同页中的一个，节省内存
2）less applicable，一个操作系统多个类似进程，如果不是由fork产生的，没有cow
write protection的方法，只能粗略知道一个页自从上次checkpoint之后是否dirty
进而有了FastHashPage之后，可以建一张表，把内存的hash value变成一个index，从而当要判断某个页是否有redundant copy存在，就可以通过hash(page)作index，然后随机选取几个位置进行比较，这样可以保证90%（或者更高概率）这两个页是相同与否。（当然逐字节比较能100%）

MD5太慢了吧
CRC的话找到一个http://www.cl.cam.ac.uk/research ... 0060000000000000000
没有测试，不知道性能（计算开销、冲突率）咋样

账号		自动登录	找回密码
密码			欢迎注册

[讨论] FastHashPage

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。