Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #11152 > unrolled thread

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

Back to article view | Back to comp.lang.c++

Contents

  Insertion Sort : C++ implementation 100 times slower than C implementation sanket <sanketsharma09@gmail.com> - 2011-10-30 22:40 -0700
    Re: Insertion Sort : C++ implementation 100 times slower than C implementation Paavo Helde <myfirstname@osa.pri.ee> - 2011-10-31 01:57 -0500
      Re: Insertion Sort : C++ implementation 100 times slower than C implementation sanket <sanketsharma09@gmail.com> - 2011-10-31 11:36 -0700
      Re: Insertion Sort : C++ implementation 100 times slower than C implementation Tsung <jiaxiang.zheng135@gmail.com> - 2011-11-02 22:00 -0700
    Re: Insertion Sort : C++ implementation 100 times slower than C implementation Juha Nieminen <nospam@thanks.invalid> - 2011-10-31 07:04 +0000
      Re: Insertion Sort : C++ implementation 100 times slower than C implementation sanket <sanketsharma09@gmail.com> - 2011-10-31 12:27 -0700
    Re: Insertion Sort : C++ implementation 100 times slower than C implementation 88888 Dihedral <dihedral88888@googlemail.com> - 2011-10-31 03:08 -0700
      Re: Insertion Sort : C++ implementation 100 times slower than C implementation "A" <a@a.a> - 2011-10-31 16:18 +0100
        Re: Insertion Sort : C++ implementation 100 times slower than C implementation Juha Nieminen <nospam@thanks.invalid> - 2011-11-01 09:20 +0000

#11152 — Insertion Sort : C++ implementation 100 times slower than C implementation

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::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

[toc] | [next] | [standalone]

#11153

sanket <sanketsharma09@gmail.com> wrote in
news:f39210e6-d052-4f82-a619-d767983cbb07@v5g2000vbh.googlegroups.com: 

> 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

[toc] | [prev] | [next] | [standalone]

#11163

On Oct 31, 1:57 am, Paavo Helde <myfirstn...@osa.pri.ee> wrote:
> sanket <sanketsharm...@gmail.com> wrote innews:f39210e6-d052-4f82-a619-d767983cbb07@v5g2000vbh.googlegroups.com:
>
> > 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

[toc] | [prev] | [next] | [standalone]

#11227

On Oct 31, 2:57 pm, Paavo Helde <myfirstn...@osa.pri.ee> wrote:
> sanket <sanketsharm...@gmail.com> wrote innews:f39210e6-d052-4f82-a619-d767983cbb07@v5g2000vbh.googlegroups.com:
>
> > 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

[toc] | [prev] | [next] | [standalone]

#11154

sanket <sanketsharma09@gmail.com> 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.

[toc] | [prev] | [next] | [standalone]

#11166

On Oct 31, 2:04 am, Juha Nieminen <nos...@thanks.invalid> wrote:
> sanket <sanketsharm...@gmail.com> 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.


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.

[toc] | [prev] | [next] | [standalone]

#11155

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::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

[toc] | [prev] | [next] | [standalone]

#11157

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 

[toc] | [prev] | [next] | [standalone]

#11174

A <a@a.a> 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?)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web