To STL or not to STL, that is the question...

[OReubens]

The whole purpose of STL (and the MFC container classes, and almost any other library I know for that matter) is to provide the programmer with a toolkit of adequately tested classes/functions that perform well under most circumstances limiting worst-case scenario's as much as possible, and providing a workable tradeoff between speed and memory usage.

And as with any tradeoff, it's sometimes not going to be good enough. I have had my share of problems where 'generic' solutions just wouldn't do. Reinventing the wheel (but with added grip and better profile for wet surface and a chery on top) is sometimes necessary.

It's hard to do decent benchmarking. Last time you checked... how many times did you actually had to write real code that did:

for (i=0; i<1000000; ++i)
    {
        li.push_back(i);
    }

;-)

[KevinHall]

Again, very true. I was just trying to use oktronic's test for comparison against his own claims.

[oktronic]

Sorry you guys posted while I was posting, so I'll try to answer your questions.

In the end though, you still have not addressed the issue of linked list vs. vector. Please comment!

My class can handle dynamic or static memory, contiguous or linked. More specifically, you can hand it any type of memory and it will use it until your size limit is hit, and then it will go dynamic, or fail depending on options. If you refer to the vector code, you'll see that's all it is, a dbl-linked list container. It has some extra functionally, but still, inside that's all it is. Unless you are only defining a linked-list as only a dynamic list?

This includes file buffered memory handling, since some lists are far to great of size to use in memory.
So you can hand it whatever you want and it will work with it, I've built in many different ways, such as file buffering, however, you can assign your own allocator just like vector does. Multiple storage ways are necessary for things like external memory, such as a video card. I try to pack functionality in where I can.

This alone is a contradiction to the statement you made before: That your class is "drop in compatible with vector".

Agreed, this is one case where it doesn't drop in perfectly. This is because vector isn't safe with types. However, you can specify what you wish to be a error value in your empty type. Which is really just a dummy type with the value that I return, if none is specified, then its just a empty type of the list type. The object of the class is to be perfectly safe. I've eliminated try-catch handling aswell which is another change. But really what I'm trying to avoid is the user dropping in my class and 100s of things don't compile. This way, the program will compile and the user will need to make some modifications to use the additional features. Generally I only do 100% drop in for controls, where I can.

I'll try. He didn't leave very complete code to compare though.

Sorry Kevin, I'd love nothing more then to post it, but I don't make up the rules...

However the principle is very easy. I did edit that code I provided to remove debug stuff, but the rest is pretty standard double-linked list. Just need a front and back pointer and a node that holds the data, prev and next pointers and you should be pretty accurate. If you are going contiguos then drop the prev and next pointers and use offsets. If you want, and trust me to do so fairly, you can give me any tests you would like and I'll give you the results.

But honestly, STL isn't going to be able to beat it out for the one reason of that STL does more. For allocator class it has to be instantiated, the iterators need to be assigned, additions and so forth. I keep track of everything, which I can do safely since nothing can me modified externally.
A worse class is map. I was going to use it as my example but between map and xtree its a mess and my replacement class is optionally balanced so I would have had to chop it up to get a comparable benchmark that you could work with.

[KevinHall]

Originally posted by oktronic
If you refer to the vector code, you'll see that's all it is, a dbl-linked list container.

...

But honestly, STL isn't going to be able to beat it out for the one reason of that STL does more. For allocator class it has to be instantiated, the iterators need to be assigned, additions and so forth. I keep track of everything, which I can do safely since nothing can me modified externally.

std::vector is NOT a linked list!!!

Originally posted by oktronic
If you want, and trust me to do so fairly, you can give me any tests you would like and I'll give you the results.

Try the tests I posted and used including the reserve(). Of coarse as OReubens pointed out this isn't real-world, but it would be interesting nonetheless.

- Kevin

[oktronic]

First for kevin:
Check out the STL code Vector in the include directory. You will find that it is indeed a linked list. But again, if you are defining a linked-list as only a dynamic, then yes and no, however at the system level, it most definently is.

I think we need to agree on a few points.
One, when compiled, the code with the fewest intructions are going to be processed in less time if the same memory allocation and retieval.

