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

[voidspace]

STL is really nifty tool to make a programmer life easier .. but STL code is hard to maintain and debug.
For example

class AFX_EXT_CLASS CBulletInfoEntry : public CObject
{
DECLARE_SERIAL(CBulletInfoEntry)

public:
int nKey; // the Key: (nRow<< 4 | nCol)
RGBCOLOR nColor;
int nRow;
int nCol;
};

typedef std::set<CBulletInfoEntry> BULLETMAP;

BULLETMAP::iterator it = m_Map.find(Key(iRowl, iCol));
ASSERT(it != m_Map.end()); // the entry should exist

// At this point i want to view the values of 'it' which is basically a item of BULLETMAP and namely CBulletInfoEntry. But I cannot do this in the debug or watch window. This is one debugging difficulty we face when using STL.
i.e it->nCol ?
it->nRow ?

Also I cannot do this in debug window it,10 ( to see all the 10 items)

STL is very good at getting the job done quickly. But if there needs to be modification to existing design or if there is a bug then STL is more harder to debug and maintain vs MFC.

[Adam Gritt]

Originally posted by voidspace
STL is really nifty tool to make a programmer life easier .. but STL code is hard to maintain and debug.

That only depends on how you use it.

Originally posted by voidspace
typedef std::set<CBulletInfoEntry> BULLETMAP;

BULLETMAP::iterator it = m_Map.find(Key(iRowl, iCol));
ASSERT(it != m_Map.end()); // the entry should exist

// At this point i want to view the values of 'it' which is basically a item of BULLETMAP and namely CBulletInfoEntry. But I cannot do this in the debug or watch window. This is one debugging difficulty we face when using STL.
i.e it->nCol ?
it->nRow ?

First off I would like to point out that the correct reference would be it->second.nCol or it->second.nRow. That is just a matter of understanding how the STL stores the information in a map. Second the only reason the other stuff is so nice in the debugger is because MS has that information configured that way in the autoexp.dat. I have actually added my own aditions so my maps, vectors and lists do similar things. For instance, adding the following line to your autoexp.dat will make the STL string template display correctly:

std::string<*> =<_Ptr, st>

Now it will display the same as a CString would.

Originally posted by voidspace
Also I cannot do this in debug window it,10 ( to see all the 10 items)

Actually this can also be done in the debug window depending on what you are using, it is just a bit more in-depth because you actually have to break it out and remember that it is a pointer and in a map the items are not stored contiguously.

[KevinHall]

Originally posted by voidspace
but STL code is hard to maintain and debug.

...

At this point i want to view the values of 'it' which is basically a item of BULLETMAP and namely CBulletInfoEntry. But I cannot do this in the debug or watch window. This is one debugging difficulty we face when using STL.

Also I cannot do this in debug window it,10 ( to see all the 10 items)

Yes, yes, yes. But this is more the fault of the debugger for not allowing such information to be seen easily. Have you ever noticed how MSVS allows you to see the contents of a _variant_t type just fine without expansion -- even though the definition of that class is not simple? I dream of the day MS has better watching of STL data!

[KevinHall]

Originally posted by Adam Gritt
I have actually added my own aditions so my maps, vectors and lists do similar things. For instance, adding the following line to your autoexp.dat will make the STL string template display correctly:

std::string<*> =<_Ptr, st>

Now it will display the same as a CString would.

