Breakthrough

Discussion in 'C Programming' started by jacob navia, Jun 4, 2012.

  1. jacob navia

    jacob navia Guest

    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.
    jacob navia, Jun 4, 2012
    #1
    1. Advertising

  2. jacob navia

    BartC Guest

    "jacob navia" <> wrote in message
    news:jqi6o4$gqf$...


    > 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
    BartC, Jun 4, 2012
    #2
    1. Advertising

  3. jacob navia

    Paul Guest

    Juha Nieminen wrote:
    > In comp.lang.c++ MelissA <> 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
    Paul, Jun 4, 2012
    #3
  4. jacob navia

    jacob navia Guest

    Le 04/06/12 18:30, BartC a écrit :
    > "jacob navia" <> wrote in message
    > news:jqi6o4$gqf$...
    >
    >
    >> 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.)
    >



    Sorry, I did not test under windows. I tested now, and you should
    just type

    make -f makefile.lcc

    That compiles in 32 bits lcc

    make -f makefile.lcc64

    That compiles 64 bit lcc
    I upddated the zip file. Please download again and tell me how it goes.

    Thanks
    jacob navia, Jun 4, 2012
    #4
  5. jacob navia

    BartC Guest

    "jacob navia" <> wrote in message
    news:jqirb6$imi$...
    > Le 04/06/12 18:30, BartC a écrit :


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


    > Sorry, I did not test under windows.


    That explains the funny line endings in the files..

    > I tested now, and you should
    > just type
    >
    > make -f makefile.lcc


    Thanks. Downloading the latest lcc 32-bits to make sure, this now gets hung
    up on errors in wchar.h (first on line 521, then on line 509).

    > That compiles in 32 bits lcc
    >
    > make -f makefile.lcc64


    I couldn't see a .lcc64 file (in the distribution downloaded after your
    post)

    Anyway I've now given up on make files (I always have trouble with them.
    Always.) I found I could build your test program by manually compiling and
    linking these files:

    intlist.c
    buffer.c
    vector.c
    bitstrings.c
    bloom.c
    containererror.c
    deque.c
    dictionary.c
    dlist.c
    fgetline.c
    generic.c
    hashtable.c
    heap.c
    iMask.c
    list.c
    malloc_debug.c
    pool.c
    pooldebug.c
    qsortex.c
    queue.c
    redblacktree.c
    scapegoat.c
    searchtree.c
    strcollection.c
    valarraydouble.c
    valarrayint.c
    valarrayuint.c
    valarraysize_t.c
    valarrayfloat.c
    valarraylongdouble.c
    valarrayuint.c
    valarraylonglong.c
    valarrayulonglong.c
    valarrayshort.c
    observer.c
    memorymanager.c
    sequential.c
    wstrcollection.c

    --
    Bartc
    BartC, Jun 4, 2012
    #5
  6. jacob navia

    jacob navia Guest

    Le 04/06/12 20:18, BartC a écrit :
    >
    >
    > "jacob navia" <> wrote in message
    > news:jqirb6$imi$...
    >> Le 04/06/12 18:30, BartC a écrit :

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

    >
    >> Sorry, I did not test under windows.

    >
    > That explains the funny line endings in the files..
    >
    >> I tested now, and you should
    >> just type
    >>
    >> make -f makefile.lcc

    >
    > Thanks. Downloading the latest lcc 32-bits to make sure, this now gets
    > hung up on errors in wchar.h (first on line 521, then on line 509).
    >


    Ahhh you are using the distribution that comes with the compiler?

    That's not really up-to-date. Please download the ccl code from

    http://code.google.com/p/ccl/
    jacob navia, Jun 4, 2012
    #6
  7. jacob navia

    MelissA Guest

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

    > In comp.lang.c++ MelissA <> 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$
    MelissA, Jun 4, 2012
    #7
  8. jacob navia

    MelissA Guest

    On Mon, 4 Jun 2012 21:44:30 +0200
    MelissA <> wrote:

    > On Mon, 4 Jun 2012 15:32:34 +0000 (UTC)
    > Juha Nieminen <> wrote:
    >
    > > In comp.lang.c++ MelissA <> 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);

    }
    MelissA, Jun 4, 2012
    #8
  9. jacob navia

    jacob navia Guest

    Confirmed.

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

    That's faster than C by a small amount...
    jacob navia, Jun 4, 2012
    #9
  10. jacob navia

    Ian Collins Guest

    On 06/ 4/12 11:38 PM, jacob navia 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...


    I don't have the original code to had, but looking back at the original
    thread, the C++ list sort was 5x faster, so I guess from your numbers it
    is now 2-3 times faster.

    --
    Ian Collins
    Ian Collins, Jun 4, 2012
    #10
  11. jacob navia

    MelissA Guest

    On Mon, 04 Jun 2012 22:42:28 +0200
    jacob navia <> 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);

    }
    MelissA, Jun 4, 2012
    #11
  12. jacob navia

    Ian Collins Guest

    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
    Ian Collins, Jun 4, 2012
    #12
  13. jacob navia

    jacob navia Guest

    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.
    jacob navia, Jun 4, 2012
    #13
  14. jacob navia

    jacob navia Guest

    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.
    jacob navia, Jun 4, 2012
    #14
  15. jacob navia

    MelissA Guest

    On Tue, 5 Jun 2012 00:16:36 +0200
    MelissA <> wrote:

    >
    > unsigned counthigh = 0,countlow = 0;

    mine error
    countlow should be 1, not 0 ;)
    MelissA, Jun 4, 2012
    #15
  16. jacob navia

    BartC Guest

    "jacob navia" <> wrote in message
    news:jqj017$vai$...
    > Le 04/06/12 20:18, BartC a écrit :


    >> Thanks. Downloading the latest lcc 32-bits to make sure, this now gets
    >> hung up on errors in wchar.h (first on line 521, then on line 509).
    >>

    >
    > Ahhh you are using the distribution that comes with the compiler?


    No. I updated lcc in case it was out-of-date and causing the problem. The
    CCL stuff is separate.

    In any case, this project doesn't need a makefile as it's straightforward
    (now I know what's needed); I will leave that to the experts.

    I wanted to test the speed of container lists versus ordinary arrays (I know
    containers are more sophisticated but your test is simple so I'm looking at
    just that).

    The results of your test program weren't so interesting, because 95% of the
    runtime seemed to be in sorting. So got rid of that, and just tested
    allocating and iterating over 100M (not 10M) int objects. This took about 8
    seconds and seem to use about 1.3GB of memory (is there a per-element
    overhead?)

    Using an ordinary allocated array, took only 1.7 seconds, and used the
    expected 0.4GB of memory.

    However this was *preallocated*, a possible advantage. (I ran the same test
    on a dynamic language, which took 16 seconds, whether the int-array was
    preallocated or not. Interestingly (need to verify this), using a
    preallocated generic list only took 10 seconds, not far off the CCL timing
    for a non-generic list).

    It seems the conclusion, if my results are valid, is that if the
    requirements are very simple, that ordinary C array handling should be
    considered if speed and memory are important. Maybe you might want to put
    forward a more elaborate test that isn't so easy to rewrite in standard C...

    --
    Bartc
    BartC, Jun 5, 2012
    #16
  17. jacob navia

    Luca Risolia Guest

    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.
    Luca Risolia, Jun 5, 2012
    #17
  18. jacob navia

    Martin Shobe Guest

    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
    Martin Shobe, Jun 5, 2012
    #18
  19. jacob navia

    MelissA Guest

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

    }
    MelissA, Jun 5, 2012
    #19
  20. In comp.lang.c++ jacob navia <> 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.
    Juha Nieminen, Jun 5, 2012
    #20
    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. MelissA

    Re: Breakthrough

    MelissA, Jun 4, 2012, in forum: C++
    Replies:
    22
    Views:
    845
    Juha Nieminen
    Jun 5, 2012
Loading...

Share This Page