Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Insertion Sort : C++ implementation 100 times slower than C implementation

Reply
Thread Tools

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

 
 
sanket
Guest
Posts: n/a
 
      10-31-2011
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:stream_iterator<int>(std::cout, "
"));
std::cout<< std::endl ;
*/

boost:rogress_timer howlong;
insertionsort(vin);
/*
std::cout<< "Sorted Array"<< std::endl ;
std::copy(v.begin(), v.end(), std: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[i] = rand()%100;
}


boost:rogress_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
 
Reply With Quote
 
 
 
 
Juha Nieminen
Guest
Posts: n/a
 
      10-31-2011
sanket <(E-Mail Removed)> wrote:
> 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.
 
Reply With Quote
 
 
 
 
88888 Dihedral
Guest
Posts: n/a
 
      10-31-2011
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:stream_iterator<int>(std::cout, "
> "));
> std::cout<< std::endl ;
> */
>
> boost:rogress_timer howlong;
> insertionsort(vin);
> /*
> std::cout<< "Sorted Array"<< std::endl ;
> std::copy(v.begin(), v.end(), std: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[i] = rand()%100;
> }
>
>
> boost:rogress_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


 
Reply With Quote
 
A
Guest
Posts: n/a
 
      10-31-2011
why not use quicksort instead it is way faster than others except maybe swap
sort?

http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html


 
Reply With Quote
 
sanket
Guest
Posts: n/a
 
      10-31-2011
On Oct 31, 1:57*am, Paavo Helde <(E-Mail Removed)> wrote:
> sanket <(E-Mail Removed)> wrote innews:(E-Mail Removed):
>
> > Hello everyone,

>
> > I implemented the insertion sort algorithm in C and C++ and tried
> > comparing the performance.
> > 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.

>
> And did you switch the optimizations on?
>
>
>
> > This is shocking to me, since C++ should be close to C in performance.
> > Why is the C++ implementation 100 times slower?

>
> The above numbers differ by a factor of 7, not 100.
>
> Cheers
> Paavo


My apologies, I meant 10 times slower.

--Sanket
 
Reply With Quote
 
sanket
Guest
Posts: n/a
 
      10-31-2011
On Oct 31, 2:04*am, Juha Nieminen <(E-Mail Removed)> wrote:
> sanket <(E-Mail Removed)> wrote:
> > 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 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.
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      11-01-2011
A <(E-Mail Removed)> wrote:
> 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?)
 
Reply With Quote
 
Tsung
Guest
Posts: n/a
 
      11-03-2011
On Oct 31, 2:57*pm, Paavo Helde <(E-Mail Removed)> wrote:
> sanket <(E-Mail Removed)> wrote innews:(E-Mail Removed):
>
> > Hello everyone,

>
> > I implemented the insertion sort algorithm in C and C++ and tried
> > comparing the performance.
> > 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.

>
> And did you switch the optimizations on?
>
>
>
> > This is shocking to me, since C++ should be close to C in performance.
> > Why is the C++ implementation 100 times slower?

>
> The above numbers differ by a factor of 7, not 100.
>
> Cheers
> Paavo


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Tetration (print 100^100^100^100^100^100^100^100^100^100^100^100^100^100) jononanon@googlemail.com C Programming 5 04-25-2012 08:49 PM
Re: HELP! Ping getting slower and slower and slower! Paul Computer Information 2 04-03-2012 05:58 PM
str.Template 4 times slower than calling replace multiple times Jack Steven Python 2 03-09-2009 05:38 AM
VS.NET is 10 times slower than VB6 John Rivers ASP .Net 91 11-02-2005 05:55 PM
Release version 30 times slower than debug version croeltgen Java 1 10-24-2004 11:49 PM



Advertisments