This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

std::unordered_map and the % operator


Hi,

Firstly, thanks to all the developers out there for providing a
wonderful library.

I am curious about the present implementation of the hash table in
std::unordered_map.

Clearly we need to ensure that the key is in the range [0,
bucket_count) however, it seems to be that
a simple modulus is a huge trouble. In particular, profiling my code,
I can see that the processor stalls for quite some time on the
modulus. Of 20 second algorithm, five seconds is spent in calls to
find(). While at this juncture I am not particularly sure, my profile
report suggests that the vast majority of this time is spent waiting
on the modulus. On some machines a divide my take up to 24 cycles,
versus only 1 or 2 for a multiplication.

I am wondering if you maintainers would accept a specialization of
this type which supports replacing the modulus with a multiplication
by a so called magic number (e.g. the multiplicative inverse of the
bucket_size in Z_n for appropriate n).

In particular, this number can be recomputed whenever the bucket_size
changes and cached. It seems to me that this will be a performance win
in almost all cases. The only situation in which it might be bad is if
lots of rehashing is occurring. Further, the version of the standard
on my apple laptop seems to have a specialization which caches the
hash code. It stands to reason then that this bucket_size data could
also be computed and cached.

Best,
-rhl


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]