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

Groups > comp.lang.c > #21807 > unrolled thread

Breakthrough

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

Contents

  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

Page 1 of 3  [1] 2 3  Next page →

#21807 — Breakthrough

Hi

In a recent discussion ("Open letter to Ian Collins") we found out that 
the main problem in the C containers library was the time taken by the 
Sort function.

The reasons for that is that it was a general sort function calling a 
general comparison function that uses memcmp...

The first step to improve performance was to write data type specific 
functions using a data type generic file. As a bonus, we get compile 
time checking and better syntax.

Still, the generic sort function was taking a lot of time.

I have written then a data type generic quick sort function that
receives as a parameter a macro that is used to compare two elements.
This vastly improves performance.

The times are:

Generic sort function without any specialized heap
(using malloc)
real	0m17.029s
user	0m16.654s
sys	0m0.368s

Generic sort function using a specialized heap
(reduces the malloc overhead)
real	0m11.759s
user	0m11.500s
sys	0m0.252s

"Templated" sort function using a macro parameter
(reduces comparisons to a simple expression)
real	0m6.453s
user	0m6.165s
sys	0m0.281s

The expression used to compare two list elements is:
#define COMPARE_EXPRESSION(A, B) \
     ((*B)->Data > (*A)->Data ? -1 : (*B)->Data != (*A)->Data)

I thank Pete for that proposal, I wouldn't have come to it
alone :-)

I would like to have the corresponding C++ times but I fear that
if I write it it would be unfair since I am not a C++ wizard...
Here is the C code for the example:

#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);
}

I have uploaded the latest code to:

http://code.google.com/p/ccl/

There you will find (in listgen.c) the "templated" version of quick sort 
in C.

[toc] | [next] | [standalone]

#21816

On Mon, 04 Jun 2012 13:38:47 +0200
jacob navia <jacob@spamsink.net> wrote:

> Hi
> 
> In a recent discussion ("Open letter to Ian Collins") we found out
> that the main problem in the C containers library was the time taken
> by the Sort function.
> 
> The reasons for that is that it was a general sort function calling a 
> general comparison function that uses memcmp...
> 
> The first step to improve performance was to write data type specific 
> functions using a data type generic file. As a bonus, we get compile 
> time checking and better syntax.
> 
> Still, the generic sort function was taking a lot of time.
> 
> I have written then a data type generic quick sort function that
> receives as a parameter a macro that is used to compare two elements.
> This vastly improves performance.
> 
> The times are:
> 
> Generic sort function without any specialized heap
> (using malloc)
> real	0m17.029s
> user	0m16.654s
> sys	0m0.368s
> 
> Generic sort function using a specialized heap
> (reduces the malloc overhead)
> real	0m11.759s
> user	0m11.500s
> sys	0m0.252s
> 
> "Templated" sort function using a macro parameter
> (reduces comparisons to a simple expression)
> real	0m6.453s
> user	0m6.165s
> sys	0m0.281s
> 
> The expression used to compare two list elements is:
> #define COMPARE_EXPRESSION(A, B) \
>      ((*B)->Data > (*A)->Data ? -1 : (*B)->Data != (*A)->Data)
> 
> I thank Pete for that proposal, I wouldn't have come to it
> alone :-)
> 
> I would like to have the corresponding C++ times but I fear that
> if I write it it would be unfair since I am not a C++ wizard...
> Here is the C code for the example:
> 
> #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);
> }
> 
> I have uploaded the latest code to:
> 
> http://code.google.com/p/ccl/
> 
> There you will find (in listgen.c) the "templated" version of quick
> sort in C.
> 

Here are timings on mu computer.

bmaxa@maxa:~/jacob/ccl$ time ./cppvec
Sum = 10738138201479754

real	0m0.899s
user	0m0.832s
sys	0m0.064s
bmaxa@maxa:~/jacob/ccl$ time ./cpplist
Sum = 10738138201479754

real	0m7.493s
user	0m7.344s
sys	0m0.136s
bmaxa@maxa:~/jacob/ccl$ time ./testlist 
Sum = 10738138201479754

