Mapping Strings in C++
cdacamar.github.io
cdacamar.github.io
- 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.
In an access pattern where the same elements are requested over and over this very quickly brings those elements to the front, giving really fast access times. This super simple data structure would totally blow the rest out of the water on this benchmark, and should illustrate the issue with it quite well.
Don't blindly throw work at multiple cores low down in algorithms. Amdahl's law tells you that the pay off is likely low, and if the program already makes proper use of the cores you're just going to slow things down.
That program is just a benchmark to map millions of string to integers, it's valid to optimize processing.
What about the inability to exit a parallel region--I was under the impression that once you start a parallel for, you can't exit it until it's run through the entire iteration.
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.
Operations have the typical complexity of the data structure. Nothing fancy.
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.
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.
Mixed (log/linear) scales on the axes
Only two columns of points on each graph matter (the last two) because the left hand side is all zeros (an artifact of the y axis not being log scale)
The y-axis is sometimes in thousands-of-mega-nanoseconds (with two significant digits) or sometimes in giga-nanoseconds (with one).
Giga-nanoseconds are seconds!
The colors for each line sometimes changes between graphs.
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.
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.
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.
> 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").
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.
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).
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.
It must be something about being close enough to the metal to realize and care about what happens.
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.
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).
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.
(Though yes, there is an aspect of your last sentence as well)
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.
Ternary search trees are really great and relatively compact. A while ago, I compared memory use of storing a dictionary (the SOWPODS word list) in Rust using various tries (as measured with the heapsize crate):
- Trie, using a HashMap to store edges: 691MB
- Trie, using a sorted Vec to store edges: 44MB
- Ternary search tree: 18MB
A typical ternary search trie is even more compact, but I implemented randomized ternary search tries, which uses two extra member variables in each node for bookkeeping (in these measurements u16s).
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.
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.
[1] Though there is an O(k) search approach too: http://www.sciencedirect.com/science/article/pii/S1570866703...
Heck, as far as I can tell, this approach is just another way of storing a tree.
That's... interesting.
If that's the case, use a C++ btree_map implementation.
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.
I also did some experiments with lookups using collections of std::map: http://0x80.pl/notesen.html#stl-map-with-string-as-key-acces...
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.
auto get_type(const std::string& type) {
auto e = m.find(type);
if (e == std::end(m)) return type_t::num_types;
return e->second;
}
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.
Catching all errors to return a default type is an arguable decision.
C++ gives you the same level of control over your program that C does, but also comes with nice low-cost (in many cases zero-cost) abstractions for when you need them.
C++ saves TONS of time and effort in our projects, thank god that I don't need to write in plain C anymore.
C has a generic sort: qsort [1] (or mergesort, heapsort or radixsort if you have specific requirements).
Templates give you compile time type checking, that's why one doesn't pass void pointers like this anymore but uses templates to implement generic functions.
That's a fair point. However, I do not tend to make many of the mistakes that would be caught by the C++ type system. But different people tend to make different kinds of mistakes.
The type bugs that happen tend to be pretty obvious and easy to debug. Good luck to you debugging template code :) I've had a harder time debugging C++ code than C code. Again, YMMV.
Although sometimes "I do not tend to make many of the mistakes that would be caught by the C++ type system" might be related to "how to use C++ type system so it would catch mistakes people tend to make".
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.
That is a clear advantage of C++.
> Also without LTO it will be very expensive as it cannot inline the compare function call.
Templates force you to expose the implementation in a header file. In C you can choose. If you move the qsort implementation in a header file, the compiler should not have any trouble inlining it.
Inlining is not always a win, though (slower compiles, bigger code, more cache misses).
Only half of the reasons why C++ is so popular have to do with the language itself. The other half is related to constraints, that don't have as robust solutions using other languages.
Nobody is claiming C++ is a great language but for a lot of constraints there are no viable options.