3 ms·

No one thinks about resizing hash tables...except for any high-frequency trading firm worth its salt. And probably several game companies. I'm sure there are ot

by jzwinck 14y ago

No one thinks about resizing hash tables...except for any high-frequency trading firm worth its salt. And probably several game companies. I'm sure there are others. It gets weirder when we talk about C++ in particular: did you know that thanks to a standards committee decision, erase by iterator in a typical C++ TR1 hash set or map is O(n)? Erase by key actually has better performance despite the extra lookup. People do think about these things, in a few places, but it can be hard to get ideal performance standardized...even in C++.

jey 14y ago
> did you know that thanks to a standards committee decision, erase by iterator in a typical C++ TR1 hash set or map is O(n) Weird, never heard of that. What is it about the iterator requirements that causes erase to be O(n)?
- jzwinck 14y ago
  It's the fact that erase(iterator) returns the "next" iterator. Since hash tables often don't shrink, they can become quite sparse, and the "next" operation is linear. This is the best link I have right now--a ticket I filed (and was fixed) for Boost's implementation: https://svn.boost.org/trac/boost/ticket/3693 https://svn.boost.org/trac/boost/ticket/3693 Note the references to GCC's implementation. As far as I can tell they fixed it in 4.7, but caused some other performance regression which is still open. And most people don't use GCC 4.7 in production environments yet.
  - pilooch 14y ago
    Reading your comment, I thought I would mention this especially nasty bug in 4.7.1: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 Short description: a measured 3x performance regression from 4.6.2 to 4.7.1 when using std::unordered_map Not sure what the status is now, my Ubuntu and Debian boxes all report gcc 4.7.2.
  - deleted 14y ago
    [deleted]
vj44 14y ago
This is extremely unfortunate - I can see the way the C++ committee argued about this issue (ie. having consistent "erase" interface across different data structures), but it's bound to backfire for many unaware. Especially in a hash table, where you conceptually don't expect erase to provide the successor.
antirez 14y ago
Redis has an implementation of incrementally rehashing hash table in "dict.c" file. Very simple to understand code. https://github.com/antirez/redis/blob/unstable/src/dict.h https://github.com/antirez/redis/blob/unstable/src/dict.h https://github.com/antirez/redis/blob/unstable/src/dict.c https://github.com/antirez/redis/blob/unstable/src/dict.c As you can see no rocket science there.
- cjh_ 14y ago
  Reading this code made my day, thank you.
- matthavener 14y ago
  Really great C code. However, "timeInMilliseconds" should really use clock_gettime(CLOCK_MONOTIC, ..) instead of gettim eofday(..). A sudden change in time due to NTP, administrator, timezone, etc, could have the loop in "dictRehashMilliseconds" running for longer than expected. (Here's someone explaining the problem with gettimeofday http://blog.habets.pp.se/2010/09/gettimeofday-should-never-be-used-to-measure-time http://blog.habets.pp.se/2010/09/gettimeofday-should-never-b...)
  - antirez 14y ago
    Good advice, thanks, taking note

by jzwinck 14y ago

jey 14y ago

> did you know that thanks to a standards committee decision, erase by iterator in a typical C++ TR1 hash set or map is O(n) Weird, never heard of that. What is it about the iterator requirements that causes erase to be O(n)?

jzwinck 14y ago
It's the fact that erase(iterator) returns the "next" iterator. Since hash tables often don't shrink, they can become quite sparse, and the "next" operation is linear. This is the best link I have right now--a ticket I filed (and was fixed) for Boost's implementation: https://svn.boost.org/trac/boost/ticket/3693 https://svn.boost.org/trac/boost/ticket/3693 Note the references to GCC's implementation. As far as I can tell they fixed it in 4.7, but caused some other performance regression which is still open. And most people don't use GCC 4.7 in production environments yet.
- pilooch 14y ago
  Reading your comment, I thought I would mention this especially nasty bug in 4.7.1: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 Short description: a measured 3x performance regression from 4.6.2 to 4.7.1 when using std::unordered_map Not sure what the status is now, my Ubuntu and Debian boxes all report gcc 4.7.2.
- deleted 14y ago
  [deleted]

vj44 14y ago

This is extremely unfortunate - I can see the way the C++ committee argued about this issue (ie. having consistent "erase" interface across different data structures), but it's bound to backfire for many unaware. Especially in a hash table, where you conceptually don't expect erase to provide the successor.

antirez 14y ago

Redis has an implementation of incrementally rehashing hash table in "dict.c" file. Very simple to understand code. https://github.com/antirez/redis/blob/unstable/src/dict.h https://github.com/antirez/redis/blob/unstable/src/dict.h https://github.com/antirez/redis/blob/unstable/src/dict.c https://github.com/antirez/redis/blob/unstable/src/dict.c As you can see no rocket science there.

cjh_ 14y ago
Reading this code made my day, thank you.
matthavener 14y ago
Really great C code. However, "timeInMilliseconds" should really use clock_gettime(CLOCK_MONOTIC, ..) instead of gettim eofday(..). A sudden change in time due to NTP, administrator, timezone, etc, could have the loop in "dictRehashMilliseconds" running for longer than expected. (Here's someone explaining the problem with gettimeofday http://blog.habets.pp.se/2010/09/gettimeofday-should-never-be-used-to-measure-time http://blog.habets.pp.se/2010/09/gettimeofday-should-never-b...)
- antirez 14y ago
  Good advice, thanks, taking note