user1995120
user1995120

Reputation: 167

Google sparse hash slow for map of int to vector

I have a map of uint64_t to vector. The map takes an unusually long time (~70s) to build compared to unordered_map(~4s) for a string input of 4MB in size. Similarly, 120s vs 2400s for a string input of size ~150MB.

Unordered_map is generally faster than google sparse hash, but the difference in time is huge. Sparse hash is ~2 times slower(than unordered map) for a map to int to int.

I fail to understand the reason behind this time difference.

Code snippet:

int main(){
std::string input,reference;

while (getline(cin,input)) {
    reference += input;
    input.clear();
}

cout<<"length of reference = "<<reference.length()<<endl;

google::sparse_hash_map<uint64_t, vector<uint32_t>> m;
//unordered_map<uint64_t, vector<uint32_t>> m;
for (auto it = reference.begin(); it != reference.end(); it++) {
    m[it-reference.begin()].push_back(it-reference.begin());
}
return 0;
}

This is the result of /usr/bin/time on the program

length of reference = 4641652
    Command being timed: "./a.out"
    User time (seconds): 76.06
    System time (seconds): 0.31
    Percent of CPU this job got: 99%
    Elapsed (wall clock) time (h:mm:ss or m:ss): 1:16.43
    Average shared text size (kbytes): 0
    Average unshared data size (kbytes): 0
    Average stack size (kbytes): 0
    Average total size (kbytes): 0
    Maximum resident set size (kbytes): 308228
    Average resident set size (kbytes): 0
    Major (requiring I/O) page faults: 0
    Minor (reclaiming a frame) page faults: 230585
    Voluntary context switches: 1
    Involuntary context switches: 2316
    Swaps: 0
    File system inputs: 0
    File system outputs: 0
    Socket messages sent: 0
    Socket messages received: 0
    Signals delivered: 0
    Page size (bytes): 4096
    Exit status: 0

Upvotes: 1

Views: 385

Answers (0)

Related Questions