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 programs 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)
Reading in word list.
Done reading in word list.
There were 118567 words in the list.
That took 203 milliseconds.
Now adding words to map. (std::hash_map)
Done.
That took 250 milliseconds.
Getting 1,000,000 strings from map. (random searches)
Done.
That took 922 milliseconds.
Press enter to continue.

(C# compiled with .NET 1.1 in SharpDevelop)
Text search test.
Reading in words to ArrayList.
Done.
There were 118566 words in the file.
That took 78 milliseconds.
Putting words into Hashtable.
Done.
That took 141 milliseconds.
Getting 1,000,000 strings from Hashtable. (random searches)
Done.
That took 734 milliseconds.

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?

------------------
+---------+
|steveth45|
+---------+

[This message has been edited by steveth45 (edited May 30, 2006).]

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 optimization 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. :-)

------------------
In the stock market, you must buy high and sell low...Wait! That's not right!
--------------
Yes, I can be intelligent at times!!

I found this link showing comparison execution time/memory usage of various languages doing various operations. What's cool is if you click on a operation, then click on the name of one of the languages listed, it will show you the code they ran for the operation..cool, so you could use their example code to do your own check I guess.

http://dada.perl.it/shootout/

This link has a nice summary of different operation performances with
Java, C#, C++. He talks briefly about the interesting Hash results as well

http://www.tommti-systems.de/go.html?http://www.tommti-systems.de/main-Dateien/reviews/languages/benchmarks.html

I got the cpp file pretty far, but then I got this error:
/usr/lib/gcc/i386-redhat-linux/3.4.5/../../../../include/c++/3.4.5/ext/hashtable.h:518:
error: no match for call to `(const __gnu_cxx::hash<std::string> )
(const std::basic_string<char, std::char_traits<char>,
std::allocator<char> >&)'

I tried fixing it the way this guy mentioned:
http://gcc.gnu.org/ml/libstdc++/2002-04/msg00107.html
...but it didn't work -- it only gave me many more pages of errors, things like:

/tmp/ccMHLAJh.o(.gnu.linkonce.t._ZN9__gnu_cxx13new_allocatorINS_15_Hashtable_nodeISt4pairIKSsSsEEEE10deallocateEPS5_j+0xd):
In function `__gnu_cxx::new_allocator<__gnu_cxx::_Hashtable_node<std: air<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > const,
std::basic_string<char, std::char_traits<char>, std::allocator<char> >
> > >::deallocate(__gnu_cxx::_Hashtable_node<std: air<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > const,
std::basic_string<char, std::char_traits<char>, std::allocator<char> >
> >*, unsigned int)':
: undefined reference to `operator delete(void*)'
/tmp/ccMHLAJh.o(.gnu.linkonce.t._ZN9__gnu_cxx13new_allocatorINS_15_Hashtable_nodeISt4pairIKSsSsEEEE8allocateEjPKv+0x17):
In function '__gnu_cxx::new_allocator<__gnu_cxx::_Hashtable_node<std: air<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > const,
std::basic_string<char, std::char_traits<char>, std::allocator<char> >
> > >::allocate(unsigned int, void const*)':
: undefined reference to `operator new(unsigned int)'
/tmp/ccMHLAJh.o(.gnu.linkonce.t._ZN9__gnu_cxx13new_allocatorINS_15_Hashtable_nodeISt4pairIKSsSsEEEE10deallocateEPS5_j+0xd):
In function `__gnu_cxx::new_allocator<__gnu_cxx::_Hashtable_node<std: air<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > const,
std::basic_string<char, std::char_traits<char>, std::allocator<char> >
> > >::deallocate(__gnu_cxx::_Hashtable_node<std: air<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > const,
std::basic_string<char, std::char_traits<char>, std::allocator<char> >
> >*, unsigned int)':
: undefined reference to `operator delete(void*)'
/tmp/ccMHLAJh.o(.gnu.linkonce.t._ZN9__gnu_cxx13new_allocatorINS_15_Hashtable_nodeISt4pairIKSsSsEEEE8allocateEjPKv+0x17):
In function `__gnu_cxx::new_allocator<__gnu_cxx::_Hashtable_node<std: air<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > const,
std::basic_string<char, std::char_traits<char>, std::allocator<char> >
> > >::allocate(unsigned int, void const*)':
: undefined reference to `operator new(unsigned int)'

And loads of other goodness. That's only 2 lines from it! There were
pages and pages of those.

Also found a link to a bug about it in GCC:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13342

"RESOLVED WONTFIX" :-\