Second. If you have pre-allocated memory, its going to be accessed faster then memory you have to allocate then access.

This seems to be the biggest issue.

If you take my code and break it into instructions, you will find that it has less instructions then vector. You can tell this simply by the number of lines of code in each since they essentially do the same thing, however you can grab the ASM from VC and check yourself. Second, if both are running the same memory routine, that the one with the least instructions will process faster.
Since the main concern is memory. First, Windows is has a linked-list memory implementation. Which means, that when you allocate memory, even on the stack, it is not contiguous. The system is the only thing that stores stuff contiguously. You can look this up if you feel I'm not being accurate.

So what this means, is that give the same memory constraints, whether heap, register or stack, pre-allocated or dynamic, that the one with the least amount of instructions is going to be faster.

Which is the case with my sample. You can count the STL C++ lines and see that there are twice as many. It still has to allocate the memory somewhere and as long as both allocate the same way, mine will be faster no matter what machine you run it on.

As for the sample test, its purpose was to give all three the most common used implementations. Which is dynamic growth at 1 element per insertion. Which is what that sample did. Sure if you pre allocate one and make the other grow one at a time, the one that grows with slow down.

for Kevin:

OOoh, BAD BAD BAD. I would never want a library that on it's own shuts down because of calling an out of bounds.

The class doesn't shut the system down, the construct (aka framework) does. There are plenty of functions that can be set up to do any form of custom handling.

PS: lol, sorry for all the editting, I'm in a hurry to go home and am not checking my grammer. Which I'm going to head out, I'll hopefully answer any other posts later.

[AvDav]

Originally posted by oktronic
First for kevin:
Check out the STL code Vector in the include directory. You will find that it is indeed a linked list.

Excuse me, but:

std::vector<int> s(2);
s[0]=129;
s[1]=981218;

int *arr=s.begin();
if(arr[1]==981218) // if this is safe
	cout << "definitely not a list";

This is in MS and SGI STLs.

[Paul McKenzie]

Originally posted by oktronic
First for kevin:
Check out the STL code Vector in the include directory. You will find that it is indeed a linked list.

A vector is guaranteed to have its storage in contiguous memory, just like an array. I don't see how this can be a linked list, especially when a vector<T> can be used with legacy functions that require a pointer to a buffer of T.

#include <vector>

void LegacyFunc(int *pInt, int nItems)
{
}

int main()
{
   std::vector<int> IntList(5);
   LegacyFunc(&IntList[0], IntList.size());
}

This code is guaranteed to work correctly, since vector's internal data representation is a contiguous buffer, not a linked list. If your linked-list class can be used as above, then you can compare it with vector (even if you call it linked-list). If it cannot be used as the code above uses it, it is not compatible with vector, and you are comparing apples with oranges.

Regards,

Paul McKenzie

[KevinHall]

Originally posted by oktronic
First for kevin:
Check out the STL code Vector in the include directory. You will find that it is indeed a linked list. But again, if you are defining a linked-list as only a dynamic, then yes and no, however at the system level, it most definently is.

from the file "vector" found in C:\Program Files\Microsoft Visual Studio\VC98\Include

 
template<class _Ty, class _A = allocator<_Ty> >
    class vector {
public:
    typedef _A::pointer _Tptr;

    //...

    typedef _Tptr iterator;

    //...

protected:

    //...

    iterator _First, _Last, _End;
};

Using the standard allocator, the iterator is a pointer an object. Thus we would have something like:

class int_vector {

protected:

    int* _First, _Last, _End;
};

This is certainly NOT a linked list. A linked list would need a pointer to a node, which is most definately not what this is. As the Paul and AvDav have pointed out, a vector must be allocated in the same way an array is -- i.e. in contiguous memory.

Originally posted by oktronic
I think we need to agree on a few points.
One, when compiled, the code with the fewest intructions are going to be processed in less time if the same memory allocation and retieval.

I believe this is incorrect. Not all assembly instructions take the same amount of time to execute. And we should all know better than assuming that all C++ instructions take the same amount of time to execute. Let us take a look at an extreme example:

