Comment by Smerity | Hacker News Reader

Comment by Smerity | Hacker News Reader

Parent Full thread

Agreed. When I was working on Google App Engine, the Quota team sat next to me. The Quota team are the service that just about every other service at Google calls to ensure a user isn't abusing "The Google". That means that they need to have insanely small response times to ensure that all the services run on time.

They hit an issue no-one really thinks about: resizing hash tables. No-one thinks about it, as it happens transparently under the surface, but for them, the few milliseconds it took to resize the hash tables would have enormously detrimental effects on just about every other Google service. The solutions they were talking about were really quite amazing. That's the insanity they face.

So, if anyone hasn't seen Google Sparsehash[1], check it out: it's another near drop-in improvement to the STL. Two bits per entry of overhead and insanely fast. I can't remember if the Quota team used it specifically, but I wouldn't be surprised if it's one of the results of their work.

[1]: http://code.google.com/p/sparsehash/

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

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.

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

Reading this code made my day, thank you.

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

Cost of hash resizing is something that was covered in my second undergrad CS course, and something that has been a recurring subject in C++ books and articles for the last two decades or so. I'm sure there are a lot of people who don't think about it often, but mainly because most people don't need to.

Performance in general is something most people don't need to consider much.

While these Google projects are great, it's also worth considering that a lot of the time, having a near drop-in replacement for an STL container may not be worth it, because the improvements it brings might not be worth the cost of bringing in a non-standard component outside of the type of extreme situations Google faces.

Thinking about the cost of resizing hash tables is standard practice in latency sensitive and/or highly concurrent systems programming.

Actually sparsehash is not optimized for speed, but reduces the usual hash map memory footprint. In practice it is on par or slower than STL unordered_map.

I should have specified earlier: Google Sparsehash also contains Densehash which is optimised for speed, not space. It, however, is also more space efficient than most other hash implementations. Check out dense_hash_map[1]

[1]: http://sparsehash.googlecode.com/svn/trunk/doc/implementatio...

For these problematics there are hashtables with progressive resize.

For the theory you can see: http://en.wikipedia.org/wiki/Linear_hashing

I did one in C at: http://tommyds.sourceforge.net/ It's competitive with the googledensehash, sometimes slower, sometimes faster. In the benchmark section there are nice graphs :)

> They hit an issue no-one really thinks about: resizing hash tables. No-one thinks about it, as it happens transparently under the surface, but for them, the few milliseconds it took to resize the hash tables would have enormously detrimental effects on just about every other Google service.

Hmm.. not sure I'd agree with your assessment that no-one thinks about it. Certainly most DB engines are very aware of this characteristic of hash tables, and it is one of the reasons B-tree style indexes are preferred (not to mention the advantages of sorting).

I think in general, people doing systems development tend to be very aware of these kinds of issues, and perhaps Google is comparatively rare in that it is a company where systems and application development are so vertically integrated. I'm not even sure if that is so terribly unique.

Reply on news.ycombinator.com