search

levitation / sparsehash

Automatically exported from code.google.com/p/sparsehash
BSD 3-Clause "New" or "Revised" License
0 stars 0 forks source link

Performance problem when hashed by pointers #80

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
What steps will reproduce the problem?

dense_hash_set<char*> set;
char tmp[2];
set.insert(tmp);
set.insert(tmp + 1);

What is the expected output? What do you see instead?

hasher returns same hash for tmp and tmp + 1, so it's a collision and 
performance drop

What version of the product are you using? On what operating system?

1.12
OS doesn't matter

Please provide any additional information below.

The problem is in hashtable-common.h:192

Since char is 1 byte it's wrong to assume that any pointers differ on 
sizeof(void*).

Proper code is:
return hash / (sizeof(HashKey) < sizeof(void*) ? sizeof(HashKey) : 
sizeof(void*));

The condition is known at compile time, so it will be optimized by compiler.

Original issue reported on code.google.com by bulovya...@gmail.com on 20 Jan 2012 at 11:54

GoogleCodeExporter commented 9 years ago 
This is a tough issue, and one I struggled with when making the pointer 
optimization.  In the common case, dense_hash_set<char*> is hashing different 
char*'s allocated separately.  In that case, dividing by sizeof(void*) is the 
right thing to do and will speed things up.

In the case where you are hashing into the same string, as in your example, 
then dividing by sizeof(void*) will do the wrong thing, and slow things down.

Did you have a real case where this is happening, that this bit you?  I don't 
expect to see these problems very often (if at all) in practice, but my 
expectations could be mistaken.

Original comment by csilv...@gmail.com on 26 Jan 2012 at 1:31

GoogleCodeExporter commented 9 years ago 
No real case, just an observation.
It's not about char only, also short* and int* (on 64 bit).
Not a big issue, of course. It's up to you. Thanks.

Original comment by bulovya...@gmail.com on 26 Jan 2012 at 9:26

GoogleCodeExporter commented 9 years ago 
OK, good to know.  I'm going to close the bug for now, but if people start 
seeing this in real applications, it would be good to reopen at that time.

Original comment by csilv...@gmail.com on 26 Jan 2012 at 7:50