rust 更快的顺序键HashMap

iyfjxgzm 于 2023-04-21 发布在其他

关注(0)|答案(5)|浏览(313)

最初我非常惊讶地发现Rust的HashMap，即使使用FNV散列器，也比Java，.NET，PHP中的等价物慢得多。我说的是优化的发布模式，我做了一些计算，发现Java/.NET/PHP中的时间低得令人怀疑。然后我突然想到--尽管我是用一个大的哈希表来测试的（数百万个条目），我阅读的大多是连续的 key 值（如14, 15, 16, ...），这显然导致了 * 大量的 * CPU缓存命中，这是由于这些语言中的标准哈希表（以及整数和短字符串的哈希代码函数）的实现方式，因此具有附近键的条目通常位于附近的内存位置。
另一方面，Rust的HashMap使用了所谓的SwissTable实现，它显然以不同的方式分配值。当我测试通过随机键阅读时，一切都很到位-“竞争对手”得分落后于Rust。
因此，如果我们需要按顺序执行大量的get，例如迭代一些有序且大部分顺序的DB ID（没有太多间隙），那么是否有一个好的Rust哈希Map实现可以与Java的HashMap或.NET的Dictionary竞争？
P.S.根据评论中的要求，我在这里粘贴了一个示例。我运行了很多测试，但这里有一个简单的示例，在Rust（发布模式）中需要75毫秒，在Java中需要20毫秒：
在Rust中：

let hm: FnvHashMap<i32, i32> = ...;  
// Start timer here
let mut sum: i64 = 0;
for i in 0..1_000_000 {
    if let Some(x) = hm.get(&i) {
        sum += *x as i64;
    }
}
println!("The sum is: {}", sum);

在Java中：

Map<Integer, Integer> hm = ...;
// Start timer here
long sum = 0;
for (int i = 0; i < 1_000_000; i++) {
    sum += hm.get(i);
}

使用HashMap<i32, i32>和它的默认SipHash哈希器需要190毫秒。我知道 * 为什么 * 它比FnvHashMap慢。我只是为了完整性而提到它。

rust

来源：https://stackoverflow.com/questions/70551997/faster-hashmap-for-sequential-keys

5条答案

按热度按时间

p4tfgftt1#

首先，这里有一些可运行的代码来衡量不同实现的效率：

use std::{collections::HashMap, time::Instant};

fn main() {
    let hm: HashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
    let t0 = Instant::now();
    let mut sum = 0;
    for i in 0..1_000_000 {
        if let Some(x) = hm.get(&i) {
            sum += x;
        }
    }
    let elapsed = t0.elapsed().as_secs_f64();
    println!("{} - The sum is: {}", elapsed, sum);
}

在我写这篇文章的旧桌面机器上，它报告运行76毫秒。由于这台机器已经有10多年的历史了，我发现你的硬件运行同样的代码需要190毫秒，这让我很困惑，所以我想知道你实际上是如何测量的。但是让我们忽略它，集中在相对数字上。
当你关心Rust中hashmap的效率，并且密钥不是来自不可信的来源时，首先要尝试的应该是切换到不抵抗DOS的哈希函数。一种可能性是来自fnv机箱的FNV哈希函数，你可以通过将HashMap切换到fnv::FnvHashMap来获得。这将性能提高到34毫秒，即2.2倍加速。
如果这还不够，您可以尝试使用rustc-hash crate中的散列（与fxhash几乎相同，但allegedly维护得更好），它使用与Rust编译器相同的函数，改编自Firefox使用的哈希。不基于任何形式化分析，它在哈希函数测试套件上表现很差，但据报道，性能始终优于FNV。这在上面的示例中得到了证实，其中从FnvHashMap切换到rustc_hash::FxHashMap将时间缩短到28 ms，即从初始时间2.7倍加速。
最后，如果你只想模仿C#和Java的操作，并且不太关心某些插入数字的模式会导致性能下降，你可以使用名称恰当的nohash_hasher crate，它会给你一个身份散列。将HashMap<i32, i32>更改为HashMap<i32, i32, nohash_hasher::BuildNoHashHasher<i32>>将时间降低到不到4毫秒，即从初始时间开始的惊人19倍加速。
由于您报告Java示例比Rust快9.5倍，因此19倍的加速应该使您的代码大约是Java的两倍。

