hash

Full source code

C++

// -*- mode: c++ -*-
// $Id$
// http://www.bagley.org/~doug/shootout/

#include <stdio.h>
#include <iostream>
#include <ext/hash_map>
#include <cstring>

using namespace std;
using namespace __gnu_cxx;

struct eqstr {
    bool operator()(const char* s1, const char* s2) const {
        return strcmp(s1, s2) == 0;
    }
};

int
main(int argc, char *argv[]) {
#ifdef SMALL_PROBLEM_SIZE
#define LENGTH 50000
#else
#define LENGTH 500000
#endif
    int n = ((argc == 2) ? atoi(argv[1]) : LENGTH);
    char buf[16];
    typedef __gnu_cxx::hash_map<const char*, int, __gnu_cxx::hash<const char*>, eqstr> HM;
    HM X;

    for (int i=1; i<=n; i++) {
        sprintf(buf, "%x", i);
        X[strdup(buf)] = i;
    }

    int c = 0;
    for (int i=n; i>0; i--) {
        sprintf(buf, "%d", i);
        if (X[strdup(buf)]) c++;
    }

    cout << c << endl;
}

Rust

// Adapted from https://github.com/llvm/llvm-test-suite and
// http://www.bagley.org/~doug/shootout/
use std::env;
use std::collections::HashMap;

#[cfg(feature = "small_problem_size")]
const LENGTH: i32 = 50000;

#[cfg(not(feature = "small_problem_size"))]
const LENGTH: i32 = 500000;

fn main() {
    let mut args = env::args();
    let n = if args.len() == 2 {
        args.nth(1).unwrap().parse::<i32>().unwrap()
    } else {
        LENGTH
    };

    let mut x = HashMap::<String, i32>::new();

    for i in 1..=n {
        let s = format!("{:X}", i);
        x.insert(s, i);
    }

    let mut c: i32 = 0;
    for i in (1..=n).rev() {
        let s = format!("{}", i);
        if x.contains_key(&s) {
            c += 1;
        }
    }

    println!("{}", c);
}

Porting notes

Using the standard string and hash map types

C++

    char buf[16];
    typedef __gnu_cxx::hash_map<const char*, int, __gnu_cxx::hash<const char*>, eqstr> HM;
    HM X;

Rust

#![allow(unused)]
fn main() {
    let mut x = HashMap::<String, i32>::new();
}

The C++ version uses the C string char* and the GNU extension hash map __gnu_cxx::hash_map as opposed to std::string and std::unordered_map. I suspect that this program was originally written before the standard hash map became part of the C++ standard.

In the Rust version, we use the Rust standard String and std::collections::HashMap rather than more faithfully reproducing C string-like data structures or reimplementing the C++ hash_map in Rust to stick to the idiomatic Rust style.

There is no need to implement or pass the hash and the equal functions for the string type for the hash map in the Rust version, which would be equivalent to __gnu_cxx::hash<const char*> and eqstr, because they are provided by the standard library. This is also the case in std::unordered_map in C++.

`For` range loops with the inclusive range ends

C++

    for (int i=1; i<=n; i++) {
        ...
    }
    ...
    for (int i=n; i>0; i--) {
        ...
    }

Rust

#![allow(unused)]
fn main() {
    for i in 1..=n {
        ...
    }
    ...
    for i in (1..=n).rev() {
        ...
    }
}

The for range loop for i in 1..=n { ... } has the range end n inclusive and is equivalent to for (int i=1; i<=n; i++) { ... } in C++.

Similarly, the reverse ordered range loop for i in (1..=n).rev() { ... } is equivalent to for (int i=n; i>0; i--) { ... } in C++.

Formating strings

C++

        sprintf(buf, "%x", i);

Rust

#![allow(unused)]
fn main() {
        let s = format!("{:X}", i);
}

A common way to format a string in Rust is to use format! roughly corresponding to sprintf in C++.

While the C++ version writes into an already allocated buffer, the Rust version allocates a new string. This could significantly affect the performance difference but it will be roughly canceled out by the fact that the C++ version will copy the key when inserting the key into hash map in the next line.

Inserting into a hash map

C++

        X[strdup(buf)] = i;

Rust

#![allow(unused)]
fn main() {
        x.insert(s, i);
}

Rust HashMap has the square bracket operator [] but it will panic if the key already exists, unlike the C++ hash map. So we use insert instead.

Checking whether an hash map already contains a key

C++

        if (X[strdup(buf)]) c++;

Rust

#![allow(unused)]
fn main() {
        if x.contains_key(&s) {
            c += 1;
        }
}

There is a subtle difference that the C++ version inserts a new entry with the default value 0 when the key is not already contained in the hash map, in addition to checking whether the key is already contained, while the Rust version only checks if the key is already contained, again, because Rust HashMap's [] operator will panic if the key does not already exist in the hash map.

This difference is absorbed by the fact that value 0 is not used across the two loops and the two if statements branch the same way.

C++ to Rust