4 ms·

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 cal

by Smerity 14y ago

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/ http://code.google.com/p/sparsehash/

pilooch 14y ago
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.
- Smerity 14y ago
  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/implementation.html http://sparsehash.googlecode.com/svn/trunk/doc/implementatio...
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.
cwzwarich 14y ago
Thinking about the cost of resizing hash tables is standard practice in latency sensitive and/or highly concurrent systems programming.
vidarh 14y ago
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.
deleted 14y ago
[deleted]
amadvance 14y ago
For these problematics there are hashtables with progressive resize. For the theory you can see: http://en.wikipedia.org/wiki/Linear_hashing http://en.wikipedia.org/wiki/Linear_hashing I did one in C at: http://tommyds.sourceforge.net/ http://tommyds.sourceforge.net/ It's competitive with the googledensehash, sometimes slower, sometimes faster. In the benchmark section there are nice graphs :)
cbsmith 14y ago
> 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.

by Smerity 14y ago

pilooch 14y ago

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.

Smerity 14y ago
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/implementation.html http://sparsehash.googlecode.com/svn/trunk/doc/implementatio...

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.

cwzwarich 14y ago

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

vidarh 14y ago

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.

deleted 14y ago

[deleted]

amadvance 14y ago

For these problematics there are hashtables with progressive resize. For the theory you can see: http://en.wikipedia.org/wiki/Linear_hashing http://en.wikipedia.org/wiki/Linear_hashing I did one in C at: http://tommyds.sourceforge.net/ http://tommyds.sourceforge.net/ It's competitive with the googledensehash, sometimes slower, sometimes faster. In the benchmark section there are nice graphs :)

cbsmith 14y ago

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