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

Discussion in 'C++' started by sanket, Oct 31, 2011.

  1. sanket

    sanket Guest

    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
     
    sanket, Oct 31, 2011
    #1
    1. Advertising

  2. sanket <> 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.
     
    Juha Nieminen, Oct 31, 2011
    #2
    1. Advertising

  3. 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
     
    88888 Dihedral, Oct 31, 2011
    #3
  4. sanket

    A Guest

    A, Oct 31, 2011
    #4
  5. sanket

    sanket Guest

    On Oct 31, 1:57 am, Paavo Helde <> wrote:
    > sanket <> wrote innews::
    >
    > > 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
     
    sanket, Oct 31, 2011
    #5
  6. sanket

    sanket Guest

    On Oct 31, 2:04 am, Juha Nieminen <> wrote:
    > sanket <> 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.
     
    sanket, Oct 31, 2011
    #6
  7. 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?)
     
    Juha Nieminen, Nov 1, 2011
    #7
  8. sanket

    Tsung Guest

    On Oct 31, 2:57 pm, Paavo Helde <> wrote:
    > sanket <> wrote innews::
    >
    > > 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
     
    Tsung, Nov 3, 2011
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Rivers

    VS.NET is 10 times slower than VB6

    John Rivers, Aug 23, 2005, in forum: ASP .Net
    Replies:
    91
    Views:
    3,133
    =?Utf-8?B?TWFuaWthbmRhbg==?=
    Nov 2, 2005
  2. croeltgen
    Replies:
    1
    Views:
    504
    Andrew Thompson
    Oct 25, 2004
  3. Jack Steven
    Replies:
    2
    Views:
    447
    Chris Rebert
    Mar 9, 2009
  4. fred
    Replies:
    3
    Views:
    284
    Zifud
    Mar 17, 2005
  5. Replies:
    5
    Views:
    891
Loading...

Share This Page