7 ms·

I know it's probably hyperbole, but why > yes, I know, friends don’t let friends use STL, but that is a topic for another discussion ? Are there known shortc

I know it's probably hyperbole, but why > yes, I know, friends don’t let friends use STL, but that is a topic for another discussion ? Are there known shortcomings with the standard library in C++?

deleted 2y ago
[deleted]
mrcode007 2y ago
No. It’s a trope. Most people can’t tell the difference. It’s highly context and application specific.
- olliej 2y ago
  Yeah the bulk of the time it doesn’t matter. The only places it really matters are if you have stronger perf requirements, or dislike stupid amounts of UB.
unwind 2y ago
I noticed the post was tagged with 'gamedev' which might be relevant, STL used to be hard to optimize due to it doing lots of heap allocations. It has been a while since I was in gamedev so perhaps not true anymore but sometimes these things change slowly with people/culture.
fyrn_ 2y ago
It has some pretty bad containers, specifically unordered_map and map, and set. There are some good talks on why from ccp con and other varius developer cons. They are still usable mind you, just it's also true that unordered_map is slower then JS or Python hashmaps in some situations because of some really questionable design choices (exposing bucket nodes, overly restrictive iterator invalidation requirements, etc..)
- krackers 2y ago
  What's the recommended drop-in replacement? absl::flat_map?
  - dataflow 2y ago
    One of the Abseil containers if you really need an associative container to begin with, but honestly often you can play quite a few tricks with just plain arrays if you get a little creative, with better performance profiles...
  - tialaramex 2y ago
    You almost certainly don't need a "drop-in replacement" which is part of the problem. If you really just need a hash table, Abseil, Boost and Folly all provide several good options to suit your needs, and if you have a favourite utility library that's not one of those three it probably has at least one hash table type. A "drop-in replacement" would commit to all the weird things about the standard library type which result in poor performance, some of them might be important to you, and you'll probably insist oh, it's not a "drop-in" replacement if I can't have those, and across the entire C++ population that means there is no high performance drop-in replacement, the type guarantees any number of weird properties and you could depend on all those, so, too bad. The most likely reliance you'd have is reference stability, maybe you give out references to items in the table and they're long lived so you mustn't invalidate them when/ if there's a resize, let alone on unrelated changes to a table which keeps the same size. Abseil, Boost and Folly all provide types which lose some performance to get this back if it's all you need to be "drop-in". The most unlikely reliances are two fold, firstly maybe you insist on messing with the bucket API, which makes no sense in open addressed tables (ie all the ones with great performance). In this case you're wedded to std::unordered_map because the details of how the type is structured are welded into your code. Sucks to be you. Secondly though, you might have decided you care about the order, the std::unordered_map says it doesn't promise an order, but on a single platform none of the implementations actually kick you if you assume the order is preserved, so you can merrily write a unit test which checks that after adding fake users Alice, Bob and Carol to your user hash table, when asked for the users back in no particular order you get exactly: Carol, Alice, Bob. Is that a good unit test? No. But the replacements will make it go red, they're not "drop-in" replacements.
