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

[gstercken]

Originally posted by oktronic
and when you show me yours, I'll show you mine.

[oktronic]

gstercken,
I'm not going to get into another flame war, please act like an adult or move on, if you really require a detailed response to your flame, then let me know where you want it, but keep this thread on topic.

Your last post has shown you to be nothing more then clueless. There are 200 odd posts in this thread all about the pros and cons of STL. If you have no idea what I'm talking about or anybody else, then you haven't been reading them, in which case, anything you say is uninformed and a waste of everybody's time.

But since you had so many questions, I'll answer them in brief.
[QUOTE]Any example where my comments were not on subject?[\QUOTE]
read your post again, find the subject.
[QUOTE]What material??[\QUOTE]
Besides what I posted, how about the other 200 odd posts.
[QUOTE]Confusion... Does this mean you finally understand that you are completely confused about the subject??[\QUOTE]
Didn't say that, perhaps you're confused? Sounds it.
[QUOTE]Has this really been proven? Where? And by whom? I don't see any evidence of that. What are "debug files"?
[\QUOTE]
All 4 answers you seek are in all these nice posts that people spent time writing for your pleasure.
[QUOTE]What the heck is "a linked-list with reserved memory"?[\QUOTE]
Just a guess, but I would say that its a linked list that has reserved memory....
[QUOTE]I think I pointed out more than once than this is completely pointless.[\QUOTE]
You saying this makes it true how exactly? And how could you point that out when you just asked what it was?
[QUOTE]Debugging issues?[\QUOTE]
Yes, as in Debugging issues.

Hope that helps you.

[gstercken]

I see... Your point of view gets clearer and clearer with every post... And dadaism is often used as a last attempt to get out of an uncomfortable discussion...

However, I hoped all the time that you would finally come up with a serious and valid argument to this discussion. Your last post is the definite proof that you painted yourself into a corner, and that you are unwilling and/or unable to seriously defend your original claim, which crumbled into dust by now.

[oktronic]

The only thing you do by continuing to flame and by not reading the posts, or adding anything constructive or accurate to this thread, is undermine your own credibility.
I'll ask you again to either act like an adult or move on.
The next phase to this thread is for actual performance tests. I submitted mine for the purpose of moving this thread forward to something more constuctive then, "I'm right, your wrong, so there". If this is to complex for you, then I'm sure there are other threads you can post in.

[KevinHall]

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

So your solution is actually slower than std::vector?

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

I already did this many posts ago. I posted the code, the compiler, the fact I used the release configuration, and the results.

[oktronic]

Hi Kevin,
Yes, I expected it to be slower since it does have more operations then vector does when both are pre-allocated.

I'm interested though, in you "pre-allocating" memory for your previous linked-list that you posted when you get a chance, so we can compare the benchmarks against optimization techniques.
If you did already posted that, if you could point me in the direction, been sifting though lots of posts as of late.

[KevinHall]

Ok, sarcasm aside. I believe what oktronic is suggesting is that his class can pre-allocate memory in much the same way std::vector can. In this sense, he will be avoiding the penalties of continually calling new. Fine. This may be a good design in some cases. I have not had the need to override the standard allocator yet, but I believe that a similar approach can be used with std::list by overriding the standard allocator (someone correct me if I am wrong). Then I would expect similar performance from both std::list and oktronic's code. Like oktronic's tests showed and he himself noted, std::vector is still faster if pre-allocated memory is used. This is due (in part at least) to the fact that std::vector does not have to assign pointers used for a linked list.

All that being said, there are two main differences (perhaps more -- can't verify since oktronic cannot release his code)between oktronic's class and std::vector:
(1) oktronic's class uses different error handling mechanisms
(2) oktronic's class is not a true "drop-in" for std::vector, because of the order (constant-time, linear, O(log(N)), ...) of certain operations. It is really more akin to std::list (which using a non-standard allocator can likely have performance on par with oktronic's class).

A few notes about the tests we have performed:
- my tests were performed without the real code behind oktronic's class
- oktronic's tests may (maybe not) be skewed to emphasize the strengths of his class
- As Paul or OReubens pointed out earlier, these tests are likely not real-world tests anyway.

All guesses as to what oktronic's class exactly does, or how it performs is unknown and further discussion will not be productive. We know that:
* oktronic's class is a linked list. And linked lists have some inherent traits (O(N) time for finding the nth element for example)
* oktronic's class is slower than std::vector and likely faster than std::list (with a standard allocator) for the over-simplified tests given. Most people might liken this to "comparing apples and oranges" though.

