Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Effortless Performance Improvements in C++: std:vector

julien.jorge.st

Post reply on HN
Print view View original

21–30 of 55 posts

Re: Effortless Performance Improvements in C++: std:vector

#21

Post by zabzonk »

TylerGlaiel wrote: post #18
cmovq wrote: post #3

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 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…

> 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 w…

> std::string can store implementation dependent - the c++ standard says nothing on this

Re: Effortless Performance Improvements in C++: std:vector

#23

Post by jeffbee »

vitus wrote: post #20
einpoklum wrote: post #10

Earlier quoted context omitted.

> 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.

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 progr…

> 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.

Re: Effortless Performance Improvements in C++: std:vector

#24

Post by Karellen »

From the article, the proposed change:

     -3,6 +3,8
     std::vector tokenize(const std::string& s)
     {
       std::vector 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 tokenize(const std::string& s)
     {
    -  std::vector result;
    +  // Expect four fields or less in our input.
    +  std::vector 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.

Re: Effortless Performance Improvements in C++: std:vector

#25

Post by dataflow »

jstimpfle wrote: post #19
adzm wrote: post #2

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.

Re: Effortless Performance Improvements in C++: std:vector

#26

Post by dataflow »

vitus wrote: post #5

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 > 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 caus…

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.

Re: Effortless Performance Improvements in C++: std:vector

#27

Post by WirelessGigabit »

Karellen wrote: post #24

From the article, the proposed change: -3,6 +3,8 std::vector tokenize(const std::string& s) { std::vector 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 tokenize(const std::string& s) { - std::vector result; + // Expect four fields or less in our input. + std::vector result(4); std…

Not the same. Your version creates a vector with 4 times the default of std::string.

    #include 
    #include 
    #include 

    template 
        std::ostream & operator &v)
    {
        s.put ('[');
        char comma[3] = { '\0', ' ', '\0' };
        for (const auto & e:v)
        {
            s  with_reservation;
        with_reservation.reserve (4);
        std::cout  via_ctor (4);
        std::cout
Yields

    with_reservation: []
    via_ctor: [, , , ]
https://onlinegdb.com/GUlVHoqC5z

Re: Effortless Performance Improvements in C++: std:vector

#28

Post by jstimpfle »

dataflow wrote: post #25
jstimpfle wrote: post #19

Earlier quoted context omitted.

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.

Re: Effortless Performance Improvements in C++: std:vector

#29

Post by vitus »

jeffbee wrote: post #23
vitus wrote: post #20

Earlier quoted context omitted.

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 progr…

> 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.

Re: Effortless Performance Improvements in C++: std:vector

#30

Post by woodruffw »

Karellen wrote: post #24

From the article, the proposed change: -3,6 +3,8 std::vector tokenize(const std::string& s) { std::vector 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 tokenize(const std::string& s) { - std::vector result; + // Expect four fields or less in our input. + std::vector result(4); std…

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

[2]: https://godbolt.org/z/7nWEe1d4b

Post reply on HN