ATL / WTL / STL

23-Oct-02 9:38

This is the code from Dinkumware STL hash_map. This is also the same code in VC++.NET hash_map class.

This function gets called for every lookup. I find that the incoming key is compared with the object bothways. I mean
The comp function returns true for greater than. So the comparison is:
if a not greater than b
if b not greater than a,
then both are equal, return value.

Why not test for equality directly than go for this method? Is there any specific reason? Now, the string comparison is done twice to check for equality. The code does not seem to be in the overridable part of the hash_map.

Question: Is there any work around to prevent the comparison from running twice?

Note: I checked the CMapStringToString in MFC and it does just one comparison.

<br />
iterator lower_bound(const key_type& _Keyval)<br />
{	<br />
// find leftmost not less than _Keyval in mutable hash table<br />
size_type _Bucket = _Hashval(_Keyval);<br />
iterator _Where;<br />
for (_Where = _Vec[_Bucket]; _Where != _Vec[_Bucket + 1]; ++_Where)<br />
	if (!this->comp(this->_Kfn(*_Where), _Keyval))<br />
		return (this->comp(_Keyval,<br />
			this->_Kfn(*_Where)) ? end() : _Where);<br />
		return (end());<br />
		}<br />

modified 29-Aug-18 21:01pm.

Tim Smith23-Oct-02 10:31

23-Oct-02 10:31

By maintaining a sorted hash chain, if the compare fails greater than then either this entry matches or there is no chance that any later entries in the chain will match.

STLPort uses a equal_to system for hash_maps. But even looking at STLPort, there is some stuff in hash_map that is a little silly because of the need to be very generic. It will only bite you if your key compares are expensive (i.e. string compares).

Which system is better? You can't say since both systems have advantages. For example, the Dink system will average (depth/2+1) for successful searches while STLPort will average (depth/2). However, if you have a system where you will have many misses, Dink system will average (depth/2+1) while STLPort will average (depth). However, since Dink is using a sort chain, that will slow down inserts.

Once again proving my point that if performance is important, the general solution isn't the best.

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

User 988524-Oct-02 8:21

24-Oct-02 8:21

How would it be if I implemented a hash map that has a tree based map as buckets to handle collisions? The bucket would be a vector. This way, the worst case performance is the tree based map + the hash calculation. But, if there are no collissions, only one comparison is needed.

Does this sound right to implement my own hash_map. I am very disappointed with this Dinkumware hash_map. The standard map gives better performance, even when there are no collissions. I have a requirement where inserts and searches are very, very frequent. CMapStringToPtr was much better than this Dink hash_map; but now the project cannot have MFC.

- Thomas

modified 29-Aug-18 21:01pm.

Tim Smith24-Oct-02 14:20

24-Oct-02 14:20

Could you use STLPort? It is starting to sound like their hash_map might work for you.

Are you recreating the hash map a lot? If not, then the auto-rehashing of STLPort's hash map would be a good feature. (For my specific needs, this one feature was a performance bottle neck)

Also, collisions don't have to be a bad thing. One of my most common speed improvements (other than removing the sometimes counter productive rehashing) is to try to make key compares very fast. For string based key compares I don't use strcmp. I store the length of string as part of the key. Thus prior to doing the actual byte compare of the string, I would compare then lengths. If they don't match, then the keys don't equal. If they do match you can use memcmp instead of strcmp for even more performance. If your keys are much more complicated than a simple string, then you can also use the computed hash value as a quick test. The important thing is to try to have a simple value that can act as a quick test to weed out the most possible slow key compares. This quick test should also be well distributed within the hash table.

Unfortunately, that speed improvement won't work for Dink's system since they want > instead of ==. If you decide to implement your own (but I would try STLPort first), I wouldn't over design it. Try a simple hash chain for collisions. Try a simple hash with a fixed width and a good quality hash generator. If you hash generator is good enough, your hash table doesn't even need to be sized by a prime. But primes work great for hash values based on such things as addresses. Try to improve your equality key test so that it is very fast. That is one thing I like about rolling your own simple hash map, you have total control over it and can design it specifically to meet your needs. For example, in my hash table for an atom table, I have the string stored in the same memory block as the rest of the hash support structure (which also means I used... MALLOC, oh horrors). This helps to prevent the CPU and L2 memory cache from having to access a ton of diverse pages. In my compiler's symbol table, I ended up storing everything including the hash in one long buffer. This allow me to quickly remove all local variables defined in a scope "{}" by restoring the hash table starting points and the size of the symbol table. 33 integer values copied with memcpy and one or a thousand local scope variables are removed in a flash. It is examples like this why I always preach that when appropriate people should never fear writing their own containers.

