layout: true name: blank styling: styling.css styling-by: Martin Weitzel .stylehint[ Styled with [{{styling}}]({{styling}}) by {{styling-by}} ] --- layout: true name: plain copyright: (CC) BY-SA branding: [Dipl.-Ing. Martin Weitzel](http://tbfe.de) customer: [für MicroConsult Training & Consulting GmbH](http://microconsult.de) {{header}} .pagefooter[ {{copyright}}: {{branding}} {{customer}} .microconsult-logo[] ] --- layout: true name: linkinfo copyright: (CC) BY-SA branding: [Dipl.-Ing. Martin Weitzel](http://tbfe.de) customer: [für MicroConsult Training & Consulting GmbH](http://microconsult.de) {{header}} .infographic[ [](InfoGraphics/{{graphic}}.png "Click to open – add [CTRL+] SHIFT for new [tabbed] window") ] .pagefooter[ {{copyright}}: {{branding}} {{customer}} .microconsult-logo[] ] --- layout: true name: withinfo copyright: (CC) BY-SA branding: [Dipl.-Ing. Martin Weitzel](http://tbfe.de) customer: [für MicroConsult Training & Consulting GmbH](http://microconsult.de) {{header}} .infolink.right[ [Click here for Info-Graphic {{graphic}}](InfoGraphics/{{graphic}}.png "add [CTRL+] SHIFT for own [tabbed] window") {{section}} ] .pagefooter[ {{copyright}}: {{branding}} {{customer}} .microconsult-logo[] ] --- layout: false template: blank [C++ STL]: 00_topics.html#agenda # [C++ STL] Odds and Ends .center[(Day 2, Optional)] ------------------------------------------------------------------------------- * [Extensions Provided by Boost ](#stl_boost_extensions) * [STL-Concurrency Support ](#stl_concurrency_support) * [STL-Quirks and Shortcomings ](#stl_quirks_and_shortcomings) ------------------------------------------------------------------------------- .center[**NOTE**] This is an optional part with topics loosely connected to the main part of this course, which put the focus on C++ STL Containers and Algorithms. The topics in this part have been moved here as they are still of some interest – if time allows – but might distract from the general picture if covered in the main parts. --- template: plain name: stl_boost_extensions header: ## Extensions Provided by Boost [Boost Platform]: http://www.boost.org From the libraries available on the [Boost Platform], probably the following are the most interesting to augment what is provided in the STL: * With respect to (additional) containers: * [Boost.Bimap ](#boost_bimap) * [Boost.MultiIndex ](#boost_multi_index) * [Boost.PropertyTree ](#boost_property_tree) * With respect to (additional) algorithms: * [Boost.Algorithm ](#boost_algorithm) * With respect to implementing Iterators: * [Boost.Iterator ](#boost_iterator) * As an alternative to the STL iterator interface for algorithms: * [Boost.Range ](#boost_range) --- template: plain name: boost_bimap header: ### Boost.Bimap [Boost.Bimap]: http://www.boost.org/doc/libs/release/libs/bimap/doc/html/index.html [Boost Platform]: http://www.boost.org [Boost.Bimap] semantically._[] combines two maps so that * efficient Bidirectional Lookup is provided, or * as a concrete example * look-up IP-Numbers for Host-Names, and * llok-up Host-Names for IP-Numbers. .I[ For more information on bidirectional maps see: http://www.boost.org/doc/libs/release/libs/bimap/doc/html/index.html ] .F[: The technique used to implement that kind of bidirectional lookup has not been researched for the purpose of that presentation. But it can be assumed – as for most libraries available on the [Boost Platform] – that is at least as performant as an equivalent "home-grown" solution based on STL components. ] --- template: plain name: boost_multi_index header: ### Boost.MultiIndex [Boost.MultiIndex]: http://www.boost.org/doc/libs/release/libs/multi_index/doc/index.html [DSL]: https://en.wikipedia.org/wiki/Domain-specific_language [Boost.MultiIndex] is the "in memory" equivalent for data base table, i.e. * by means of very advanced template programming a versatile parametrized class is provided * extending the principles of a map to multiple columns, * each of which may be * indexable (or not) * unique (or not) * … From the client's perspective it rather is a [DSL] to be used in a "Cook-Book" style._[], probably extending the examples from the documentation. .I[ For more information on multi-index tables see: http://www.boost.org/doc/libs/release/libs/multi_index/doc/index.html ] .F[: I.e. that the complexity of advanced template programming is mostly on the implementer's side. (Though clarity of error messages may still be an issue.) ] --- template: plain name: boost_property_tree header: ### Boost.PropertyTree [Boost.PropertyTree]: http://www.boost.org/doc/libs/release/doc/html/property_tree.html [GoF-Composite]: https://en.wikipedia.org/wiki/Composite_pattern [Boost.PropertyTree] provides a data structure close to the [GoF-Composite] design pattern. It allows for * hierarchical nesting (in principally unlimited depths) * of pairs of * keys and * values, * with the latter introducing recursion by * supporting property (sub-) tree * besides atomic elements. A typical application of property trees (from Boost) is to make the contained information persistent, e.g. to conserve a programs state between runs. .I[ For more information on property trees see: http://www.boost.org/doc/libs/release/doc/html/property_tree.html ] --- template: plain name: boost_property_tree header: #### Property Tree Serialisation Formats [XML]: http://www.xml.com/pub/a/98/10/guide0.html?page=2#AEN58 [JSON]: http://json.org/ [JavaScript]: https://simple.wikipedia.org/wiki/JavaScript [INFO File]: http://www.boost.org/doc/libs/release/doc/html/property_tree/parsers.html#property_tree.parsers.info_parser [INI-Files]: https://en.wikipedia.org/wiki/INI_file There are several serialisation formats to chose from when a property tree is stored to a file or read-back: * [XML] with pre-defined tags (**not** any generic XML structure); * [JSON] a hierarchical data format (made popular by [JavaScript]) for simple data exchange in web applications and elsewhere; * [INFO File] a hierarchical format (much similar to the former), which was specially designed for storing a property tree in a text file; * [INI-Files] as in early versions of MS-Windows.._[] .F[: When storing to and reading from ini-files there are limitations to the property tree content, especially ini-files were not designed to hold (and easily edit) nested data structures. ] --- template: plain name: boost_algorithm header: ### Boost.Algorithm [Boost.Algorithm]: http://www.boost.org/doc/libs/release/libs/algorithm/doc/html/index.html [Boost.Algorithm] extends the [Algorithm Dimension](04_day2.html#stl_algorithm_extensions) of the STL. E.g. there are algorithms applicable to containers * for efficiently sub-sequences * applying comparisons * … (and more) … Since 2011 with each of the released ISO standards._[] parts of this library were included. So using [Boost.Algorithm] also is a way to get (some) C++11/C++14 compatibility even if not (yet) provided by the compiler/library vendor. .F[: I.e. at the time of writing this, with C++11/14. ] .I[ For more information on extended algorithms see: http://www.boost.org/doc/libs/release/libs/algorithm/doc/html/index.html ] --- template: plain name: boost_iterator header: ### Boost.Iterator [Boost.Iterator]: http://www.boost.org/doc/libs/release/libs/iterator/doc/index.html [Boost.Iterator] is two things: 1. It is a clean-up (beyond a pure re-wording) for the [Iterator Categories](04_day2.html/#iterator_categories) as originally specified with C++98. 2. It helps to avoid systematic code when implementing new iterators. .I[ For more information on extensions to iterators see: http://www.boost.org/doc/libs/release/libs/iterator/doc/index.html ] --- template: plain name: boost_range header: ### Boost.Range [Boost.Range]: http://www.boost.org/doc/libs/release/libs/range/doc/html/index.html [U*ix Pipeline]: https://en.wikipedia.org/wiki/Pipeline_%28Unix%29 [Boost.Range] implements all STL algorithms with a different interface: * Instead of supplying two iterators to specify a range by the element it starts with and the first element beyond its end, * **a single argument** has to be specified * which is a **model of some a range concept**, and * can be created in various ways. Of course, creating a range from two iterators is still possible – but it is not any more the **only** way, as it is with the classic STL API.._[] .I[ For more information on extensions to iterators see: http://www.boost.org/doc/libs/release/libs/range/doc/html/index.html ] .F[: Besides overloads making algorithms accept a range (created by a pair of iterators or another container that is to be processed in its entirety), there are overloads for `operator|` giving "chained algorithms" the nifty look&feel of [U*ix Pipeline]s. ] --- template: plain name: stl_concurrency_support header: ## STL Concurrency Support [Concurrency Support]: http://en.cppreference.com/w/cpp/thread Though C++11 introduced substantial [Concurrency Support] in the language and library * the STL **does not provide a direct interface** to distribute work among several threads, as a means to improve performance on multi-core CPUs, instead * the STL specification gives leeway to exploit chances for parallelizing independent parts of the work, as long as it stays within the limits of the specified algorithmic complexity. .W[ The problem is not that STL algorithms cannot be parallelized – it is rather that developers might not be aware that it does. ] --- template: plain name: parallelizing_transparently header: ### Parallelizing Transparently E.g. it is **unspecified** by the ISO standard * in which order `std::count_if` accesses the sequence to process * which algorithm is used by `std::sort` Therefore a conforming implementation could well be split the work over a number threads, given its complexity is O(N) or O(N×log
2
(N) respectively. .N[ If not explicitly specified for an algorithm, **no particular order** should be assumed in which the elements on a container are accessed. ] As this may not have been the case in the past,._[] * the problem might occur without warning, * when old code is compiled with a new library version, * that implements parallelized algorithms without giving notice. .F[: The author confesses guilty for having used at least one example to demonstrate the use of STL algorithms, that had a stateful functor, hence depending on linear sequential access of container elements, front to back, but the algorithm used in the example didn't guarantee this! ] --- template: plain name: parallelizing_explicitly header: ### Parallelizing Explicitly If a given library implementation does not exploit chances for parallelizing, it may be done explicitly. Given there are four CPU cores, sorting a large._[] array might be done by * **first** sorting four independent, equally sized segments in four threads – using `std::sort` and a bit of arithmetic with respect to the borders, * **then** merging the two bottom and the two top segments in two threads – using `std::inplace_merge` (and some recycled border calculation from the first step), and * **finally** merging the two sorted sections resulting from the previous step – again using `std::inplace_merge` on the whole array. .W[ Though the above sounds simple – and in fact is not that hard to achieve with what is already provided by the STL – understand that any added complexity tends to make a program harder to understand and more difficult to maintain. ] --- template: plain name: parallelizing_efficient header: ### Improving Performance Before applying a performance improvement, be sure to understand the following: * If some part of a complex task contributes 20% to its total runtime, * a performance improvement of 30% wins 6% total, * a performance improvement of 50% wins 10% total, and * **no** performance improvement will ever win more than 20%. * Other if some part of a complex task contributes 90% to its total runtime, * then … (you will surely be able to do the math yourself). .N[ Especially on modern hardware he total effect of performance improvements s often extremely hard to predict.._[] ] .F[: To put it in different words: Long gone are the days when you could determine assembler instructions issued by the compiler for a particular piece of code and count (and add) instruction cycle times … too strong is the influence of the various cache levels and in turn code locality (contrary to more or less random branching) is a big factor. ] --- template: plain name: parallelizing_efficient header: #### Measuring Performance - A Word to the Wise To determine runtime-performance of a particular piece of code * **Measure before you start** … * … and be sure to measure correctly by * using actually relevant test-data, * concentrate on determining the "bottle necks", * and check the final conclusions for plausibility! .N[ The improvements most worth-while often lurk in nested loops!._[] ] * Even on the short run, * `O(N²)` is already much worse as O(N×log(N)), * which is in turn worse as `O(N)` or even `O(1)`. * But pay also attention to potentially sacrificing locality * as provided by an `std::vector` or `std::array`, by switching to * "clever" algorithms with a more random memory access pattern. .F[: If you have a good understanding not only of the container data structures but also of searching, sorting and partitioning algorithms in provided in the C++ Standard Library, you may already be able to achieve really big improvements. ] --- template: plain name: parallelizing_for_scalability header: #### Scalability to Multiple Cores [Packaged Task]: http://de.cppreference.com/w/cpp/thread/async The following is well-known – and can be demonstrated by measurements: .N[ To increase performance it is contra-productive to split a CPU-bound task to more threads as there are physical cores.._[] ] When parallelizing with [Packaged Task]s in many cases * the decision in many cases is best left to the library (implementation), * assuming it has platform or operating system specific means to adapt actual (hardware) concurrency in the optimal way. .W[ **Explicitly exempt** from that advice are more or less sophisticated networks of **tasks that run independently** from each other, **communicating via buffered pipelines**. ] **Such designs easily deadlock if the library is allowed to silently turn asynchronous into synchronous calls.** .F[: Or at least to more threads as there independent partial hardware processing units that can work physically concurrent, like there are in hyper-threading architectures. ] --- template: plain name: stl_quirks_and_shortcomings header: ## STL-Quirks and Shortcomings [Scott Meyers]: http://www.aristeia.com/ Though the STL has been designed by only two original contributors and therefore has a quite uniform look&feel, there is some "historic ballast" that is difficult to get rid of. The areas considered on the following pages are: * A few case [Inconsistent naming](#stl_naming_inconsistencies). * Some non-obvious [Peculiarities of "Big-O"](#stl_big_o_peculiarities) complexity specifications. Both are considered more closely on the next two pages.._[] .F[: To give credit where credit is due: this whole section was inspired by some sequences from the following [Scott Meyers] video, starting at [minute 37:54](https://www.youtube.com/watch?feature=player_detailpage&v=5tg1ONG18H8#t=2274): https://www.youtube.com/watch?v=5tg1ONG18H8 ] --- template: plain name: stl_naming_inconsistencies header: ### STL Naming Inconsistencies [Stable Sort]: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability Purging an element with a given value * from an `std::list` and an `std:forward_list` is done with the member function `remove`, while * from any associative container it is done with with the member function `erase`. Sorting elements * of an `std::list` or an `std::forward_list` needs to be done with the member function `sort` * which **guarantee** a [Stable Sort], while * for any other sequential container it is done with the (non-member) algorithm `std::sort`, template: plain name: summary header: ## Summary This part * first covered the various [Iterator categories](#stl_iterator_categories), * then compared [Call-Backs from Standard Algorithms](#stl_algorithm_interface) in the form * [Functors](#callback_with_lambda) (= classes with overloaded `operator()`), * [Functions](#callback_with_function) (= classic C function pointers), and * [Lambdas](#callback_with_lambda) (= function literals, as introduced with C++11) ------------------------------------------------------------------------------- What to do next? * [Go back to the Agenda](00_topics.html#agenda) and chose a specific part … * … or [continue with next part](04_day2.html), * … or with the next (and last) page of this part. * (if this is desired `std::stable_sort` has to be used). (More cases as those discussed above may exist.) --- template: plain name: stl_big_o_peculiarities header: ### STL Non-Obvious "Big-O" Complexity Usually operations are not implemented if this were only possible with a substantial performance penalty. * Therefore `std::vector` has no member function `push_font` as `std::deque` and `std::list` have … * … but you can still use the `insert` member function anywhere, though O(N
2
) performance. * Nonetheless `std::binary_search` is applicable to linear lists and specified to have "good" O(log
2
(N)) performance … * … though in this case you would naively expect much worse O(N). * Adding elements to an `std::vector` at its end is specified to run in amortized constant time, * even though the available space must be eventually enlarged, * an operation more and more expensive, each time it happens. (More cases as those discussed above may exist.)