Effortless Performance Improvements in C++: std:vector • Hacker News Board

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

#51

Post by vitus » Thu, Mar 09, 2023, 1:42 AM UTC

sagarm wrote: post #46

dataflow wrote: post #39

Earlier quoted context omitted.

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.

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

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

#52

Post by Calavar » Thu, Mar 09, 2023, 4:39 AM UTC

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…

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.

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

#53

Post by jeffbee » Thu, Mar 09, 2023, 2:36 PM UTC

Calavar wrote: post #52

TylerGlaiel wrote: post #18

Earlier quoted context omitted.

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

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.

I don’t see why moving std::string needs to branch. You just copy the source and then zero it out, unconditionally.

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

#54

Post by ckennelly » Fri, Mar 10, 2023, 4:44 AM UTC

jeffbee wrote: post #53

Calavar wrote: post #52

Earlier quoted context omitted.

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.

I don’t see why moving std::string needs to branch. You just copy the source and then zero it out, unconditionally.

It depends on your STL implementation's representation of string: 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.

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

#55

Post by TylerGlaiel » Fri, Mar 10, 2023, 8:11 AM UTC

Calavar wrote: post #52

TylerGlaiel wrote: post #18

Earlier quoted context omitted.

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

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.

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)