- tialaramex 2y ago
  I've watched a few talks about the STL containers. I don't think they're savage enough. In particular the C++ growable array type std::vector is often cited as good. Is it terrible? No. But it's still not actually as good as it should be, we can easily do better if we provide the proper API. Growable arrays are a very popular idea. Your preferred language almost certainly has them, but they might be built in to the language as an optimisation, if "normal" arrays in your language can grow and that's fast enough, chances are you're got the growable array type just as the only array, which is fine (but won't fly on tiny embedded systems). This type has amortized O(1) aka constant time growth, which is one of those tricks which is amazing if you've never seen it before, then it just seeps into your understanding of the world and so it's easy to imagine why C++ doesn't do any better. As a necessary optimisation beyond the amortized growth we must be able to tell a growable array hints about its future size. The only hint provided in the C++ STL is reserve, which tells the array its maximum final size. Rust calls this hint Vec::reserve_exact, if our array isn't this big, we should grow immediately, makes sense. Here's where the problem kicks in: Suppose I don't know the maximum final size, but I do know I need to put say, at least 50 more things in the container? Algorithmically the answer is actually yes, the amortized growth can be preserved if we either grow sooner or skip growth steps and otherwise the hint can be ignored, this is Rust's Vec::reserve If we try to use the C++ reserve here (aka Vec::reserve_exact) even though this isn't the final size, we destroy our amortized growth performance, our container may have lousy performance. If we just don't bother because we can't express our hint, our container has worse performance than necessary because we grow more often or less optimally.
  - mandarax8 2y ago
    Easily solved manually reserving exponentially. All my projects use some variation of this: https://github.com/facebook/folly/blob/9f125c94e10fd01f5567cdbc317f8026de3a20b5/folly/container/Reserve.h#L49 https://github.com/facebook/folly/blob/9f125c94e10fd01f5567c... But I've burned myself on this a few times before.
    - jstimpfle 2y ago
      resize(size() + N), resize(size() - N) should do the trick too, unless default constructing your elements is costly or not defined. But I wonder what use case there is where you can't just push_back() one by one? The only potential issue here is that there might be a reallocation happening while append this range of N elements, but can't imagine what might break.
deleted 2y ago
[deleted]
bowsamic 2y ago
STL has been both historically and recently slow in many ways. Many game devs are making their own engine, especially historically, so they just implement their own version of STL in the way they want. Or they use another engine which has made its own replacement. Even Andreas of SerenityOS made his own entire STL (and also his own Objective-C like class system). The C++ STL is probably one of the most commonly avoided standard libraries of any language. I can’t think of another that is so often replaced by bespoke code
- brabel 2y ago
  When I was learning C++ in 2008, I remember people telling me STL was one of the greatest accomplishments in computer science.
  - flohofwoe 2y ago
    It always depended on the specific C++ bubble you're in. The stdlib was also controversial back then (even in the late 90's when I started to use C++).
  - bowsamic 2y ago
    Well, 2008 was a long time ago, but back then it was even worse.
  - tialaramex 2y ago
    STL stands for Standard Template Library, which is an important piece of Generic Programming - it provides algorithms which are generic over the container types, so there's one library implementation of say sorting, and you can (but shouldn't) sort a linked list if you want to. When you see people asking why language X doesn't have "generics" this is the feature they're asking about - it's so fundamental now but in the 1990s it wasn't even obvious that you might want to write software this way. Generic Programming had been tried before, but the STL is an important idea and WG21 (the C++ Standards Committee) were persuaded to include it in the requirements for the new ISO standard. However, in C++ because the STL is a big part of their Standard Library, and because Microsoft insists on naming their entire implementation of the Standard Library STL, it's usual to say STL to mean the entire stdlib, even though many parts of it aren't about generic programming at all. So the STL is a crucial idea and inventing that was a tremendous accomplishment - but the C++ stdlib, which may be called "STL" and is in this article, is not a very good realisation of that idea. Indeed I'd argue the C++ programming language isn't a good realisation of that idea either - it was possible to write the STL for C++ and so that's what was done, but knowing this is a good idea you'd design the language differently. And people have.
glandium 2y ago
On top of what sibling comments mention, another common problem is that the STL has many different implementations with different/inconsistent performance profiles. If you want containers with guaranteed performance characteristics, you're better off using your own or a third party.
snovv_crash 2y ago
The algorithms are generally fine, it's the containers which are very heavy on heap allocations, particularly the maps and trees.
dataflow 2y ago
People exaggerate this a lot, but mainly it's just the discontiguous containers (and regexes) that often have better alternatives. They're not bad for what they're trying to accomplish -- they just provide guarantees you often don't need, which results in you paying costs you shouldn't need to.
- swiftcoder 2y ago
  Worth noting that this issue is not unique to the C++ standard library either. Java is saddled with an overly-general HashMap implementation with awful worst-case performance characteristics as well, and older versions of Rust's HashMap had performance problems as well (though these have mostly been addressed).
  - LgWoodenBadger 2y ago
    But Java has ConcurrentHashMap as a drop-in replacement that is better in every way
    - swiftcoder 2y ago
      ConcurrentHashMap is more performant in multi-threaded scenarios (it takes a performance hit versus the regular HashMap when single-threaded). Apart from that, it is fairly similar, and doesn't address the ridiculous rate of cache misses at all
ttfkam 2y ago
I love how all the responses are talking about these arcane footguns that require watching obscure talks to be aware of. Then there's the other segment of C++ programmers talking about how modern C++ is so much better now to the point that Rust and other languages are unnecessary. The cognitive dissonance is intoxicating.
ksherlock 2y ago
std::vector<bool>.

