6 ms·

Effortless Performance Improvements in C++: std:vector

• adzm 4y ago
  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.
  • jstimpfle 4y ago
    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.
    • dataflow 4y ago
      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.
      • jstimpfle 4y ago
        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.
        • dataflow 4y ago
          > 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.
          • jstimpfle 4y ago
            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.
            • dataflow 4y ago
              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.
              • jstimpfle 4y ago
                Well you're clearly wrong and I've explained why.
                • dataflow 4y ago
                  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.
    • vitus 4y ago
      The less space-efficient but more cpu-efficient alternative is to store an offset and a length. Which is, in essence, a string_view.
      • jstimpfle 4y ago
        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.
        • sagarm 4y ago
          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.
          • jstimpfle 4y ago
            Where did I mention standard library? > It works well for its intended purpose. The intended purpose is quite general. Which admits other, better solutions in specific applications.
• 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 ago
    I 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 ago
    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.
  • rhdunn 4y ago
    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.
  • quadrature 4y ago
    based on the final paragraph i'm guessing this will be the next blogpost in the series.
  • returningfory2 4y ago
    A 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.
• vitus 4y ago
  IMO any discussion of std::vector::reserve should be accompanied by warnings that it can actually make your program slower if used improperly. https://en.cppreference.com/w/cpp/container/vector/reserve 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.
  • einpoklum 4y ago
    > The cost of vector dynamic reallocation has gone down dramatically since C++11 introduced move constructors 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.
    • vitus 4y ago
      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.
• peterept 4y ago
  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).
  • jeffbee 4y ago
    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.
    • jstimpfle 4y ago
      To prevent any misunderstandings, programming C using strtok is a mistake too.
  • jstimpfle 4y ago
    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?
• beached_whale 4y ago
  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
• deleted 4y ago
  [deleted]
• camel-cdr 4y ago
  A bunch of, if not all of, the optimizations mentioned here have already been implemented in the repo [0], the blog is just trying to catch up. [0] https://github.com/mediakind-video/effortless-performance-improvements-cpp/tree/master/lib/src https://github.com/mediakind-video/effortless-performance-im...
• Karellen 4y ago
  From the article, the proposed change: -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.
  • woodruffw 4y ago
    At `-O1` and higher, `clang` recognizes the `reserve()` pattern and turns it into the reserving constructor[1]. GCC does the same[2]. [1]: https://godbolt.org/z/Tjazsd686 https://godbolt.org/z/Tjazsd686 [2]: https://godbolt.org/z/7nWEe1d4b https://godbolt.org/z/7nWEe1d4b
  • WirelessGigabit 4y ago
    Not the same. Your version creates a vector with 4 times the default of std::string. #include <string> #include <iostream> #include <vector> template < typename T > std::ostream & operator<< (std::ostream & s, const std::vector < T > &v) { s.put ('['); char comma[3] = { '\0', ' ', '\0' }; for (const auto & e:v) { s << comma << e; comma[0] = ','; } return s << ']'; } int main () { std::vector < std::string > with_reservation; with_reservation.reserve (4); std::cout << "with_reservation: " << with_reservation << std::endl;; std::vector < std::string > via_ctor (4); std::cout << "via_ctor: " << via_ctor << std::endl;; return 0; } Yields with_reservation: [] via_ctor: [, , , ] https://onlinegdb.com/GUlVHoqC5z https://onlinegdb.com/GUlVHoqC5z
• user32456 4y ago
  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?
  • LordDragonfang 4y ago
    Not exactly the same, but there's this, previously seen on HN: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times... https://news.ycombinator.com/item?id=26296339 https://news.ycombinator.com/item?id=26296339
• not2b 4y ago
  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.