robin_hood::map overflow

[ihmin]

Dear developer,

I am using robin hood map (3.11.2) under MinGW. I got overflow error when insert some number as below log.

... Add 20686628 Add 20790466 Add 20950897 Add 20938052 Add 20481416 terminate called after throwing an instance of 'std::overflow_error' what(): robin_hood::map overflow

I have attach reproduce file. Please check it. :)

Thank you.

test.zip

[ktprime]

it does not be reproduced on my mac/clang. what's your mingw version?

[ktprime]

it can be reproduced on win10 with mingw/gcc or msvc++ 2019. i think it's the bad hash function hash_int. but std::hash is ok. I also test with very bad input hash function, robin-hood map also crash by overflow, maybe it's a bug or the design issuse(not happen with absl/emhash/tsl).

[ihmin]

@ktprime Actually, currently I used tsl temporarily because this bug. How can I fix this error?

[ktprime]

@ihmin I have no way to fix this bug, you can use my efficient hashmap(or the other phmap, absl, f14 ...) https://github.com/ktprime/emhash/blob/master/hash_table7.hpp, it's loadfactor can set to 0.999(always fast for insert). it's high optimized for key integer.

[ihmin]

@ktprime Thanks for let me know regarding other hashing table. How about speed and memory usage than robin?

[ktprime]

@ihmin performance depends on usecase(7 factors). you can get some benchmark results on my git https://github.com/ktprime/emhash. I also bench more than 5 thirdaprty program, my hash performance is very fastest for integer compared with others. it save more memory than other's with high load facror(1.0) or sizeof(key)%8 != sizeof(value)%8. you can run my bench program https://github.com/ktprime/emhash/blob/master/bench/ebench.cpp with command make ET=1 ABSL=1 EMH=5

[martinus]

Thank you for the reproducer! Can you give this version a try: https://raw.githubusercontent.com/martinus/robin-hood-hashing/master/src/include/robin_hood.h

[ktprime]

@martinus it's ok and no overflow now.

[ihmin]

@martinus Thanks for fix. all values stored to robin succesufully. 👍

[ihmin]

@ihmin performance depends on usecase(7 factors). you can get some benchmark results on my git https://github.com/ktprime/emhash. I also bench more than 5 thirdaprty program, my hash performance is very fastest for integer compared with others. it save more memory than other's with high load facror(1.0) or sizeof(key)%8 != sizeof(value)%8. you can run my bench program https://github.com/ktprime/emhash/blob/master/bench/ebench.cpp with command make ET=1 ABSL=1 EMH=5

Thanks for explain detailed. I will testing with emhash for performance compare with robin. 👍