CODEWITHSUNDEEP
rust
kezzos
kezzos

Reputation: 3221

Why is this hashmap search slower than expected?

What is the best way to check a hash map for a key? Currently I am using this:

let hashmap = HashMap::<&str, &str>::new();  // Empty hashmap

let name = "random";

for i in 0..5000000 {
    if !hashmap.contains_key(&name) { 
        // Do nothing
        }
}

This seems to be fast in most cases and takes 0.06 seconds when run as shown, but when I use it in this following loop it becomes very slow and takes almost 1 min on my machine. (This is compiling with cargo run --release). The code aims to open an external program, and loop over the output from that program.

let a = vec!["view", "-h"]; // Arguments to open process with
let mut child = Command::new("samtools").args(&a)
                                        .stdout(Stdio::piped())
                                        .spawn()
                                        .unwrap();

let collect_pairs = HashMap::<&str, &str>::new();

if let Some(ref mut stdout) = child.stdout {
    for line in BufReader::new(stdout).lines() {
        // Do stuff here          
        let name = "random";
        if !collect_pairs.contains_key(&name) {
            // Do nothing
        }
    }
}

For some reason adding the if !collect_pairs.contains_key( line increases the run time by almost a minute. The output from child is around 5 million lines. All this code exists in fn main()

EDIT

This appears to fix the problem, resulting in a fast run time, but I do not know why the !hashmap.contains_key does not work well here:

let n: Option<&&str> = collect_pairs.get(name);
if match n {Some(v) => 1, None => 0} == 1 {
  // Do something
}

Upvotes: 2

Views: 687

Answers (2)

kezzos
kezzos

Reputation: 3221

Ive found my problem, Im sorry I didnt pick up until now. I wasnt checking the return of if !collect_pairs.contains_key(&name) properly. It returns true for some reason resulting in the rest of the if block being run. I assumed it was evaluating to false. Thanks for the help

Upvotes: 0

Steve Klabnik
Steve Klabnik

Reputation: 15539

One thing to consider is that HashMap<K, V> uses a cryptographically secure hashing algorithm by default, so it will always be a bit slow by nature.

get() boils down to

self.search(k).map(|bucket| bucket.into_refs().1)

contains_key is

self.search(k).is_some()

As such, that get() is faster for you seems strange to me, it's doing more work!

Also,

if match n {Some(v) => 1, None => 0} == 1 {

This can be written more idiomatically as

if let Some(v) = n {

Upvotes: 3

Related Questions