I believe we have be quite hard on oktronic (some of that probably warranted, some probably not). I do believe that his claims have been overly bold, that he has done everything to hold his position on his prize piece of code. Our poking and prodding has only served to build his defensiveness. oktronic, in the future chill-out a little bit. I can vouch that most if not all of the people who confronted you really want to get to the truth, are interested in helping others, and interested in learning more -- just take a look at their posts in the past. In the past, I have come up with some insight and solutions people have found very valuable. I have also been corrected many times. So be it! That's part of me growing and learning as a programmer.

I think that's enough on this topic.

Originally posted by oktronic
I'm interested though, in you "pre-allocating" memory for your previous linked-list that you posted when you get a chance, so we can compare the benchmarks against optimization techniques.
If you did already posted that, if you could point me in the direction, been sifting though lots of posts as of late.

No, I didn't do that test, b/c until now I don't think I understood what you were trying to do. And I don't feel like spending anymore time on this topic. Sorry! After thinking about what you claim you are doing, I don't question your results. I still don't think that your class and std::vector are fair comparisons, because all other operations will vary greatly in their performance. std::vector will be much slower trying to insert elements in the middle of the data; your class (and any linked list for that matter) will be slower trying to randomly access elements (not iterating through elements). This is because of the very nature of linked lists and the very nature of arrays. My only question would be how well std::list would perform using a non-standard allocator. Even then, it would not be fair to compare against your class because of the different error handling -- which is absolutely fine -- it just isn't the way many programmers want to handle errors.

- Kevin

[oktronic]

Ok, Kevin,
This bothers me.
I don't recall making any bold statements. I told you that my class can perform as fast if not faster then vector, but I asked you to create your own and compare. I could have used list, but I did that on purpose. So my class isn't in question here. It goes far beyond STL. As for "drop-in", this is a terminology issue. "drop-in" means will compile in place of. "in-place" code must adhere to the code its replacing. I believe I stated much earlier that my class is different.

Besides all that though, I wasn't asking you to compare your code to my class.
What I made you do was write the class. A little bold, but not in statement.
It was said C++ contiguous memory is faster then dynamic. I told you that the system hit is minimal and explained with example. Nothing bold yet.
You don't believe me, so I challenged you to simply modify your linked-list class and compare.
This is what I don't get. All you have to do is add 2 functions for allocation calls and 2 pointers and 2 counts. took me 5 minutes to modify your code and run the tests, I did the pre-alloc in the constructor since all I want to test in this case is the insert. I actually had the time to add the checks in so the class could grow as a linked list when its limit was full. Nothing complex here.
I wanted you to write this so you can see, for yourself, how your class and the system interact. This way there is no argument. Simple fact. You can hardly argue with your own eyes.
I haven't made any claims that my class is some form of magical class that will solve the world's problems. I specifically encouraged you to do the work yourself so you would learn.
Yet, for some reason since the beginning of time, people who like to argue, rarely like to learn and even in the face of their own findings will refuse to accept theory as fact.
All you would have to do is try the very assumption you are proposing and see the results for yourself, no bold statements, no magic pills, just old fashioned trial and error programming.
So this does bother me. Lots of people quoting, lots of flames, lots of accusations, yet nobody seems to want to actually try the very thing they are talking about. I've been asking for 2 days now, so imagine my disappointment.
You own a computer, you have a compiler, you assumingly know how to program, so I say do the work and learn. If this is a bold statement, then color me bold.

[KevinHall]

Originally posted by oktronic
Ok, Kevin,
This bothers me.

Wow! That was the most concilliatory message you have received in this forum. It was not a flame-war message by any means.

Originally posted by oktronic
This is what I don't get. All you have to do is add 2 functions for allocation calls and 2 pointers and 2 counts. took me 5 minutes to modify your code and run the tests, I did the pre-alloc in the constructor since all I want to test in this case is the insert. I actually had the time to add the checks in so the class could grow as a linked list when its limit was full. Nothing complex here.
I wanted you to write this so you can see, for yourself, how your class and the system interact.

Didn't I say that I could understand how you got the results you did? And all I said was I didn't want to be on this topic anymore. Nothing about what you said being complex.

Originally posted by oktronic
yet nobody seems to want to actually try the very thing they are talking about. I've been asking for 2 days now, so imagine my disappointment.