real	0m4.320s
user	0m4.180s
sys	0m0.140s

Sources:
---- cppvec.cpp

#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

#define N 10000000

int main()
{
  std::vector<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::sort(L1.begin(),L1.end());
  
  for(auto it : L1)
  {
    newSum+= it;
  }
  
  if (sum != newSum)
          printf("Failed\n");
  else    printf("Sum = %lld\n",sum);
                                   
}

----cpplist.cpp

#include <list>
#include <cstdio>
#include <cstdlib>

#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);
  }
  
  L1.sort();
  
  for(auto it : L1)
  {
    newSum+= it;
  }
  
  if (sum != newSum)
          printf("Failed\n");
  else    printf("Sum = %lld\n",sum);
                                   
}

Compile with -std=c++0x for gcc 4.6 or -std=c++11 for 4.7

As you can see your program is faster than list version
of C++, but is less elegant ;)


Greets!

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

#21817

In comp.lang.c++ MelissA <melis@a.com> wrote:
> #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);

Your test is basically useless as a measurement of sorting speed because
the vast majority of the time will be spent on those push_back() calls.

If you want to test sorting speed and nothing else, you have to discard
the time spent in memory allocation.

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

#21818

On 2012-06-04, Juha Nieminen <nospam@thanks.invalid> wrote:
> In comp.lang.c++ MelissA <melis@a.com> wrote:
>> #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);
>
> Your test is basically useless as a measurement of sorting speed because
> the vast majority of the time will be spent on those push_back() calls.
>
> If you want to test sorting speed and nothing else, you have to discard
> the time spent in memory allocation.

On the machine that I tried, most of the time was spent on the
implicit destruction of the list at program termination.

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

#21820

Le 04/06/12 17:44, Ike Naar a écrit :
>
> On the machine that I tried, most of the time was spent on the
> implicit destruction of the list at program termination.

Yes, I see a noticeable delay between the printing of the
result sum and the end of the program.

Apparently cleaning up is quit e expensive since destructors must be
called 100 million times.

In the CCL you can ADD a destructor if you want but they are NOT
required as in C++.

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

#21838

On 06/ 5/12 04:03 AM, jacob navia wrote:
> Le 04/06/12 17:44, Ike Naar a écrit :
>>
>> On the machine that I tried, most of the time was spent on the
>> implicit destruction of the list at program termination.
>
> Yes, I see a noticeable delay between the printing of the
> result sum and the end of the program.
>
> Apparently cleaning up is quit e expensive since destructors must be
> called 100 million times.
>
> In the CCL you can ADD a destructor if you want but they are NOT
> required as in C++.

So not leaking memory is optional :)

-- 
Ian Collins

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

#21841

Le 05/06/12 00:23, Ian Collins a écrit :
>> In the CCL you can ADD a destructor if you want but they are NOT
>> required as in C++.
>
> So not leaking memory is optional :)

No. You do  a

iintList.Finalize(list);

The advantage is that you free ALL memory in a single call to a function
that destroys the heap not individually (list element by list element)
but in blocks of 1000 list elements each you see?

C++ calls destructors 100 million times. That takes time.

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

#21845

On 05/06/2012 00:31, jacob navia wrote:
> Le 05/06/12 00:23, Ian Collins a écrit :
>>> In the CCL you can ADD a destructor if you want but they are NOT
>>> required as in C++.
>>
>> So not leaking memory is optional :)
>
> No. You do a
>
> iintList.Finalize(list);
>
> The advantage is that you free ALL memory in a single call to a function
> that destroys the heap not individually (list element by list element)
> but in blocks of 1000 list elements each you see?
>
> C++ calls destructors 100 million times. That takes time.

Not necessarily. Memory deallocation and object destruction are two 
separate things usually controlled by an allocator. With regard to the 
standard containers an allocator is always an (optional) template 
parameter. If you really want, you can provide your preferred 
deallocation strategy for a given type T to std::list, so that it frees 
the memory in blocks of 1000 and doesn't destroy any object.

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

