4 ms·
Tokenizing by storing strings in a vector is almost never what you want for high performance code, as it will result in an allocation for each token. If you ca
by cmovq 4y ago
Tokenizing by storing strings in a vector is almost never what you want for high performance code, as it will result in an allocation for each token.
If you can keep the original source string around, consider using std::vector<std::string_view> with each string_view pointing to part of the original text.
An even better approach is to avoid using an intermediary vector altogether if all you need is to process the tokens one-by-one and store them in a map. You could have `std::string_view parse_next_token(std::string_view *text);` which advances the source text and returns the next token.
- Negitivefrags 4y agoI like to implement an iterator that returns string_view when dereferenced. You can make the ergonomics quite nice with a helper class. for( auto value : from_csv( str ) ) { … }
- jeffbee 4y agoRight? Effortless performance improvements without having to make it a "journey" and write 50 blog posts: absl::StrSplit will stop this vector reallocation and get rid of those string copies, and if you want you can just iterate over it without storing anything.
- rhdunn 4y agoThat follows one of the core optimization strategies: "do less work", or more precisely, "don't do work you aren't going to use, and don't repeat work you've already done". Here, the extra work is that of copying the token text to create new string objects.
- quadrature 4y agobased on the final paragraph i'm guessing this will be the next blogpost in the series.
- returningfory2 4y agoA complementary idea is to reuse the vector of strings across different calls to `tokenize`. The main loop in the code is of the form: { std::vector<std::string> tokens = tokenize(line); // do work with tokens } which you could change to std::vector<std::string> tokens; { tokens.clear(); tokenize(line, &tokens); // do work with tokens } Combined with your suggestion to use std::string_view, this would mean only O(1) allocations across the program for this part of the code.
- jstimpfle 4y agoJust store the offsets into the corresponding source file. Why even fool around with a silly string view? A 32 bit integer per token is sufficient in many circumstances.
- TylerGlaiel 4y ago> Tokenizing by storing strings in a vector is almost never what you want for high performance code, as it will result in an allocation for each token. not quite, std::string can store <=22 character strings without needing to allocate (in 64 bit mode at least) (look up short string optimization), 22 characters is actually quite a lot in the context of tokenization, so its not a given that switching to string views would be an improvement here
- zabzonk 4y ago> std::string can store <=22 character strings without needing to allocate implementation dependent - the c++ standard says nothing on this
- TylerGlaiel 4y agosure but this is how pretty much every implementation does it these days, so you should be able to safely rely on that (or just drop in your own version that provides that guarantee if you are really concerned about it)
- Calavar 4y agoI would expect that std::string_view would still be significantly faster. Copying or moving an std::string with small string optimization is likely going to boil down to a branch (to check if the instance is using the small string optimization) and a memcpy. As opposed to copying or moving an std::string_view, which should be two MOV instructions.
- jeffbee 4y agoI don’t see why moving std::string needs to branch. You just copy the source and then zero it out, unconditionally.
- ckennelly 4y agoIt depends on your STL implementation's representation of string: https://godbolt.org/z/nMYGYoWbq https://godbolt.org/z/nMYGYoWbq * libstdc++ has an internal reference to its own address for the SSO. If the moved-from string was referencing its SSO buffer, the moved-to string needs to use its own address. The branch is differentiating the SSO state from a heap-allocated state. * libc++ string move can be implemented this way, but the branch ends up happening on access to the string. It still needs to discard the old heap allocated buffer, if need-be as well.
- ddtaylor 4y agoI looked at the original code from Part 1 and it really makes me confused at why you would implement most of this in this way - even if your goal is to simply test the bottlenecks of various STL implementations. I don't think it's a terrible series and I think the author has the right idea, but the choices in implementing things like taking in a large string and returning a large string when you're basically saying the use case is CSV record parsing is strange.