So looks like one would have to write their own hashing algorithm for
that data type or something, I don't remember enough about CPP at this
point to move forward on it.

However, the csharp stuff worked great! On my Athlon 1800+ w/ 512
megs of RAM running CentOS 4 and compiling with Mono:

[clint@clintherron CSharpCPlusPlusTest]$ mono csharptest.exe Text search test. Reading in words to ArrayList. Done. There were 118566 words in the file. That took 291 milliseconds. Putting words into Hashtable. Done. That took 255 milliseconds. Getting 1,000,000 strings from Hashtable. Done. That took 989 milliseconds.

On the same machine running Windows XP Pro compiled with Visual Studio
2005 Express:

D:\Documents and Settings\Clint\My Documents\Visual Studio 2005\Projects\csharptest\csharptest\bin\Release>csharptest.exe Text search test. Reading in words to ArrayList. Done. There were 118566 words in the file. That took 47 milliseconds. Putting words into Hashtable. Done. That took 203 milliseconds. Getting 1,000,000 strings from Hashtable. Done. That took 937 milliseconds.

So as expected, Linux is a little bit slower, but not *too* much so. The part where it really loses is in the file access bit though, which kindof surprises me.

I'd still be interested in seeing how well C++ did, but at least we've got a
Linux/Windows comparison of Steve's code.

[This message has been edited by HanClinto (edited May 31, 2006).]

He said something similar to SSquared in that managed languages handle memory better. He didn't emphasize the allocation as much as the deallocation, because managed languages hold off deallocating memory until they do their lump garbage collection which can be faster than just nickle and diming with a bunch of little deallocations.

He also said that the file read time discrepancy between Linux and Windows is likely because my Linux install is using the default Linux file access configuration (which it is). He said that Linux comes with default "slow but safe" hard drive access parameters. He also pointed me to an article on the subject that he said was 6 years old but still relevant. I imagine that Windows does some of this access optimization automatically, and now I'm kindof curious to know how well Linux would do if I ran hdparm and optimized my settings.

Cheers!

--clint

It was pretty cool to see the Linux vs. Windows results HanClinto.

For an absolutely fascinating read (at least I think so) on .NET's garbage collection, read the following: http://msdn.microsoft.com/msdnmag/issues/1100/gci/

The information pertaining to memory allocation speed is right at the top in the section titled "Resource Allocation".

Keep in mind, this is specific to Microsoft's CLR. This is NOT the same as what Java uses. Unfortunately, I do not remember the exact details of Java's GC implementation, but I do recall it being different. I just wouldn't want people thinking if they've read one article on GC, then it is the one and only way to do it.

C# has the fastest hashmap but slow matrix multiply and nested loops.

------------------
2Co 7:10 For godly sorrow worketh repentance to salvation not to be repented of: but the sorrow of the world worketh death.

[VoHW] (Help needed) [Blog] - Truedisciple (mp3)

[This message has been edited by jari (edited May 31, 2006).]

------------------
+---------+
|steveth45|
+---------+

quote:

---

Originally posted by steveth45:
I'm impressed with Mono's performance. That validates the use of C# as a cross-platform game development language.

---

One thing that especially impressed me about C# during this test Steve was that with even a fairly small and simple C++ application like this test that you wrote, I still had to make a fair number of changes to get it to compile under Linux (and I never quite got it).

For C#, I just copy/pasted and it worked flawlessly under Linux and Windows first time (well, second time -- the first time I forgot to put the word file in the directory).

That ease-of-use is wonderful. No ./configure -- no hokey makefiles, no gcc version discrepancies -- just compile and run.

It's for reasons like that that interpreted languages have my vote for cross-platform game development all the way. I totally agree about the rendering engine -- let it be written in C++ for performance (like how Irrlicht, Torque and pyGame do it), but I never want to go back to writing gameplay code in C++.

--clint

quote:

---

Originally posted by coolj:
Does it appear to you that memory usage for c# is 4x to 10x higher than c and c++? That could be a significant factor. However maybe this is due to .net being loaded. I don't know.

---

That doesn't surprise me at all. I agree with you -- I would also guess it's largely due to the overhead of the runtime.

But my desktop has 512 megs of ram, and my laptop has a gig -- memory's not an issue for me. Speed is important -- not performance so much, but mainly speed of development. That's why I like C# -- I can just operate so much more quickly than in C++.

--clint

I was actually thinking about writing libraries in C++ for game engine side of things and then using the libraries in C# as I could do some rapid application development (GUIs) and such in C# much faster then in C++... I will definately do that now, as it looks like C# isn't as silly of an idea anymore :P