#21846

Luca Risolia wrote:

> On 05/06/2012 00:31, jacob navia wrote:
>> Le 05/06/12 00:23, Ian Collins a écrit :
>>>> In the CCL you can ADD a destructor if you want but they are NOT
>>>> required as in C++.
>>>
>>> So not leaking memory is optional :)
>>
>> No. You do a
>>
>> iintList.Finalize(list);
>>
>> The advantage is that you free ALL memory in a single call to a function
>> that destroys the heap not individually (list element by list element)
>> but in blocks of 1000 list elements each you see?
>>
>> C++ calls destructors 100 million times. That takes time.
>
> Not necessarily. Memory deallocation and object destruction are two 
> separate things usually controlled by an allocator. With regard to the 
> standard containers an allocator is always an (optional) template 
> parameter. If you really want, you can provide your preferred 
> deallocation strategy for a given type T to std::list, so that it frees 
> the memory in blocks of 1000 and doesn't destroy any object.
>

In the code that lead to this, the list was a list of ints. They don't
even have destructors to call, so the time certainly wasn't spent
calling them.

Martin Shobe

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

#21819

Le 04/06/12 17:32, Juha Nieminen a écrit :
> In comp.lang.c++ MelissA<melis@a.com>  wrote:
>> #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);
>
> Your test is basically useless as a measurement of sorting speed because
> the vast majority of the time will be spent on those push_back() calls.
>

The purpose of this test is to compare the STL to the C Containers 
Library (CCL). With this in mind I wanted a big test with both systems 
doing roughly the same thing:

1) Allocate a list
2) Fill it with 100 million random numbers adding each number
    to a grand total
3) Sort it
4) Go through the whole list again, reading the data and verify that
    you get the same number.
5) Destroy the list.

> If you want to test sorting speed and nothing else, you have to discard
> the time spent in memory allocation.

Yes, but what I want to test is the speed to do ALL tasks mentioned above

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

#21854

In comp.lang.c++ jacob navia <jacob@spamsink.net> wrote:
>> If you want to test sorting speed and nothing else, you have to discard
>> the time spent in memory allocation.
> 
> Yes, but what I want to test is the speed to do ALL tasks mentioned above

Then you will be comparing C++'s default memory allocator speed to whatever
that C list was using.

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

#21823

Juha Nieminen wrote:
> In comp.lang.c++ MelissA <melis@a.com> wrote:
>> #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);
> 
> Your test is basically useless as a measurement of sorting speed because
> the vast majority of the time will be spent on those push_back() calls.
> 
> If you want to test sorting speed and nothing else, you have to discard
> the time spent in memory allocation.

If you're going to collect timing information, it should be
collected right around the working part of the test, and
inside the code itself. Rather than recording the runtime of
the entire executable, and all those rand() calls.

    generate_random_numbers
    ...
    get_time_before
    do_the_sort
    get_time_after
    ...
    print ( get_time_after - get_time_before )

   Paul

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

#21828

On Mon, 4 Jun 2012 15:32:34 +0000 (UTC)
Juha Nieminen <nospam@thanks.invalid> wrote:

> In comp.lang.c++ MelissA <melis@a.com> wrote:
> > #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);
> 
> Your test is basically useless as a measurement of sorting speed
> because the vast majority of the time will be spent on those
> push_back() calls.
> 
> If you want to test sorting speed and nothing else, you have to
> discard the time spent in memory allocation.
Here is just sorting time, C version is significantly faster:

bmaxa@maxa:~/jacob/ccl$ ./testlist
sort time 3.140
Sum = 10738138201479754
bmaxa@maxa:~/jacob/ccl$ ./cpplist
sort time 5.350
Sum = 10738138201479754
bmaxa@maxa:~/jacob/ccl$ 

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

#21829

On Mon, 4 Jun 2012 21:44:30 +0200
MelissA <melis@a.com> wrote:

