C++ containers that save memory and time

http://google-opensource.blogspot.com/2013/01/c-containers-that-save-memory-and-time.html

by dsr12 • 13 years ago

231 111 13 years ago

google-opensource.blogspot.com

leetrout• 13 years ago

And this is why you need to know all the algo and data structure "basics" when interviewing at the big G. Because people there are working on these sorts of optimizations in their spare time.

eridius• 13 years ago

What does knowing this stuff at interview-time have to do with being able to implement it later? I certainly don't remember how b-trees work off the top of my head, but what I do know is how to find out the answer given a computer and an internet connection.

lifty• 13 years ago

Having the details and characteristics of the b-trees(among other things) in memory allows you to consider them as possible solutions to a problem you are facing. If you dont know the details you would probably not know they are a good fit for a particular problem. The more detailed knowledge you have in your memory the bigger your possible solution set will be, thus, you will have a better chance at solving a particular problem.

I think Google is not looking for people that can follow specs(although thats valuable also) but people that can come up with brilliant solutions to hard problems.

pretoriusB3• 13 years ago

>but what I do know is how to find out the answer given a computer and an internet connection.

Then you are not good enough for them. They want someone that breaths and knows these things inside out and backwards.

Any half-competent dabbler can look them up and implement them. Creating novel solutions takes more deep understanding of them than that.

KMag4• 13 years ago

I averaged somewhere between one and two interviews per week during my 4 years with Google. Google has (or at least had) more applicants than they can shake a stick at. They have the choice between smart people who can look up things on the Internet but aren't interested enough to memorize the basics, and smart people who are interested enough in the subject matter to have the basics memorized (or at least are smart enough to put on a good show of loving the subject matter).

Maybe having the basics memorized isn't necessary for the job, but it's a good signal that you're not a zombie banging out code without really being interested or thinking critically about what you're doing. It's not a perfect signal, but it's still a useful signal.

Everyone knows you need to know your basic data structures for a Google interview. If you don't know your data structures, cram for a week or two before your interview. The basic data structures are just the basic starting point for the data structures interview questions. The interviewer needs to know you know the basic data structures before they start throwing curveballs at you to see how you think about and solve hard data structures problems. The people who think they're too smart or too cool for the basic data structures questions are just going to drown, so if they bomb the basic data structures questions, the interviewer justs moves on and pretends that was where the question ended. There's no sense in frustrating the interviewee and making the whole company look mean and forcing the interviewee to answer questions they lack the background knowledge to begin solving.

On top of that, if you can't even be bothered to cram some basic data structures for an interview, you're not going to fit in well at Google.

I also asked some constrained bin packing questions, related to scheduling distributed computations in a cluster and placing files in a distributed filesystem, but I'd simplify the problem a bit and make up some slightly silly story about kids selling candy or something. The simplification and the non-computer back story helps reduce the amount of assumed specialized knowledge, and keeps people from over-thinking the thing, thinking it's a trick question, or otherwise running off into the weeds.

Silly stories really do help people accept the simplified problem and not get lost thinking they're supposed to be thinking outside the box. If you ask a question about networking, people will suggest reducing the number of intermediate switches or maybe even swapping the network media with something with a higher signal propagation velocity. Rephrase it as kids playing Pokemon with cards, and they're moere likely to notice that O(N^2) network traffic can be reduced to O(Log(N)).

Some people just thought some problem involving candy or trading cards instead of computers was beneath them and silly, obviously missing that the underlying problem had real implications for computing at massive scales. If they got upset about the problem, I just let it go, since arguing with them or making them feel dumb by pointing out the isomorphism would just rile them up for their next interviewer. I usually genuinely hoped they'd do better with the next interviewer. Good engineers are hard to find, and if I'm the only person they rubbed the wrong way, they're unlikely to be working with me anyway.

If you notice how the simplified silly problem is probably related to a real problem the interviewer has had to solve, it's probably best to make a nonchalant comment. "Oh, so it looks like a constrained bin packing problem, maybe with applications in distributed storage or distributed process scheduling, or something like that. Let's see, you said the Hershey Bars can't be kept near dogs, so let me think about the heuristic of allocating them first. They're each $X and Y Calories, so ..."

If you think an interview question is silly, make sure you hide that opinion well from the interviewer. You're likely missing something, especially if your interviewer appears otherwise bright.

adamnemecek2• 13 years ago

Or maybe it's self-selection bias.

andreasvc6• 13 years ago

I don't understand what this is supposed to add to the observation that these subjects are important at Google interviews. It seems tautological to refer to interview requirements as "selection bias".

Smerity2• 13 years 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/

pilooch2• 13 years 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.

jzwinck2• 13 years 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++.

cwzwarich• 13 years ago

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

vidarh• 13 years 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.

amadvance• 13 years ago

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

cbsmith9• 13 years 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.

damian2000• 13 years ago

Anyone know why the STL doesn't use B trees? Are there use cases where Red-Black trees are better?

SenorWilson• 13 years ago

I don't really think it is possible to say one is better than another without a specific application in mind. Probably just chose whatever one they wanted at the time.

andreasvc6• 13 years ago

You can, you can talk about which operations need to be fast, as shown by the big-O complexity. You can also talk about constant factors, the cost of specific operations such as comparisons, and locality of reference. In my opinion the latter aspects should be emphasized more because you sometimes come across people who built their careers around slightly more optimal datastructures in terms of big-O complexity, which are nevertheless impractical in any but the most extreme situations due to constant factors (which may only get a footnote mention).

andreasvc6• 13 years ago

It says in the article that B-trees are advantageous when the cost of cache-misses would be worse than the cost of comparisons; e.g., in the case of integers. In comparison, a Red-Black tree would do less comparisons, and hash-table is faster on average but is unordered (more differences?).

taeric3• 13 years ago

In other words, benchmark heavily. And unless you have trees of integers, don't expect the same results.

gsg2• 13 years ago

The STL guarantees both iterator and address stability for the elements of a set, map, or the unordered variants. Those guarantees can't be provided by many more compact representations.

Note that this rules out more than just B-trees: open addressed hash tables and judy array like structures have the same issue.

brooksbp• 13 years ago

What do you mean by "iterator and address stability"?

guilloche2• 13 years ago

Without considering cache-miss, Red-black tree is much faster than B-tree. So this b-tree implementation must be tailored to cache-line size, and it may performs badly on some CPUs.

The performance gain on the B-tree container is also largely depends on the size of value. So choose this one carefully.

loeg• 13 years ago

> So this b-tree implementation must be tailored to cache-line size, and it may performs badly on some CPUs.

Um, no, Btrees are always going to win here as long as key size is relatively small compared to the number of items in the structure. Btrees, for small keyed associations, have a much better "branching factor per cache line." This means that fewer cache misses are needed to find relevant items (insert, delete, read, …), because the trees are shallower, and the cost of a cache miss on a btree node isn't much more expensive than an R-B node.

Benchmark everything and tune your B-Tree container size appropriately, definitely. You could even instantiate the template with multiple different sizes at compile time and benchmark them at run-time, then elect the most efficient implementation for the hardware currently being used.

chrisaycock• 13 years ago

Facebook released their C++ containers last year as well, which they named Folly. An interesting feature they added is that their vector class is "aware" of the memory allocator. Ie, if jemalloc is available, then the vector class will attempt to resize all dynamic memory structures to fit within cache hierarchy sizes.

http://news.ycombinator.com/item?id=4059356

grundprinzip• 13 years ago

One question: Is this something similar to the CSB+ Tree (Cache Conscious B+ Tree)

http://people.cs.aau.dk/~simas/dat5_07/papers/p475-rao.pdf

Or are the optimisations mentioned there still valid?

arianvanp3• 13 years ago

Reading C++ code always gives me a weird feeling something is inherently wrong with the language. Header files containing nearly all the implementation because that's the only place where you can define templates is so odd... (https://code.google.com/p/cpp-btree/source/browse/btree.h)

guilloche2• 13 years ago

agreed.

blablabla123• 13 years ago

Thanks to Comeau C++'s standard compliance, you can put the template into the .cc files. ;)

KMag4• 13 years ago

I think the complaint is more about the C++ compiler needing to expand the template every place it's used, as opposed to Java/C# generics and OCaml functors (functions taking modules as arguments and returning modules as values) which necessitate a pointer indirection at runtime (which a VM/JIT/smart linker may or may not be sophisticated enough to optimize away) but allow the call site to be ignorant of the implementation details at compile time.

There are workarounds in C++, but they're less elegant.

Arguably, the decision to keep using the C linker and use name mangling and template expansion in the compiler instead of making the linker smarter (or adding a phase between compilation/assembly and linking) was a mistake. Some kind of object file pre-processor that performed name mangling and template expansion on object files probably would have still been necessary, at least in the early years. Certainly incremental compilation and linking would be easier if template expansion were performed on object code (or a low-level intermediate representation) rather than source code.

shawn-butler9• 13 years ago

I think Sun's compiler also was compliant.

cbsmith9• 13 years ago

Even the EDG guys who wrote that support for the export keyword feel like it was a really, really bad thing: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n142...

halayli• 13 years ago

Welcome to templates and inline functions.

viraptor2• 13 years ago

Comments like this one don't help either:

    // Inside a btree method, if we just call swap(), it will choose the
    // btree::swap method, which we don't want. And we can't say ::swap
    // because then MSVC won't pickup any std::swap() implementations. We
    // can't just use std::swap() directly because then we don't get the
    // specialization for types outside the std namespace. So the solution
    // is to have a special swap helper function whose name doesn't
    // collide with other swap functions defined by the btree classes.

zanny• 13 years ago

I don't get whats wrong. They have an implementation of swap in their namespace already they don't want to use, the standard one isn't templated to work with their btree, so you use a different swap in methods.

Sounds more like this should be btree::swap and whatever they have as swap() should be something else.

cbsmith9• 13 years ago

That helps a lot. This is a pretty complicated nuance in the implementation that you rarely find in libraries in any language.

alexeiz• 13 years ago

There is nothing wrong with that code. The comment is strange, but the code is fine. 'swap' function call has to be resolved via ADL and this is how it's done correctly. It's unfortunate that the C++ Standard essentially requires swap to be called this way (i.e.: using std::swap; swap(a, b);). In your code it's best factored out into a separate 'swap_helper' function and this is what's done there.

C++ is convoluted. Sometimes code that seems quite wrong has a good reason to exist.

shawn-butler9• 13 years ago

I would suggest if you have this feeling that you don't have a good grasp on metaprogramming. This link might help: http://www.parashift.com/c++-faq-lite/templates-defn-vs-decl...

Also the use of extern keyword for templates which is valid according to the standard is limited by compiler compliance. Kind of a chicken-egg problem, not a language problem.

Finally you might investigate the extern template keyword in c++11: http://en.wikipedia.org/wiki/C++11#Extern_template

I have always wondered whether a grand rethinking of compilers/linkers wasn't in order given the radically different face of computing and computational resources available now as opposed to 30+ years ago.

bo1024• 13 years ago

> I would suggest if you have this feeling that you don't have a good grasp on metaprogramming.

I don't think someone has to be an expert on metaprogramming to recognize the flaws in C++ (although I do think it helps).

loup-vaillant• 13 years ago

Since you mention the FAQ, I just have to mention the FQA: http://www.yosefk.com/c++fqa/templates.html#fqa-35.12

More seriously, the primary use of template is not meta programming, but good old parametric polymorphism (or «genericity»). They are more capable than that, but only by accident. https://en.wikipedia.org/wiki/Turing_tarpit

If you want actual meta programming, look at Haskell combinator libraries, Lisp macros, and external DSLs (in ascending order of "meta").

cbsmith9• 13 years ago

Yes, it is a flawed language to have a declaration and the definition are all in one place together. What other language does this aside from Ruby, Python, Perl, JavaScript, Java, C#, Smalltalk, VisualBasic, PHP, Haskell, Lua...

fauigerzigerk2• 13 years ago

None of these other languages requires code to be compiled each and every time it is imported/included.

arianvanp3• 13 years ago

Haskell is a great example where interface and implementation are decoupled.. typeclasses are used a lot to describe problems with similar patterns. Look at monads, monad transformers, applicatives and functors. I don't think half of them even have default implementations defined.

shin_lao• 13 years ago

I would recommend to have a look at sorted arrays first. There is an implementation available in Boost:

http://www.boost.org/doc/libs/1_52_0/doc/html/container/non_...

cbsmith9• 13 years ago

Sorted arrays are a common choice that I've seen people go to in lieu of std::set, but a proper B-tree implementation kicks butt compared to a sorted array for performance when mutating data, and actually an unsorted array tends to kick but for small array sizes (<100 elements).

olivier1664• 13 years ago

I'm confuse. From my understanding of B-Tree, B-Tree are good when you load data from hard drive. It allow to minimize the number of time you load a range of data from the hard drive. Since C++B-Tree is in RAM, and thus the data loading should be less important, how does it appears to have a so good benchmark? What is the secret ingredient?

alexgartrell• 13 years ago

If I had to guess, I'd say better cache locality. It's tremendously more expensive to go to main memory for something than to go to the cache.

C++ containers that save memory and time

Related Stories