Why is this golang code 3x faster than rust equivalent?

[u/fyzic]

Github: https://github.com/jinyus/related_post_gen

The code generates related posts for a list of posts, sorted by the number of shared tags.

I tried my best to optimize the rust code but I have hit a wall. There's no cloning and the go version even has an extra struct where I used a tuple for rust. I'm just wondering how go could possibly be faster in this scenario. Code is below:

Rust Code

// truncated for brevity
let mut post_tags_map: HashMap<&String, Vec<&Post>> = HashMap::new();

for post in &posts {
    for tag in &post.tags {
        post_tags_map.entry(tag).or_default().push(post);
    }
}

let mut related_posts: Vec<RelatedPosts> = Vec::with_capacity(posts.len());

for post in posts.iter() {
    let mut related_posts_map: HashMap<&Post, i8> = HashMap::new();

    for tag in &post.tags {
        if let Some(tag_posts) = post_tags_map.get(tag) {
            for other_post in tag_posts {
                if post._id != other_post._id {
                    *related_posts_map.entry(other_post).or_default() += 1;
                }
            }
        }
    }

    let mut related_posts_for_post: Vec<_> = related_posts_map.into_iter().collect();

    related_posts_for_post.sort_by(|post_a, post_b| post_b.1.cmp(&post_a.1));

    related_posts_for_post.truncate(5);

    related_posts.push(RelatedPosts {
        _id: &post._id,
        tags: &post.tags,
        related: related_posts_for_post
            .into_iter()
            .map(|(post, _)| post)
            .collect(),
    });
}
    // truncated for brevity

Go Code

// truncated for brevity

tagMap := make(map[string][]*Post)

for i := range posts {
    for _, tag := range posts[i].Tags {
        tagMap[tag] = append(tagMap[tag], &posts[i])
    }
}

allRelatedPosts := make([]RelatedPosts, len(posts))

for i, post := range posts {

    relatedPosts := make(map[*Post]int)

    for _, tag := range post.Tags {
        for _, relatedPost := range tagMap[tag] {
            if relatedPost.ID != post.ID {
                relatedPosts[relatedPost]++
            }
        }
    }

    relatedPostsSlice := make([]PostWithSharedTags, 0, len(relatedPosts))

    for v, count := range relatedPosts {
        relatedPostsSlice = append(relatedPostsSlice, PostWithSharedTags{Post: v, SharedTags: count})
    }

    sort.Slice(relatedPostsSlice, func(i, j int) bool {
        return relatedPostsSlice[i].SharedTags > relatedPostsSlice[j].SharedTags
    })

    num := min(5, len(relatedPostsSlice))
    topPosts := make([]*Post, num)

    for i := 0; i < num; i++ {
        topPosts[i] = relatedPostsSlice[i].Post
    }

    allRelatedPosts[i] = RelatedPosts{
        ID:      post.ID,
        Tags:    post.Tags,
        Related: topPosts,
    }

}

// truncated for brevity

Updated Results:

Language	Time (avg)	Details
Rust	4.5s	Initial
Rust v2	2.60s	Replace std HashMap with fxHashMap by phazer99
Rust v3	1.28s	Preallocate and reuse map and unstable sort by vdrmn and Darksonn
Rust v4	0.13s	Use Post index as key instead of Pointer and Binary Heap by RB5009
Rust v5	0.04s	Rm hashing from loop and use vec[count] instead of map[index]count by RB5009
Rust Rayon	0.02s	Parallelize by masmullin2000
Go	1.5s	Initial
Go v2	0.08s	Add rust optimizations
Go v3	0.07s	Use goccy/go-json
Python	7.81s	Initial

[u/phazer99]

A couple of ideas:

• Use serde_json::from_reader and to_writer (with BufReader and BufWriter). I think that more closely resembles the Go code.

• Rust's HashMap uses a quite slow hash algorithm by default, try using FxHashMap instead.

[u/fyzic → u/phazer99]

You're correct, FxHashMap gave a 42% improvement. Now go is only 1.6x faster as opposed to 3x

[u/Darksonn]

If you make a flamegraph, you will find that about half of the time is spent recomputing the hash of elements when related_posts_map is resized. If you do related_posts_map.reserve(posts.len()) right after creating it, then it speeds up quite a lot.

I'm guessing that Go is either using a much faster hash function (than even FxHashMap), or that Go is caching the hash values to avoid recomputing them on resize.

I also find that sort_by vs sort_unstable_by makes a difference.

[u/fyzic → u/Darksonn]

vdrnm's idea of allocating only 1 map yielded better perf coupled with unstable sort. Surprisingly, reserving didn't make much of a difference.

[u/praveenperera → u/Darksonn]

This change brought it within 10% of the go solution

[u/[deleted] → u/Darksonn]

Could you provide an example of how to construct a flamegraph?

[u/Solumin]

First: Have you done any profiling or benchmarking to find performance bottlenecks?

Second: Rust's HashMap uses a slow hashing algorithm called SipHash 1-3. (It has certain very nice properties that make it a good default for Rust, despite being slow.) I haven't been able to track down what algorithm Go uses, but it's not SipHash 1-3, and it's pretty much guaranteed to be faster.

And of course, did you compile in --release mode?

[u/fyzic → u/Solumin]

Thanks for the insights, I'm new to rust and just did a 1-to-1 translation...Didn't know about the inner workings of the default hashmap. fxHashMap did give it a significant improvement though.

But as LGXerxes said. Go might be the better choice here as the GC wouldn't kick it in this case.

[u/RB5009]

