I also love using flat_map etc which implements a map as a sorted vector. Look up is blazing fast. And perhaps surprisingly, allocating a new vector and copying everything over is actually pretty fast too.
The best "look up" of tokens is to just lex them given an offset into the source file. No need to have a permanent token storage. It's a waste of space.
That's not as cache-friendly. The "best" way in terms of performance is probably to intern them adjacently in a single string, then have offsets into that.
That would be a consideration if you'd have to frequently scan the tokens linearly. But I can't think of a scenario where you'd want to do that at all. And if you've got such a situation, I would say that indexing into the original file contents is pretty close to optimal in terms of cache. Because tokens are already extremely close in the source code, optimizing for a source where they are spaced wide out seems silly.
In many scenarios you need token spans / token strings only for diagnostics, in other words you almost never need them. When any individual data item is rarely looked up, being economical about memory footprint will in fact improve your overall cache hit rate. You only want to store enough information to retrieve the tokens just in case, so storing file offsets is exactly the right call.
> That would be a consideration if you'd have to frequently scan the tokens linearly. But I can't think of a scenario where you'd want to do that at all.
Joining them has nothing to do with linear scanning. Binary search or anything else will still be cache friendlier by having them be adjacent rather than spread apart.
There are also additional advantages I didn't mention. e.g., you can combine strings from multiple files (and throw away the files) without needing to track or care where they came from. They're not performance-related though.
And no, I'm not saying you should do this everywhere. Use what makes sense for your situation.
You still haven't explained what you want to do with the data, so suggesting any particular storage is pointless. I can't imagine why you'd want to binary search a set of tokens (or token strings for that matter), it seems kinda silly. A frequent application of search is binding identifiers to definitions by walking scope-chains, but that's something different than simply a list of tokens.
I'm saying literally anything you want to do with them is faster due to cache locality if they're closer together than farther apart as with the file offset proposal.
I don't even see anywhere where what I wrote is wrong, let alone clearly so. The whole discussion was about string containers, how fast lookups are, etc. and I was talking about how anything you want to do with the strings is faster if they're closer together. I also said you shouldn't that if that doesn't make sense for your situation. Your "you're wrong" comment was that the program can end up slower when you collect the strings but don't use them... which was completely beside the point and ignored the actual point I was making. It was kind of strange too, given the parent you originally replied to said nothing about their use case, and apparently you just picked and assumed the only real use case for string lookups is diagnostic offsets.
You're making statements that are unspecific and generalizing ("anything you want to do"), while I've presented an explanation why the "cache-efficient" storage optimization may in fact be a pessimization for common token access patterns, because the cost of additional resource consumption can outweigh any marginal benefits this may have for access times of rarely used data.
> The whole discussion was about string containers, how fast lookups are, etc
No, it was about token storage.
> Your "you're wrong" comment was that the program can end up slower when you collect the strings but don't use them
No, it was assuming common access patterns of token data in parsers, which aren't "you don't use them" but "you rarely access them, likely only once when parsing but on rare occasion you have to refer back to specific tokens later".
Note that a string view only gives you the token text, not the token in general (like, most importantly, the token type, i.e. identifier, string literal, integer literal, keywords, etc). So the additional length information that's contained in the file doesn't help much, you'll have to lex again anyway, unless you're only interested in the text.
Apart from that -- a string view is typically understood as being implemented using a pointer to the string buffer, which is something else -- a pointer is 64 bits instead of 32 bit (on most systems, of course). And it requires the source file to be cached in memory at a stable location, can't be serialized and deserialized, etc. etc.
In short, it's the typical fashionable modern C++ approach that is also wrong.
What would be the point of adding a string as int32 offset/size pair to the standard library? It would be meaningless without supporting infrastructure to link it to a backing buffer, and it can't represent strings over 4GB. If it's something that you can make work, declaring the typedef or struct is trivial.
string_view is a useful general purpose tool that implements the std::string API for e.g. taking strings of various types in general purpose function signatures. Obviously it's not meant to be serialized and deserialized. It works well for its intended purpose.
The two are not mutually exclusive: you could turn your 32-bit offset/length pair into a string_view to pass to functions that operate in the context of a single string.
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.
Right? 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.
That 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.
Just 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.
> 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
sure 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)
I 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.
* 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.
string view is theoretically going to be faster, but its the type of thing you'd really need to profile in actual context to see to what extent that is true or not. I was mainly just pointing out that (small) strings are actually way faster than people would think since they don't actually need to allocate memory
if I was actually tasked with hyper-optimizing a tokenizer I would probably skip past string view and do a pair of U16 indexes instead assuming the input file is less than 65k characters [with a "slow path" that uses U32 instead]. I just think that its probably not actually going to be a whole order of magnitude faster than just using string (unless there's long tokens)
I 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.
> Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing the capacity to grow linearly rather than exponentially) and result in increased computational complexity and decreased performance.
The cost of vector dynamic reallocation has gone down dramatically since C++11 introduced move constructors -- the example of a vector<string> actually uses std::move (which is comparable to copying 3 pointers, as opposed to the pointed-to allocation of the underlying string). Of course, that specific case relies on std::string's move constructor being defined as noexcept. So, when used properly, reserve will speed up your program, just often not as much as you might expect.
Vector reallocations result in an average of one* move (which yes, is effectively a copy for types like string_view) per element under normal operation. If you're concerned about that single copy (primarily: if profiling has demonstrated that this is a real bottleneck), and you know the target size a priori, then yes, by all means, use reserve.
Just be warned that if you do it wrong, you can literally make your program exponentially slower. And, that it's less imperative to do so now than it was 15 years ago.
(I'm personally much less concerned about the cost of copying 16B from a string_view, than I am about copying 24B + arbitrary amounts of underlying storage from a string.)
* Yes, I know, elements at the beginning of the vector will be moved/copied more often than elements at the end.
> arbitrary amounts of underlying storage from a string
The whole point of move construction is that moving a string is almost as cheap as moving a string_view. The moved-to string now owns the external storage and the moved-from string does not.
Exactly, which is why I haven't worried about it ever since I started working with C++11. It was certainly the case that reserve was critical back in the C++03 days, though.
I literally ran into this some 2-3 days ago. It's a subtle and awful footgun. I don't see why they couldn't mandate geometric growth and have reserve_exact or something for this.
Not really. Not every problem is that simple. For example sometimes you need to know that insertion will not allocate and/or move data around at the wrong point, so you need to reserve() beforehand despite not knowing the final size.
If I want pointer stability, I usually use resize() + operator[] instead of reserve, though of course this requires a cheap default constructor. reserve + push_back feels more likely to subtly rather than loudly break due to future changes.
Is resize() guaranteed to respect geometric growth? I know it has for me in practice, but this made me question everything. And more generally, it's nice when you can do that, but it's not a substitute. From an API standpoint it seems really weird for reserve() and resize() to differ in what they set the target capacity to - the natural thing would seem to be that they should only differ in the initialization + resizing, not in the reservation.
If you want pointer stability, then reserve + push_back is sufficient to avoid reallocations, if you have an upper bound on the final size (which you need anyways to use resize effectively). Else, you should probably be storing a vector<unique_pointer<T>> which has its own downsides (mostly around locality).
Side note: vector::operator[] is UB for out-of-bounds access; if your goal is for something to break loudly, you should be using vector::at().
To avoid memory allocations, and if you can modify the source string in place, then an alternative is to return std::vector<char*> and modify the string to replace the separators with '\0'.
Of course, as that post suggests, use reserve() to encourage having the vector itself as optimal as possible. (In my strsplit call I pass it in as optional so each caller can optimize it).
That's just strtok, and programming C++ as if you are an unreformed C programmer is always a mistake. If you want to not copy the strings, string_view. We also have std::split and std::views::split etc.
As a general rule, don't overwrite your input data. That's a hardcore space optimization that can end up making your program slower. At the minimum it will lead to headaches later on. Are you sure you won't need the pristine input for diagnostic and error messages later on? Do you always have at least 1 separator character to overwrite in the first place?
With vector for trivial things, push_back is almost always slower than resizing and then trimming down if needed. The memset to zero it out is minuscule to the cost of push_back. Guess if you don't know how many and it will probably be faster. if you run out, do another block
-3,6 +3,8
std::vector<std::string> tokenize(const std::string& s)
{
std::vector<std::string> result;
+ // Expect four fields or less in our input.
+ result.reserve(4);
std::string::size_type f = 0;
std::string::size_type p = s.find(':');
I wonder why not:
-3,6 +3,7
std::vector<std::string> tokenize(const std::string& s)
{
- std::vector<std::string> result;
+ // Expect four fields or less in our input.
+ std::vector<std::string> result(4);
std::string::size_type f = 0;
std::string::size_type p = s.find(':');
?
It's not a big difference, but vectors have a constructor that takes an initial reservation size in order to facilitate pre-allocation.
Edit: No it doesn't. I've not written C++ in anger in... actually quite a bit longer than I thought. And it shows. Doh. Thanks, wirelessgigabit.
This one was kind of short but I'm enjoying following along this series. Does anyone have any blog/other reading recommendations that are similar to these posts, e.g. performance-learning related?
The article suggests that an std::vector allocates just barely enough memory to hold its elements. No real implementation (from GNU, clang or MSoft) works that way, because it would make a loop like
for (const auto& value : some_container)
my_vector.push_back(value);
quadratic in the number of elements. To get linear time, when a reallocation occurs extra memory has to be allocated; we might double the allocated storage each time, or use Fibonacci numbers and get about a 1.6 ratio.
An early implementation of Microsoft Foundation Classes (pre-STL) had this bug: repeatedly appending one character at a time to a string had quadratic cost, because they got this wrong. I used to include a version of this as an interview question: how do you grow a dynamically allocated buffer, and what happens if you do it wrong.
It's true that if you know exactly how many elements you need you can reserve that space in one call. But doing this wrong (always allocating exactly what you need, no spare capacity) can sometimes increase the number of allocations you need.
54 comments
[ 8.2 ms ] story [ 154 ms ] threadIn many scenarios you need token spans / token strings only for diagnostics, in other words you almost never need them. When any individual data item is rarely looked up, being economical about memory footprint will in fact improve your overall cache hit rate. You only want to store enough information to retrieve the tokens just in case, so storing file offsets is exactly the right call.
Joining them has nothing to do with linear scanning. Binary search or anything else will still be cache friendlier by having them be adjacent rather than spread apart.
There are also additional advantages I didn't mention. e.g., you can combine strings from multiple files (and throw away the files) without needing to track or care where they came from. They're not performance-related though.
And no, I'm not saying you should do this everywhere. Use what makes sense for your situation.
> The whole discussion was about string containers, how fast lookups are, etc
No, it was about token storage.
> Your "you're wrong" comment was that the program can end up slower when you collect the strings but don't use them
No, it was assuming common access patterns of token data in parsers, which aren't "you don't use them" but "you rarely access them, likely only once when parsing but on rare occasion you have to refer back to specific tokens later".
Apart from that -- a string view is typically understood as being implemented using a pointer to the string buffer, which is something else -- a pointer is 64 bits instead of 32 bit (on most systems, of course). And it requires the source file to be cached in memory at a stable location, can't be serialized and deserialized, etc. etc.
In short, it's the typical fashionable modern C++ approach that is also wrong.
string_view is a useful general purpose tool that implements the std::string API for e.g. taking strings of various types in general purpose function signatures. Obviously it's not meant to be serialized and deserialized. It works well for its intended purpose.
The two are not mutually exclusive: you could turn your 32-bit offset/length pair into a string_view to pass to functions that operate in the context of a single string.
> It works well for its intended purpose.
The intended purpose is quite general. Which admits other, better solutions in specific applications.
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.
for( auto value : from_csv( str ) ) { … }
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
implementation dependent - the c++ standard says nothing on this
* 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.
if I was actually tasked with hyper-optimizing a tokenizer I would probably skip past string view and do a pair of U16 indexes instead assuming the input file is less than 65k characters [with a "slow path" that uses U32 instead]. I just think that its probably not actually going to be a whole order of magnitude faster than just using string (unless there's long tokens)
https://en.cppreference.com/w/cpp/container/vector/reserve
> Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing the capacity to grow linearly rather than exponentially) and result in increased computational complexity and decreased performance.
The cost of vector dynamic reallocation has gone down dramatically since C++11 introduced move constructors -- the example of a vector<string> actually uses std::move (which is comparable to copying 3 pointers, as opposed to the pointed-to allocation of the underlying string). Of course, that specific case relies on std::string's move constructor being defined as noexcept. So, when used properly, reserve will speed up your program, just often not as much as you might expect.
1. It's gone down, but it's still very high.
2. It hasn't gone down for types types like std::string_view, for which moving and copying take about the same amount of effort.
Just be warned that if you do it wrong, you can literally make your program exponentially slower. And, that it's less imperative to do so now than it was 15 years ago.
(I'm personally much less concerned about the cost of copying 16B from a string_view, than I am about copying 24B + arbitrary amounts of underlying storage from a string.)
* Yes, I know, elements at the beginning of the vector will be moved/copied more often than elements at the end.
The whole point of move construction is that moving a string is almost as cheap as moving a string_view. The moved-to string now owns the external storage and the moved-from string does not.
push_back and emplace_back already give you geometric growth; reserve is supposed to circumvent this.
Side note: vector::operator[] is UB for out-of-bounds access; if your goal is for something to break loudly, you should be using vector::at().
Of course, as that post suggests, use reserve() to encourage having the vector itself as optimal as possible. (In my strsplit call I pass it in as optional so each caller can optimize it).
[0] https://github.com/mediakind-video/effortless-performance-im...
It's not a big difference, but vectors have a constructor that takes an initial reservation size in order to facilitate pre-allocation.
Edit: No it doesn't. I've not written C++ in anger in... actually quite a bit longer than I thought. And it shows. Doh. Thanks, wirelessgigabit.
[1]: https://godbolt.org/z/Tjazsd686
[2]: https://godbolt.org/z/7nWEe1d4b
https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
https://news.ycombinator.com/item?id=26296339
for (const auto& value : some_container) my_vector.push_back(value);
quadratic in the number of elements. To get linear time, when a reallocation occurs extra memory has to be allocated; we might double the allocated storage each time, or use Fibonacci numbers and get about a 1.6 ratio.
An early implementation of Microsoft Foundation Classes (pre-STL) had this bug: repeatedly appending one character at a time to a string had quadratic cost, because they got this wrong. I used to include a version of this as an interview question: how do you grow a dynamically allocated buffer, and what happens if you do it wrong.
It's true that if you know exactly how many elements you need you can reserve that space in one call. But doing this wrong (always allocating exactly what you need, no spare capacity) can sometimes increase the number of allocations you need.