> On Mon, 4 Jun 2012 15:32:34 +0000 (UTC)
> Juha Nieminen <nospam@thanks.invalid> wrote:
> 
> > In comp.lang.c++ MelissA <melis@a.com> wrote:
> > > #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);
> > 
> > Your test is basically useless as a measurement of sorting speed
> > because the vast majority of the time will be spent on those
> > push_back() calls.
> > 
> > If you want to test sorting speed and nothing else, you have to
> > discard the time spent in memory allocation.
> Here is just sorting time, C version is significantly faster:
> 
> bmaxa@maxa:~/jacob/ccl$ ./testlist
> sort time 3.140
> Sum = 10738138201479754
> bmaxa@maxa:~/jacob/ccl$ ./cpplist
> sort time 5.350
> Sum = 10738138201479754
> bmaxa@maxa:~/jacob/ccl$ 
> 

But watch out this:
It is faster to populate vector from list, then
to sort vector , then to clear list, then
to populate list from vector then C version! ;)

bmaxa@maxa:~/jacob/ccl$ time ./cpplist
sort time 0.750
Sum = 10738138201479754

real	0m1.813s
user	0m1.660s
sys	0m0.152s
bmaxa@maxa:~/jacob/ccl$ time ./testlist
sort time 3.140
Sum = 10738138201479754

real	0m4.302s
user	0m4.208s
sys	0m0.096s
bmaxa@maxa:~/jacob/ccl$ cat cpplist.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)
  {
    newSum+= it;
  }
  
  if (sum != newSum)
          printf("Failed\n");
  else    printf("Sum = %lld\n",sum);
                                   
}

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

#21831

Confirmed.

real	0m5.112s
user	0m4.600s
sys	0m0.487s

That's faster than C by a small amount...

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

#21837

On Mon, 04 Jun 2012 22:42:28 +0200
jacob navia <jacob@spamsink.net> wrote:

> Confirmed.
> 
> real	0m5.112s
> user	0m4.600s
> sys	0m0.487s
> 
> That's faster than C by a small amount...
> 
> 

This is with my inplace qsort with bidirectional
iterators:


bmaxa@maxa:~/jacob/ccl$ time ./cpplist1
sort time 1.480
Sum = 10738138201479754

real	0m2.105s
user	0m1.936s
sys	0m0.168s
bmaxa@maxa:~/jacob/ccl$ time ./testlist 
sort time 3.130
Sum = 10738138201479754

real	0m4.265s
user	0m4.128s
sys	0m0.136s
bmaxa@maxa:~/jacob/ccl$ cat QSort.h
#include <algorithm>

namespace VLib{
using std::swap;

template <typename T,typename F>
void qsort(T begin, T end, unsigned size, F f)
{
  if(begin == end)return;

  T high = end;
  if(!size)
  {
   T tmp = begin;
   while(tmp!=end){ high=tmp++;++size; }
  }
  else
  {
   --high;
  }

  if(size == 1)return;

  T low = begin;
  ++low;

  unsigned counthigh = 0,countlow = 0;
  do
  {
    while(high != low && f(*begin,*high)){ --high;++counthigh; }
    while(low != high && f(*low,*begin)){ ++low;++countlow; }
    
    if(low != high && !f(*low,*begin) && !f(*begin,*low) && !f(*begin,*high) && !f(*high,*begin))
    {
     while(high != low && !f(*high,*low) && !f(*low,*high)){ --high;++counthigh; }
    }
    
    swap(*low,*high);
  }while(low != high);
  swap(*low,*begin);
  T i = low;
  
  while(++i != end && !f(*i,*low) && !f(*low,*i) )--counthigh;
  
   VLib::qsort(begin,low,countlow,f);
   VLib::qsort(i,end,counthigh,f);
}

template <typename T>
inline void qsort(T begin, T end, unsigned size = 0)
{
 VLib::qsort(begin,end,size,std::less<typename std::iterator_traits<T>::value_type>());
}

}
bmaxa@maxa:~/jacob/ccl$ cat cpplist1.cpp
#include <list>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include "QSort.h"

