![\"templatesTypeTraits\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2021\/11\/templatesTypeTraits.png\")
<\/p>\nThe type-traits library has two main goals: correctness and optimization. Today, I write about optimization.<\/p>\n
<\/p>\n
<\/p>\n
This post is the last post in my miniseries about the type-traits library. I have already written the following posts:<\/p>\n
std::is_base_of<\/code><\/a><\/li>\n- The Type-Traits Library: Correctness<\/a><\/li>\n<\/ul>\n
Before I write about optimization in C++, I want to tell a short anecdote. I often have the following conversation with my students in my classes:<\/p>\n
\n- Me: Why do we have the feature ABC in C++?<\/li>\n
- Student: I don’t know.<\/li>\n
- Me: If you don’t have an answer, say performance. This always works in C++.<\/li>\n<\/ul>\n
So, let me write about the type-traits library from the optimization perspective.<\/p>\n
Optimization<\/h2>\n
The idea is quite straightforward and used in the Standard Template Library (STL). If the elements of a range are simple enough, the algorithms of the STL like std::copy, std::fill,<\/span><\/code> or std::equal <\/span><\/code>are directly applied to memory. Instead of using std::copy<\/span> to copy each element one by one, all is done in one big step. Internally, C functions like memcmp<\/a>, memset<\/a>, <\/span><\/code>memcpy<\/code>,<\/span> <\/a>or memmove<\/span><\/a><\/code> are used. The small difference between memcpy<\/span><\/code> and memmove<\/span> <\/code>is that memmove<\/span> <\/code>can deal with overlapping memory areas.
<\/span><\/p>\nThe implementations of the algorithm std::copy<\/span>, std::fill,<\/span><\/code> or std::equal<\/span><\/code> use a simple strategy. std::copy<\/span><\/code> is like a wrapper. This wrapper checks if the elements are simple enough. If so, the wrapper will delegate the work to the optimized copy function. If not, the conservative copy algorithm is used. This conservative one copies each element after the other. The functions of the type-traits library are heavily used to make the right decision.<\/p>\nThe graphic shows the general strategy:<\/p>\n
![\"PerformanceDecision\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2021\/12\/PerformanceDecision.png\")
<\/p>\n
<\/p>\n
That was the theory, but here is the practice. Which strategy is used by std::fill<\/span><\/code>?<\/p>\n<\/p>\nstd::fill<\/h2>\n
std::fill <\/a>assigns each element in the range a value. The listing shows a GCC-inspired implementation of std::fill.<\/p>\n<\/p>\n
\n\/\/ fillGCC.cpp<\/span>\r\n \r\n#include <cstring><\/span>\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <type_traits><\/span>\r\n\r\nnamespace<\/span> my{\r\n\r\n template<\/span> <<\/span>typename<\/span> I, typename<\/span> T, bool<\/span> b><\/span>\r\n void<\/span> fill_impl(I first, I last, const<\/span> T&<\/span> val, const<\/span> std::<\/span>integral_constant<<\/span>bool<\/span>, b>&<\/span>){\r\n while<\/span>(first !=<\/span> last){\r\n *<\/span>first =<\/span> val;\r\n ++<\/span>first;\r\n }\r\n }\r\n\r\n template<\/span> <<\/span>typename<\/span> T> \/\/ (2)<\/span><\/span>\r\n void<\/span> fill_impl(T*<\/span> first, T*<\/span> last, const<\/span> T&<\/span> val, const<\/span> std::<\/span>true_type&<\/span>){\r\n std::<\/span>memset(first, val, last-<\/span>first);\r\n }\r\n\r\n template<\/span> <<\/span>class<\/span> I<\/span>, class<\/span> T<\/span>><\/span>\r\n inline<\/span> void<\/span> fill(I first, I last, const<\/span> T&<\/span> val){\r\n typedef<\/span> std::<\/span>integral_constant<<\/span>bool<\/span>,std::<\/span>is_trivially_copy_assignable<<\/span>T><\/span>::<\/span>value
&&<\/span> (sizeof<\/span>(T) ==<\/span> 1<\/span>)><\/span> boolType; \/\/ (1)<\/span>\r\n fill_impl(first, last, val, boolType());\r\n }\r\n}\r\n\r\nconst<\/span> int<\/span> arraySize =<\/span> 100<\/span>'<\/span>000<\/span>'<\/span>000<\/span>;\r\nchar<\/span> charArray1[arraySize]=<\/span> {0<\/span>,};\r\nchar<\/span> charArray2[arraySize]=<\/span> {0<\/span>,};\r\n\r\nint<\/span> main<\/span>(){\r\n\r\n std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n\r\n auto<\/span> begin =<\/span> std::<\/span>chrono::<\/span>steady_clock::<\/span>now();\r\n my::<\/span>fill(charArray1, charArray1 +<\/span> arraySize,1<\/span>);\r\n auto<\/span> last =<\/span> std::<\/span>chrono::<\/span>steady_clock::<\/span>now() -<\/span> begin;\r\n std::<\/span>cout <<<\/span> \"charArray1: \"<\/span> <<<\/span> std::<\/span>chrono::<\/span>duration<<\/span>double<\/span>><\/span>(last).count() <<<\/span> \" seconds<\/span>\\n<\/span>\"<\/span>;\r\n\r\n begin =<\/span> std::<\/span>chrono::<\/span>steady_clock::<\/span>now();\r\n my::<\/span>fill(charArray2, charArray2 +<\/span> arraySize, static_cast<\/span><<\/span>char<\/span>><\/span>(1<\/span>));\r\n last=<\/span> std::<\/span>chrono::<\/span>steady_clock::<\/span>now() -<\/span> begin;\r\n std::<\/span>cout <<<\/span> \"charArray2: \"<\/span> <<<\/span> std::<\/span>chrono::<\/span>duration<<\/span>double<\/span>><\/span>(last).count() <<<\/span> \" seconds<\/span>\\n<\/span>\"<\/span>;\r\n\r\n std::<\/span>cout <<<\/span> '\\n'<\/span>;\r\n\r\n}\r\n<\/pre>\n<\/div>\n <\/p>\n
Back to the code example. If the expression boolType()<\/span> in line (1) is true,<\/span> the optimized version of my::fill_impl<\/span> in line 2 is used. This variant fills the memory of 100 million entries with the value 1. sizeof(char)<\/span> is 1.<\/p>\nWhat about the performance of the program? I compiled the program without optimization to measure the non-optimized performance.<\/p>\n
![\"fillGcc\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2021\/12\/fillGcc.png\")
<\/h3>\n
The optimized version in line (2) is about ten times faster. Interestingly, when I enable full optimization, both variants are equally fast because the compiler generates the same code for both variants. Also, the generic version (line (3)) uses memset<\/code>: fillGCC.cpp<\/code> with maximum optimization on Compiler Explorer<\/a>.<\/p>\nI presented an old GCC implementation std::fill,<\/code> because the newer ones are not so easy to read. Here are the essential parts of the GCC 6 implementation.<\/p>\nstd::fill<\/code><\/h3>\n<\/p>\n
\n\/\/ fill <\/span>\r\n\/\/ Specialization: for char types we can use memset. <\/span>\r\ntemplate<\/span><<\/span>typename<\/span> _Tp><\/span>\r\n inline<\/span> typename<\/span>\r\n __gnu_cxx::<\/span>__enable_if<<\/span>__is_byte<<\/span>_Tp>::<\/span>__value, void<\/span>>::<\/span>__type \/\/ (1)<\/span>\r\n __fill_a(_Tp*<\/span> __first, _Tp*<\/span> __last, const<\/span> _Tp&<\/span> __c)\r\n {\r\n const<\/span> _Tp __tmp =<\/span> __c;\r\n if<\/span> (const<\/span> size_t<\/span> __len =<\/span> __last -<\/span> __first)\r\n __builtin_memset(__first, static_cast<\/span><<\/span>unsigned<\/span> char<\/span>><\/span>(__tmp), __len);\r\n }\r\n<\/pre>\n<\/div>\n <\/p>\n
The GCC 6 implementation uses SFINAE. The full specialization of the function template __fill_a <\/code>use __builtin_memset. <\/code>The crucial part in this implementation is line (1): __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type. <\/code>Let me rewrite this expression in a human-readable way and use the official names.<\/p>\n<\/p>\n
\nstd::<\/span>enable_if<<\/span>std::<\/span>is_byte<<\/span>Tp>::<\/span>value, void<\/span>>::<\/span>type\r\n<\/pre>\n<\/div>\n <\/p>\n
The expression checks first if the template parameter TP is a byte:std::is_byte<T>::value<\/a><\/code>. If this expression evaluates to true<\/code> thanks to