Great work guys, hope others also start looking into C#, it's great especially for getting apps done, but seems a bit more flexable then VB... could just be me :P

------------------
"But it is God who judges: He brings one down, he exalts another." - Psalm 75:7

So here's the output from the c++ run on Linux:

[clint@clintherron CSharpCPlusPlusTest]$ ./a.out Reading in word list. Done reading in word list. There were 118567 words in the list. That took 140 milliseconds. Now adding words to map. Done. That took 340 milliseconds. Getting 1000000 strings from map. Done. That took 1590 milliseconds. Press enter to continue.

And another run of the c# one for good measure.

[clint@clintherron CSharpCPlusPlusTest]$ mono csharptest.exe Text search test. Reading in words to ArrayList. Done. There were 118566 words in the file. That took 261 milliseconds. Putting words into Hashtable. Done. That took 234 milliseconds. Getting 1,000,000 strings from Hashtable. Done. That took 992 milliseconds.

So I'm glad we've got the comparison now for Linux. Fun stuff!

--clint

Try adding the following to your c++ file, and see if you get any performance improvement:

// ** new compare function ** //

struct new_comp
{
enum
{
bucket_size = 1,
min_buckets = 65536};

size_t operator()(const char *s1) const
{
const unsigned char *p = (const unsigned char *)s1;
size_t hashval = 0;

while (*p != '\0')
hashval = hashval * 37 + *p++;
return (hashval);
}

bool operator()(const char *s1, const char *s2) const
{
return (strcmp(s1, s2) < 0);
}
};

// *** example usage*** //

int main()
{
hash_map<const char *, int, new_comp> mymap;
}

[This message has been edited by coolj (edited June 01, 2006).]

Coolj, We are using std::string, not const char*, but it may work with minor tweaking because std::string is basically a wrapper for char*.

------------------
+---------+
|steveth45|
+---------+

Here it is:

