Help understanding article

Its not really clear from the article, there isn't enough code. He appears to be doing some form of object recycling, but it isn't clear from the classes posted how he differentiates between "live" objects and recycled ones. The ownership semantics are totally unclear too.

I suspect he could have achieved the same using std::vector<>, or possibly two vectors of "live" and "dead" Points (which have been allocated dynamically). He leaves this somewhat cyptic remark in the comments:

Quote:

Then the question is why not use vector - not so simple - the actual data structure represented is not a POINT - it's more complicated. This means that every push and pop invokes the copy constructor, which will be 2.6 million copy constructors. Tried it - not acceptable.

Essentially, I don't see how he removed this need in his program. If he is recycling objects, then he will need to do something similar anyway.

I'd need a lot more code and context to figure out what he is talking about. Preferably some kind of actual program where you could measure the performance impact of different designs.

The interesting feature of this system is that he's bound the container to the object implementation. In particular, as he noted at the beginning of the article, the purpose of the objects in question was to live in a stack. The critical observation here is the behaviour of a stack: when you pop an element, then push a new one, you can reuse the memory of the popped element for the newly pushed one. You only need to actually allocate when the stack itself is empty. This means that the stack essentially becomes a cache; after allocating N items, it is cheaper to allocate up to N items again because the cache holds the allocated memory for each element, and the stack container tracks which elements are actually in use.

This doesn't answer the question of how he thinks he got away without the copy constructor overhead, though, which I'm honestly a bit fuzzy on, but oh well - the raw concept is still useful, and indeed we use a similar trick at work for fast allocation all the time.

Quote:

when you pop an element, then push a new one, you can reuse the memory of the popped element for the newly pushed one.

Maybe I misunderstood what he was planning to use this for. What if he pops 3 elements, and then adds three? wouldn't that then force his code to use "new" at least two more times?

Quote:

after allocating N items, it is cheaper to allocate up to N items again

If his app needs to pop the entire list of say, 20 items, except one element, how will he keep track of the other 19 that were allocated and reuse them? I don't see any way of reusing memory without traversing all elements looking for an empty one each time.

I know an array is out of the question for a set of indeterminate size, because any kind of reallocation to add space would necessitate the copying of all the data to a new location, which can be slow....

Do you guys see what I am getting at here?

The article is right about one thing - when dealing with tons of short-lived small allocations, new should (must) be avoided.

The rest can be ignored. It's generally thinking in the right direction, but there's tons of inaccuracies scattered throughout.

std::stack is fine. Otherwise, use std::vector. Considering compiler and STL versions are not mentioned, it was likely done using MVS with checked iterators running in debug mode.

Well, that guy who wrote the nonsignificant article made all the destructors virtual. And deleting items with virtual destructors is time-consuming. So he wrote a custom stack which does not actually delete popped elements. Instead the elements are kept around for later allocations. This way no destructors are getting called. Well they are only called when the whole stack is destroyed.

So basically he did an absolute unnecessary optimization with his custom allocator, which could have been avoided completely by simply using std::vector instead of std::stack, which uses std::list internally by default in many STL distributions. However that guy doesn't seem to be that smart.

Just ignore that article.

[Edited by - Christian Weis on August 7, 2010 9:04:14 PM]

Quote:

Just ignore that article.

sounds like a plan lol

Quote:

Original post by Christian Weis which could have been avoided completely by simply using std::vector instead of std::stack, which uses std::list internally by default in many STL distributions.

1) "many STL distributions" are not relevant, because we are talking about the standard library here, not "the STL", which hasn't really been relevant as such in many, many years.

2) The default underlying container for std::stack is in fact std::deque, and this is actually specified in the standard and not just "what everyone does". It can, of course, be overridden with the second, optional template parameter.