void a()
{
    int i;
    int x;
    for (i=0;i<1000000000;++i)
        x = i;
}

void b()
{
    double x = sqrt(2.0);
    int z = x;
    cout << z << endl;
    string s("Hi there!");
    cout << s << endl;
}

*Which of these two functions has fewer assembly instructions?

*Which of these two functions has fewer C++ instructions?

* Which will run faster?

Originally posted by oktronic
First, Windows is has a linked-list memory implementation. Which means, that when you allocate memory, even on the stack, it is not contiguous. The system is the only thing that stores stuff contiguously. You can look this up if you feel I'm not being accurate.

Are you saying that the following:

int* x = new int[500];

will not allocate contiguous memory for x?

Originally posted by oktronic
for Kevin:

quote:
--------------------------------------------------------------------------------
OOoh, BAD BAD BAD. I would never want a library that on it's own shuts down because of calling an out of bounds.
--------------------------------------------------------------------------------

That wasn't me who stated that.

- Kevin

[oktronic]

Ok, we're going to need to take a step back here.
I'm talking on a system level and you're talking C++ semantics.

int* ptr = new int[50];

while this is "contiguous" relative to a C++ interface. However, at the operating system level, it isn't.
Window's uses a linked list implementation to store memory.
This is how it allows memory segmentation.
So even though you asked for 50 ints, that memory can be scattered anyway through out memory with pointers at segmentation points that point to other locations. Not that I can remember back that far, but I believe this is called paging.
This is also why when you have, let’s say 2GBytes of system memory, that when you ask for 1 Gig that it may very well fail. This is because you are asking for 1 Gig and they system will actually require more for pointers to each segment.

This article has some useful information. However, its incomplete as its hard to find decent references for this. But it should show you that you're memory is segmented by the operating system with pointers between segments done as pages. The operating system determines all this for you.

http://www.cs.wpi.edu/~claypool/cour...slides/mem.pdf

Here a more advanced example.
Again, I didn't read through looking for his errors as I'm sure there's going to be a few since I think its a graduate assignment,
but from the brief scan it looks ok, just don't hold anything he says as gospel.

http://www.cs.buffalo.edu/~bina/cse4...02/VMOct17.pdf

While looking at .NET, I've noticed that they have re-written STL in .NET and while its still a mess, its much cleaner then its predecessor, they've replaced single variable names with actual names. And I've noticed that they have added exception handling into their class, which now means that they will have even more overhead while using STL, but its now a little safer.

But anyway, what the memory stuff means is that iterating between "contiguous" and between a list of pointers to elements may take the same amount of time, since the memory you're using very well is a list itself.

But besides all this, since vector is indeed reallocating its entire memory block each time, then wouldn't that be horribly inefficient? As I said before, data streams, such as a character array, rarely give you their size first, they usually have a terminator, such as a string has a NULL and a file an EOF.
So I recommend trying the 2, allocate a chunk of memory for my linked list to hold the data and shift the pointers around and then try the same block size for vector. I think you'll be surprised at the difference in performace.

So I'll shift terminology, been working a little too much at the system level as of late.

So I'll add another negative to STL, horrible memory management using shifting contiguous memory for allocation forcing the system to keep shifting memory around to compensate.

[KevinHall]

Originally posted by oktronic
But besides all this, since vector is indeed reallocating its entire memory block each time, then wouldn't that be horribly inefficient? As I said before, data streams, such as a character array, rarely give you their size first, they usually have a terminator, such as a string has a NULL and a file an EOF.

...

So I'll add another negative to STL, horrible memory management using shifting contiguous memory for allocation forcing the system to keep shifting memory around to compensate.

Why would std::vector need to reallocate memory every time if it really a linked list?

As far as bad memory management goes, that's something that is a trade off in performance -- std::vector is more efficient in accessing members; std::list (and your class) are more efficient in adding members at random places in memory. If you know ahead of time that you'll just keep adding members at the end, then std::vector can be more efficient (see the results of my test earlier or perform the tests you said you would perform).

