From: Eugene, OR, USA
|I've always promoted C++ as the ultimate game programming language, but recently I've been eating my words. Allow me to explain. I've been planning on writing an RPG that parses normal English expressions. In preparation, I wanted to find the fastest way to look up a word from an associative list so I can read in a word and quickly access related game data. I thought C++ / STL would be the fastest solution. So, I wrote a little program that loads a long list of words from a text file (about 110,000), puts them into an associative list and then does a bunch of random searches. On the C++ side, I used a "stdext::hash_map" and the "std::string" object. I thought I had found the fastest way until, after discussing the issue with HanClinto, a big C# and .NET proponent, I decided to do a comparison. Using SharpDevelop I created a similar program using a "Hashtable" and the "string" type. Both program ran so fast that I had to set the number of random searches to 1,000,000. Here is the output:
(C++ w/ STL - compiled with Visual C++ 2005 Express)
(C# compiled with .NET 1.1 in SharpDevelop)
C# wins on all counts. Both Han and I had fully expected C++ to be faster. I've emailed the code for both programs to Han, and he's going do the same test in Linux with GCC compiling the C++ code and Mono compiling the C# code.
As far as simplicity goes, the C++ code was slightly longer (a few lines) and the Hashtable in C# was a little simpler to implement than the stdext::hash_map.
Any thoughts on this?
From: Pacific Northwest
|Amen bro! You see the light. ;-)
It's possible a lot of the speed may be related to memory allocation which is actually faster in managed code than C++. I assume you are using ever-expanding hash tables and lists that grow as needed. Try creating everything with their correct size FIRST so there is no extra allocation necessary. That way you can remove memory allocation from the equation. Although there is still the memory allocation for each word read from the file. Which reminds me, perhaps file I/O is faster in .NET, and may explain the rather large time discrepancy in the two timings when reading in from the file. But that is pure speculation on my part.
I guess the larger and more interesting issue is with the retrieval time. Perhaps the C# Hashtable uses a faster mechanism to find an item. Also, try not to use a random search. Doing a sequential search through each item will force both programs to be running the same type of sequence of steps. The C# Hashtable may also be speedier at the expense of memory usage.
Also, I noticed the C# version read in ONE less word than the C++ one. That might really speed things up too. :-)
BTW, there seems to be a forum issue when the '#' symbol is in a subject. To post, I had to take the link/URL and change the "|NMB|" back to a "#" and then it worked. In fact, I needed to do the same thing to edit this message when I added this paragraph.
[This message has been edited by SSquared (edited May 30, 2006).]