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

Groups > comp.lang.c++ > #11155

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

Show all headers | View raw

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

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web