UPDATE: For an update on the implementation and the conclusions see A comparison of two std::transform alternatives revisited.

I was writing a small utility function to transform a string to uppercase. The obvious solution for that is std::transform, but as I was writing it I realized there are several alternatives:

  • transform an existing string, by setting its elements to uppercase one by one
  • iterate over an existing string, and insert a copy of its uppercased elements into another string, initially empty, using std::back_inserter

Obviously, the second approach should be slower since it has to deal with buffer reallocations. However, I was curious how slower comparing to the first approach that would be. So I decided to test it.

UPDATE: It has been suggested that in the second version I should make a reserve of the string before using std::back_inserter to add characters to the string. Therefore I added a 3rd version that does that.

This is how I implemented the two version different versions of the helper function:

To test it, I decided to randomly generate strings. The length of the strings and their content is randomly generated. Both functions are tested with the same strings after a copy is initially done.

The results, tested with a 64-bit release build with Visual Studio 2015 Update 2, look like below. Times are in microseconds.

No of strings time v1 time v2 time v3 Percentage of slowdown with v2 Percentage of slowdown with v3
1000 40 57 64 42.5 60
10000 593 568 637 42.5 53.1
100000 3894 5769 6497 48.2 66.8
1000000 40005 57852 65793 44.6 64.5
10000000 394573 584048 734463 48 86.1
100000000 4298742 6171199 7577972 43.6 76.3

I have run this several times with similar results. The following image shows how much slower the versions using std::back_inserter were comparing with the version that modifies the string directly. With blue it is represented the results for version 2 and with orange the results for version 3 (with initial reservation).
transform

This clearly indicates that using std::back_inserter is slower, and it is actually 30 to 60% slower. However, what has surprized me is that reserving the necessary space for the string before std::back_inserter starts inserting elements is even slower (in some cases it can take twice as much time than version 1). Of course this measures the time to allocate the buffer too, not just the time for transforming the string, but the point here is to profile the entire function, not just the transform operation.

, , , Hits for this post: 4231 .
Trackback

6 comments untill now

  1. Gravatar
    Cristian @ 2016-09-07 11:31

    The second version does more allocations. What happens if you call an uppertext.reserve(text.size()) before std::transform?

  2. Gravatar

    You could have used std::string::reserve in your back_inserter function.

  3. Gravatar

    Hello,

    To be fair and only measure the overhead of std::back_inserter, the to_upper_v2 should do a uppertext.reserve(text.size()) before call the transform.

  4. Gravatar

    I have taken the feedback for using reserve() before calling transform() and the results were surprising. This version is even slower. I have triple checked to see if I made a mistake, but could not spot any.

  5. Gravatar

    My bad, I do not spend enough time to read the test case.
    The length of the string is always < 3 and std::string in Microsoft STL have a small buffer optimization of 16 bytes. This explain why the V3 is slower, no reallocation was perform but more calls are done.

  6. Gravatar

    No, the length of the strings is between 3 and 12 characters. But you are absolutely correct about the Microsoft buffer optimization.

Add your comment now