8 ms·
Mapping Strings in C++
- jstarks 10y agoIt would be interesting to see a zoomed in view of how things perform at small numbers of elements. Perhaps an unsorted vector is actually the best up to a certain point, for example.
- Sharlin 10y agoNo, the charts should use a log-log scale. Now only the x axis is logarithmic which makes the behavior confusingly exponential-looking and also hides the differences at small sizes.
- Joeri 10y agoI love how it's always the native code developers who worry the most about performance implications, when they often have the least to gain from doing so. It must be something about being close enough to the metal to realize and care about what happens.
- Rusky 10y agoThey're often using native code because they have much stricter performance requirements, which means they have everything to gain by doing so. (Though yes, there is an aspect of your last sentence as well)
- deleted 10y ago[deleted]
- deleted 10y ago[deleted]
- perfmode 10y agoThe last time I wrote production C++ was at Google. There, when requests are coming in at a torrential rate, every instruction counts. In cases like that, it's perfectly reasonable to sweat the details when selecting a data structure.
- deleted 10y ago[deleted]
- khedoros1 10y agoHopefully if you're using C++, it's because the performance implications matter. And hopefully, you're nitpicking on the implementation of the mapping algorithm for the same reason. Third, that's that only good reason to be close to the metal anymore: that there's a requirement for some particular speed target, and none of the "good enough" solutions are good enough. Otherwise, why wouldn't I build my program in Python or something? If selecting the right data structure just based on Big-O notation will get me to a good enough solution, digging down is just a waste of time, like saving microseconds when network latency is 1000 times the problem.
- pklausler 10y agoThere are other reasons to use C++ besides performance, and other reasons to not use Python besides performance.
- khedoros1 10y agoSure, but it's one of the biggest go/no-go reasons. Preexisting codebase, available libraries suitable to the problem domain, platform limitations, desire to obfuscate code, developer experience, desire for speed of development, and whatever else I'm forgetting would be other reasons to choose a particular set of technologies. But the comment I was responding to was about performance implications, and whether or not development was "close to the metal", so my response was too (using C++ and Python as examples of lower-abstraction and higher-abstraction languages).
- harry8 10y agoThere are other reasons that are at least 9 times in 10 (probably more) completely dominated by a performance justification on occasions where people actually have the choice rather than having it made for them.
- emmelaich 10y agoThere's a element of that but like @khedoros1 says you have it backwards. By comparison, Java programmers typically have very little mechanical sympathy. Just yesterday one suggested to me that he could add a Kafka instance on our machine (rather than a new topic queue on the existing Kafka) to speed up things. I pointed out it would probably make little difference as it would be hitting the same disk. And it would complicate their code because they'd have to switch connection details depending on the topic.
- deleted 10y ago[deleted]
- ot 10y agoIf you don't need sorted search (lower/upper bound) or prefix search I doubt even a good trie would beat a good hash table. Have you tried google::dense_hash_map? std::unordered_map is slower because it uses chaining to resolve collisions.
- jnordwick 10y agoTries have the incredibly useful feature that they fail fast and match fast when you get to a unique prefix. Hash you always need to process the full string though.
- ot 10y agoUnless you're talking about extremely long strings, computing a hash takes far less time than a cache miss.
- jnordwick 10y agoYeah, the most cache-friendly structure is going to win, but failing fast means no strcmp test if you happen to get a collision, which is potential miss to fetch the characters. And if the hash uses bucket chaining, the programming gods help you. On an interview I was once asked to calculate the latency on a hash fetch in Java with the JDK String, hit and miss. It all basically boils down to how many caches misses are you going to have. I literally just counted up the memory accesses and counted up the hits and misses then gave an answer for cold and hot cache. Then we worked on rewriting it.
- _pdp_ 10y agoI wrote a 3D engine in C++ many years ago and it still feels wrong. At least with C you get the power to do things the way you want to and yes it is mostly unsafe if you don't know what you are doing. IMHO C++ is a failed attempt to reinvent already working language. C should not be extended. There are other languages like go and rust that provide good performance while not bastardizing C.
- khedoros1 10y agoC++ today and C++ many years ago are very different languages.
- ar15saveslives 10y agoDefine "bastardizing C". Which improvement do you consider as "failed attempts"? RAII, constructors/destructors, so you don't need to write spaghetti code to free resources reliably? Templates, so you can write sort() function once, for all comparable types? Lambdas? Or maybe GLib is somehow better than stl/boost? C++ saves TONS of time and effort in our projects, thank god that I don't need to write in plain C anymore.
- pg314 10y ago> Templates, so you can write sort() function once, C has a generic sort: qsort [1] (or mergesort, heapsort or radixsort if you have specific requirements). [1] https://linux.die.net/man/3/qsort https://linux.die.net/man/3/qsort
- emmelaich 10y agoqsort is both unsafer and slower than a good templated sort.
- pg314 10y agoThere are indeed trade-offs. But the comment I was replying to implied that you couldn't write a generic sort for all comparable types. That is wrong. Unsafer yes. But it's only slower because it's not being inlined. If the compiler can see both the implementation of qsort and the comparison function, there is no reason why it would be slower than a templated sort. You could accomplish this with link-time optimisation or by moving the implementation of qsort to a header file. A trade-off you didn't mention: templates will cause multiple copies of the sort to be inlined in the executable. This can lead to bigger executables (with slower start-up) and more cache misses. Another trade-off: templates lead to much slower compile times.
- utopcell 10y agoThe performance gap between unordered_map<> and the custom implementations seems to be less than 2X. This will quickly evaporate if one uses an efficient hash such as dense_hash_map<>.
- rocqua 10y agoFor the trie, things would be a lot better if the words got longer. All the 'inefficiencies' of a trie lie in the pointer chasing. The great thing is that you can process a string 'on-line'. If things start getting really big, there are some tricks with LCP-arrays and constant time RMQ (range minimal query) that have great theoretical performance. I haven't seen that stuff in practice though.
- emmelaich 10y agoYou could even do better and use a perfect hash if you have known constant list of strings.
- jnordwick 10y agoTries can be memory hogs and the techniques for level and path compression can add significant overhead. It would have been interesting to see memory usage. I've of the more interesting data structures for things like this are Ternary Search Trees after each subtree starts with a common prefix. That would have been an interesting comparison. https://en.m.wikipedia.org/wiki/Ternary_search_tree https://en.m.wikipedia.org/wiki/Ternary_search_tree
- mtanski 10y agoOverhead, fragmentation, pointer chasing, malloc() bound. It's one of those data structures that makes perfect sense in CS theory but is only applicable in a limited set of real world problems. For now we're beholden to implementation of our architectures, their quirks and side effects.
- jnordwick 10y agoYou can fix some of that and techniques like a binary trie can give better cache performant/smaller levels, but while a trie sounds simple they are surprisingly difficult to get to perform better. The optimizations for hashes are far easier to implement IMHO
- blt 10y agoUsing a memory arena helps a lot with the problems you mentioned.
- wmu 10y agoThat's true. Years ago I did some experiments with various trie representations and despite my effort, glibc malloc was reporting 40-50% of internal fragmentation. Once switched to memory arenas, I nearly rid off fragmentation.
- rocqua 10y agoSuffix tries are an even better example. Donald Knuth once heralded them as the greatest algorithmic break-through of the '70s but in practice, it doesn't quite perform. The point of suffix tries is finding substrings. I.e. build a suffix trie of all of Shakespear's works in linear time and memory (linear w.r.t. the total length of the string). And then, given a potential quote of length K, see if it is in Shakespear's work in O(K) time. The big draw there is that the complexity of string lookups does not depend on the length of the big text against which you are matching. This finds practical use in genome sequencing.
- mtanski 10y agoBased on experience I'm going to form an educated guess (hypothesize) and say that both std::map and author's trie container are primarily bound by pointer chasing. Obviously one should test this. If that's the case, use a C++ btree_map implementation.
- adzm 10y agoI'm fond of sorted vectors as well such as boost flat_map. The worst case performance can be surprising! But eventually if it gets too big you'll need a btree
- pekk 10y agoCan you share an instance where you actually needed a btree? What made it a true need (business need of some kind maybe_ and not just a measurable difference?
- AstralStorm 10y agoGenerally the requirement for range queries and piercing queries. (Does range x,y contain object o; is object o overlapping range described by object p) Additionally requirement to maximize immutability for reasons of thread safety. Range queries do not really work well on sorted vectors even if you have as many as needed indices. Immutability and race freedom are even more complex. With a tree, copy on write solves many problems. (And can be much cheaper than copying whole structure.) If not, you can atomically replace subtrees in a safe way.
- jsnell 10y agoThe benchmark is kind of dodgy. - It looks up the same key on every iteration, so every level of the trie stays in the cache, no matter how large the nominal data set size is. - The setup appears to be such that even though the key is 128 bytes, it's probably not going to share a prefix longer than 4-5 bytes. - The code is constructing a temporary string of the 128 byte key for every lookup in the hash table (by going from a string to char-pointer to string), but not for the trie. So it first eliminates the problems of a trie (especially the cache inefficiency) by an unrealistic test setup, and then has a bug introducing probably a factor of 2 unnecessary overhead to the hash table.
- trishume 10y agoSo basically none of the results are remotely relevant to real use. Except maybe that unordered_map is faster on large data sets than map. Another thing I noticed is it starts with the example of a type column on a database, then proceeds to use graphs with a logarithmic scale on the x axis but not the y axis, so you can basically only see two data points, which are for millions of strings. He also only uses long strings, where I would expect the type column to be the opposite This means even if the benchmarks were valid, I still wouldn't know what to use if I wanted to map 2-10 different short strings to numbers I wouldn't know what the right answer is. Of course the real right answer for that case, which I'd guess is a perfect hash function, wasn't tested.
- user5994461 10y agomap is a red and black tree, unordered_map is a hash table. Operations have the typical complexity of the data structure. Nothing fancy.
- trishume 10y agoExactly. I predicted every benchmark result except for the trie one, which surprised me a ton (wut??!! but pointer chasing costs!), apparently though that was just bad benchmarking putting the only path ever tested in cache.
- 10y ago
- toth 10y agoInteresting write up. There was a claim I didn't understand though > Let’s fix this. An easy way to get our std::vector implementation in-line with the rest of the containers is we can sort it and utilize an algorithm, std::lower_bound, in order to speed up our lookup times. Unless I'm missing something, isn't this wrong? The point of the vector is that v[enum_value] gives you the name of enum_value as a string. Once you sort it this relationship no longer holds, unless it so happens that the vector was already sorted (which happens to be the case for "circle", "square", "triangle").
- quinnftw 10y agoI thought this aswell, but you have it backwards. The point is to convert a string to it's corresponding enum, not the other way around.
- toth 10y agoI get that part, that's why you use std::find or std::lower_bound on the vector, but my point is that std::lower_bound will not give you the right answer unless your enum is defined with the names in alphabetical order.
- SoapSeller 10y agoYou are absolutely right - and the benchmark in the repository doesn't even try to get the value - it's only check for existent of key. However, it can easily be fixed by using something like vector<tuple<string, types_t>> and supplying predicates for both std::sort and std::lower_bound to only consider the first element in the tuple. There will be some performance hit, but should be minimal.
- toth 10y agoI see, that makes sense. I guess at that point you have something very much like std::map, except it doesn't keep itself sorted, you have to do it yourself. I guess for cases like this where you initialize it once and never change it again it could even be a better choice (i.e., faster initialization).
- ericseppanen 10y agoIn the first chart, the units for the Y axis appear to be "giga-nanoseconds". That's... interesting.
- sillysaurus3 10y agoAlso either the best or worst name for a band, depending on what music you're into.
- archgoon 10y agoWell, from the band's perspective, it's preferable to the nanosecond gig.
- Animats 10y agoWhy is the time for map lookup going up so fast for large numbers of strings? Is he running out of memory and thrashing? Is the implementation of map broken? Does the benchmark include growing the map? (If you include growth time, map insertion is O(N log N, because you need log N recopies of size N.)
- TillE 10y ago> Is he running out of memory and thrashing? Sort of. It's probably the level below that: these results look fairly typical of a data structure growing larger than the cache, which is usually 8 MiB now.
- martincmartin 10y agoUpdate: The author is always using a collection of 1,000,000 entries. The horizontal axis is the number of lookups, into a collection of 1,000,000 entries, e.g. always ~ 20 entries in the tree. So the x-axis is logrithmic, but the y axis is linear and we expect the graph to be linear. Original comment: Good question. The x-axis is logrithmic, the y axis is linear. Without cache effects, std::map and lower_bound should take logrithmic time, so should be a straight line on the graph. Also, unordered_map should be constant time, independent of size. So its either cache effects (including swapping / thrashing), or there's some other overhead that's dominating the whole thing, and the author isn't measuring what they think.
- deleted 10y ago[deleted]
- bshlgrs 10y ago"At around 1,000,000 elements our unsorted vector takes around 32 minutes to lookup a string." I don't at all believe that C++ can only iterate through 2000 strings a second. Python takes an imperceptibly small time to iterate through an array of a million strings when I test it out in my repl, and I imagine C++ would either be as fast or somewhat faster. This number is so ridiculous that it makes me very skeptical of the rest of the article.
- martincmartin 10y agoThe x-axis is the number of iterations, i.e. the number of lookups. The collection is always size 1,000,000. Also, each of those lookups is for the exact same entry, so after the first time, it'll be all cache hits. Well, except for the std::vector, which is what you're talking about... :)
- jstimpfle 10y agoStrings are length 10 to 100. A cache line is 64 bytes. A cache miss is < 1000 cycles < 10^3ns. That makes < 1s for 10^6 strings. Furthermore adjacent strings are likely to be adjacent in memory, from which I would naively expect cache prefetching to succeed. Additionally, the curve is quadratic (if at all), not linear. I bet the author looked up all n strings from the vector of n strings.
- aarongolliver 10y agoI think the curves are linear because the x-axis is log scale but the y-axis is not.
- jstimpfle 10y agoGotcha. It's probably still quadratic, just judging from the values. You can't need 32 minutes for 10^6 100-byte comparisons (which typically abort after the first character compares unequal. Not that that matters).
- user5994461 10y agoauto get_type(const std::string& type) { auto e = m.find(type); if (e == std::end(m)) return type_t::num_types; return e->second; } I don't understand the point of that code. Use "map.at(key)" and you get the value from the map. No need for function and branching and whatever. If you really want to mess around, you compare "map.at(key)" against "map[key]". at return a const, [] is not const and allows to create the key (if I remember well). To conclude, if you really really want to show off your optimization skill, you optimize return types: "auto &&" vs "auto &" vs "auto" vs a few other ones. Can't help you with that last one. One decade of C++ and still struggling with reference, value copy, left-value reference... That reminds me how bad C++ is a mess. 5 minutes of optimizations and my brain is already hurting. Good thing I moved to DevOps. More pay, less hassle.
- charles-salvia 10y agoThe point is apparently to return "type_t::num_types" if the key doesn't exist in the map. Using at() throws an exception if the key doesn't exist.
- user5994461 10y agoThat's an artificial requirements, you can do the same with at() or change the requirements. Catching all errors to return a default type is an arguable decision.
- cbsmith 10y agoThis seems fairly involved for a problem that should be solved in the database... I mean seriously, this is the kind of thinking that at least in theory is going on inside a relational database. If you have a table mapping these strings to values, (or, in a more sane database, it's the way around), you would just do the join and be done with it.
- rleigh 10y agoThe plots would have benefitted from a log scale on the y axis, or both axes. The behaviour at the low end can't be clearly visualised since it's squished to the baseline by the exponential behaviour for high x values.
- wmu 10y agoI'm wondering why the author didn't try to use binary search on sorted std::vector. It should be as fast as std::map (if not faster). I also did some experiments with lookups using collections of std::map: http://0x80.pl/notesen.html#stl-map-with-string-as-key-access-speedup-3-04-2010 http://0x80.pl/notesen.html#stl-map-with-string-as-key-acces...