Aarrrgghhhh.... It doesn't matter. I don't think you'll understand what I, Paul, AvDav, gstercken, OReubens are saying.... or anyone else for that matter. Oh well!

- Kevin

[oktronic]

[QUOTE]Aarrrgghhhh.... It doesn't matter. I don't think you'll understand what I, Paul, AvDav, gstercken, OReubens are saying.... or anyone else for that matter. Oh well!
[QUOTE]

Unfortunately Kevin, I feel that you don't understand, the mentioned linked list is in the system, I provided 2 documents to help explain that. If you don't understand them, please feel free to ask me any questions, but please do not tell me that I don't understand. I understand I've gone a little beyond the scope of just STL, but your belief that a pre-allocated "contiguous" memory is faster then a external pre-allocated linked-list implementation is flawed at the system level.

[QUOTE]stdvector is more efficient in accessing members; stdlist (and your class) are more efficient in adding members at random places in memory[QUOTE]

More efficient then what?

vector does this begin() + elem for operator[].

are you telling me that this:

int ptr = new int[50];

int a = ptr + 50;

is more effiecent then a dereferencing a pointer?

int a = *tempptr ;

if you read the documentation, you would see that the call
ptr + 50
is actually a reference to an address, then the system has to iterate through memory to the page frame that contains element 50.

if you were to simply dereference a pointer to that address like so

*tempptr;

then all the system has to do is go to that address....you do the work for the system instead of the other way around.

So while I'm busy misunderstanding, can you explain to me why using my own list is more inefficient then iterating through system memory list to the 50th element? The hit in memory allocation comes from the system having to allocate a chunk of memory and set up the memory in the system. If you pre-allocate memory, just like vector does, then you don't have to ask the system memory for the hit, and all you have to do is copy the data into the pre-allocated memory. Which is the same thing that vector does except that I have pointer to each of the elements. An extra 8 bytes of data per node. Then I iterate through the list, just as the system would have to, to reach the element you want. But there is a minor hit, but were?

I actually know the answer, and you will find the answer in the documentation provided, but the question I have for you Kevin, is can you find it?

Now personally, I think I'm going beyond the scope of this thread, so I'd recommend that everybody take Kevin's example, pre-allocate memory for data storage and run your benchmark. I think that speaks for itself.

[Adam Gritt]

First, why are we comparing personal code to STL code? I thought this was supposed to be MFC vs STL. However, before we can really decide that we have to agree to what implementation of the STL we are going to look at. MFC is usually either 4.2 or 7.0/7.1 (4.2 was what shipped with VC6). With STL you can use the default that comes with VC6, or VC7.0/7.1 or you can use SGI or STLPort or Dinkumware. Each one, although similar in its interface, does differ in its implementation. Also you can't complain about Memory Leaks in STL without saying the same of MFC because both have become time tested now. If memory leaks exist then either you did some improper programing using them or its your object that has the problem. I have run into cases where it was an implementation problem in the use of MFC or STL.

Now, when programming with MFC you usually end up including the world in your application. No matter where you are (with a few exceptions) you can create any MFC object that exists without have to change the includes as long as you are linked back to stdafx.h. With STL though you tend to only include that which you need. If you are just using a List you only include list. If you need to sort then you have to include algorithm.

Darwin, have you ever done COM programming (C++ not VB)? If so have you used MFC in your COM programming?

[gstercken]

oktronic,

your posts clearly reveal a series of fundamental misconceptions about how memory is organized and accessed. While it is true that dynamic memory is allocated in blocks which are maintained by the system in linked lists, this occurs on a completely different level of granularity than the single elements of an array or other type of container that one might implement. In other words, 1000 bytes allocated with a single new or malloc are of course guaranteed to be in contiguos memory, that is, the single bytes have consecutive addresses, which has important consequences for any algorithm operating on them, namely the possibility to immediately access any single element in constant time by just calculating its address from an offset. OTOH, the memory address of an element of a linked list does not allow you to make any assumption about the addresses of other elements, as the elements are generally allocated with separate calls to the memory manager, so to find an element, you have to walk the list element by element, which takes linear time: The more elements you have, the more time it takes to find a specific one.

