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

31–40 of 55 posts

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

#31

Post by dataflow »

jstimpfle wrote: post #28
dataflow wrote: post #25

Earlier quoted context omitted.

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

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

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

#32

Post by vitus »

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.

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

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

#33

Post by jstimpfle »

dataflow wrote: post #31
jstimpfle wrote: post #28

Earlier quoted context omitted.

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

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

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.

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

#34

Post by jstimpfle »

vitus wrote: post #32
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.

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

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

#35

Post by dataflow »

jstimpfle wrote: post #33
dataflow wrote: post #31

Earlier quoted context omitted.

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

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.

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.

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

#36

Post by jstimpfle »

dataflow wrote: post #35
jstimpfle wrote: post #33

Earlier quoted context omitted.

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.

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.

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

#38

Post by sagarm »

dataflow wrote: post #26
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.

> subtle and awful footgun

push_back and emplace_back already give you geometric growth; reserve is supposed to circumvent this.

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

#39

Post by dataflow »

sagarm wrote: post #38
dataflow wrote: post #26

Earlier quoted context omitted.

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.

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

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

#40

Post by LordDragonfang »

user32456 wrote: post #37

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?

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

https://news.ycombinator.com/item?id=26296339

Post reply on HN