CRC32 Hash PK Murmur Hash「建议收藏」

CRC32 Hash PK Murmur Hash「建议收藏」硬件指令实现的CRC32运算在多款主流CPU上性能超越Murmurhash,碰撞性能基本一致,多数场景可以使用CRC32硬件指令优化HASH算法提升性能

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

     murmurhash是一种高性能、低碰撞率的非加密hash算法本测试采用版本为urmurhash2;硬件加速crc32 hash需要CPU支持SSE4.2指令集,市面上绝大部分CPU已支持,具体可检查你所使用的CPUflags


  murmurhash2的代码实现

uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )
{
  // 'm' and 'r' are mixing constants generated offline.
  // They're not really 'magic', they just happen to work well.

  const uint32_t m = 0x5bd1e995;
  const int r = 24;

  // Initialize the hash to a 'random' value

  uint32_t h = seed ^ len;

  // Mix 4 bytes at a time into the hash

  const unsigned char * data = (const unsigned char *)key;

  while(len >= 4)
  {
    uint32_t k = *(uint32_t*)data;

    k *= m;
    k ^= k >> r;
    k *= m;

    h *= m;
    h ^= k;

    data += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array

  switch(len)
  {
  case 3: h ^= data[2] << 16;
  case 2: h ^= data[1] << 8;
  case 1: h ^= data[0];
      h *= m;
  };

  // Do a few final mixes of the hash to ensure the last few
  // bytes are well-incorporated.

  h ^= h >> 13;
  h *= m;
  h ^= h >> 15;

  return h;
} 

  crc32代码实现

static inline uint32_tcrc32c_sse42_u8(uint8_t data, uint32_t init_val){	__asm__ volatile(			"crc32b %[data], %[init_val];"			: [init_val] "+r" (init_val)			: [data] "rm" (data));	return init_val;}static inline uint32_tcrc32c_sse42_u16(uint16_t data, uint32_t init_val){	__asm__ volatile(			"crc32w %[data], %[init_val];"			: [init_val] "+r" (init_val)			: [data] "rm" (data));	return init_val;}static inline uint32_tcrc32c_sse42_u32(uint32_t data, uint32_t init_val){	__asm__ volatile(			"crc32l %[data], %[init_val];"			: [init_val] "+r" (init_val)			: [data] "rm" (data));	return init_val;}static inline uint32_thash_crc(const void *data, uint32_t data_len, uint32_t init_val){	unsigned i;	uintptr_t pd = (uintptr_t) data;	for (i = 0; i < data_len / 8; i++) {		init_val = crc32c_sse42_u8(*(const uint64_t *)pd, init_val);		pd += 8;	}	if (data_len & 0x4) {		init_val = crc32c_sse42_u32(*(const uint32_t *)pd, init_val);		pd += 4;	}	if (data_len & 0x2) {		init_val = crc32c_sse42_u16(*(const uint16_t *)pd, init_val);		pd += 2;	}	if (data_len & 0x1)		init_val = crc32c_sse42_u8(*(const uint8_t *)pd, init_val);	return init_val;}

              测试代码实现

std::set<int> g_knocked_set;uint32_t g_spare_range = 0;static inline uint64_trdtsc(void){    unsigned long long ret;    __asm__ __volatile__("rdtsc" : "=A" (ret));    return ret;}void printHelp(const char *progname) {    printf("%s\n\n", progname);    printf("-h            Print this help\n");    printf("-f <file>     File name\n");    printf("-m <mode>     1:murmur 2:crc -1:murmur_knocked -2:crc_knocked\n");    exit(0);}static inline void crc_hash(std::string &s) {    hash_crc(s.c_str(), s.size(), 16);}static inline void knocked_crc_hash(std::string &s) {    uint32_t h = hash_crc(s.c_str(), s.size(), 16);    g_knocked_set.insert(h % g_spare_range);}static inline void murmur_hash2(std::string &s) {    MurmurHash2(s.c_str(), s.size(), 16);}static inline void knocked_murmur_hash2(std::string &s) {    uint32_t h = MurmurHash2(s.c_str(), s.size(), 16);    g_knocked_set.insert(h % g_spare_range);}int main(int argc, char* argv[]){    char c, buf[1024];    char *fname = NULL;    FILE *file = NULL;    std::list<std::string> patterns;    uint64_t tbegin, tend;    int mode = 1;        while ((c = getopt(argc,argv,"f:hm:")) != -1) {        switch (c) {            case 'h':                printHelp(argv[0]);                break;            case 'f':                fname = strdup(optarg);                break;            case 'm':                mode = atoi(optarg);                break;        }    }    if (!fname) {        printHelp(argv[0]);    }    file = fopen(fname, "r");    if ( !file) {        printf("fname[%s] open error.\n", fname);        exit(-1);    }    while(fgets(buf, 1024, file) != NULL) {//        printf("%s", buf);        std::string s(buf);        patterns.push_back(s);    }    g_spare_range = patterns.size();    if (mode == 1) {        tbegin = rdtsc();        std::for_each(patterns.begin(), patterns.end(), murmur_hash2);        tend = rdtsc();        printf("[murmur]    %u\n", tend - tbegin);    }        if (mode == 2) {        tbegin = rdtsc();        std::for_each(patterns.begin(), patterns.end(), crc_hash);        tend = rdtsc();        printf("[crc]   %u\n", tend - tbegin);    }    if (mode == -1) {        std::for_each(patterns.begin(), patterns.end(), knocked_murmur_hash2);        printf("[murmur]    %f\n", g_knocked_set.size()/(g_spare_range * 1.0));    }    if (mode == -2) {        std::for_each(patterns.begin(), patterns.end(), knocked_crc_hash);        printf("[crc]    %f\n", g_knocked_set.size()/(g_spare_range * 1.0));    }    return 0;}

       

测试方法:

        存在一定测试误差,包含了遍历SET的时间,可能收到内存读取效率的影响,严格测试应该考虑到这些因素,每个测试用例测试100次,取算数平均值,参考标准方差,后续可以对测试做一定优化排除各类干扰,因此,本测试只做算法间的效率横向对比,不做某个算法绝对速率参考,评估时间单位使用clock,一个clock=1/CPU频率(秒)

        1、1000条16字节随机字符串测试

CRC32 Hash PK Murmur Hash「建议收藏」

        2、1000条64字节随机字符串测试

CRC32 Hash PK Murmur Hash「建议收藏」

        3、1000条128字节随机字符串测试

CRC32 Hash PK Murmur Hash「建议收藏」

         4、相同CPU不同长度随机字符串测试

CRC32 Hash PK Murmur Hash「建议收藏」

图示直观~~

CRC32 Hash PK Murmur Hash「建议收藏」
CRC32 Hash PK Murmur Hash「建议收藏」

由此可见,硬件指令实现的CRC32运算在多款主流CPU上性能超越Murmurhash,碰撞性能基本一致,多数场景可以使用CRC32硬件指令优化HASH算法提升性能。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183553.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 注会综合记忆锦囊:手绘PEST模型,记忆可以这样玩「建议收藏」

    注会综合记忆锦囊:手绘PEST模型,记忆可以这样玩「建议收藏」【】综合的记忆量非常庞大,且看小萌有妙招,通过“关键词”和“手绘图”带你一起巧记忆。一、PEST宏观环境分析:4项1.政治因素:4项(1)执政党所持的态度和推行的基本政策(2)企业所在国家和地区的政局稳定状况(3)政府行为对企业的影响(4)各政治利益集团对企业活动产生的影响2.法律环境因素:4项(1)国家司法机关和执法机关(2)国际法所规定的国际法律环境和目标国

  • 设计测试用例的方法

    设计测试用例的方法如果测试的时间有限,如何保证在有限的时间内让产品上线?(1)有限的时间内测试,保证用户经常使用(使用频率比较高,主要的,核心的功能)功能的质量(2)如果有限的时间所有的功能不能完全测完,可以和产品经理开发商量,把没有通过测试的,有风险的功能把用户的入口,屏蔽掉(让用户无法使用),产生错误风险就会降低(3)本次测试,测试报告写清楚,这次上线,哪些功能测试了,哪些功能没有测试,上线风险分析清楚。百度云盘的测试用例太多了,如何去写?(1)用户经常使用的功能有哪些?文件的存储(长传,接受)下载分享

  • python flask教程_python框架有哪些

    python flask教程_python框架有哪些大家好,这算是我使用CSDN以来第一次正二八经的想自己写一篇博客。如果有写的不好的地方还请大家见谅!使用pipenv的方便之处就是可以单独的为每一个python 项目建立对应的虚拟环境,而且该过程简单方便。下面我会用简短的步骤来描述这个过程:1. 首先使用pip进行安装pipenv。 用管理员身份打开命令行(cmd),然后输入pipinstallpipenv 回车,结果如下图所…

  • 解决Error response from daemon: oci runtime error: container_linux.go:247: starting container process「建议收藏」

    解决Error response from daemon: oci runtime error: container_linux.go:247: starting container process「建议收藏」我是在guigu上学习的springboot的视频,有一些很难受的问题,这个问题已经让我难受一天多了,后来终于在一片文章中解决了,给大家分享一下:docker启动容器报错:Errorresponsefromdaemon:ociruntimeerror:container_linux.go:247:startingcontainerprocesscaused”write………

  • mysql常用语句大全_什么是SQL语句

    mysql常用语句大全_什么是SQL语句讲解了,MySQL中常用的语法,并且包含了使用实例。

  • vim打开文件时提示E325[通俗易懂]

    vim打开文件时提示E325[通俗易懂]vim打开文件时,它提示E3225:ATTENTION

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号