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

11–20 of 55 posts

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

#11

Post by rhdunn »

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…

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.

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

#12

Post by quadrature »

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…

based on the final paragraph i'm guessing this will be the next blogpost in the series.

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

#14

Post by returningfory2 »

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…

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 tokens = tokenize(line);
        // do work with tokens
    }
which you could change to

    std::vector 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.

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

#15

Post by jstimpfle »

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…

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.

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

#16

Post by jstimpfle »

peterept wrote: post #6

To avoid memory allocations, and if you can modify the source string in place, then an alternative is to return std::vector 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).

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?

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

#17

Post by jstimpfle »

jeffbee wrote: post #9
peterept wrote: post #6

To avoid memory allocations, and if you can modify the source string in place, then an alternative is to return std::vector 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.

To prevent any misunderstandings, programming C using strtok is a mistake too.

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

#18

Post by TylerGlaiel »

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 would be an improvement here

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

#19

Post by jstimpfle »

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.

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

#20

Post by vitus »

einpoklum wrote: post #10
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…

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

Post reply on HN