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

S

sanket

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;
while(*it2 > key && it2 >= begin ) { *(it2+1) = *it2; it2--;}
*(it2 + 1) = key;
}

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::eek:stream_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::eek:stream_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 = rand()%100;
}


boost::progress_timer howlong;
insertionsort(a, n);
/*
for(i = 0; i < n; i++)
{
printf("%d ", a);
}
*/
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
 
J

Juha Nieminen

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

Firstly, the implementations are different (one uses iterators, the other
uses direct indexing). That doesn't explain it, though.

Secondly, your implementation is buggy. You are indexing out of boundaries.
(I'll leave it as an exercise to find the bug.)

Thirdly, when I run the two programs in my system (after fixing the bug),
there's no measurable difference between them (both take a small fraction of
a second to run with 10000 elements).

Either the bug is causing a large delay for some reason (it's undefined
behavior after all), you are not compiling with optimizations, or there's
something else going on.
 
8

88888 Dihedral

sanketæ–¼ 2011å¹´10月31日星期一UTC+8下åˆ1時40分18秒寫é“:
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::eek:stream_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::eek:stream_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 = rand()%100;
}


boost::progress_timer howlong;
insertionsort(a, n);
/*
for(i = 0; i < n; i++)
{
printf("%d ", a);
}
*/
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
 
S

sanket

  Firstly, the implementations are different (one uses iterators, the other
uses direct indexing). That doesn't explain it, though.

  Secondly, your implementation is buggy. You are indexing out of boundaries.
(I'll leave it as an exercise to find the bug.)

  Thirdly, when I run the two programs in my system (after fixing the bug),
there's no measurable difference between them (both take a small fractionof
a second to run with 10000 elements).

  Either the bug is causing a large delay for some reason (it's undefined
behavior after all), you are not compiling with optimizations, or there's
something else going on.


I got rid of the bug and turned on optimization level -02 for both
implementations. The C++ code is much faster now. It now takes 0.03
seconds for 10000 elements, 3.58 seconds for 100000 elements and
104.15 seconds for 500000 elements, whereas the C code now takes 0.02
seconds for 10000 elements, 2.87 seconds for 100000 elements and 71.44
seconds for 500000 elements.
 
J

Juha Nieminen

A said:
why not use quicksort instead it is way faster than others except maybe swap
sort?

I don't think that was the point.

(Yet another fake sender name for our old friend Paul?)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,835
Latest member
KetoRushACVBuy

Latest Threads

Top