Re: template size and speed

charles.lobo@gmail.com wrote:


Welcome to the board!


That's unfair!! I guess you aren't completely aware of the cost of
allocating memory dynamically using 'new' operator (see down below for
the results I got, which might be of interest to you).


Okay, I have gone through and found that you are actually trying to
implement "a LIFO doubly linked list". (LIFO: Last In First Out i.e. on
traversing the list starting with MyTList::GetNodes(), the last element
inserted into the list would be the first element that would be
visited).


Usually, the "language implementers" strive their best to enforce a
near "zero-cost" overhead (either in terms of time or space) on usage
of any language feature and that too "C++" would be at the forefront in
matters like this. As a "language user", one should not worry about
things like this.


No, I think you are mistaken. "Algorithm Implementations" (but not most
likely "Language Implementations") matter a lot!!! When you are trying
to compare/compete the performance of your code with some of the best
implementation's (i.e. library writer's), everything matters!


Question: Why are you trying to insert "a pointer to a ListNode, that
inturn holds a pointer to an object" into the list, rather than
inserting "a pointer to a ListNode, that 'contains' an object"? The
latter would cut down one-half of the calls to "new" operator!

//////////////////////////////////////////////////////////////////////
Vulnerable fragments of the code you presented:
===================================


Probable "driver" should have been:
=========================
int main(){
   ....
    MyTList<double> aMyTList;

    for (int i = 0;i < 1000000;i++)
        aMyTList.Insert (new double(i));
   ....
}
//////////////////////////////////////////////////////////////////////

Instead, why not the following can be??

//////////////////////////////////////////////////////////////////////
Suggested change:
==============
template <class T>
class ListNode
{
public:
    ListNode (T pVal) {uVal = pVal;}
    T uVal; //Hold "Object" itself, rather than a pointer to it
    ...
};
template <class T>
class MyTList
{
public:
   ...
    void Insert (T e) {
            ListNode<T> * ln;
        ln = new ListNode<T> (e);
       ...
    }
  ...
};

Probable "driver" can be:
================
int main(){
   ....
    MyTList<double> aMyTList;

    for (int i = 0;i < 1000000;i++)
        aMyTList.Insert (i); //Default copy constructor of ListNode
will suffice
   ....
}
//////////////////////////////////////////////////////////////////////

I tried the above approach and following are the results on my machine
using 'GNU's gcc' compiler:

Run Time with the code you presented to 'insert' 1000000 doubles: 650
seconds

                          =========
Run Time with my suggested change: 360 seconds
                                                        =========

If you are ready to consider a bit more advanced version of mine that
would do the memory allocation in "chunks" rather than one by one on
demand, then the results would be more interesting. Here is my quick
and dirty "bit more advanced version" (this should be compilable and
executable with 'GNU's gcc'):

//////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <iostream>
#include <vector>

using namespace std;

template <class T>
class ListNode
{
public:
    T uVal;
    ListNode<T>* uNext;
    ListNode<T>* uPrev;
};

template <class T>
class MyTList
{
public:
    MyTList (size_t myPoolSize = 1000000) {
        vFirst = NULL;

        // Extra baggage initialization
        _myPoolSize = myPoolSize;
        _myMemoryPool = new ListNode<T>[_myPoolSize];
        _myNext = _myPoolSize - 1;
    }

    void Insert (T e) {
         ListNode<T>* ln;

        if(_myNext<0){
           // memory pool exhausted; so, let's refill it!
          _myMemoryPool = new ListNode<T>[_myPoolSize];
          _myNext = _myPoolSize - 1;
        }
        ln = &(_myMemoryPool[_myNext--]);

        ln->uVal = e; //Default assignment operator of "ListNode"
suffices in this case.

        ln->uNext = vFirst;
        ln->uPrev = NULL;
        if (vFirst != NULL)
            vFirst->uPrev = ln;
        vFirst = ln;
    }
    ListNode<T> * GetNodes () { return vFirst;}

private:
    ListNode<T> * vFirst;

    // Extra baggage for memory management and for extra performance!!
    ListNode<T>* _myMemoryPool;
    size_t _myPoolSize;
    int _myNext;
};

int main()
{
    clock_t t1 = clock();

    MyTList<double> aMyTList;
    for (int i = 0; i < 1000000; ++i)
        aMyTList.Insert(i);

    clock_t t2 = clock();

    std::vector<double> aVec(1000000);
    for (int i = 0; i < 1000000; ++i)
       aVec.push_back(i);

    clock_t t3 = clock();

    cout << "MyTList: " << t2 - t1 << endl;
    cout << "std::vector: " << t3 - t2 << endl;

    return 0;
}

//////////////////////////////////////////////////////////////////////

And the ouput was this:

MyTList: 30
std::vector: 50

(We can beat them, Charles!!)


Hence, I don't want to comment upon your "non-template" version!! But I
would like to repeat what I had said in my earlier posting:-


-srikar vedantam

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]