Why traversing Go hashmap so slower then C++ hashmap

[Yan Li]

System env:

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 18.04.6 LTS
Release:        18.04
Codename:       bionic

$ go version

go version go1.18.3 linux/amd64

$ g++ -v

gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)

Test traversing Go hashmap:

package main

import (
    "fmt"
    "time"
)

var size = 9999999;

func test_map() {
    m1 := make(map[int]int)
    for i := 0; i < size; i++ {
        m1[i] = i
    }

    sum := 0
    s := time.Now()
    for _, v := range(m1) {
        sum += v
    }
    fmt.Printf("m1  range sum:%v %v\n", sum, time.Since(s))

    sum = 0
    s = time.Now()
    for i := 0; i < size; i++ {
        sum += m1[i]
    }
    fmt.Printf("m1 direct sum:%v %v\n", sum, time.Since(s))
}

func main() {
    test_map()
}

Test traversing C++ hashmap:

#include <unordered_map>

#include <stdio.h>
#include <stdint.h>
#include <unistd.h>

int size = 9999999;

static uint64_t
gettime() {
    uint64_t t;
    struct timespec ti;
    clock_gettime(CLOCK_MONOTONIC, &ti);
    t = (uint64_t)ti.tv_sec * 1000;
    t += ti.tv_nsec / 1000000;
    return t;
}

void test_hashmap() {
    std::unordered_map<int, int> m1;
        for (int i = 0; i < size; i++) {
        m1[i] = i;
    }

    uint64_t sum = 0;
    uint64_t s = gettime();
    s = gettime();
    for (auto& v : m1) {
        sum += v.second;
    }
    printf("v1 foreach sum:%lu ms:%lu\n", sum, gettime() - s);

    sum = 0;
    s = gettime();
    for (int i = 0; i < size; i++) {
        sum += m1[i];
    }
    printf("v1  direct sum:%lu ms:%lu\n", sum, gettime() - s);
}

int main() {
    test_hashmap();
    return 0;
}

Compare running result:

running Go

$ go build test.go
$ ./test
m1  range sum:49999985000001 161.385148ms
m1 direct sum:49999985000001 851.517707ms

running C++

$ g++ -g -Wall -O2 test.cc
$ ./a.out
v1 foreach sum:49999985000001 ms:31
v1  direct sum:49999985000001 ms:104

Question:

Go 161.385148ms vs C++ ms:31

Go 851.517707ms vs C++ ms:104

My question is why traversing go map Significantly slowly?

Can it be improved?

[Ian Lance Taylor]

On Tue, Jun 28, 2022 at 9:56 PM Yan Li <yl.mec...@gmail.com> wrote:
>
> Question:
> Go 161.385148ms vs C++ ms:31
> Go 851.517707ms vs C++ ms:104
> My question is why traversing go map Significantly slowly?
> Can it be improved?

I don't know exactly why there is a speed difference.

That said, there are significant differences between Go map and C++
unordered_map. For example:

- Go map iteration is in random order. C++ unordered_map iteration is
unpredictable but consistent.

- If you add an element to a Go map during the iteration, the behavior
is specified. If you add an element to a C++ unordered_map all
iterators may be invalidated, breaking the loop.

Also, there is an implementation difference: the C++ code is compiled
inline with the exact types being used. This takes more compile time
but produces faster run time. The Go code uses a single shared
implementation for maps of all types. This takes less compile time
but more run time.

Perhaps a combination of all these things explains the difference, or
perhaps there is more going on that I don't know about.

Ian