赞(0）回复(0）举报 2023-04-21

bejyjqdl2#

根据用户4815162342的建议，我决定再进行一些测试。这次我使用了另一台安装Ubuntu 20.04的机器。

Rust代码

println!("----- HashMap (with its default SipHash hasher) -----------");
let hm: HashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
for k in 0..6 {
    let t0 = Instant::now();
    let mut sum: i64 = 0;
    for i in 0..1_000_000 {
        if let Some(x) = hm.get(&i) {
            sum += *x as i64;
        }
    }
    let elapsed = t0.elapsed().as_secs_f64();
    println!("The sum is: {}. Time elapsed: {:.3} sec", sum, elapsed);
}

println!("----- FnvHashMap (fnv 1.0.7) ------------------------------");
let hm: FnvHashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
for k in 0..6 {
    let t0 = Instant::now();
    let mut sum: i64 = 0;
    for i in 0..1_000_000 {
        if let Some(x) = hm.get(&i) {
            sum += *x as i64;
        }
    }
    let elapsed = t0.elapsed().as_secs_f64();
    println!("The sum is: {}. Time elapsed: {:.3} sec", sum, elapsed);
}

println!("----- FxHashMap (rustc-hash 1.1.0) ------------------------");
let hm: FxHashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
for k in 0..6 {
    let t0 = Instant::now();
    let mut sum: i64 = 0;
    for i in 0..1_000_000 {
        if let Some(x) = hm.get(&i) {
            sum += *x as i64;
        }
    }
    let elapsed = t0.elapsed().as_secs_f64();
    println!("The sum is: {}. Time elapsed: {:.3} sec", sum, elapsed);
}

println!("----- HashMap/BuildNoHashHasher (nohash-hasher 0.2.0) -----");
let hm: HashMap<i32, i32, nohash_hasher::BuildNoHashHasher<i32>> = (0..1_000_000).map(|i| (i, i)).collect();
for k in 0..6 {
    let t0 = Instant::now();
    let mut sum: i64 = 0;
    for i in 0..1_000_000 {
        if let Some(x) = hm.get(&i) {
            sum += *x as i64;
        }
    }
    let elapsed = t0.elapsed().as_secs_f64();
    println!("The sum is: {}. Time elapsed: {:.3} sec", sum, elapsed);
}

顺便说一句，最后一个可以替换为这个较短的类型：

let hm: IntMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();

对于那些感兴趣的人来说，这是IntMap的定义：

pub type IntMap<K, V> = std::collections::HashMap<K, V, BuildNoHashHasher<K>>;

Java代码

在同一台机器上，我测试了一个Java示例。我没有安装JVM，所以我使用了Docker镜像adoptopenjdk/openjdk14，并直接将下面的代码粘贴到jshell>中（不确定这是否会影响Java的计时）。所以这是Java代码：

Map<Integer, Integer> hm = new HashMap<>();
for (int i = 0; i < 1_000_000; i++) {
    hm.put(i, i);
}
for (int k = 0; k < 6; k++) {
    long t0 = System.currentTimeMillis();
    // Start timer here
    long sum = 0;
    for (int i = 0; i < 1_000_000; i++) {
        sum += hm.get(i);
    }
    System.out.println("The sum is: " + sum + ". Time elapsed: " + (System.currentTimeMillis() - t0) + " ms");
}

结果

Rust（释放模式）：

----- HashMap (with its default SipHash hasher) -----------
The sum is: 499999500000. Time elapsed: 0.149 sec
The sum is: 499999500000. Time elapsed: 0.140 sec
The sum is: 499999500000. Time elapsed: 0.167 sec
The sum is: 499999500000. Time elapsed: 0.150 sec
The sum is: 499999500000. Time elapsed: 0.261 sec
The sum is: 499999500000. Time elapsed: 0.189 sec
----- FnvHashMap (fnv 1.0.7) ------------------------------
The sum is: 499999500000. Time elapsed: 0.055 sec
The sum is: 499999500000. Time elapsed: 0.052 sec
The sum is: 499999500000. Time elapsed: 0.053 sec
The sum is: 499999500000. Time elapsed: 0.058 sec
The sum is: 499999500000. Time elapsed: 0.051 sec
The sum is: 499999500000. Time elapsed: 0.056 sec
----- FxHashMap (rustc-hash 1.1.0) ------------------------
The sum is: 499999500000. Time elapsed: 0.039 sec
The sum is: 499999500000. Time elapsed: 0.076 sec
The sum is: 499999500000. Time elapsed: 0.064 sec
The sum is: 499999500000. Time elapsed: 0.048 sec
The sum is: 499999500000. Time elapsed: 0.057 sec
The sum is: 499999500000. Time elapsed: 0.061 sec
----- HashMap/BuildNoHashHasher (nohash-hasher 0.2.0) -----
The sum is: 499999500000. Time elapsed: 0.004 sec
The sum is: 499999500000. Time elapsed: 0.003 sec
The sum is: 499999500000. Time elapsed: 0.003 sec
The sum is: 499999500000. Time elapsed: 0.003 sec
The sum is: 499999500000. Time elapsed: 0.003 sec
The sum is: 499999500000. Time elapsed: 0.003 sec

Java：

The sum is: 499999500000. Time elapsed: 49 ms  // see notes below
The sum is: 499999500000. Time elapsed: 41 ms  // see notes below
The sum is: 499999500000. Time elapsed: 18 ms
The sum is: 499999500000. Time elapsed: 29 ms
The sum is: 499999500000. Time elapsed: 19 ms
The sum is: 499999500000. Time elapsed: 23 ms

（使用Java，前1-2次运行通常较慢，因为JVM HotSpot尚未完全优化相关代码。

赞(0）回复(0）举报 2023-04-21

s4chpxco3#

Rust的HashMap默认使用SipHash的实现作为哈希函数。SipHash旨在避免基于预测哈希冲突的拒绝服务攻击，这是哈希Map中使用的哈希函数的重要安全属性。
如果你不需要这种保证，你可以使用一个更简单的哈希函数。一个选择是使用fxhash crate，它应该可以将从HashMap<i32, i32>阅读整数的速度提高3倍。
其他的选择是实现你自己的平凡散列函数（例如，通过简单地使用身份函数，这是一个适合大多数连续键的散列函数），或者使用向量而不是散列Map。
.NET uses the identity function for hashes of Int32 by default，所以它不能抵抗哈希洪水攻击。当然这更快，但缺点甚至没有在documentation of Dictionary中提到。无论如何，我更喜欢Rust的“默认安全”方法而不是.NET的任何一天，因为许多开发人员甚至没有意识到可预测的哈希函数可能会导致的问题。如果你不这样做，Rust仍然允许你使用更高性能的哈希函数。不需要哈希泛洪保护，所以对我个人来说，这似乎是Rust的一个优点，至少与.NET相比，而不是弱点。