U++ forum: Welcome to the forum

Status & Roadmap

Authors & License

Funding Ultimate++

Search on this site

Search in forums

Home » Community » Coffee corner » Map implementation

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Return to the default flat view

Create a new topic

Submit Reply

Re: Map implementation [message #51524 is a reply to message #51523]

Wed, 10 April 2019 11:07

mirek is currently offline

mirek
Messages: 14257
Registered: November 2005

Ultimate Member

Update: Upon further investigation... The proposed change is not perfect. Better solution:


inline dword FoldHash(dword h)
{
	return SwapEndian32(2833151717 * h);
}

Interestingly, in this particular case it runs slower. It took me a couple of hours to figure out why: It is cache issue. This much better FoldHash actually spreads hashes nicely through hash space (thus causing cache misses), while the previous one tended to put them close (cache hits). It had accidentally fixed this particular benchmark's collisions, but would probably fail in some other scenario.

Conclusion: At this number of elements, the benchmark is memory bound (for int), so well working hasmap will perform similary to std::set (actually, I think the benchmark favors std::set here, as sequential numbers will repeat the same path in the binary tree, which is more cache friendly).

Original FoldHash was too simplistic for ink keys, this new version should be harder to attack.

In future version of Index, I will try to randomize FoldHash (and other hashing ops).

Mirek

Report message to a moderator

Send a private message to this user

[Message index]

		Map implementation By: cbpporter on Thu, 21 March 2019 16:32
		Re: Map implementation By: mirek on Fri, 22 March 2019 07:18
		Re: Map implementation By: Novo on Wed, 27 March 2019 03:33
		Re: Map implementation By: cbpporter on Tue, 02 April 2019 14:13
		Re: Map implementation By: Novo on Tue, 02 April 2019 17:48
		Re: Map implementation By: Novo on Tue, 02 April 2019 18:39
		Re: Map implementation By: cbpporter on Mon, 08 April 2019 13:57
		Re: Map implementation By: mirek on Mon, 08 April 2019 22:37
		Re: Map implementation By: cbpporter on Tue, 09 April 2019 14:57
		Re: Map implementation By: mirek on Tue, 09 April 2019 17:16
		Re: Map implementation By: mirek on Wed, 10 April 2019 11:07
		Re: Map implementation By: cbpporter on Wed, 10 April 2019 11:39
		Re: Map implementation By: Novo on Wed, 10 April 2019 17:09
		Re: Map implementation By: mirek on Wed, 10 April 2019 17:37
		Re: Map implementation By: Novo on Sat, 13 April 2019 20:58
		Re: Map implementation By: Novo on Sat, 13 April 2019 21:07
		Re: Map implementation By: mirek on Sun, 14 April 2019 08:03
		Re: Map implementation By: Novo on Sun, 14 April 2019 18:55
		Re: Map implementation By: mirek on Sun, 14 April 2019 19:52
		Re: Map implementation By: mirek on Tue, 16 April 2019 12:38
		Re: Map implementation By: Novo on Tue, 16 April 2019 16:38
		Re: Map implementation By: mirek on Tue, 16 April 2019 19:33
		Re: Map implementation By: Novo on Tue, 16 April 2019 22:36
		Re: Map implementation By: Novo on Wed, 17 April 2019 05:40
		Re: Map implementation By: mirek on Wed, 17 April 2019 08:54
		Re: Map implementation By: Novo on Wed, 17 April 2019 16:13
		Re: Map implementation By: mirek on Wed, 17 April 2019 18:39
		Re: Map implementation By: mirek on Fri, 07 June 2019 13:58
		Re: Map implementation By: Novo on Tue, 25 June 2019 15:20
		Re: Map implementation By: mirek on Wed, 26 June 2019 12:07
		Re: Map implementation By: Novo on Mon, 01 July 2019 06:26
		Re: Map implementation By: mirek on Mon, 01 July 2019 17:53
		Re: Map implementation By: Novo on Sat, 13 April 2019 21:25
		Re: Map implementation By: Novo on Wed, 10 April 2019 16:13
		Re: Map implementation By: mirek on Wed, 10 April 2019 17:50
		Re: Map implementation By: Novo on Wed, 10 April 2019 16:48

Previous Topic:	[Skylark][witz] How would you do this
Next Topic:	[SOLVED]Sharing Ptr of object to dll

Goto Forum:

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

PDF

]

Current Time: Sat May 10 20:58:20 CEST 2025

Total time taken to generate the page: 0.02459 seconds