Please enlighten the rest of us and list the link to appropriate web documentation concerning this. Also, would you mind posting what additions you have made? That will make my life (and others') easier!

Thanks!

[vicodin451]

Originally posted by KevinHall
Please enlighten the rest of us and list the link to appropriate web documentation concerning this. Also, would you mind posting what additions you have made? That will make my life (and others') easier!

Thanks!

MSDN,
"Visual Studio"
"Displaying Elements of a Custom Data Type"

Native Code
When you are using interface elements such as the Watch window, the Visual Studio debugger automatically expands common data types to show their most important elements. If you have your own custom data types that you want the debugger to autoexpand, you can add rules to the file autoexp.dat, which is located in the \bin directory. Instructions on how to write autoexp rules are located in the file itself.

Note The structure of this file and the syntax of autoexp rules may change from one release of Visual Studio to the next.

[Paul McKenzie]

The STL containers aren't constrained into doing the default memory management. I don't see why a custom allocator couldn't be written for std::list if "reserved memory" were an issue.

Regards,

Paul McKenzie

[voidspace]

Refering to autoexp.dat is good but better would be if there was some generic list of things that can be added to it to make STL debugging more easier. If some one can post the entries they made to autoexp.dat that would be much appriciated.

[KevinHall]

Visual Studio .NET 2003 added the following:

std::map<*>=size=<_Mysize>
std::vector<*>= first=<_First> last=<_Last>
std::list<*> =size=<_Mysize>
std::multimap<*>=size=<_Mysize>
std::set<*> =size=<_Mysize>
std::deque<*> =size=<_Mysize>
std::queue<*> =size=<c._Mysize>
std::priority_queue<*>= first=<c._First> last=<c._Last>
std::stack<*> =size=<c._Mysize>
std::binder1st<*>= op=<op> value=<value>
std::binder2nd<*>= op=<op> value=<value>
std::pair<*> =first=<first> second=<second>
std::less<*>=lessthan
std::greater<*>=greaterthan

I believe most of these will work for VS 6.0, but I have not checked them all.

[gstercken]

oktronic,

although this discussion is somewhat running on the spot, I'll try to answer once more. The problem I (and I think others as well) have with your kind of argumentation that you hardly ever get to the point which is actually being discussed. You keep saying that others are wrong, whithout further explaining why.

What about the different levels of abstraction you are deliberately intermixing? Any comment on that? What about the fact that the links you posted are about low level memory management issues at the hardware / OS level, but have nothing to do with algorithms and their complexity?

Until now, you still didn't make your point very clear. You started out by claiming to have a self-implemented vector template class which can be used as a drop-in compatible replacement for std::vector, yet being more readable in code, and performing better than std::vector and CArray. However, what you showed us was the implementation of a linked list (rather to be compared to std::list than std::vector), so your benchmark, which used tail insertion, was completely meaningless. Furthermore, it has been pointed out that your class is not compatible with std::vector for several reasons. A more meaningful benchmark test conducted by Kevin showed that your class performed somewhat near to std::list (which was to be expected), and was about 10 times slower than std::vector with a pre-allocated size (which is also within the normal range of expectation).

However, you completely ignored those facts, only stating that std::vector is also a linked list implementation (which has been proven wrong), and that your class would perform the same as std::vector if only pre-allocated memory was used. Now, pre-allocating memory makes sense for an array, but not for a linked list, and it remained completely unclear how memory should be "pre-allocated" for the class you posted so far.

Instead, you diverted the discussion to how virtual memory is handled at the hardware / OS level, something completely unrelated to the original subject. You posted two links to what you called "documentation", but there were only slides meant to accompany a basic class on OS design. You still didn't comment on that, leaving everyone with the impression that you fail to perceive the fundamental difference between virtual memory management at the hardware level and data structures at the software level.

I apologize if I sound a little harsh now , but most of the statements you made so far (and also some technical terms used in a slightly out-of-place manner) have the smell of hot air, and leave the impression that you have not the slightest of what you are talking about.

So your posts to this thread so far leave everyone puzzled: Did you just want to add some noise, or do you really have valid arguments to contribute? If so, you should rather lay them out clearly, instead of just making doubtful claims.

Oh, and yes:

Originally posted by oktronic
I wasn't comparing it to a linked list.

Yes, you were, as your original statement leading to this quote was "can you explain to me why using my own list is more inefficient then iterating through system memory list to the 50th element?". Here's why: "my own list" in this context means your linked list implementation, and "iterating through system memory list" was the way you claimed to understand how array elements were accessed.

Originally posted by oktronic
Exactly, I was hoping Kevin picked that up, that's why I set that up for him since he didn't seem to understand.

What do you mean by "set that up for him"? You mean you intentionally made a wrong statement as sort of a bait, to have him pick it up? My impression is that Kevin understood very well what he's talking about, while your preceding statement about adding a value to a pointer and dereferencing it showed, once again, a severe misconception about the entire subject.

Originally posted by oktronic
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.

No, no, again. The point about arrays is that you can randomly access any element in constant time, not just iterate through it. The cost of iterating an array vs. iterating a list is always linear, and only differs in details. It might be a little faster or a little slower, depending on the actual implementation. Complexity comes in only when you have to access an arbitrary element.

Originally posted by oktronic
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.

As already said above: pre-allocating memory makes sense for an array, but not for a linked list. Kevin already had to make guesses and anticipate your linked-list code in order to run his benchmark. How would you want him to implement something as a pre-allocation scheme (which is meaningless for a linked list) for your class?

Originally posted by oktronic 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.

Thank you. The second "document" you mention is a slide show which reminds me of the material presented at my undergrad OS design class 15 years ago. Nice slides, but, as said above, completely unrelated to the discussion in this thread. The thread's original subject was somewhat like "I hate STL, I prefer MFC containers", and, as expected, led to heavy debates on that topic. Your contribution first sounded like "I roll my own STL replacement, which is much better", but then you failed to show how and why, and the discussion diverted into complexity considerations for arrays vs. linked lists, as you seemed (and still seem) to completely ignore that important point. Instead, you brought up the links to the OS design slides, which, I say it again, have no relevance to the original topic. That maneuver just showed your concepts about memory, addresses, pointers etc. to be rather diffuse.

Originally posted by oktronic
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.

Wow, impressing. Look, I have been living in Verona and heard Placido Domingo at the Arena, but that doesn't make me a tenor. I've met Marvin Minsky and Joseph Weizenbaum, but that doesn't make me an AI philosopher. Reading their works, however, can give you a slight idea. So if you've really read Knuth, are you sure you also understood what you read?

Originally posted by oktronic
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.

So if you've got them in your library, just pick up Vol. 1, "Fundamental Algorithms" and turn to page 244. Read chapter 2.2.2, "Sequential Allocation" and the following chapter 2.2.3, "Linked Allocation". After that, come back and tell us if you still support the statemets you made above about arrays and linked lists.

Originally posted by oktronic
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.

Yes, OS design is fun, but again, as said above, is not related to the subject here. As to the pre-allocated memory, see above.

Originally posted by oktronic
But please, less telling everybody that they are wrong and more time proving your points.

Note that I'm not "telling everybody that they are wrong", but that several posters here are having a hard time trying to convince you that you're actually missing the point. I think I proved my points more than enough. Just read what I wrote and go into it instead of just ignoring the key arguments.

Originally posted by oktronic
I have handed you the ability to prove me wrong, use it.

I think I sufficiently did so...

[gstercken]

OK, I just noticed that my last post floats more or less on the flame war level, and contributes little to the original STL discussion (which has been carried on in the meantime). My apologies, but I didn't want to leave that branch of the discussion completely uncommented.

[oktronic]

gstercken

I'll ask you to please keep your comments on subject. You will find a character debate will not lead you anywhere you want to go.
If you don't understand any of the material, then please ask.

I actually had a long drawn out post to point out every post that you seem to have missed to show your post to be silly and unfounded, but I'm not going to play that game twice.

You feel your right. Good for you.

But is your position so weak that your only recourse to try to make yourself look big, by talking big? Maybe you feel if you confuse me, and the issue, you might actually make yourself right? hmmm...

The current issue was whether or not STL is more efficient then anything else, I believe this is where we were.
Its already been proven that its badly designed, badly written, badly documented, hard to debug (except for modifying the debug files as proposed, which does help) and even for compact code, it could actually be more compact.

So I'm still waiting for you to benchmark a linked-list with reserved memory to see if vector using "contiguous" memory is so much faster, or at least see a argument for this,
I believe that's where we were.
There is no point to starting this debate all over with the debugging issues again.

[KevinHall]

Originally posted by oktronic
So I'm still waiting for you to benchmark a linked-list with reserved memory to see if vector using "contiguous" memory is so much faster, or at least see a argument for this,
I believe that's where we were.

oktronic, I thought you were going to provide us with the benchmark tests!

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.

Have you rescinded your offer?

Originally posted by oktronic
Its already been proven that its badly designed, badly written, badly documented, hard to debug (except for modifying the debug files as proposed, which does help) and even for compact code, it could actually be more compact.

I believe most modern versions of the STL are well designed and well written.

Documentation and ease of debugging really depend on the who wrote the documentation and who wrote the debugger.

As far as being "compact" -- well, that's a trade off for any application -- do you optimize for speed or optimize of smaller (more compact) code size?

[AvDav]

To say the true, I don't understand the points that it is bad documented and hard to debug. All you need to know about STL is how to use containers, algorithms, functors etc, these are documented too much. Why do you need to deep into STL code with debugger? To find a bug in STL?

[gstercken]

Originally posted by oktronic
I'll ask you to please keep your comments on subject.

Any example where my comments were not on subject?

Originally posted by oktronic
If you don't understand any of the material, then please ask.

What material?

Originally posted by oktronic
But is your position so weak that your only recourse to try to make yourself look big, by talking big? Maybe you feel if you confuse me, and the issue, you might actually make yourself right? hmmm...

Confusion... Does this mean you finally understand that you are completely confused about the subject?

Originally posted by oktronic
The current issue was whether or not STL is more efficient then anything else, I believe this is where we were.
Its already been proven that its badly designed, badly written, badly documented, hard to debug (except for modifying the debug files as proposed, which does help) and even for compact code, it could actually be more compact.

Has this really been proven? Where? And by whom? I don't see any evidence of that. What are "debug files"?

Originally posted by oktronic
So I'm still waiting for you to benchmark a linked-list with reserved memory to see if vector using "contiguous" memory is so much faster, or at least see a argument for this,
I believe that's where we were.

What the heck is "a linked-list with reserved memory"? I think I pointed out more than once than this is completely pointless. You still failed to come up with an explanation about how you would reserve memory for a linked list, like you failed to comment on any other of the key arguments.

Originally posted by oktronic
There is no point to starting this debate all over with the debugging issues again.

Debugging issues?

[oktronic]

I'm hoping you will do the benchmark yourself so you can see where optimization will come into play, but the stats are, using the same test except that I kicked up the count to 5 Million in the loop to increase resolution, at 1 mil they were both at less then 20ms.

vector = 120ms av.
linked-list = 160ms av.

It was expected that the list would be alittle slower since the
it does assign the pointers, and that's going to take a little time.
But I think it demonstrates how the system optimizations are a negative for the vector, since 40 ms spread isn't that much of a bonus for 5 mil inserts.

This was using my own, but I'll write up another to post that does this and when you show me yours, I'll show you mine. I'm interested in your solution.