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

41–50 of 55 posts

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

#41

Post by TylerGlaiel »

zabzonk wrote: post #21
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…

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

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)

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

#42

Post by ddtaylor »

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…

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.

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

#43

Post by dataflow »

jstimpfle wrote: post #36
dataflow wrote: post #35

Earlier quoted context omitted.

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.

Well you're clearly wrong and I've explained why.

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.

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

#44

Post by not2b »

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.

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

#45

Post by sagarm »

jstimpfle wrote: post #34
vitus wrote: post #32

Earlier quoted context omitted.

The less space-efficient but more cpu-efficient alternative is to store an offset and a length. Which is, in essence, a string_view.

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

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.

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

#46

Post by sagarm »

dataflow wrote: post #39
sagarm wrote: post #38

Earlier quoted context omitted.

> subtle and awful footgun push_back and emplace_back already give you geometric growth; reserve is supposed to circumvent 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.

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

#47

Post by jstimpfle »

dataflow wrote: post #43
jstimpfle wrote: post #36

Earlier quoted context omitted.

Well you're clearly wrong and I've explained why.

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

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

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

#48

Post by [deleted] »

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.

[deleted]

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

#49

Post by dataflow »

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.

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.

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

#50

Post by jstimpfle »

sagarm wrote: post #45
jstimpfle wrote: post #34

Earlier quoted context omitted.

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

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

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.

Post reply on HN