Perhaps a reader has a suggestion on how to write a better iterator than the one I knocked together for this tutorial, or better, has a way to update the StringMap for efficient interoperability with the STL?

thx.

I have retimed the code as well, just to be sure.

The fix to exception safety is actually pretty simple now that I think about it. We can replace malloc/free with new[] and delete[], since they will throw if the allocation fails. Whether or not the assignment of Data can throw doesn’t matter; one would expect the user to need to deal with a failure of assignment in the map, it’s not the place of the map to deal with it.

I’ve written a new post to help explain some of the characteristics of game code that non-game coders find hard to fathom. I don’t think it’s really fair to say our code is horrible or hacky!

http://meshula.net/wordpress/?p=185

Beauty is in the eye of the beholder, and what seem to some practitioners to be the most hideous code possible, to someone else can be an elegant rose. I must point out that a wood carver would never allow his knives to cut another material, yet for carving wood, his knives are the perfect instrument. Game code by and large is craft informed by engineering.

Incidentally, it wasn’t just the upper limit on capacity that concerned me with StringMap.

The exception-safety aspect did concern me. The fact that Mike claims that it “can’t throw exceptions” just goes to show how subtle exceptions can be, if a good C++ programmer can’t spot situations where it might happen. There’s the inOrder stuff that manipulates STL containers (which is safe in this case), there’s always the possibility that Data::operator=() might throw (which, again, is safe in this case, but it only takes a small refactor and instantly it’s not).

Dealing with error conditions is the biggie. Admittedly, it’s the original code’s fault that the return value of malloc() isn’t checked, but still, it’s a fault.

Alexey wrote: “It is common in game programming to use limited containers for performance reasons.”

I don’t think I’ll ever understand game programmers. They do the most horrible hacks that anyone else in any other area of high-performance computing wouldn’t even begin to consider.

I suspect it’s more often for deadline reasons than performance reasons, but don’t quote me on that.

Here’s the dictionary.txt file I used:

http://java.sun.com/docs/books/tutorial/collections/interfaces/examples/dictionary.txt

Here’s the timing code. I haven’t filled in a gcc version of the cycle timer. I would appreciate your timings with STLPort; I might imagine it to be much faster than the Dinkumware implementation Microsoft ships. Please also mention which compiler and settings you used.

Sorry for the screwball formatting, I need some kind of nice code display plugin…


class Cycles
{
public:
Cycles()
{
Reset();
}

// 273M
ct.Reset();
for (size_t i = 0; i < dictionary.size(); ++i)
{
int data;
std::map::iterator j = mapTest2.find(dictionary[i]);
}
ct.Sample();
printf("map, find, %15llu\n", ct.Total()/1000000L);
}
}

My goal in wrapping Bentley & Sedgewick’s code was to use it almost verbatim. It is well known code that works well and has a large body of documentation to go with it, and I didn’t really want to modify it for stylistic reasons. The only reason to wrap it was that as implemented you could have only one global tree, which is kind of useless. But wrapped into a class it became immediately useful.

In general, I would agree with you that simply slapping a class on C code is ugly, but I felt I was justified just this once

I’ll refer to this nice paper on the boost site on exception safety:

http://www.boost.org/community/exception_safety.html

Since the code I’ve posted can’t throw exceptions, I’ll assume you are referring to the notion of dealing reasonably with error conditions (which this code doesn’t, input checking would be an obvious improvement at little runtime burden), that resources aren’t leaked (it doesn’t, so that’s one positive), and that errors are reported to the user (they aren’t).

I’ll certainly agree with you that this is not production quality code; it’s meant to be illustrative of how a StringMap could take the place of a std::map with a string key.

I’m afraid I have to agree with you that the freearr mechanism they proposed is not the clearest thing ever; I had to read it slowly for the ah-hah! light to go on. The sheer lightness of it did impress me though, so I figured why mess with it? It works.

As Alexey says it is common to use limited custom containers for performance reasons. So while I would definitely adopt remedies to the points you mention in production code, I would also not go and add all the extra bits (like a remove method) that would make the code larger and less focussed on doing one thing very well.

PS. I seems the publishing system likes to eat some symbols, I’m pretty sure “if (bufn– == 0)” should really be “if (bufn–- == 0)”!

Most other high-performance C++ application areas wouldn’t stand for that. Is this common in games programming?

Anyway, some suggestions on how to make the C-style pool allocation work in C++.

First, I’d replace each pool with a lightweight object that owns the pool. Perhaps something like this:

struct Pool
{
Tnode* buf;
Pool() : buf(new Tnode[buffPoolGrowSize]) {}
~Pool() { delete[] buf; }
};

Another option is boost::scoped_array.

2. Replace freearr with a dynamic container of pools. Probably std::deque is the best option here, because it doesn’t do any copying.