Ok, I am stopping now. I am starting to ramble. Smile | :)

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

Tim Smith24-Oct-02 14:29

24-Oct-02 14:29

Oh, and depending on the application, letting the hash table grow too wide can be counter productive. In the case of my compiler where I needed to save the hash state often, the optimal size was 256. But for overall performance, given that the symbol table search wasn't taking up much time, a hash width of 32 worked just fine (and my hash chains were getting 70+ entries deep Eek! | :eek:

). I attribute the high performance to that simple length optimization in the key compare. The symbol table hardly ever made any false compares. (In fact, I think I will go add a counter to test just that.) Smile | :)

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

Tim Smith24-Oct-02 14:41

24-Oct-02 14:41

Ok, here are some hard numbers from my compiler. This is with a symbol table where the hash is 32 entries wide. Each chain is known to average around 70 entries.

Total number of key compares: 58,028,872
Key compares rejected by hash/length test: 53,786,758
Slow key compares resulting in a match: 4,242,114
Slow key compares resulting in a failure: 0

As you can see, by testing the combination of the hash value and the string length, I was able to eliminate ALL false slow key compares.

Next I disabled the hash test for early key rejection. This resulted in 1,675,277 failed key compares.

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

User 988525-Oct-02 1:56

25-Oct-02 1:56

Thank you very much for the info. I am downloading STLPort now. Also, I will try the length and memcmp instead of the strcmp that I am using now, as you suggested.

Thank you once again. I will keep you posted on my adventures with the hash_map. Smile | :)

modified 29-Aug-18 21:01pm.

Joao Vaz25-Oct-02 6:10

Joao Vaz

25-Oct-02 6:10

Cool , always learning ,I love CP, I don't known very well the hash algorithms, do you known some good resource where it explains the basic terminology and optimizations on the algorithms like this one on maps, besides the normal computer science books ?

Cheers,Joao Vaz
And if your dream is to care for your family, to put food on the table, to provide them with an education and a good home, then maybe suffering through an endless, pointless, boring job will seem to have purpose. And you will realize how even a rock can change the world, simply by remaining obstinately stationary.-Shog9

Tim Smith25-Oct-02 7:16

25-Oct-02 7:16

No. I make this stuff up on the fly, test it, and then hope I am not talking out of my arse. WTF | :WTF:

(OMG, my secret is out.)

In all seriousness, that simple string optimization is from my work with the Forth language in the 80s. They had to deal with a wealth of symbols stored in a 4 wide hash table.

Darn it. I just was looking for a resource that I found last night that talked about a lot of hash optimizations. Can't seem to find the one I liked.

I did find this...

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html[^]

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

Joao Vaz25-Oct-02 7:48

Joao Vaz

25-Oct-02 7:48

Tim Smith wrote:
and then hope I am not talking out of my arse.

Experience, experience Wink | ;)

Tim Smith wrote:
Forth language in the 80s.

OMG | :OMG:

, I'm must admit that the 1st time that I've heard of Forth was here on CP when Valer Bocan posted his Forth compiler for .NET Blush | :O

Tim Smith wrote:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html[^]

Thanks, the article is nice and not too difficult to follow up Smile | :)

Cheers,Joao Vaz
And if your dream is to care for your family, to put food on the table, to provide them with an education and a good home, then maybe suffering through an endless, pointless, boring job will seem to have purpose. And you will realize how even a rock can change the world, simply by remaining obstinately stationary.-Shog9

Tim Smith25-Oct-02 8:38

25-Oct-02 8:38

One thing I noticed.

