{"id":2273,"date":"2016-09-12T13:26:15","date_gmt":"2016-09-12T11:26:15","guid":{"rendered":"http:\/\/mariusbancila.ro\/blog\/?p=2273"},"modified":"2016-09-12T13:26:15","modified_gmt":"2016-09-12T11:26:15","slug":"a-comparison-of-two-stdtransform-alternatives-revisited","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2016\/09\/12\/a-comparison-of-two-stdtransform-alternatives-revisited\/","title":{"rendered":"A comparison of two std::transform alternatives revisited"},"content":{"rendered":"

In the previous post<\/a> I have compared two alternative ways of transforming a string to upper case, both using std::transform<\/tt>: one that modifies an existing string and one that generates a new one by inserting at the end using std::back_inserter<\/tt>. For the second alternative I have presented two implementations, one that does an initial reservation for the newly created string and one that does not.<\/p>\n

inline std::string to_upper_v2(std::string const & text)\r\n{\r\n  auto uppertext = std::string{};\r\n  std::transform(std::begin(text), std::end(text), std::back_inserter(uppertext), toupper);\r\n  return uppertext;\r\n}\r\n \r\ninline std::string to_upper_v3(std::string const & text)\r\n{\r\n   auto uppertext = std::string{};\r\n   uppertext.reserve(text.size());\r\n   std::transform(std::begin(text), std::end(text), std::back_inserter(uppertext), toupper);\r\n   return uppertext;\r\n}<\/pre>\n
The curious conclusion of the tests was that the version with reserve was actually slower than the one that did not perform an initial reservation.<\/p>\n
The solution was built with Visual Studio 2015 Update 2. As it was later noticed in the comments, the actual cause of that is a Microsoft optimization for std::string<\/tt> by using an array of 16 characters for strings that do not exceed this size and only dynamically allocate memory for larger strings. Since all the strings had a length between 3 and 12 characters, this optimization was used for all strings. Therefore, reserve()<\/tt> dynamically allocated memory that was never used and its execution time only added to the overall time.<\/p>\n
To actually be able to test the performance of these two implementations with VC++, the strings should be larger than 16 characters. So I changed the code to generate strings between 17 and 25 characters long.<\/p>\n
auto dist_len = std::uniform_int_distribution<>{ 3, 12 };<\/pre>\n
The results this time were totally different. The 3rd version with initial reserving was more performant than the one that did not do that. It can also be noticed that the more strings need to be transformed the more similar times it takes for all the versions.<\/p>\n\n\n\n\n\n\n\n\n\n
No of strings<\/td>\ntime v1<\/td>\ntime v2<\/td>\ntime v3<\/td>\nPercentage of slowdown with v2<\/td>\nPercentage of slowdown with v3<\/td>\n<\/thead>\n
1000<\/td>\n122<\/td>\n219<\/td>\n205<\/td>\n79.5<\/td>\n68.0<\/td>\n<\/tr>\n
10000<\/td>\n1202<\/td>\n2178<\/td>\n2055<\/td>\n81.2<\/td>\n71.0<\/td>\n<\/tr>\n
100000<\/td>\n13563<\/td>\n22758<\/td>\n21431<\/td>\n67.8<\/td>\n58.0<\/td>\n<\/tr>\n
1000000<\/td>\n136160<\/td>\n225669<\/td>\n214149<\/td>\n65.7<\/td>\n57.3<\/td>\n<\/tr>\n
10000000<\/td>\n1368034<\/td>\n2268991<\/td>\n2155969<\/td>\n65.9<\/td>\n57.6<\/td>\n<\/tr>\n
100000000<\/td>\n23090172<\/td>\n27997658<\/td>\n27322888<\/td>\n21.3<\/td>\n18.3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
In the chart below with blue it is represented the results for version 2 and with orange the results for version 3 (with initial reservation).
\n\"transform2\"<\/a><\/p>\n
Note<\/b>: Generating 100 milion strings between 17 and 25 characters require a lot of memory. In my tests it peaked to 13GB. So if you want to run the code you should be aware of this.<\/p>\n","protected":false},"excerpt":{"rendered":"
In the previous post I have compared two alternative ways of transforming a string to upper case, both using std::transform: one that modifies an existing string and one that generates a new one by inserting at the end using std::back_inserter. For the second alternative I have presented two implementations, one that does an initial reservation … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[7],"tags":[485,486,451,487],"class_list":["post-2273","post","type-post","status-publish","format-standard","hentry","category-c","tag-algorithm","tag-back_inserter","tag-c","tag-transform"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t