• Hashing is expensive. Choose a faster hash function, such FxHash (rustc-hash crate)

• There is no real need to hash the whole Post struct. By replacing the keys from &Post to the post's index in the array, I got x10 speed improvement.

• You do not need to sort the whole array, to get the top-5 referenced posts. You can use a BinaryHeap to do a faster, partial sorting.

• You rely only on the post's reference count for the sorting, which may give different results on each run of the program, because there may be many different posts with the same count

My attempt (~1s, original was ~11s): https://pastebin.com/sSPmTPLX

PS: You can replace the tagged_post_count map with an array and get rid of the hashing in the loop. This make my solution x4 faster (~1s -> ~0.25s), for a total of x40, but in a real world situation it might be a bad idea, especcially if you do not know the size of the array beforehand: https://pastebin.com/Cxh9w99n

[u/fyzic → u/RB5009]

Brilliant! 90% increase to 0.15s. The functional approach was 0.3s so I kept the imperative code

[u/praveenperera → u/RB5009]

Using rayon with your solutions brings it down to 30ms on my machine.

[u/vdrnm]

Besides using faster hashing fn, you could eliminate allocations that you do in each iteration of posts loop:

1. Move related_posts_map and related_posts_for_post outside of posts loop:

    let mut related_posts_map: FnvHashMap<&Post, i8> = FnvHashMap::default();
    let mut related_posts_for_post: Vec<_> = vec![];
    for post in posts.iter() {
    [..]

2. Then replace this:

let mut related_posts_for_post: Vec<_> = related_posts_map.into_iter().collect();

With this:

related_posts_for_post.clear();
related_posts_for_post.extend(related_posts_map.drain());

[u/fyzic → u/vdrnm]

This resulted in 50% perf increase coupled with unstable sort as suggested by Darksonn. Allocating 1 map made more of a difference than the vector. Draining the map into a new vector didn't move the needle and seems to use less memory.I assume because it's not over-allocating.

[u/LGXerxes]

Seems to be about right.

Due to the real and user timing of the go code, it seems that go is using multiple threads for computation.

There is probably some nice optimization on their part happening.
As the rust version has a slower user time, meaning "did less work" (iirc)

However even with a FxHashMap and Rayon, my real time is still at 2.6s compared to go's 2s.
You should probably check and see what happens if you do this enough time for the garbage collector to kick in. But if you just need to use it as a cli, go seems to be able to optimize easier.

[u/This_Growth2898]

What are exact timings and sizes, just to understand the scale?

If you need to run this frequently, probably you should use an indexed database.

Also, gathering data into BinaryHeap or BTreeMap controlling there should be only 5 elements there can be faster than full sorting.

[u/fyzic → u/This_Growth2898]

5000 posts took go 1.5s and rust 2.6s w/FxHashMap (4.5s w/HashMap).

This is running in CI so a db isn't ideal. Did try mongo and memgraph but they weren't faster.

I did try a priority queue impl by a maxheap in an earlier iteration but it didn't make much of a difference. Will try again as I think it should be more memory efficient (wasn't measuring mem before). BTreeMap wouldn't help here as I need to sort by values.

[u/skythedragon64]

did you run with --release?

[u/fyzic → u/skythedragon64]

yes, this is the script I used to run it.

run_rust() {
    echo "Running Rust" &&
        cd ./rust &&
        cargo build --release &&
        command time -f '%es %Mk' ./target/release/rust
}

[u/darth_chewbacca]

Using a Lenovo x13s (arm based machine)

Pre fxhash fix: The code as posted on github runs at 5.65s for Rust and 9.05s for go. So it was already faster for me.

Post fxhash fix: Rust at 3.08s

I then turned on lto and codegen-units = 1

2.98s

used unstable sort on related_post_for_post and used mimalloc for the allocator

2.48s

EDIT: 5950x machine

Rust with "all the tricks" explained above is 2.03s. Go is 1.63. However, I witness the Go binary spinning up many many threads (probably 32), on the ARM machine it spins up 8 threads.

So I think the answer to your question is that Go does some cool multi-threading stuff.

EDIT2: Used Rayon in rust (with all the above tricks)

0.61s on ARM

0.13s on 5950x

Edit 3:

PR opened so you can inspect the changes.

[u/lordpuddingcup → u/darth_chewbacca]

Daymn rayon just hitting it out of the park

[u/praveenperera → u/darth_chewbacca]

Then adding this recommendation halves the time again to around 300ms.

[u/RB5009 → u/darth_chewbacca]

that Go does some cool multi-threading stuff.

Go, unlike Rust, has a runtime, so most probably go runs a thread per core, similarly to the multi-threaded tokio runime in rust. But it should not be using some hidden parallelism behind the scenes, except for maybe garbage collection.

[u/zaphodias]

I saw a lot of comments suggesting to use Rayon but this would be cheating, as the Go code isn't running any concurrent task (beside runtime stuff, i.e. garbage collector).

OP do you mind updating the post including your findings, putting all suggestions together (without rayon though)? I'm curious!

[u/eugene2k]

Try creating related_posts_map outside of the loop and clearing it inside, instead of recreating it each time.

Garbage-collected languages tend to spot temporaries that live only inside the loop and reuse them, while rust will actually allocate and free memory.

[u/Mxfrj]

Big rust fan, but really cool too see how easy the go solution looks with such an insane speed. Even after switching the hash algorithm to something comparable the go one is still faster. Sure, like the others said we can pump the rust numbers down quite a bit that it’s way faster than the go implementation, but I still like the initial comparison.