That article talked about rehashing to attempt to find an empty slot. When I say rehash, I mean using some heuristic to detect that the depth of the hash has become too large, thus triggering a resize of the hash table requiring all keys to be rehashed back into the larger table.

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

Joao Vaz25-Oct-02 8:56

Joao Vaz

25-Oct-02 8:56

Tim Smith wrote:
That article talked about rehashing to attempt to find an empty slot. When I say rehash, I mean using some heuristic to detect that the depth of the hash has become too large, thus triggering a resize of the hash table requiring all keys to be rehashed back into the larger table.

... and there will be light !!! Thanks, I didn't quite understand this part . Rose | [Rose]

I must understand better some algorithms , it makes a hell of a difference .

Cheers,Joao Vaz
And if your dream is to care for your family, to put food on the table, to provide them with an education and a good home, then maybe suffering through an endless, pointless, boring job will seem to have purpose. And you will realize how even a rock can change the world, simply by remaining obstinately stationary.-Shog9

User 988530-Oct-02 13:39

30-Oct-02 13:39

I did a performance analysis of my whole program and it turned out that hash_map was the least of my problems.

check this out
http://www.codeproject.com/script/comments/forums.asp?msg=323560&forumid=4486#xx323560xx

This is my hash_compare implementation. It works quite well. As you can see, I increased the starting bucket size to 512 and it works well. I am not at all concerned abut a little higher memory usage Big Grin | :-D

<code>// Template specialization for using DINKUMWARE STL hash_map classes
namespace std
{
	struct str_hash : public binary_function<size_t, char, size_t>
	{
		inline size_t operator() (const size_t hash, const char c)
		{
			return (hash<<5) + hash + c;
		}
	};

	template<> class hash_compare <string, less<string> >
	{
		less<string> comp;
		public:
			enum
			{						// parameters for hash table
				bucket_size = 4,	// 0 < bucket_size
				min_buckets = 512	// min_buckets = 2 ^^ N, 0 < N
			};	

		inline size_t operator()(const string& k) const
		{
			return accumulate(k.begin(), k.end(), 0, str_hash() );
		}

		inline bool operator()(const string& k1, const string& k2) const
		{
			return k1 > k2;
		}
	};
}</code>

modified 29-Aug-18 21:01pm.

Tim Smith30-Oct-02 14:49

30-Oct-02 14:49

LOL, been there done that.

I love Vtune since it helps me to avoid thinking the wrong thing is bottle neck. I can not recomend Vtune enough. (Even though Intel's support sucks really bad.)

I have to admit that I was a tiny bit skeptical that the extra Dink compare would have made that much of a difference. Especially since the extra compare was there to help avoid running down the whole chain in the case of a failure to match.

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

User 988530-Oct-02 16:09

30-Oct-02 16:09

i could not suspect a member variable in a class causing such a problem, until I profiled it. Big Grin | :-D

Thomas

modified 29-Aug-18 21:01pm.

xstring info

Senkwe Chanda23-Oct-02 0:38

Senkwe Chanda

23-Oct-02 0:38

Hi guys, I'm in a situation where my code (a steaming mass of it) makes heavy use of stl [strings]. I now need to convert my code so that it's fully unicode compliant. Out of curiosity I simply exchanged wstring for string and included [xstring] and recompiled. So there's now a million or so compiler errors being spewed out. That was expected, but whats the best way to go about performing such a conversion? I've noticed for example that the "==" operator doesn't seem to be supported by stl's unicode string class. I expect there to be many more issues as well.

If you know of a good site I can visit on the issue (I just want to get it over with pretty quickly) please supply a url. Currently, google spits out everything BUT discussions on stl unicode support.

Thanks guys!!

Senkwe

ASP.NET can never fail as working with it is like fitting bras to supermodels - it's one pleasure after the next - David Wulff

Re: xstring info

Senkwe Chanda23-Oct-02 1:35

Senkwe Chanda

23-Oct-02 1:35

Ok, scratch that, MSDN came to my rescue (surprisingly). I was wrong on so many levels.

Cheers

ASP.NET can never fail as working with it is like fitting bras to supermodels - it's one pleasure after the next - David Wulff

Re: xstring info

Tim Smith23-Oct-02 2:38