Hi,
I have recently begun using templates in C++ and have found it to be
quite useful. However, hearing stories of code bloat and assorted
problems I decided to write a couple of small programs to check. What I
expected was that there would be minor code bloat and some speed
improvement when using templates. However...
I wrote a basic list container (using templates), and a list container
(using virtual derived classes). I also tried with the std lib vector
class. I ran 1000000 inserts and accesses to all these lists and got
the following results (compiling on windows with microsoft compiler):
Size:
22,528 mytpl.exe
36,864 nonstd.exe
40,960 std.exe
The first is my template list, the second my non-template list, and the
third is using the std vector.
The first surprise was that my template list was actually *smaller*
than the non-template version! Very surprising. However, it's not all
good news. I then ran some timing tests.
Time:
875: running std.exe
1484: running nonstd.exe
1563: running mytpl.exe
As expected, the std vector is the fastest. However my template list
class is the *slowest*!!! This was definitly not expected.
Does anyone have any inputs on what's going on?
cheers,
/Charles
--
It's hard to comment without actually taking a look at what/how you
programmed!!
However, the above results are not so surprising (to me) due to the
following reasons/assumptions:
mytpl.exe: (basic list container using templates) you would have used
a single class with few basic operations to attain the functionality
you intended for.
nonstd.exe: (using virtual derived classes) you would have used many
classes to attain the same functionality.
std.exe: (using std::vector) vector comes with a quite a bit of
baggage (allocators, iterators ...). However, it's interesting to know
that you implemented a "list" using "vector" in spite of "std::list"
availability!
Question: Is the 'list' you implemented a "linked list" kind of thing
or an "array" kind?
Very surprising. However, it's not all
Again, it's hard to say why, without actually analyzing your programs
(for time and space complexities of the algorithms you applied). A
language (C++ or anything else) wouldn't be able to come to rescue us
from our programming inefficiencies and definitely it would be worth
spending more time on improving our algorithm efficiencies rather than
niggling over the way we use a language.
Yes I see that
. I've pasted my code below. This is the first time
I've posted to a usenet group. I've also made the mistake of
You are basically right about the way I've written the classes.
However, my understanding was that the compiler would generate the
classes in the template version which I hand coded in the virtual
derived class version. So the net result would have been a slight
increase in the template version (as the compiler would have copied the
entire class for every new type).
I used std::vector simply because I read somewhere that it was the
fastest container available and I wanted to use it as a benchmark for
the "best possible" performance
It's a "linked list" kind. Have pasted the code below.
Actually what I'm looking at is the *cost* of template usage (if any)
in terms of speed and size. I'm not really looking for the best
implementation of a list. From what I read, templates should have given
me larger code that may have been faster. Instead it gave me smaller
code that's slower which is what I found surprising.
Programs follow:
----------------------- Template List ----------------------------
template <class T>
class ListNode
{
public:
ListNode (T * pVal) {uVal = pVal;}
T * uVal;
ListNode<T>* uNext;
ListNode<T>* uPrev;
};
template <class T>
class MyTList
{
public:
MyTList () { vFirst = NULL; }
void Insert (T * e) {
ListNode<T> * ln;
ln = new ListNode<T> (e);
ln->uNext = vFirst;
ln->uPrev = NULL;
if (vFirst != NULL)
vFirst->uPrev = ln;
vFirst = ln;
}
ListNode<T> * GetNodes () { return vFirst;}
private:
ListNode<T> * vFirst;
};
--------------------------------- Template List ends
----------------------------
--------------------------------- Non Template List
-----------------------------
class ListElem
{
public:
virtual ~ListElem (void) {}
ListElem * uNext;
ListElem * uPrev;
};
class MyList
{
public:
MyList () { vFirst = NULL;}
void Insert (ListElem * e) {
e->uNext = vFirst;
e->uPrev = NULL;
if (vFirst != NULL)
vFirst->uPrev = e;
vFirst = e;
}
ListElem * GetNodes () { return vFirst; }
private:
ListElem * vFirst;
};
------------------------------ Non template list ends
--------------------------
Note that the code is *very* similar for the template and non-template
version. I had to derive a ListElem for the non-template class:
class MyClassElem : public ListElem
{
public:
MyClassElem (MyClass * c) { uMyClass = c; }
MyClass * uMyClass;
};
But didn't have to do anything for the template version.
The cpp test code basically just runs two loops (inserting and
get-ting 1000000 elements).
cheers,
/Charles
