dqfxao2898
2019-02-12 19:05 浏览 368

go和c ++之间的地图性能比较[关闭]

I don't understand how golang is outperforming c++ in this operation by 10 times, even the map lookup is 3 times faster in go than c++.

this is the c++ snippet

#include <iostream>
#include <unordered_map>
#include <chrono>

std::chrono::nanoseconds elapsed(std::chrono::steady_clock::time_point start) {
    std::chrono::steady_clock::time_point now = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(now - start);
}
void make_map(int times) {
    std::unordered_map<double, double> hm;
    double c = 0.0;
    for (int i = 0; i < times; i++) {
        hm[c] = c + 10.0;
        c += 1.0;
    }
}

int main() {
    std::chrono::steady_clock::time_point start_time = std::chrono::high_resolution_clock::now();
    make_map(10000000);
    printf("elapsed %lld", elapsed(start_time).count());
}

this is the golang snippet:

func makeMap() {
    o := make(map[float64]float64)
    var i float64 = 0
    x := time.Now()
    for ; i <= 10000000; i++ {
        o[i] = i+ 10
    }
    TimeTrack(x)
}
func TimeTrack(start time.Time) {
    elapsed := time.Since(start)

    // Skip this function, and fetch the PC and file for its parent.
    pc, _, _, _ := runtime.Caller(1)

    // Retrieve a function object this functions parent.
    funcObj := runtime.FuncForPC(pc)

    // Regex to extract just the function name (and not the module path).
    runtimeFunc := regexp.MustCompile(`^.*\.(.*)$`)
    name := runtimeFunc.ReplaceAllString(funcObj.Name(), "$1")

    log.Println(fmt.Sprintf("%s took %s", name, elapsed))
}

What I'd like to know is how to optimize the c++ to achieve better performance.

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

3条回答 默认 最新

  • 已采纳
    dongzi5673 dongzi5673 2019-02-12 20:01

    Updated to measure similar operations for both cpp and go. It starts measurment before calling the map-making function and ends it when the function returns. Both versions reserve space in the map and return the created map (from which a couple of numbers are printed).

    Slightly modified cpp:

    #include <iostream>
    #include <unordered_map>
    #include <chrono>
    
    std::unordered_map<double, double> make_map(double times) {
        std::unordered_map<double, double> m(times);
    
        for (double c = 0; c < times; ++c) {
            m[c] = c + 10.0;
        }
        return m;
    }
    
    int main() {
        std::chrono::high_resolution_clock::time_point start_time = std::chrono::high_resolution_clock::now();
        auto m = make_map(10000000);
        std::chrono::high_resolution_clock::time_point end_time = std::chrono::high_resolution_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end_time-start_time);
        std::cout << elapsed.count()/1000000000. << "s
    ";
        std::cout << m[10] << "
    "
                  << m[9999999] << "
    ";    
    }
    
    % g++ -DNDEBUG -std=c++17 -Ofast -o perf perf.cpp
    % ./perf
    2.81886s
    20
    1e+07
    

    Slightly modified go version:

    package main
    
    import (
        "fmt"
        "time"
    )
    
    func make_map(elem float64) map[float64]float64 {
        m := make(map[float64]float64, int(elem))
        var i float64 = 0
        for ; i < elem; i++ {
            m[i] = i + 10
        }
        return m
    }
    
    func main() {
        start_time := time.Now()
        r := make_map(10000000)
        end_time := time.Now()
        fmt.Println(end_time.Sub(start_time))
        fmt.Println(r[10])
        fmt.Println(r[9999999])
    }
    
    % go build -a perf.go
    % ./perf
    1.967707381s
    20
    1.0000009e+07
    

    It doesn't look like a tie as it did before the update. One thing slowing the cpp version down is the default hashing function for double. When replacing it with a really bad (but fast) hasher, I got the time down to 1.89489s.

    struct bad_hasher {
        size_t operator()(const double& d) const {
            static_assert(sizeof(double)==sizeof(size_t));
    
            return
                *reinterpret_cast<const size_t*>( reinterpret_cast<const std::byte*>(&d) );
        }
    };
    
    点赞 评论 复制链接分享
  • duanbu1998 duanbu1998 2019-02-12 19:51

    It's a bit hard to pin down "the speed of C++" (for almost any particular thing) because it can depend on quite a few variables, such as the compiler you use. For example, I'm typically seeing a difference of 2:1 or so between gcc and msvc for the C++ version of this code.

    As far as differences between C++ and Go, I'd guess it's mostly down to differences in how the hash tables are implemented. One obvious point is that Go's map implementation allocates data space in blocks of 8 elements at a time. At least the standard library implementations I've seen, std::unordered_map places only one item per block.

    We'd expect this to mean that in a typical case, the C++ code will do much larger number of individual allocations from the heap/free store, so its speed will depend much more heavily on the speed of the heap manager. The Go version should also have a substantially higher locality of reference so it makes better user of the cache.

    Given those differences, I'm a little surprised that you're only seeing a 10:1 difference. My immediate guess would have been (somewhat) higher than that--but as we all know, one measurement is worth more than 100 guesses.

    Reference

    Go's Map Implementation

    liststdc++ unordered_map

    libc++ unordered_map

    点赞 评论 复制链接分享
  • duanbin3021 duanbin3021 2019-02-12 20:41

    Meaningless microbenchmarks produce meaningless results.


    Continuing @mrclx's and @TedLyngmo's microbenchmark thread, fix the bug in @TedLyngmo's Go microbenchmark:

    perf.go:

    package main
    
    import (
        "fmt"
        "time"
    )
    
    func makeMap(elem float64) time.Duration {
        x := time.Now()
        o := make(map[float64]float64, int(elem))
        var i float64 = 0
        for ; i < elem; i++ {
            o[i] = i + 10
        }
        t := time.Now()
        return t.Sub(x)
    }
    
    func main() {
        r := makeMap(10000000)
        fmt.Println(r)
    }
    

    Output:

    $ go version
    go version devel +11af353531 Tue Feb 12 14:48:26 2019 +0000 linux/amd64
    $ go build -a perf.go
    $ ./perf
    1.649880112s
    $ 
    

    perf.cpp:

    #include <iostream>
    #include <unordered_map>
    #include <chrono>
    
    void make_map(double times) {
        std::unordered_map<double, double> hm;
        hm.reserve(static_cast<size_t>(times)); // <- good stuff
    
        for (double c = 0; c < times; ++c) {
            hm[c] = c + 10.0;
        }
    }
    
    int main() {
        std::chrono::high_resolution_clock::time_point start_time = std::chrono::high_resolution_clock::now();
        make_map(10000000);
        std::chrono::high_resolution_clock::time_point end_time = std::chrono::high_resolution_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end_time-start_time);
        std::cout << elapsed.count()/1000000000. << "s
    ";
    }
    

    Output:

    $ g++ --version
    g++ (Ubuntu 8.2.0-7ubuntu1) 8.2.0
    $ g++ -DNDEBUG -std=c++17 -Ofast -o perf perf.cpp
    $ ./perf
    3.09203s
    $ 
    

    Go leads!

    点赞 评论 复制链接分享

相关推荐