|
I'm benchmarking some algorithm implementations and comparing different approaches and I got some results that got me thinking about CMap's hash table.
I've always used CMap with string keys and never gave the default hash function much thought outside of making sure my hash table size was roughly 20% larger than the number of objects planned to store, and that the size was a prime number as some documentation/literature recommends.
I'm playing with integer keys and my lookup times are varying enough with large samples to get me thinking that I might be doing something wrong. (I'm populating a CMap with 64 key/values and performing 50,000,000 lookups while using a performance counter. I'm comparing lookups for each of the items placed in the map)
My questions are, when using integer keys, should I expect large fluctuations in lookup time? Is my goal to set up the lookup table size to the most keys used or the highest key value? Or is it generally frowned upon to use integer keys with maps? (I understand that the hash function does this to strings anyways, but is it somehow inefficient to use integers outright?)
Thanks
-- modified at 16:57 Tuesday 22nd August, 2006
A sequential search on an array with these elements in it is getting better average times. Do I need more elements in the CMap to properly benchmark it?
I also found it is acting like there are collision in the hash table. The lookup times seem to decrease as I increment through the keys toward the center. I found something by Ivor Horton that says the default hash simply bit shifts my key 4 to the left...
|
|
|
|
|
Sounds fishy.. hash maps with integer keys are about as fast as it gets. The hash generator is basically just modulo some prime number. Have you tried std::hash_map?
--
Touch eyeballs to screen for cheap laser surgery
|
|
|
|
|
I think I found out why I'm chasing my tail. Apparently the HashKey function does a bit shift to the right 4 places by default for primitive types. Since I was using such a small sample for my elements (64), most of the integer falls off the right side during the bitshift leaving me with a tiny integer and numerous key collisions invoking the subsequent linear searches for a majority of my elements.
This would explain most of the behaviour I was seeing.
As a quick sobriety check, I bit shifted my keys to the left before insertion and before each lookup and my benchmarks are much more consistent now. I'm not sure what to override the function with as I'm not really knowledgeable of hash functions but at least I know what I'm fighting at this point.
Jörgen Sigvardsson wrote: Have you tried std::hash_map?
This is on my todo list one of these years. I've been finding it hard to get the time to rid myself of MFC.
Thanks for the reply.
|
|
|
|
|
Have you found out anything else?
Does it makes sense to call the InitHashTable function to increase the hash table size? The default number of buckets is 17, but I am adding over 20,000 (yes, 20 THOUSAND) items to the hash map. I use VTune and it says that the CMapWordToOb::GetAssocAt is using roughly 30% of my CPU time!
Not that I can enable any debugging or tracing within the MFC module itself, but I suspect I have a lot of collisions and the resultant linear searching 
Any sufficiently gross incompetence is nearly indistinguishable from malice.
|
|
|
|
|
Yes. You should make the lookup table roughly 20% larger than the expected maximum number of entries. Of course, for very large maps, memory considerations may make smaller tables practical if the resultant linear searches are expected to be short. In your case 20000 values of type WORD seems reasonable so I would follow the above rule and make the table 120% of 20000 which is 24000. This number should be prime so 24001 would suffice.
However, if your keys values ARE the integers between 0 and 20000 or some sequence of consecutive numbers then an array would suffice since no hashing would be required to determine the index or placement.
Hope that helps,
Take care
|
|
|
|
|
Thanks for the helpful information.
Increasing the hash table size to 5003 was a significant performance improvement over leaving it at the default size of 17 
Any sufficiently gross incompetence is nearly indistinguishable from malice.
|
|
|
|
|
At my work, we have a third party software that we would like to modify to better suit our production needs.
I searched through the third party's DLL and found the function that applies to what we need to modify.
Not sure if its even function hooks I want to deal with...
If it is possible, I would just like to modify the array which the function gets its values from, if not, then I would like to modify a functions parameters.
Anyone know how to do this? or can point me in the right direction? I havent programmed in awhile, but by doing this we can run more efficiently so I think it would be worth it.
Thanks for any help.
|
|
|
|
|
Why the drastic approach of hooking the function calls? Is it not possible to just call the functions differently, or is it not possible for you to recompile the DLL clients? 
--
Based on a True Story
|
|
|
|
|
Sounds like there are 2 things to consider. A) injecting your code into the other process (assuming the 3rd party code is in its own process), and then B) intercepting/hooking the DLL calls.
A) to do this, you can create your own DLL containing the code you want to inject. then set a windows hook, specifying your DLL and the function. windows will then load your DLL into all applicable processes and you can then check to see if its the process of interest, and then proceed to B to intercept the DLL calls
B) intercepting DLL calls in your process is a bit tricky. "Programming Applications for Microsoft Windows" by Jeffrey Richter goes into this in depth and he provides a class which encapsulates all the hard work for you. With his class, its a few lines of code to inject your own function in place of a specified DLL call (could be an OS API, or in your case a 3rd party DLL). your function can do its processing and then call the original using his class as well. I was surprised at how easy it was to do, given his class.
granted, the other option is to go bug the 3rd party and tell them to fix their code  but that wouldn't be nearly as fun!
|
|
|
|
|
I am trying to indicate that class CSentenceAr COULD throw the same object as an exception:
SentenceAr.h
class CSentenceAr
{
...
protected:
bool readFile(char strFileToRead[MAX_SENTENCE_LENGTH + 1]) throw (CSentenceAr);
// #1 (see below)
...
};
SentenceAr.cpp
bool CSentenceAr::readFile(char strFileToRead[MAX_FILENAME_LENGTH])
{
char strLine[MAX_SENTENCE_LENGTH + 1];
fstream fileToRead(strFileToRead,ios::in);
if (ios::good != false)
...
return true;
}
else
{ //Error: file cannot be read
throw (CSentenceAr);
// #2 (see below)
return false;
}
fileToRead.close();
}
#1: \SentenceAr.h(21): warning C4290: C++ exception specification ignored except to indicate a function is not __declspec(nothrow)
#2: \SentenceAr.cpp(43): error C2059: syntax error : ';'
Jon
|
|
|
|
|
jon_80 wrote: bool readFile(char strFileToRead[MAX_SENTENCE_LENGTH + 1]) throw (CSentenceAr);
Shouldn't this be:
bool readFile(char strFileToRead[MAX_SENTENCE_LENGTH + 1]) { throw (CSentenceAr); }
"Money talks. When my money starts to talk, I get a bill to shut it up." - Frank
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
I meant to declare that the function can throw the exception, doesn't this syntax indicate that this is what the function does?
I tried it anyway just in case and it doesn't compile.
Jon
|
|
|
|
|
jon_80 wrote: I meant to declare that the function can throw the exception, doesn't this syntax indicate that this is what the function does?
Yes, it does. Though, it is not really necessary (it is more for readability than anything else). That said, attaching throw () to the end of a method definition declares that it will NOT throw.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
jon_80 wrote: I meant to declare that the function can throw the exception, doesn't this syntax indicate that this is what the function does?
I've not ever seen throw() used in a class definition like that.
jon_80 wrote: I tried it anyway just in case and it doesn't compile.
My bad. I did not notice that the method already had a body.
"Money talks. When my money starts to talk, I get a bill to shut it up." - Frank
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
DavidCrow wrote: I've not ever seen throw() used in a class definition like that.
You probably have, you just never realized it before. Many of the MFC classes have definitions that use it, but it is hidden behind a #define macro.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: ...but it is hidden behind a #define macro.
I'm looking in afxdb.h at CRecordset::Open() but I don't see any mention of an exception. How is this done?
"Money talks. When my money starts to talk, I get a bill to shut it up." - Frank
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
I'm on a Linux box at the moment, so I can't look it up. However, I do remember CFile having a constructor that throws an exception. If you look at the header file for it, you should see something at the end of the defintion that looks like _THROW() (which is #define'd as throw(...)). There is also a #define for _NOTHROW() (which is #define'd as throw()). The first means the function will throw an exception. The latter means the function cannot throw an exception (you will actually get a compiler error if you throw an exception from a function declared with the throw() directive.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: However, I do remember CFile having a constructor that throws an exception. If you look at the header file for it, you should see something at the end of the defintion that looks like _THROW() (which is #define'd as throw(...)).
From afx.h, I found:
CFile();
CFile(int hFile);
CFile(LPCTSTR lpszFileName, UINT nOpenFlags);
"Money talks. When my money starts to talk, I get a bill to shut it up." - Frank
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
DavidCrow wrote: CFile(LPCTSTR lpszFileName, UINT nOpenFlags);
That is the one that throws the exception. I thought it had the macro beside it, but it might be on the Open method. Either way, if you search the MFC include directories for _THROW, you should see it.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: That is the one that throws the exception.
True, but I see no way of knowing this without looking at the constructor's implementation.
Zac Howland wrote: I thought it had the macro beside it, but it might be on the Open method.
Neither one. I don't find "throw" in any class definition.
"Money talks. When my money starts to talk, I get a bill to shut it up." - Frank
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
DavidCrow wrote: True, but I see no way of knowing this without looking at the constructor's implementation.
That is in the src directory ... can't remember the filename off the top of my head, but it isn't too difficult to search for.
DavidCrow wrote: Neither one. I don't find "throw" in any class definition.
I know I've seen it in some of the MFC definitions before, but when I do a search on my VS.Net 2003, I find it in the implementation of STL:
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xstddef(26): #define _THROW0() throw ()
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xstddef(27): #define _THROW1(x) throw (...)
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xstddef(28): #define _THROW(x, y) throw x(y)
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xstddef(39): #define _THROW0()
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xstddef(40): #define _THROW1(x)
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xstddef(41): #define _THROW(x, y) x(y)._Raise()
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xtree(592): _THROW(out_of_range, "invalid map/set<T> iterator");
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xtree(913): _THROW(length_error, "map/set<T> too long");
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xutility(866): istreambuf_iterator(streambuf_type *_Sb = 0) _THROW0()
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xutility(871): istreambuf_iterator(istream_type& _Istr) _THROW0()
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xutility(969): ostreambuf_iterator(streambuf_type *_Sb) _THROW0()
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xutility(974): ostreambuf_iterator(ostream_type& _Ostr) _THROW0()
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\xutility(1003): bool failed() const _THROW0()
Among a host of others.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
jon_80 wrote: bool readFile(char strFileToRead[MAX_SENTENCE_LENGTH + 1]) throw (CSentenceAr);
Microsoft's compiler doesn't distinguish between a specificed throw and a generic one. That is, what you have is equivalent to writing:
bool readFile(char strFileToRead[MAX_SENTENCE_LENTH + 1]) throw (...);
As a side note, you should NOT use the same class you are throwing from as the exception type you are throwing. It would then be possible to end up with an infinite throw problem -- which is very very bad.
Unless you have to define your own exception class for an assignment, you should use the standard exception class, or use MFC's CException class.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: Unless you have to define your own exception class for an assignment, you should use the standard exception class, or use MFC's CException class.
Or inherits a class from that. It allows you to add more flexibility.
|
|
|
|
|
True ... forgot to mention that as well. However, you rarely need any more information than what those classes already support, and even the other STL exceptions are mostly just blank classes derived from std::exception.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Oh ic. To be honest I wish I could use MFC, but the syllabus covers basic C++ and we have to abide by it for the major part, because I'm still at the lower end of the learning curve 
MFC has its own exceptions and they resemble so much the exceptions that I'm used to with VB for example.
hehe... I think that if I decide to become a software engineer and use C++, I'll need more than silicone
Jon
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
