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)


相关推荐

  • matlab画三维图像例题_matlab画三维曲面

    matlab画三维图像例题_matlab画三维曲面我可能真的太闲了吧···在网上看到这图觉得挺好看:t=0:pi/360:2*pi;x=sin(t);y=cos(t);z=2*x.^2+y.^2;figureplot3(x,y,z,’Color’,’r’,’LineWidth’,2);xlabel(‘x’);ylabel(‘y’);zlabel(‘z’);title(‘z=(cost)^2+2*(sint)^2’);ax…

    2022年10月11日
  • php中的func_num_args、func_get_arg与func_get_args函数

    php中的func_num_args、func_get_arg与func_get_args函数

    2021年10月30日
  • java运行时异常的特点是什么_java运行时异常与一般异常

    java运行时异常的特点是什么_java运行时异常与一般异常1,java.lang.NullPointerException这个异常的解释是”程序遇上了空指针”,简单地说就是调用了未经初始化的对象或者是不存在的对象,这个错误经常出现在创建图片,调用数组这些操作中,比如图片未经初始化,或者图片创建时的路径错误等等。2,java.lang.ClassNotFoundException异常的解释是”指定的类不存在”,这里主要考虑一下类的名称和路径是否正确即可…

  • 安装EIGEN库_安装第三方库的方法

    安装EIGEN库_安装第三方库的方法官网:https://eigen.tuxfamily.org/index.php?title=Main_Page源码链接:https://gitlab.com/libeigen/eigen/-/releases/3.4.0解压出来:安装使用方法在文件下:我们按照自己习惯来:安装完成下次在cmake就可以使用了

    2022年10月19日
  • Android常用加密方式

    Android常用加密方式加密解密简介加密技术是最常用的安全保密手段,利用技术手段把重要的数据变为乱码(加密)传送,到达目的地后再用相同或不同的手段还原(解密)。加密技术包括两个元素:算法和密钥。算法是将普通的信息或者可以理解的信息与一串数字(密钥)结合,产生不可理解的密文的步骤,密钥是用来对数据进行编码和解密的一种算法。在安全保密中,可通过适当的钥加密技术和管理机制来保证网络的信息通信安全。加迷解密分类分为不可逆和…

  • jlink 与 swd 接口定义「建议收藏」

    jlink 与 swd 接口定义「建议收藏」1.JLink介绍J-Link是SEGGER公司为支持仿真ARM内核推出的JTAG仿真器。J-Link支持所有基于ARM架构的处理器或微控制器配合IAREWAR,ADS,KEIL等集成开发环境进行开发过程中进行单步控制执行调试。J-Link除了可以配合集成开发环境进行调试程序,进行程序下载之外,J-Link还可以单独使用。比如在产品的生产环节中,就可以单独使用J-Link进行固件的下载。JLink,SWD接口定义缺口向左,左边为JLink接口定义,右边为SWD接口定义JTAG

发表回复

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

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