struct new_comp { enum { bucket_size = 1, //min_buckets = 65536 min_buckets = 131072 }; size_t operator()(std::string s1) const { const unsigned char *p = (unsigned char *)s1.c_str(); size_t hashval = 0; while (*p != '\0') hashval = hashval * 37 + *p++; return (hashval); } bool operator()(std::string s1, std::string s2) const { //return (strcmp(s1, s2) < 0); return s1 < s2; } }; // use: stdext::hash_map<string, string, new_comp>

It is just a little slower than the default implementation in VC++. It did the search in 969 ms instead of 922 ms. It did work, though, and it may give Han a significant speed boost if the slowness of the G++ implementation is due to an inefficient algorithm for larger maps.

------------------
+---------+
|steveth45|
+---------+

I did notice you change min_buckets from 65536. It suppose to be a power of 2....oh well, I doubt it would matter much!

------------------
+---------+
|steveth45|
+---------+

STL (standard template libary) was not designed for speed, but for flexibilty. C++ is 10 times out of 10 faster than c#. Why?? It's how many layers of interfaces you have to go through to get at the hardware. C# has more than c++.

Try the same test, write your data structures to deal with the string search, and see what your results are.

------------------
"Give me chastity and continence, but not just now." Saint Augustine, ca 410 AD.

I found it cool that they mentioned the Reality engine way back then, and that's the same engine that Xcrucifix and Boanerges are using to develop their Christian games now. Very cool.

--clint

------------------
+---------+
|steveth45|
+---------+

quote:

---

Originally posted by steveth45:
I did a quick test of this, and by changing the C++ code to not copy around strings each loop but use references instead, it ran significantly faster.

---

Interesting, Steve -- how much faster? Faster than C#?

--clint

quote:

---

Originally posted by HanClinto:
Interesting, Steve -- how much faster? Faster than C#?

--clint

---

Not quite. The cpp code takes 828 ms now, instead of 922. C# is still faster for me at 734 ms. But it's within spittin' distance.

------------------
+---------+
|steveth45|
+---------+

------------------
All Your Base Are Belong To Us!!! chown -r us ./base
"After three days without programming, life becomes meaningless.'' -- Tao of Programming Book 2

"Oh, bother," said the Borg. "We've assimilated Pooh."

"Socialism works great... if there are no people involved." -- Pastor David Ginter, Union Church of Guatemala.

My Programming and Hacker/Geek related Blog

/* * Created by steveth45 * Date: 5/29/2006 */ using System; using System.IO; using System.Collections; using System.Collections.Specialized; namespace cs_word_search { class MainClass { public static void Main(string[] args) { Console.WriteLine("Text search test."); if(!File.Exists("ospd.txt")) { Console.WriteLine("File not found!"); return; } ArrayList vWords = new ArrayList(); object[] vWords_2; Hashtable slWords = new Hashtable(); int start_time; int end_time; using (StreamReader sr = File.OpenText("ospd.txt")) { string s = ""; Console.WriteLine("Reading in words to ArrayList."); start_time = Environment.TickCount; while ((s = sr.ReadLine()) != null) { vWords.Add(s); } end_time = Environment.TickCount; Console.WriteLine("Done."); Console.WriteLine("There were " + vWords.Count.ToString() + " words in the file."); Console.WriteLine("That took " + (end_time - start_time).ToString() + " milliseconds."); } vWords_2 = vWords.ToArray(); Console.WriteLine("Putting words into Hashtable."); start_time = Environment.TickCount; foreach(string i in vWords) { if(!slWords.ContainsKey(i)) // This is here because... { string val = i + "-"; slWords.Add(i, val); // .Add() throws an exception on identical keys } } end_time = Environment.TickCount; Console.WriteLine("Done."); Console.WriteLine("That took " + (end_time - start_time).ToString() + " milliseconds."); Console.WriteLine("Getting 1,000,000 strings from Hashtable."); string temp; int it = 0; int cWords = vWords_2.Length; Random numberGen = new Random(); start_time = Environment.TickCount; while(it < 1000000) { string lookup = (string)vWords_2[numberGen.Next()%cWords]; temp = (string)slWords[lookup]; // if(temp != null) // Uncomment this section to verify the correct values are found. // { // if(!temp.Equals(lookup+"-")) // Console.WriteLine("Wrong word returned!"); // } it++; } end_time = Environment.TickCount; Console.WriteLine("Done."); Console.WriteLine("That took " + (end_time - start_time).ToString() + " milliseconds."); } } }

// cpp_word_search.cpp // created by steveth45 // #include <iostream> #include <fstream> #include <string> #include <vector> #include <hash_map> #include <time.h> using namespace std; //#define MY_HASH stdext::hash_map<string, string, new_comp> #define MY_HASH stdext::hash_map<string, string> // ** new compare function ** // struct new_comp { enum { bucket_size = 1, min_buckets = 131072 }; size_t operator()(std::string s1) const { const unsigned char *p = (unsigned char *)s1.c_str(); size_t hashval = 0; while (*p != '\0') hashval = hashval * 31 + *p++; return (hashval); } bool operator()(std::string s1, std::string s2) const { //return (strcmp(s1, s2) < 0); return s1 < s2; } }; string find_string(MY_HASH& a_map, string& a_string) { MY_HASH::iterator it; it = a_map.find(a_string); if(it != a_map.end()) return (*it).second; else return ""; } int main(int argc, char * argv[]) { string line; ifstream wordlist; vector<string> vWords; vector<string> vWords_2; MY_HASH mWords; srand(time(NULL)); wordlist.open("ospd.txt"); if(!wordlist.is_open()) return 1; cout << "Reading in word list." << endl; unsigned int start_time = clock(); while (! wordlist.eof()) { getline (wordlist,line); vWords.push_back(line); } unsigned int end_time = clock(); cout << "Done reading in word list." << endl; cout << "There were " << vWords.size() << " words in the list." << endl; cout << "That took " << (end_time - start_time) * CLK_TCK / 1000 << " milliseconds." << endl; wordlist.close(); vWords_2 = vWords; cout << "Now adding words to map." << endl; start_time = clock(); vector<string>::iterator itvw = vWords.begin(); while(itvw != vWords.end()) { mWords[*itvw] = *itvw + "-"; itvw++; } end_time = clock(); cout << "Done." << endl; cout << "That took " << (end_time - start_time) * CLK_TCK / 1000 << " milliseconds." << endl; cout << "Getting 1000000 strings from map." << endl; int i = 0; int cWords = vWords_2.size(); string temp; start_time = clock(); while(i < 1000000) { //string lookup = vWords_2[rand()%cWords]; //temp = find_string(mWords, lookup); find_string(mWords, vWords_2[rand()%cWords]); //if(temp.compare(lookup + "-")!=0) // Uncomment this section to verify the correct values are found. // cout << "Wrong word returned!"; i++; } end_time = clock(); cout << "Done." << endl; cout << "That took " << (end_time - start_time) * CLK_TCK / 1000 << " milliseconds." << endl; cout << "Press enter to continue." << endl; getchar(); return 0; }

------------------
+---------+
|steveth45|
+---------+