The slide shows you are referring to with the two links, OTOH, are about virtual memory and the mapping of logical addresses to physical addresses. However, this is mainly a hardware issue, done by the MMU, and completely transparent to software, so it can be ignored in this discussion. To the software, a (logically) contigous block of memory is accessible as a single block, even if the block actually spreads over different blocks of physical memory, as the mapping is done by the hardware. Software will see the block as one single block, to every effect, even considering performance.

So we are actually dealing with three different levels of abstraction: The hardware mapping of virtual memory to physical memory (which we can safely ignore in this discussion, as we have seen), the way the memory manager maintains separate allocation units as chunks in a linked list (which is also completely meaningless for this discussion), and the way our algortihms and data structures organize and access the memory they allocate (which is what this discussion is all about).

Originally posted by oktronic
if you read the documentation, you would see that the call
ptr + 50
is actually a reference to an address, then the system has to iterate through memory to the page frame that contains element 50.

if you were to simply dereference a pointer to that address like so

*tempptr;

then all the system has to do is go to that address....you do the work for the system instead of the other way around.

Yes, this clearly shows your misconception. Adding a value to a pointer is simply an arithmetic operation, no iteration through memory is involved here. Dereferencing that pointer will just access the contents of memory at that address, always in constant time. The fact that this might require the MMU to translate that logical address to a physical one is, again, completely meaningless, as it occurs on a very low level and still in constant time.

Originally posted by oktronic
So while I'm busy misunderstanding, can you explain to me why using my own list is more inefficient then iterating through system memory list to the 50th element?

Simple: Because using your linked list, this will involve 50 pointer operations: Each time, an offset is added to a pointer (to access the member containing the next-pointer) and dereferencing the result (to get a pointer to the next element). Note that each dereferencing operation will also invoke the MMU for an address translation. The cost for this operation grows proportionally with the number of elelments in the list. OTOH, when using an array, accessing the 50th element is just a matter of a multiplying 50 by the size of an element and adding the result to the array's base address (a simple arithmetic operation, no memory operation involved here!). Then you dereference the resulting address (which will, again, invoke the MMU, but only once), and access the element. Note that this remains exactly the same if your array has 1.000.000 elements instead of 50.

And this brings us to the key point when comparing different data structures (here: containers) against each other: The distinguishing feature of a certain type of container is not its actual implementation (although it practically boils down to that, in the end), but rather the complexity guarantees it makes with respect to certain operations. For example, the data structure commonly known as array or vector (and implemented by std::vector or CArray) guarantees O(1) complexity for accessing arbitrary elements. That's the outstanding quality of arrays, and that's why we use them when we need to access elements in constant time. Note that no guarantees are made for other operations such as insertion and removal of elements: They may be O(log(N)), O(N), even O(N*N) - that's up to the implementation.
Somewhat at the other end of the spectrum, we find the linked list. We know that the cost of finding a specific element is generally O(N), but have the guarantee that adding or removing a known element is done in constant time, O(1). So a list (as implemented by std::list or CList) is the container we choose when adding or removing elements should be always fast, regardless of the size of the list, but we don't need random access to the elements. Likewise, every other type of container (binary tree, queue, stack, hash table...) makes different guarantees about the complexity of different operations, especially when it comes to sorting or accessing elements in a certain order.

Now looking back at what you state about your 'MyTemplateList' implementation:

Originally posted by oktronic
My class can handle dynamic or static memory, contiguous or linked. More specifically, you can hand it any type of memory and it will use it until your size limit is hit, and then it will go dynamic, or fail depending on options. If you refer to the vector code, you'll see that's all it is, a dbl-linked list container. It has some extra functionally, but still, inside that's all it is. Unless you are only defining a linked-list as only a dynamic list?

