why emplace_hint slow than insert in map?

Question

uint64_t get_ticks(){
    struct timeval now;
    gettimeofday(&now, NULL);
    uint64_t r = ((now.tv_sec) * 1000) +((now.tv_usec) / 1000);
    return r;}

emplace_hint usage like this:

    #define MAX_INSRT 500000
int main(int argc,char** argv)
{
     int last;
     map<int,int> mps;
     map<int,int>::iterator it;
     uint64_t beg,end;
     string str;
     it = mps.end();
     beg=get_ticks();
     for(int i=0;i<MAX_INSRT;i++) {
         int x = rand()%200000000;
         it = mps.lower_bound(x);
         if (it != mps.end() && it->first == x) {
             ;
         } else {
             mps.emplace_hint(it,x,i);
         }
     }
     end=get_ticks();
     printf("cost time = %lu, map size = %zu\n",end-beg,mps.size());
     return 0;
}

output: cost time = 740, map size = 499343

insert usage like this:

#define MAX_INSRT 500000
int main(int argc,char** argv)
{
     int last;
     map<int,int> mps;
     map<int,int>::iterator it;
     uint64_t beg,end;
     string str;
     it = mps.end();
     beg=get_ticks();
     for(int i=0;i<MAX_INSRT;i++) {
         int x = rand()%200000000;
         mps.insert(map<int,int>::value_type(x,i));
     }
     end=get_ticks();
     printf("cost time = %lu, map size = %zu\n",end-beg,mps.size());
     return 0;
}

output: cost time = 691, map size = 499343

compile: $g++ -g -std=c++11 -o new_map new_map.cc

g++ version: gcc version 4.9.2 (GCC)

don't understand why is it happen...

Answer 1

I repeated the test on wandbox.org (after applying some cosmetics to the sample code):

#include <sys/time.h>
#include <iomanip>
#include <iostream>
#include <map>

const int N = 10;
const int Max = 100000;

uint64_t get_ticks()
{
  struct timeval now;
  gettimeofday(&now, NULL);
  const uint64_t r = ((now.tv_sec) * 1000) +((now.tv_usec) / 1000);
  return r;
}

uint64_t checkInsert()
{
  std::map<int, int> map;
  const uint64_t t0 = get_ticks();
  for (int i = 0; i < Max; ++i) {
    const int x = rand() % 200000000;
    map.insert(std::make_pair(x, i));
  }
  const uint64_t t1 = get_ticks();
  return t1 - t0;
}

uint64_t checkEmplace()
{
  std::map<int, int> map;
  const uint64_t t0 = get_ticks();
  for (int i = 0; i < Max; ++i) {
    const int x = rand() % 200000000;
    const std::map<int, int>::iterator iter = map.lower_bound(x);
    if (iter == map.end() || iter->first != x) {
      map.emplace_hint(iter, x, i);
    }
  }
  const uint64_t t1 = get_ticks();
  return t1 - t0;
}

int main()
{
  for (int i = 1; i <= N; ++i) {
    uint64_t tIns = checkInsert();
    uint64_t tEmp = checkEmplace();
    std::cout << std::setw(10) << tIns << std::setw(10) << tEmp << '\n';
  }
  // done
  return 0;
}

The compiler was gcc HEAD 9.0.0 201808 with -O2.

Output:

    71        62
    45        76
    90        75
    81        77
    83        81
    79        70
    87       102
    92        85
    85        67
    78        96

Live Demo on wandbox

My interpretation:

It is not possible to measure a significant difference between std::map::insert() and std::map::emplace_hint() – at least not for a std::map<int, int>.

The measurement noise seems to hide any true difference in the experiment if it exists at all.