#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);
  }
  
  clock_t t = clock();
  VLib::qsort(L1.begin(),L1.end());
  clock_t et = clock();
  printf("sort time %.3f\n",float(et - t)/CLOCKS_PER_SEC);
  
  for(auto it : L1)
  {
    newSum+= it;
  }
  
  if (sum != newSum)
          printf("Failed\n");
  else    printf("Sum = %lld\n",sum);
                                   
}

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

#21842

On Tue, 5 Jun 2012 00:16:36 +0200
MelissA <melis@a.com> wrote:

> 
>   unsigned counthigh = 0,countlow = 0;
mine error  
countlow should be 1, not 0 ;)

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

#21849

Final QSort.h (corrected errors, this one is little bit slower)

#include <algorithm>

namespace VLib{
using std::swap;

template <typename T,typename F>
void qsort(T begin, T end, unsigned size, F f)
{
  if(begin == end)return;

  T high = end;
  if(!size)
  {
   T tmp = begin;
   while(tmp!=end){ high=tmp++;++size; }
  }
  else
  {
   --high;
  }

  if(size == 1)return;
  T low = begin;
  unsigned count = 0;
  while(++count<size/2)++low;
//  printf("size %u\n",size);
  swap(*low,*begin);
  low = begin;
  ++low;

  unsigned counthigh = 0,countlow = 1;
  do
  {
    while(high != low && f(*begin,*high)){ --high;++counthigh; }
    while(low != high && f(*low,*begin)){ ++low;++countlow; }
    
    if(low != high && !f(*low,*begin) && !f(*begin,*low) && !f(*begin,*high) && !f(*high,*begin))
    {
     while(high != low && !f(*high,*low) && !f(*low,*high)){ --high;++counthigh; }
    }
    
    swap(*low,*high);
  }while(low != high);
  swap(*low,*begin);
  T i = low;
  
  while(++i != end && !f(*i,*low) && !f(*low,*i) )--counthigh;
  
   VLib::qsort(begin,low,countlow,f);
   VLib::qsort(i,end,counthigh,f);
}

template <typename T>
inline void qsort(T begin, T end, unsigned size = 0)
{
 VLib::qsort(begin,end,size,std::less<typename std::iterator_traits<T>::value_type>());
}

}

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

#21923

Juha Nieminen於 2012年6月4日星期一UTC+8下午11時32分34秒寫道：
> In comp.lang.c++ MelissA <melis@a.com> wrote:
> > #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);
> 
> Your test is basically useless as a measurement of sorting speed because
> the vast majority of the time will be spent on those push_back() calls.
> 
> If you want to test sorting speed and nothing else, you have to discard
> the time spent in memory allocation.

For known numeric types of arrays to be sorted, then the radix sort is 
faster if the allocation  of the memory does not slow down a lot.illion

The problem is  for the size of 100 million elements. I sugest 
one can sort from the first digit of 8 to 12 bits for the first 2 or 3 digits.


Then one can sort those with the same prefax chunk by the traditional radix
sort if necessary, thus the cache hit rate is increased in all passes of digits.


  





Juha Nieminen於 2012年6月4日星期一UTC+8下午11時32分34秒寫道：
> In comp.lang.c++ MelissA <melis@a.com> wrote:
> > #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);
> 
> Your test is basically useless as a measurement of sorting speed because
> the vast majority of the time will be spent on those push_back() calls.
> 
> If you want to test sorting speed and nothing else, you have to discard
> the time spent in memory allocation.

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

#21822

"jacob navia" <jacob@spamsink.net> wrote in message 
news:jqi6o4$gqf$1@speranza.aioe.org...


> I have uploaded the latest code to:
>
> http://code.google.com/p/ccl/
>
> There you will find (in listgen.c) the "templated" version of quick sort 
> in C.

How do you build this thing? Typing make gives errors:

c:\lcc\bin\make says something about bitstrings.o.

Copying makefile.lcc to makefile then doing the same:

c:\lcc\bin\make now complains about something in lcc64.

(I never use 'make' so haven't got a clue. A readme file might be helpful 
though.)

-- 
Bartc

 

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web