Re: Insertion Sort : C++ implementation 100 times slower than C implementation

From:

88888 Dihedral <dihedral88888@googlemail.com>

Newsgroups:

comp.lang.c++

Date:

Mon, 31 Oct 2011 03:08:33 -0700 (PDT)

Message-ID:

<15218511.770.1320055713751.JavaMail.geo-discussion-forums@prms22>

sanket=E6=96=BC 2011=E5=B9=B410=E6=9C=8831=E6=97=A5=E6=98=9F=E6=9C=9F=E4=B8=
=80UTC+8=E4=B8=8B=E5=8D=881=E6=99=8240=E5=88=8618=E7=A7'=E5=AF=AB=E9=81=
=93=EF=BC=9A

Hello everyone,

I implemented the insertion sort algorithm in C and C++ and tried
comparing the performance.

Here are the implementations
1. C++

# include<iostream>
# include<vector>
# include<iterator>
# include<algorithm>
# include<cstdlib>
#include <boost/progress.hpp>

using namespace std;

typedef std::vector<int> t1;

void insertionsort(t1& vin)
{
    t1::iterator it1;
    t1::iterator it2;
    t1::iterator begin = vin.begin();
    t1::iterator end = vin.end();
    for(it1 = begin + 1; it1 != end; it1++)
    {
        int key = *it1;
        it2 = it1 - 1;

it2 ranges in [ begin, it1),

while(*it2 > key && it2 >= begin ) { *(it2+1) = *it2;
it2--;}

it2 ranges in [begin-1, it1-2]

*(it2 + 1) = key;

valid access range in *(it2+1) , one iterator is enough

     }

    return;

}

int main(int argc, char* argv[])
{
    if(argc != 2){cout << "Usage:\na.out <number of elements>" << endl;
exit(-1);}

    int b = 0;
    int n = atoi(argv[1]);

    t1 v;
    v.reserve(n);
    for(int i=0; i < n; i++) { b = rand(); v.push_back(b);}
    t1 &vin = v;

    /*
    std::cout<< "Unsorted Array"<< std::endl ;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, "
"));
    std::cout<< std::endl ;
    */

    boost::progress_timer howlong;
    insertionsort(vin);
    /*
    std::cout<< "Sorted Array"<< std::endl ;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, "
"));
    std::cout<< std::endl ;
    */

    return 0;
}

2. C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <boost/progress.hpp>

void insertionsort(int* a, int n)
{
    int i, j;
    int key;
    for(i= 0; i < n; i++)
    {
        key = a[i+1];
        j = i ;

        while(a[j] > key && j >= 0) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

int main(int argc, char** argv)
{
    int n = atoi(argv[1]);
    int * a = (int*)malloc(n * sizeof(int));
    int i = 0;

    for(i = 0; i < n; i++)
    {
        a[i] = rand()%100;
    }

    boost::progress_timer howlong;
    insertionsort(a, n);
    /*
    for(i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    */
    printf("\n");
    return 0;
}

Here are the performance results:

Number of integer elements C implementation C++ implementation
10000 0.16 s
1.17 s
100000 16.69 s
116.16s

I compiled both programs using g++ compiler and used boost to measure
the time elapsed.

This is shocking to me, since C++ should be close to C in performance.
Why is the C++ implementation 100 times slower?

Thanks,
Sanket