It seems as if your container wants to be some kind of general allround container, using dynamic or static memory, contiguous or linked as needed, just to fit any needs. This makes it neither a real array nor a real linked list, as it makes no guarantee whatsoever about the complexity of well-defined operations.
So it seems you really missed the most important point about why there are different types of containers, and it explains why you deliberately tried to compare the performace of a linked list with that of an array.
I think you should strongly consider reading about the subject (Donald Knuth's "The Art of Computer Programming", especially Vol. 1, "Fundamental Algorithms" and Vol. 3, "Sorting and Searching" are a good starting point. First published in 1963, they are still highly relevant). Furthermore, regarding sources like the two you pointed out, you should understand that they refer to memory management issues on a completely different level of abstraction than what we are discussing when talking about containers.

[KevinHall]

Originally posted by KevinHall

void list_test()
{
    std::list<int> li;
    int i;

    for (i=0; i<1000000; ++i)
    {
        li.push_back(i);
    }
}

void vector_test()
{
    std::vector<int> vi;
    int i;

    vi.reserve(1000000);
    for (i=0; i<1000000; ++i)
    {
        vi.push_back(i);
    }
}

I ran this code (release build with MSVC 6.0) and profiled it 30 times (with us resolution). Here are the results:

list_test(): 905.5 +/- 3.7 ms
vector_test(): 89.1 +/- 1.1 ms.

Originally posted by KevinHall
Ok, so I've tested what I think oktronic's class looks like (again 30 tests with MSVC 6.0 release build). Here are the results (and to be fair to oktronic, I don't have the sources to his class):

list_test(): 908.1 +/- 1.9 ms
MyTemplateList_test(): 898.9 +/- 7.0 ms
vector_test(): 91.9 +/- 1.4 ms

Actually, I overlooked something in my tests. vector_test() and list_test() actually deallocates the entire list at the end of the function. MyTemplateList_test() did not. Taking that into account, I'm quite sure that the STL outperforms the MyTemplateList that I tested with (see previous post for code).

- Kevin

[oktronic]

Because using your linked list, this will involve 50 pointer operations: Each time, an offset is added to a pointer (to access the member containing the next-pointer) and dereferencing the result (to get a pointer to the

I wasn't comparing it to a linked list.
I was comparing ptr + 50 to *tempptr.

Adding a value to a pointer is simply an arithmetic operation, no iteration through memory is involved here.

Exactly, I was hoping Kevin picked that up, that's why I set that up for him since he didn't seem to understand. That's one of the differences between array iteration and ptr. Its 1 operation to get array address, one addition to new address, 1 operation to get value from address.
However for a simple de-reference, its 1 to get address, 1 to get value. Which is one less operation, so its faster. Which is the point for pre-allocated memory.

you see if you have block of memory for data segment, even for a linked list, if I take first pointer, just like vector does, and I do the same thing to my reserved segment, and set the offset, then it will be just as fast as vector, even though its a linked list.
Twice now I have asked you to simply modify the code Kevin provided and pre-allocate memory for it. So please do so and you will see the results for yourself making this argument moot.

your posts clearly reveal a series of fundamental misconceptions

Actually, Since you seem to have a interesting understanding of the concepts, you should read the second document provided. Its more advanced then the first, but I think you should be able to understand how a page system works. You made several incorrect points about the system, but I think you're able to understand them so I would suggest picking up an advanced operating design book next time you're out.

I think you should strongly consider reading about the subject (Donald Knuth's "The Art of Computer Programming", especially Vol. 1, "Fundamental Algorithms" and Vol. 3, "Sorting and Searching" are a good starting point.

Read them all, got them in my library. Meet Knuth here at Stanford. I should mention I live in the Bay Area and have done some work there.
What kind of bothers me a little, is you quote his book and yet I don't think you know what's in them. So I will suggest the same thing to you, read them and then quote them. But please don't just quote any random books to try to make a point. If you have specific points you feel these books illustrate, then quote the points at least then I might get to see that you understand the point you are making.

While you are about 60% right in your post, there's a lot of holes and I could go on about this for months, operating system design can be a lot of fun and a lot of irritation, but in the interest of this thread, please just add pre-allocated memory to Kevin's class and run your benchmark. If you have any problems with that let me know and I'll explain.
But please, less telling everybody that they are wrong and more time proving your points. I have handed you the ability to prove me wrong, use it.