大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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字节随机字符串测试
2、1000条64字节随机字符串测试
3、1000条128字节随机字符串测试
4、相同CPU不同长度随机字符串测试
图示直观~~
由此可见,硬件指令实现的CRC32运算在多款主流CPU上性能超越Murmurhash,碰撞性能基本一致,多数场景可以使用CRC32硬件指令优化HASH算法提升性能。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183553.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...