4 ms·

The API design of STL is often over-constrained. That is, The style is very kitchen-sink and generalized, which means implementers have little flexibility. Ev

by chubot 3y ago

The API design of STL is often over-constrained. That is, The style is very kitchen-sink and generalized, which means implementers have little flexibility. Every “real” C++ codebase I’ve worked on has its own data structures for most things. And that’s a feature of C++, not a bug. For example, don’t use std::unordered_map for anything performance sensitive. It’s a shockingly slow hash table because the interface constrains it to allocate a lot. The STL isn’t designed for optimum performance. It’s easy to do better by satisfying your app’s requirements and nothing else.

vlovich123 3y ago
There’s also other reasons. For example, take binary search: * prefetch + cmov. These should be part of the STL but languages and compilers struggle to emit the cmov properly (Rust’s been broken for 6 years: https://github.com/rust-lang/rust/issues/53823 https://github.com/rust-lang/rust/issues/53823). Prefetch is an interesting one because while you do optimize the binary search in a micro benchmark, you’re potentially putting extra pressure on the cache with “garbage” data which means it’s a greedy optimization that might hurt surrounding code. Probably should have separate implementations as binary search isn’t necessarily always in the hot path. * Eytzinger layout has additional limitations that are often not discussed when pointing out “hey this is faster”. Adding elements is non-trivial since you first have to add + sort (as you would for binary search) and then rebuild a new parallel eytzinger layout from scratch (i.e. you’d have it be an index of pointers rather than the values themselves which adds memory overhead + indirection for the comparisons). You can’t find the “insertion” position for non-existent elements which means it can’t be used for std::lower_bound (i.e. if the element doesn’t exist, you just get None back instead of Err(position where it can be slotted in to maintain order). Basically, optimizations can sometimes rely on changing the problem domain so that you can trade off features of the algorithm against the runtime. These kinds of algorithms can be a bad fit for a standard library which aims to be a toolbox of “good enough” algorithms and data structures for problems that appear very very frequently. Or they could be part of the standard library toolkit just under a different name but you also have to balance that against maintenance concerns.
derefr 3y ago
Is there a statically-compiled language where the subset of methods of an API or ADT that ever get referenced, determines at link time which implementation of the API or ADT gets linked + WPOed against? Because it seems “obvious” to enable programs that don’t depend on the over-constraining parts of things like std::unordered_map, to specialize the implementation they’re using so that it doesn’t employ the overhead-laden parts required to make those uncalled methods function. And “just have two copies of the code and pick between them based on control-flow info” seems like a very trivial way to do it for at least some low-hanging-fruit cases.

by chubot 3y ago

vlovich123 3y ago

There’s also other reasons. For example, take binary search: * prefetch + cmov. These should be part of the STL but languages and compilers struggle to emit the cmov properly (Rust’s been broken for 6 years: https://github.com/rust-lang/rust/issues/53823 https://github.com/rust-lang/rust/issues/53823). Prefetch is an interesting one because while you do optimize the binary search in a micro benchmark, you’re potentially putting extra pressure on the cache with “garbage” data which means it’s a greedy optimization that might hurt surrounding code. Probably should have separate implementations as binary search isn’t necessarily always in the hot path. * Eytzinger layout has additional limitations that are often not discussed when pointing out “hey this is faster”. Adding elements is non-trivial since you first have to add + sort (as you would for binary search) and then rebuild a new parallel eytzinger layout from scratch (i.e. you’d have it be an index of pointers rather than the values themselves which adds memory overhead + indirection for the comparisons). You can’t find the “insertion” position for non-existent elements which means it can’t be used for std::lower_bound (i.e. if the element doesn’t exist, you just get None back instead of Err(position where it can be slotted in to maintain order). Basically, optimizations can sometimes rely on changing the problem domain so that you can trade off features of the algorithm against the runtime. These kinds of algorithms can be a bad fit for a standard library which aims to be a toolbox of “good enough” algorithms and data structures for problems that appear very very frequently. Or they could be part of the standard library toolkit just under a different name but you also have to balance that against maintenance concerns.

derefr 3y ago

Is there a statically-compiled language where the subset of methods of an API or ADT that ever get referenced, determines at link time which implementation of the API or ADT gets linked + WPOed against? Because it seems “obvious” to enable programs that don’t depend on the over-constraining parts of things like std::unordered_map, to specialize the implementation they’re using so that it doesn’t employ the overhead-laden parts required to make those uncalled methods function. And “just have two copies of the code and pick between them based on control-flow info” seems like a very trivial way to do it for at least some low-hanging-fruit cases.