I didn't understand what you were trying to do until tonight. You refused to give me code when I asked (ok, maybe it considered IP for the company you work for). You didn't even post pseudo-code though. People cannot try an idea until they understand. And, I'm talking with respect to the idea of pre-allocation here, not the linked-list snippet.

Originally posted by oktronic (emphasis added)
you assumingly know how to program

Now this is demeaning!!! I've seen many people say you are mistaken, but I don't recall (and maybe I am wrong) anyone saying that there was doubt you could program. People stated doubt about your understanding of the topic in question, but not about ability to program. Anyway, a quick review of the messages someone has posted can easily reveal whether or not someone has the ability to program.

[KevinHall]

Ok, I just wanted to check to make sure I have not misspoken. Let's see what has happened:

http://www.codeguru.com/forum/showth...126#post851126

This is a message where you violently attack Paul. It could be argued that Paul drew first blood though (at least in this thread-- I do not know if there was other history here). If I had to make an analogy here: Paul may have cut off your finger, but you cut off his head!

http://www.codeguru.com/forum/showth...957#post852957

Originally posted by oktronic
Here is my own 'vector' style class. Has all the fat cut out and is drop in compatible with vector.

vector.push_back(i) = 1.2 seconds.
MyTemplateList.push_back(i) = 0.6 seconds.
CArray.Add(i) = 12 seconds.

So as you can see, and feel free to try, user written is fastest (providing done right), STL is middle and CArray is so poor that last is too good for it....
But to give CArray some credit, its far more defensible and easier to debug then STL.

So you decide which you feel is "better"....Again I vote user written because you control the performance and you know you can be at least as fast as the library, have more functionality and be better designed, which is everything you could want in a program or library.

