NABhash 欢迎试用, 40GB/s 哈希速度

2019-04-24 23:56:54 +08:00
 mengzhuo

https://github.com/mengzhuo/nabhash

现在只有 Go 版本

4081 次点击
所在节点    程序员
22 条回复
blless
2019-04-25 01:19:38 +08:00
跟 xxhash 对比有啥优势吗?
blless
2019-04-25 01:29:59 +08:00
40g ……有点夸张 mark 明天再看
hearfish
2019-04-25 06:08:40 +08:00
meow hash 啊,利用硬件 aes 指令来达到这速度,挺好挺好
KgM4gLtF0shViDH3
2019-04-25 07:49:46 +08:00
官网打不开
mscb
2019-04-25 07:51:04 +08:00
支持一下,一直在关注楼主的博客😁
mengzhuo
2019-04-25 08:02:06 +08:00
@hearfish 参考了 meow hash 的思路,主要是 meow hash 在 final block 的处理上太复杂了, nab 把长度按 uint64 xor 进 state 里就行了。
mengzhuo
2019-04-25 08:03:13 +08:00
@blless 快一些~
murmur
2019-04-25 08:13:43 +08:00
楼主你的使用场景是什么,既然是基于 AES 那就不是标准 hash,为什么我不用更快的 crc32 呢
reus
2019-04-25 08:29:40 +08:00
@murmur crc32 是纠错用的,不是 hash 用的…
tempdban
2019-04-25 08:35:20 +08:00
@reus 实际上 crc32 广泛的用来做 hash
mengzhuo
2019-04-25 10:20:33 +08:00
@murmur hash 没有标准不标准。
只有是否 Crypto-Safe 和 SMhasher 测试过不过的问题。
For Fun 也是一个作用嘛~

@tempdban 那就用得有问题了。hash 只是 checksum 的子集,checksum 并不保证冲突,只是校验有没有更改。
tempdban
2019-04-25 11:06:44 +08:00
@mengzhuo hash 又不是只能当签名用?
tempdban
2019-04-25 11:07:20 +08:00
@mengzhuo “那就用得有问题了” 还是建议少说这种话
blless
2019-04-25 11:21:02 +08:00
data size: 4350
goos: windows
goarch: amd64
pkg: gitlab.dianchu.cc/DevOpsGroup/goutils/structhash
BenchmarkSpeed/xxhash-8-12 30000000 39.2 ns/op 204.07 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-8-12 20000000 73.0 ns/op 109.54 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-16-12 30000000 40.6 ns/op 394.15 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-16-12 20000000 72.1 ns/op 221.90 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-32-12 50000000 40.2 ns/op 796.20 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-32-12 20000000 70.6 ns/op 453.30 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-64-12 30000000 42.3 ns/op 1512.89 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-64-12 20000000 62.6 ns/op 1021.62 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-128-12 30000000 47.2 ns/op 2710.10 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-128-12 20000000 62.9 ns/op 2034.49 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-256-12 30000000 55.9 ns/op 4577.90 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-256-12 20000000 64.6 ns/op 3961.26 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-512-12 20000000 73.0 ns/op 7018.40 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-512-12 20000000 67.1 ns/op 7625.44 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-1024-12 20000000 106 ns/op 9648.91 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-1024-12 20000000 73.3 ns/op 13975.12 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-2048-12 10000000 181 ns/op 11261.76 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-2048-12 20000000 89.7 ns/op 22825.68 MB/s 80 B/op 2 allocs/op
BenchmarkSpeed/xxhash-4096-12 5000000 323 ns/op 12679.08 MB/s 8 B/op 1 allocs/op
BenchmarkSpeed/nabhash-4096-12 10000000 124 ns/op 32986.55 MB/s 80 B/op 2 allocs/op

win10 i8700 go1.12 跑了下测试
我用的 https://github.com/cespare/xxhash
数据大于 512 字节开始就比 xxhash 快了
reus
2019-04-25 11:35:33 +08:00
@tempdban 哦,你喜欢啦。
mengzhuo
2019-04-25 20:43:28 +08:00
@tempdban

不是语气问题。
Hash 至少要满足 collision free 的,至少 CRC32 是不满足的,拿来做 Hash 就会出现重复键的数据,程序就会出错的。

https://stackoverflow.com/questions/460576/hash-code-and-checksum-whats-the-difference
tempdban
2019-04-25 21:26:05 +08:00
@mengzhuo https://doc.dpdk.org/api/rte__hash__crc_8h.html 本来我没想和你犟这个事,你贴的网页你自己都不看的么。
“拿来做 Hash 就会出现重复键的数据”
你的 HASH 能没有冲突?
mengzhuo
2019-05-02 23:54:53 +08:00
@tempdban 这个 Collision free 是指可行的范围内,不要强掰“所有 hash 都不能冲突”。
CRC32 只能生成 32 位的 hash 值,也就是最多 2^32 个数据( 4294967296 ),也就 40 亿。
sha1,ipv6 或者我的算法都是 128 位,最多 2^128 ( 3.4028237e+38 ),比所有目前可观测的星星都多 200 倍。

p.s. 为了验证冲突率,我还特意添加了 Smhasher
https://github.com/aappleby/smhasher/wiki/SMHasher
结果所有测试都通过了,这下我更加放心了。
mengzhuo
2019-05-02 23:57:02 +08:00
@bestkayle 好了,加了张图

Github page 真香哈
tempdban
2019-05-03 00:09:18 +08:00
@mengzhuo 没完没了了,我 CRC32 几个周期,你的 hash 几个周期,可行范围内,你知道我可行范围是啥啊。
我完全没说你的算法问题,我只是告诉那个人,有很多 hash 是 CRC 做的,完全不带情绪。
第一条甚至都没 @你
你的东西好,行,高性能软件里无数的 hash 都是 CRC 做的,人也没觉得冲突大啊。
那就用得有问题了,这是你原话,这些年用的好好的凭什么到你这就有问题。
我就问你 crc32 能不能做 hash ?扯这么多干什么

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/558419

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX