11 ms·
C++ containers that save memory and time
- leetrout 14y agoAnd 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 14y agoWhat 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 14y agoHaving 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.
- meric 14y agoI would think a person who can specialise, learn and memorise the details and characteristics of a particular domain quickly, say b-trees, when he is working on relevant problem, would be more important than knowing about all things computer science related at the same, and lesser, detail. Wouldn't it be more important to have people to come up with brilliant solutions on problems they are working on, rather than hard problems in general that have already been solved?
- venomsnake 14y agoAs always in our field it is somewhere in the middle - having knowledge of the platform and the field is something that can give you some hints in advance about potential problems with the approach for a difficult problem. After all a timely - "This is not going to work well because there will be lots of branch mispredictions and you will be going out of the L3 cache a lot, and RAM is terribly slow" can save a lot of time and effort for some classes of tasks that big scalabiliy companies have to deal often.
- pretoriusB 14y ago>Wouldn't it be more important to have people to come up with brilliant solutions on problems they are working on, rather than hard problems in general that have already been solved? Most of the times the guys that can come with "brilliant solutions" on new problems are those that know the solved problems inside and out. The other guys just keep reinventing the wheel (only worse).
- Scene_Cast2 14y agoTypically, one doesn't know that a problem is in a specific implementation domain (b-trees) unless one knows that domain. For example, I have M time slots and N people that need to be scheduled. Each of the N people has a time schedule for the M slots (either free or busy). If a person doesn't know about bipartite graph matching (or even graphs at all), then they're less likely to come up with a polynomial-runtime solution. Now, if a person knows about bipartite matching, they might as well learn the algorithms (max flow, etc) to solve it (even for fun, at least I know I would).
- pretoriusB 14y 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.
- eli_gottlieb 14y agoThe difference being that novel solutions require actual domain knowledge rather than an n-levels-deep memorization of the entirety of your Algorithms 1 and 2 courses from university.
- pretoriusB 14y agoThe domain knowledge when it comes to implementing algorithms is algorithms themselves...
- eli_gottlieb 14y agoYes, but the algorithms relevant to a domain are not Algorithms 1&2 class algorithms. For example, writing a network protocol requires knowledge of finite-state machines, writing a type-inference engine requires knowledge of unification, writing a thread scheduler requires knowledge of various scheduling algorithms. Knowing the most efficient way to find all the anagrams in a text is not relevant to any of them, though. And yes, I was given that problem in an interview last week. I got it right, but the actual position involved more knowledge of architecture, assembly, and compilation than of Algorithms Guru Yoga.
- DannyBee 14y agoWell, I hope you weren't asked that at Google , since it's a banned question. If you were, let me know privately :) I assume you understand the goal of these questions is not to figure out if you can perform memorization of algorithms 1 + 2, but to understand how you think about problems and watch you do it? Note that, at least at Google, they still try to hire generalists (in most cases), so you would still get that "kind" of question there, even for a job involving architecture and assembly. This is a deliberate choice. Of course, i'm sure you also realize that a lot of the algorithms in "architecture, assembly, and compilation" were developed by people who started out more as "Algorithms Guru Yoga" folks. Gregory Chaitan, who developed Graph Coloring for register allocation, was definitely not a compiler guy Only half the folks on the original conference paper for Static Single Assignment form for compilers were compiler people actually trying to solve that problem. Robert Tarjan was not a compiler guy, but his scheme for computing dominators is still the main one used today, and his union-find algorithms (he also proved the upper bound on the already-known versions) are what are used for a lot of type unification algorithms. The list goes on of "Algorithms Guru Yoga" folks who came up with the premiere solutions to problems in the field you are talking about. So when you say "novel solutions require actual domain knowledge rather than an n-levels-deep memorization of the entirety of your Algorithms 1 and 2 courses from university.", it's a bit hard to take that seriously. Novel solutions require both domain level knowledge, and the understanding you learned in Algorithms 1 and 2. Even the question you got about anagrams does not require any n-level wrote memorization. It requires only the most basic understanding of data structures, and an understanding of how to design algorithms.
- deleted 14y ago[deleted]
- KMag 14y agoI 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.
- adamnemecek 14y agoOr maybe it's self-selection bias.
- andreasvc 14y agoI 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".
- adamnemecek 14y agoWhat I meant is that maybe the people working at Google were interested in algorithms even before working at Google and therefore they went to work for Google and therefore they work on algo in their free time. I did not say selection bias, I said self-selection bias http://en.wikipedia.org/wiki/Self-selection_bias http://en.wikipedia.org/wiki/Self-selection_bias
- Smerity 14y agoAgreed. 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 agoActually 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 agoI 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 agoNo 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++.
- deleted 14y ago[deleted]
- damian2000 14y agoAnyone know why the STL doesn't use B trees? Are there use cases where Red-Black trees are better?
- deleted 14y ago[deleted]
- SenorWilson 14y agoI 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.
- andreasvc 14y agoYou 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).
- taeric 14y agoYou don't seem to be disagreeing. The point was that you need to know which properties matter to your application before you can truly decide where you should worry about emphasis. But, for those that want a good example of what you are talking about, it seems to mirror the recent post by Carmack regarding ray tracing. If I recall, the point was that, though ray tracing is better in O terms, it has an outrageous constant factor.
- _delirium 14y agoAnother wrinkle is that the constant factors can be data-dependent: which data structure to choose can heavily depend on the distribution of data you typically see.
- deleted 14y ago[deleted]
- chrisaycock 14y agoFacebook 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 http://news.ycombinator.com/item?id=4059356
- grundprinzip 14y agoOne 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 http://people.cs.aau.dk/~simas/dat5_07/papers/p475-rao.pdf Or are the optimisations mentioned there still valid?
- arianvanp 14y agoReading 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 https://code.google.com/p/cpp-btree/source/browse/btree.h)
- guilloche 14y agoagreed.
- blablabla123 14y agoThanks to Comeau C++'s standard compliance, you can put the template into the .cc files. ;)
- KMag 14y agoI 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.
- cbsmith 14y agoActually, C#'s generics don't require a pointer indirection. It works almost like a hybrid between C++'s templates and Java's Generics.
- shin_lao 14y agoI 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_standard_containers.html#container.non_standard_containers.flat_xxx http://www.boost.org/doc/libs/1_52_0/doc/html/container/non_...
- cbsmith 14y agoSorted 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 14y agoI'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 14y agoIf 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.