Yep, I still believe this is a bold statement -- not that someone can write their own code optimized for a particular situation. I believe the two bold claims were (a) that your class was a drop-in replacement for std::vector and (b) your timing results given that the two classes are fundamentally different (you didn't write an array or vector replacement, you wrote a linked list replacement) and the fact that for the given situation, there was a simple, very simple way to optimize std::vector's behavior (you'll find many posts in CodeGuru where someone is told "use reserve()").

[Yves M]

I guess nobody asked for it, but here is some code that shows timing differences between std::list with and without my custom allocator and std::vector. The custom allocator essentially reserves all memory up-front.

Results in seconds:

std::vector with reserve         : 0.0115378
std::vector without reserve      : 0.0775238
Custom allocator with std::list  : 0.0763225
Standard allocator with std::list: 9.09361
C-style array                    : 0.0121524

Here is the code:

#include <limits>
#include <iostream>
#include <list>
#include <conio.h>
#include <vector>
#include "../../../utils/utils.h"

const size_t TEST_SIZE = 10000;
const double TIME_MULTIPLIER = 100.0;

const size_t MAX_SIZE = (TEST_SIZE + 1) * 12;

class MemoryPool
{
  unsigned char  *m_data;
  size_t      m_top;
  int        m_refcount;
public:
  MemoryPool()
  {
    m_data = new unsigned char&#091;MAX_SIZE&#093;;
    m_top = 0;
    m_refcount = 0;
  }
  ~MemoryPool()
  {
    delete &#091;&#093; m_data;
  }
  void AddRef()
  {
    ++m_refcount;
  }
  void *alloc_mem(size_t n)
  {
    if ((MAX_SIZE - m_top) >= n) {
      size_t old_top = m_top;
      m_top += n;
      return m_data + old_top;
    } else {
      return 0;
    }
  }
  void Release()
  {
    if (--m_refcount == 0) {
      delete this;
    }
  }
};

template <class T>
class MyAlloc {
public:
  // type definitions
  typedef T        value_type;
  typedef T*       pointer;
  typedef const T* const_pointer;
  typedef T&       reference;
  typedef const T& const_reference;
  typedef std::size_t    size_type;
  typedef std::ptrdiff_t difference_type;

  // rebind allocator to type U
  template <class U>
  struct rebind {
    typedef MyAlloc<U> other;
  };

  // return address of values
  pointer address (reference value) const {
    return &value;
  }
  const_pointer address (const_reference value) const {
    return &value;
  }

  /* constructors and destructor
  * - nothing to do because the allocator has no state
  */
  MyAlloc() throw() {
    m_pPool = new MemoryPool;
    m_pPool->AddRef();
  }
  MyAlloc(const MyAlloc& src) throw() {
    m_pPool = src.m_pPool;
    m_pPool->AddRef();
  }
  template <class U>
  MyAlloc (const MyAlloc<U> &src) throw() {
    m_pPool = src.m_pPool;
    m_pPool->AddRef();
  }
  ~MyAlloc() throw() {
    m_pPool->Release();
  }

  // return maximum number of elements that can be allocated
  size_type max_size () const throw() {
    return MAX_SIZE / sizeof(T);
  }

  // allocate but don't initialize num elements of type T
  pointer allocate (size_type num, const void* = 0) {
    // print message and allocate memory with global new
    pointer ret = (pointer) m_pPool->alloc_mem(num * sizeof(T));
    return ret;
  }

  // initialize elements of allocated storage p with value value
  void construct (pointer p, const T& value) {
    // initialize memory with placement new
    new((void*)p)T(value);
  }

  // destroy elements of initialized storage p
  void destroy (pointer p) {
    // destroy objects by calling their destructor
    p->~T();
  }

  // deallocate storage p of deleted elements
  void deallocate (pointer p, size_type num) {
    // do not deallocate memory
  }

  MemoryPool  *m_pPool;
};

// return that all specializations of this allocator are interchangeable
template <class T1, class T2>
bool operator== (const MyAlloc<T1>&, const MyAlloc<T2>&) throw() {
  return true;
}
template <class T1, class T2>
bool operator!= (const MyAlloc<T1>&, const MyAlloc<T2>&) throw() {
  return false;
}

void fun_my_alloc()
{
  std::list<int, MyAlloc<int> > l;
  for (int i = 0; i < TEST_SIZE; ++i) {
    l.push_back(10);
  }
}

void fun_std_list()
{
  std::list<int> l;
  for (int i = 0; i < TEST_SIZE; ++i) {
    l.push_back(10);
  }
}

void fun_std_vector()
{
  std::vector<int> l;
  l.reserve(TEST_SIZE);
  for (int i = 0; i < TEST_SIZE; ++i) {
    l.push_back(10);
  }
}

void fun_std_vector_no_reserve()
{
  std::vector<int> l;
  for (int i = 0; i < TEST_SIZE; ++i) {
    l.push_back(10);
  }
}

void fun_c_array()
{
  int *pl = new int&#091;TEST_SIZE&#093;;
  for (int i = 0; i < TEST_SIZE; ++i) {
    pl&#091;i&#093; = 10;
  }
  delete &#091;&#093; pl;
}

using namespace std;

int main()
{
  CPrecisionTimer ct;
  double tim_my_alloc, tim_std_list, tim_std_vector, tim_std_vector_no_reserve, tim_c_array;
  cout << "Timing c-style array" << endl;
  ct.Start();
  fun_c_array();
  tim_c_array = ct.Stop();
  cout << "Timing std::vector with reserve" << endl;
  ct.Start();
  fun_std_vector();
  tim_std_vector = ct.Stop();
  cout << "Timing std::vector without using reserve" << endl;
  ct.Start();
  fun_std_vector_no_reserve();
  tim_std_vector_no_reserve = ct.Stop();
  cout << "Timing Custom allocator with std::list" << endl;
  ct.Start();
  fun_my_alloc();
  tim_my_alloc = ct.Stop();
  cout << "Timing Standard allocator with std::list" << endl;
  ct.Start();
  fun_std_list();
  tim_std_list = ct.Stop();

  cout << "std::vector with reserve         : " << tim_std_vector * TIME_MULTIPLIER << endl;
  cout << "std::vector without reserve      : " << tim_std_vector_no_reserve * TIME_MULTIPLIER << endl;
  cout << "Custom allocator with std::list  : " << tim_my_alloc * TIME_MULTIPLIER << endl;
  cout << "Standard allocator with std::list: " << tim_std_list * TIME_MULTIPLIER << endl;
  cout << "C-style array                    : " << tim_c_array * TIME_MULTIPLIER << endl;
  _getch();
  return 0;
}

[edit: corrected two problems: delete [] in MemoryPool's destructor and fun_std_vector should only reserve TEST_SIZE memory]

[Yves M]

Here is the code for utils.h, which contains just a Windows-specifc high-resolution timer:

#include <windows.h>

class CPrecisionTimer  
{
public:
  double Stop();
  long double ToDouble(LARGE_INTEGER& val);
  void Start();
  CPrecisionTimer();
  virtual ~CPrecisionTimer();
private:
  LARGE_INTEGER m_start;
  LARGE_INTEGER m_freq;
};

CPrecisionTimer::CPrecisionTimer()
{
  QueryPerformanceFrequency(&m_freq);
}

CPrecisionTimer::~CPrecisionTimer()
{

}

void CPrecisionTimer::Start()
{
  QueryPerformanceCounter(&m_start);
}

long double CPrecisionTimer::ToDouble(LARGE_INTEGER &val)
{
  long double f = val.u.HighPart;
  f = f * (DWORD)-1;//4294967296;
  f += val.u.LowPart;
  return f;
}

double CPrecisionTimer::Stop()
{
  LARGE_INTEGER curval;
  QueryPerformanceCounter(&curval);
  long double f = ToDouble(m_start);
  long double f1 = ToDouble(curval);
  long double f3 = ToDouble(m_freq);
  return (f1 - f)/f3;
}

[Yves M]

First a word of warning about the code above. You will need to have a compiler which understands templates better than VC6. I compiled this on VC.NET 2003 in Release mode to get the results.

Now, for the interpretation of the results:

std::vector with reserve         : 0.0115378
std::vector without reserve      : 0.0775238
Custom allocator with std::list  : 0.0763225
Standard allocator with std::list: 9.09361
C-style array                    : 0.0121524

• The difference between std::vector and the c-style array is minimal and probably due to random system influences. Moving the timing order around will in fact result in these two swapping the top spot. This means that in practice, push_back and array assignment are pretty much the same speed, if the vector has enough memory.
• std::vector without reserve is about seven times slower. Of course, this all goes into reallocation and copying of elements. The one conclusion is obvious, namely that if you can, use reserve.
• std::list with the default allocator is abysmally slow. This time is *mostly* spent in new and delete, as the version with the custom allocator is much faster.
• std::list, whichever allocator you use, uses 3 times as much memory (at least) as a vector or a c-style array. This is because each node has a forward and a backward pointer as well (and my machine is 32 bits). This is inherent in linked lists, so please don't say it's STL's fault

Anyways, what I'm trying to say is that for many problems you have to fiddle around until you find a good solution. STL's containers are a good solution for many cases and if you do find performance problems, it is very likely that you'll be able to sort these out by either switching to a different container or by tweaking the allocator.

I for one think that it is quite impressive what speed gains you can achieve by using a different allocator (here it's 120 times faster). This is one of the nice things about STL that MFC doesn't have. How would you provide a custom allocator for a CArray ? For a CList or a CMap ? The STL is extended much more easily than MFC, if it's possible at all with MFC.

[voidspace]

std::map<*>=size=<_Mysize>
std::vector<*>= first=<_First> last=<_Last>
std::list<*> =size=<_Mysize>
std::multimap<*>=size=<_Mysize>
std::set<*> =size=<_Mysize>
std:eque<*> =size=<_Mysize>
std::queue<*> =size=<c._Mysize>
std:riority_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:air<*> =first=<first> second=<second>
std::less<*>=lessthan
std::greater<*>=greaterthan


adding this to autoexp.dat does not expand it values ..


BULLETMAP::iterator it = m_Map.find(Key(iRowl, iCol));
ASSERT(it != m_Map.end()); // the entry should exist
if(it != m_Map.end())
{
int nRow = it->nRow; // codepoint A

......
......
}

I can view the value of nRow
but I cannot directly view the values of it->nRow or it->nCol or any of its members at codepoint A. This is using VS.Net 2003. It is kinda important for me to know this as there are thousands of lines of STL code which other programmers had written and programmers are not perfect. They can leave bugs here and there and to be able to debug into STL data is a requirement from my prespective. With superfast machines (hardware wise) it is important to be able to debug and track or integrate new features into existing architecture quickly and easily rather than speed.
The time has come where a programmer time is more critical than machine computing time.

[KevinHall]

Originally posted by voidspace
adding this to autoexp.dat does not expand it values ..

I know, but it's better than what VS 6.0 did before.

In VS .NET 2003, there is a hook to build your own display string for a given type. Granted this is still not perfect as there is no way to do custom expansions, but it's still better than VS 6.0.

It seems MS is making progress, and I'd still like to see them make things even easier. It's not impossible to find things using the debugger, it's just a mess a right now (finding a specific value in an std::map can require following many, many pointers). But again this is not a design problem of the STL, it is something that the maker of the debugger (MS is this case) could fix if they put enough effort into it.