I know it's probably hyperbole, but why > yes, I know, friends don’t let friends use STL, but that is a topic for another discussion ? Are there known shortcomings with the standard library in C++?

deleted 2y ago

[deleted]

mrcode007 2y ago

No. It’s a trope. Most people can’t tell the difference. It’s highly context and application specific.

olliej 2y ago
Yeah the bulk of the time it doesn’t matter. The only places it really matters are if you have stronger perf requirements, or dislike stupid amounts of UB.

unwind 2y ago

I noticed the post was tagged with 'gamedev' which might be relevant, STL used to be hard to optimize due to it doing lots of heap allocations. It has been a while since I was in gamedev so perhaps not true anymore but sometimes these things change slowly with people/culture.

fyrn_ 2y ago

It has some pretty bad containers, specifically unordered_map and map, and set. There are some good talks on why from ccp con and other varius developer cons. They are still usable mind you, just it's also true that unordered_map is slower then JS or Python hashmaps in some situations because of some really questionable design choices (exposing bucket nodes, overly restrictive iterator invalidation requirements, etc..)

krackers 2y ago
What's the recommended drop-in replacement? absl::flat_map?
- dataflow 2y ago
  One of the Abseil containers if you really need an associative container to begin with, but honestly often you can play quite a few tricks with just plain arrays if you get a little creative, with better performance profiles...
- tialaramex 2y ago
  You almost certainly don't need a "drop-in replacement" which is part of the problem. If you really just need a hash table, Abseil, Boost and Folly all provide several good options to suit your needs, and if you have a favourite utility library that's not one of those three it probably has at least one hash table type. A "drop-in replacement" would commit to all the weird things about the standard library type which result in poor performance, some of them might be important to you, and you'll probably insist oh, it's not a "drop-in" replacement if I can't have those, and across the entire C++ population that means there is no high performance drop-in replacement, the type guarantees any number of weird properties and you could depend on all those, so, too bad. The most likely reliance you'd have is reference stability, maybe you give out references to items in the table and they're long lived so you mustn't invalidate them when/ if there's a resize, let alone on unrelated changes to a table which keeps the same size. Abseil, Boost and Folly all provide types which lose some performance to get this back if it's all you need to be "drop-in". The most unlikely reliances are two fold, firstly maybe you insist on messing with the bucket API, which makes no sense in open addressed tables (ie all the ones with great performance). In this case you're wedded to std::unordered_map because the details of how the type is structured are welded into your code. Sucks to be you. Secondly though, you might have decided you care about the order, the std::unordered_map says it doesn't promise an order, but on a single platform none of the implementations actually kick you if you assume the order is preserved, so you can merrily write a unit test which checks that after adding fake users Alice, Bob and Carol to your user hash table, when asked for the users back in no particular order you get exactly: Carol, Alice, Bob. Is that a good unit test? No. But the replacements will make it go red, they're not "drop-in" replacements.
