Re: Breakthrough

From	jacob navia <jacob@spamsink.net>
Newsgroups	comp.lang.c
Subject	Re: Breakthrough
Date	2012-06-05 00:26 +0200
Organization	lccwin
Message-ID	<jqjcmt$3bm$1@speranza.aioe.org> (permalink)
References	<jqi6o4$gqf$1@speranza.aioe.org> <a34pjgFu5cU4@mid.individual.net>

Show all headers | View raw

C:   6.6 s
C++ 14.760

See the analysis after this session transcript. Please try this in your 
machine using the latest version of libccl.a


~/stl/test $ cat listexample.cpp
#include <list>
#include <cstdio>
#include <cstdlib>

#define N 10000000

int main()
{
   std::list<int> L1;
   long long sum=0,newSum=0;
   int i;
   for( i = 0; i < N; ++i)
   {
     int d = rand();
     sum+=d;
     L1.push_back(d);
   }

   L1.sort();

   //for(auto it : L1)
   std::list<int>::iterator it;
   for(it=L1.begin(); it != L1.end(); ++it)
   {
     newSum+= *it;
   }

   if (sum != newSum)
           printf("Failed\n");
   else    printf("Sum = %lld\n",sum);

}

~/stl/test $ g++ -O2 -o listexample-cpp listexample.cpp
~/stl/test $ time ./listexample-cpp
Sum = 10737818730605039

real	0m14.760s
user	0m14.438s
sys	0m0.320s
~/stl/test $ cat tintlist.c
#include <stdlib.h>
#include "containers.h"
#include "intlist.h"
#define N 10000000
int main(void)
{
	intList *L1;
	size_t i;
	int d;
	long long sum=0,newSum=0;
	Iterator *it;
	int *pint;

	L1 = iintList.Create(sizeof(int));
	iintList.UseHeap(L1,NULL); // Use specialized Heap
	// Add N random numbers to the integer list
	for (i=0; i<N;i++) {
		d = rand();
		sum += d;
		iintList.Add(L1,d);
	}
	// Sort it
	iintList.Sort(L1);
	// Go through the sorted list using an iterator
	it = iintList.NewIterator(L1);
	i=0;
	for (pint = it->GetFirst(it); pint; pint = it->GetNext(it)) {
		newSum += *pint;
	}
	// Verify that both sums are identical
	if (sum != newSum)
		printf("Failed\n");
	else	printf("Sum = %lld\n",sum);
	// Destroy the list
	iintList.Finalize(L1);
}
~/stl/test $ gcc -O2 -I.. -o listexample-c tintlist.c ../libccl.a
~/stl/test $ time ./listexample-c
Sum = 10737818730605039

real	0m6.584s
user	0m6.319s
sys	0m0.258s
~/stl/test $

Analysis:
---------
The main problems in the C++code are:

1) malloc overhead. There are several solutions to that, but none are 
standard.
2) Apparently the algorithm for sorting a list is different in C++ to 
the one I use. I copy the list into a vector and sort the vector, then
copy the sorted result into a list again.

For example:
~/stl/test $ cat tintlist1.cpp
#include <list>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>

#define N 10000000

int main()
{
   std::list<int> L1;
   long long sum=0,newSum=0;
   for(int i = 0; i < N; ++i)
   {
     int d = rand();
     sum+=d;
     L1.push_back(d);
   }
   std::vector<int> tmp(L1.begin(),L1.end());
   clock_t t = clock();
   std::sort(tmp.begin(),tmp.end());
   clock_t et = clock();
   L1.clear();
   L1.insert(L1.begin(),tmp.begin(),tmp.end());
   printf("sort time %.3f\n",float(et - t)/CLOCKS_PER_SEC);

//  for(auto it : L1)
  std::list<int>::iterator it;
   for(it=L1.begin(); it != L1.end(); ++it)

   {
     newSum+= *it;
   }

   if (sum != newSum)
           printf("Failed\n");
   else    printf("Sum = %lld\n",sum);

}
  This code takes only
~/stl/test $ time ./tintlist1-cpp
sort time 1.138
Sum = 10737818730605039

real	0m5.137s
user	0m4.656s
sys	0m0.476s

An improvement of 300%.

Of course now we aren't fair to C since I could have done a vector sort 
and I would be faster than C++ anyway.

Conclusion:

Probably C and C++ go at the same speed.

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

Thread

Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 13:38 +0200
  Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 14:20 +0200
    Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-04 15:32 +0000
      Re: Breakthrough Ike Naar <ike@iceland.freeshell.org> - 2012-06-04 15:44 +0000
        Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 18:03 +0200
          Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:23 +1200
            Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:31 +0200
              Re: Breakthrough Luca Risolia <luca.risolia@studio.unibo.it> - 2012-06-05 01:43 +0200
                Re: Breakthrough Martin Shobe <martin.shobe@yahoo.com> - 2012-06-05 00:26 +0000
      Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 17:47 +0200
        Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-05 05:36 +0000
      Re: Breakthrough Paul <nospam@needed.com> - 2012-06-04 12:32 -0400
      Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 21:44 +0200
        Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 22:01 +0200
          Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 22:42 +0200
            Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:16 +0200
              Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:47 +0200
              Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 03:34 +0200
      Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-06 17:28 -0700
  Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 17:30 +0100
    Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 19:30 +0200
      Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 19:18 +0100
        Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 20:50 +0200
          Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-05 00:31 +0100
  Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-04 17:23 -0400
    Re: Breakthrough Noob <root@localhost> - 2012-06-05 09:10 +0200
      Re: Breakthrough Ike Naar <ike@sverige.freeshell.org> - 2012-06-05 08:03 +0000
      Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 00:20 -0400
        Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 00:06 -0500
          Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 09:10 -0400
            Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 09:23 -0500
              Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 19:49 -0400
                Re: Breakthrough Willem <willem@toad.stack.nl> - 2012-06-07 15:10 +0000
                Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-08 01:37 +0200
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 09:55 -0400
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 21:26 -0400
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-09 23:49 -0400
                Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-11 06:50 -0700
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-11 22:36 -0400
  Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:02 +1200
    Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:26 +0200

csiph-web