Hacker News Reader

Comment by jzwinck | Hacker News Reader

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++.

View on HN

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.c

As you can see no rocket science there.

Reading this code made my day, thank you.

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-b...)

Good advice, thanks, taking note

> 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)?

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

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.

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

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.

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.

Reply on news.ycombinator.com