tialaramex 2y ago
I've watched a few talks about the STL containers. I don't think they're savage enough. In particular the C++ growable array type std::vector is often cited as good. Is it terrible? No. But it's still not actually as good as it should be, we can easily do better if we provide the proper API. Growable arrays are a very popular idea. Your preferred language almost certainly has them, but they might be built in to the language as an optimisation, if "normal" arrays in your language can grow and that's fast enough, chances are you're got the growable array type just as the only array, which is fine (but won't fly on tiny embedded systems). This type has amortized O(1) aka constant time growth, which is one of those tricks which is amazing if you've never seen it before, then it just seeps into your understanding of the world and so it's easy to imagine why C++ doesn't do any better. As a necessary optimisation beyond the amortized growth we must be able to tell a growable array hints about its future size. The only hint provided in the C++ STL is reserve, which tells the array its maximum final size. Rust calls this hint Vec::reserve_exact, if our array isn't this big, we should grow immediately, makes sense. Here's where the problem kicks in: Suppose I don't know the maximum final size, but I do know I need to put say, at least 50 more things in the container? Algorithmically the answer is actually yes, the amortized growth can be preserved if we either grow sooner or skip growth steps and otherwise the hint can be ignored, this is Rust's Vec::reserve If we try to use the C++ reserve here (aka Vec::reserve_exact) even though this isn't the final size, we destroy our amortized growth performance, our container may have lousy performance. If we just don't bother because we can't express our hint, our container has worse performance than necessary because we grow more often or less optimally.
- mandarax8 2y ago
  Easily solved manually reserving exponentially. All my projects use some variation of this: https://github.com/facebook/folly/blob/9f125c94e10fd01f5567cdbc317f8026de3a20b5/folly/container/Reserve.h#L49 https://github.com/facebook/folly/blob/9f125c94e10fd01f5567c... But I've burned myself on this a few times before.
  - jstimpfle 2y ago
    resize(size() + N), resize(size() - N) should do the trick too, unless default constructing your elements is costly or not defined. But I wonder what use case there is where you can't just push_back() one by one? The only potential issue here is that there might be a reallocation happening while append this range of N elements, but can't imagine what might break.

deleted 2y ago

[deleted]

bowsamic 2y ago

STL has been both historically and recently slow in many ways. Many game devs are making their own engine, especially historically, so they just implement their own version of STL in the way they want. Or they use another engine which has made its own replacement. Even Andreas of SerenityOS made his own entire STL (and also his own Objective-C like class system). The C++ STL is probably one of the most commonly avoided standard libraries of any language. I can’t think of another that is so often replaced by bespoke code

brabel 2y ago
When I was learning C++ in 2008, I remember people telling me STL was one of the greatest accomplishments in computer science.
- flohofwoe 2y ago
  It always depended on the specific C++ bubble you're in. The stdlib was also controversial back then (even in the late 90's when I started to use C++).
- bowsamic 2y ago
  Well, 2008 was a long time ago, but back then it was even worse.
- tialaramex 2y ago
  STL stands for Standard Template Library, which is an important piece of Generic Programming - it provides algorithms which are generic over the container types, so there's one library implementation of say sorting, and you can (but shouldn't) sort a linked list if you want to. When you see people asking why language X doesn't have "generics" this is the feature they're asking about - it's so fundamental now but in the 1990s it wasn't even obvious that you might want to write software this way. Generic Programming had been tried before, but the STL is an important idea and WG21 (the C++ Standards Committee) were persuaded to include it in the requirements for the new ISO standard. However, in C++ because the STL is a big part of their Standard Library, and because Microsoft insists on naming their entire implementation of the Standard Library STL, it's usual to say STL to mean the entire stdlib, even though many parts of it aren't about generic programming at all. So the STL is a crucial idea and inventing that was a tremendous accomplishment - but the C++ stdlib, which may be called "STL" and is in this article, is not a very good realisation of that idea. Indeed I'd argue the C++ programming language isn't a good realisation of that idea either - it was possible to write the STL for C++ and so that's what was done, but knowing this is a good idea you'd design the language differently. And people have.

glandium 2y ago

On top of what sibling comments mention, another common problem is that the STL has many different implementations with different/inconsistent performance profiles. If you want containers with guaranteed performance characteristics, you're better off using your own or a third party.

snovv_crash 2y ago

The algorithms are generally fine, it's the containers which are very heavy on heap allocations, particularly the maps and trees.

dataflow 2y ago

People exaggerate this a lot, but mainly it's just the discontiguous containers (and regexes) that often have better alternatives. They're not bad for what they're trying to accomplish -- they just provide guarantees you often don't need, which results in you paying costs you shouldn't need to.

swiftcoder 2y ago
Worth noting that this issue is not unique to the C++ standard library either. Java is saddled with an overly-general HashMap implementation with awful worst-case performance characteristics as well, and older versions of Rust's HashMap had performance problems as well (though these have mostly been addressed).
- LgWoodenBadger 2y ago
  But Java has ConcurrentHashMap as a drop-in replacement that is better in every way
  - swiftcoder 2y ago
    ConcurrentHashMap is more performant in multi-threaded scenarios (it takes a performance hit versus the regular HashMap when single-threaded). Apart from that, it is fairly similar, and doesn't address the ridiculous rate of cache misses at all

ttfkam 2y ago

I love how all the responses are talking about these arcane footguns that require watching obscure talks to be aware of. Then there's the other segment of C++ programmers talking about how modern C++ is so much better now to the point that Rust and other languages are unnecessary. The cognitive dissonance is intoxicating.

ksherlock 2y ago

std::vector<bool>.