{"id":5036,"date":"2016-11-21T07:18:44","date_gmt":"2016-11-21T07:18:44","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/type-traits-performance-matters\/"},"modified":"2023-06-26T12:35:40","modified_gmt":"2023-06-26T12:35:40","slug":"type-traits-performance-matters","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/type-traits-performance-matters\/","title":{"rendered":"Type-Traits: Performance Matters"},"content":{"rendered":"

If you look carefully, you see type-traits have a big optimization potential. The type-traits support the first step to analyze the code at the compile-time and, in the second step, to optimize the code based on that analysis. How is that possible? Dependent on the type of variable, a faster variant of an algorithm will be chosen.<\/p>\n

<\/p>\n

Work on the entire memory area<\/h2>\n

The idea is quite straightforward and is used in current Standard Template Library implementations (STL) implementations. If the elements of a container are simple enough, the algorithm of the STL, like std::copy, std::fill,<\/span> or  std::equal <\/span>will directly be applied to the memory area.  Instead of using std::copy<\/span> to copy the elements individually, all is done in one large step.  Internally, C functions like memcmp<\/a>, memset<\/a>, <\/span>memcpy,<\/span> <\/a>or memmove<\/span><\/a> are used. The small difference between memcpy<\/span> and memmove<\/span> is that memmove<\/span> can deal with overlapping memory areas.
<\/span><\/p>\n

The implementations of the algorithm std::cop<\/span>y, std::fill,<\/span> or std::equal<\/span> use a simple strategy.  std::copy<\/span> is like a wrapper. This wrapper checks if the element is simple enough. If so, the wrapper will delegate the work to the optimized copy function. If not, the general copy algorithm will be used. This one copies each element after the other. If the elements are simple enough, the functions of the type-traits library will be used to make the right decision. <\/p>\n

The graphic shows this strategy once more:<\/p>\n

 \"ContainerVersusElement\"<\/p>\n

That was the theory, but here is the practice. Which strategy is used by std::fill<\/span>?<\/p>\n<\/p>\n

std::fill<\/h2>\n

std::fill <\/a>assigns each element in the range a value. The listing shows a simple implementation.<\/p>\n

\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51<\/pre>\n<\/td>\n
\n
\/\/ fill.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> <typename<\/span> I, typename<\/span> T, bool<\/span> b>\r\n  void<\/span> fill_impl(I first, I last, const<\/span> T& val, const<\/span> std::integral_constant<bool<\/span>, b>&){\r\n    while<\/span>(first != last){\r\n      *first = val;\r\n      ++first;\r\n    }\r\n  }\r\n\r\n  template<\/span> <typename<\/span> T>\r\n  void<\/span> fill_impl(T* first, T* last, const<\/span> T& val, const<\/span> std::true_type&){\r\n    std::memset(first, val, last-first);\r\n  }\r\n\r\n  template<\/span> <class<\/span> I<\/span>, class<\/span> T<\/span>>\r\n  inline<\/span> void<\/span> fill(I first, I last, const<\/span> T& val){\r\n    \/\/ typedef std::integral_constant<bool,std::has_trivial_copy_assign<T>::value && (sizeof(T) == 1)> boolType;<\/span>\r\n    typedef<\/span> std::integral_constant<bool<\/span>,std::is_trivially_copy_assignable<T>::value && (sizeof<\/span>(T) == 1)> boolType;\r\n    fill_impl(first, last, val, boolType());\r\n  }\r\n}\r\n\r\nconst<\/span> int<\/span> arraySize = 100000000;\r\nchar<\/span> charArray1[arraySize]= {0,};\r\nchar<\/span> charArray2[arraySize]= {0,};\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  auto<\/span> begin= std::chrono::system_clock::now();\r\n  my::fill(charArray1, charArray1 + arraySize,1);\r\n  auto<\/span> last=  std::chrono::system_clock::now() - begin;\r\n  std::cout <<  \"charArray1: \"<\/span> << std::chrono::duration<double<\/span>>(last).count() << \" seconds\"<\/span> << std::endl;\r\n\r\n  begin= std::chrono::system_clock::now();\r\n  my::fill(charArray2, charArray2 + arraySize, static_cast<\/span><char<\/span>>(1));\r\n  last=  std::chrono::system_clock::now() - begin;\r\n  std::cout <<  \"charArray2: \"<\/span> << std::chrono::duration<double<\/span>>(last).count() << \" seconds\"<\/span> << std::endl;\r\n\r\n  std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
my::fill<\/span> make in line 27 the decision which implementation of my::fill_impl<\/span> is applied. To use the optimized variant, the elements should have a compiler-generated copy assignment operator std::is_trivially_copy_assignable<T><\/span> and should be 1 byte large: sizeof(T) == 1. <\/span>The function std::is_trivially_copy_assignable <\/span>is part of the type-traits. I explain in the post Check types<\/a> the magic behind the type-traits functions.<\/p>\n
My GCC 4.8 calls instead of the function std::is_trivially_copy_assignable<\/span> std::has_trivial_copy_assign<\/span>. If you request the copy assignment operator with the keyword default from the compiler, the operator will be trivial. <\/span><\/p>\n
\n
struct<\/span> TrivCopyAssign{\r\n  TrivCopyAssign& operator<\/span>=(const<\/span> TrivCopyAssign& other)= default<\/span>;\r\n};
\r\n<\/pre>\n<\/div>\n
Back to the code example. If the expression boolType()<\/span> in line 27 is true,<\/span> the optimized version of my::fill_impl<\/span> in lines 18 – 21 will be used. This variant fills in opposite to the generic variant my::fill_impl<\/span> (line 10 -16) the entire memory area – consisting of 100 million entries – with the value 1.  sizeof(char)<\/span> is 1.<\/p>\n
What about the performance of the program? I compiled the program without optimization. The execution of the optimized variant is about 3 times faster on windows; about 20 times faster on Linux.<\/p>\n
Microsoft Visual 15<\/h3>\n
\"fillWindows\"<\/p>\n
GCC 4.8<\/h3>\n
\"filLLinux\"<\/p>\n
The decision of which variant of an algorithm should be used is sometimes not so easy to make.<\/p>\n
std::equal<\/h2>\n
The implementer of std::equal<\/span> had special humor because he called his decision criteria __simple.<\/span> The code is copied from the GCC 4.8 STL implementation.<\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12<\/pre>\n<\/td>\n
\n
template<\/span><typename<\/span> _II1, typename<\/span> _II2>\r\ninline<\/span> bool<\/span> __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2){\r\n  typedef<\/span> typename<\/span> iterator_traits<_II1>::value_type _ValueType1;\r\n  typedef<\/span> typename<\/span> iterator_traits<_II2>::value_type _ValueType2;\r\n  const<\/span> bool<\/span> __simple = ((__is_integer<_ValueType1>::__value\r\n                         || __is_pointer<_ValueType1>::__value )\r\n                        && __is_pointer<_II1>::__value\r\n                        && __is_pointer<_II2>::__value\r\n                        &&__are_same<_ValueType1, _ValueType2>::__value\r\n                        );\r\n  return<\/span> std::__equal<__simple>::equal(__first1, __last1, __first2);\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
I have a different perception of __simple<\/span>. To use the optimized variant of std::equal<\/span>, the container elements have to fulfil some assurances. The elements of the container have to be of the same type (line 9) and have to be an integral or a pointer (line 5 and 6). In addition, the iterators have to be pointers (lines 7 and 8).
<\/span><\/p>\n
What’s next?<\/h2>\n
They didn’t make it in the C++98 standard. But we have them in C++11: hash tables. The official name is an unordered associative container. Unofficially, they are often called dictionaries. They promise one important feature: performance because their access time is constant in the optimal case.<\/p>\n
Why we need the unordered associative container? What makes them different from the C++98 ordered associate containers (std::map, std::set, std::multimap, <\/span>and std::multiset<\/span>)? That’s the story of the next post.<\/a><\/span><\/p>\n
 <\/p>\n
 <\/p>\n

<\/strong><\/span><\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n<\/p>\n
<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"
If you look carefully, you see type-traits have a big optimization potential. The type-traits support the first step to analyze the code at the compile-time and, in the second step, to optimize the code based on that analysis. How is that possible? Dependent on the type of variable, a faster variant of an algorithm will […]<\/p>\n","protected":false},"author":21,"featured_media":5033,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[364],"tags":[419],"class_list":["post-5036","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-embedded","tag-type-traits"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5036","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5036"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5036\/revisions"}],"predecessor-version":[{"id":6924,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5036\/revisions\/6924"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5033"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5036"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5036"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5036"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}