basic_string::insert benchmarks

[Paolo Carlini]

Hi all,

today I have carried out some more systematic benchmarks.
Basically, I think we should not aim for the impossible: making an insert
operation in the middle of a long string as fast (per char) as an append or an
assign: every time, unavoidably, *all* the chars after the insertion point must
be moved forward. Do you all agree on this?
This means that, for instance:

#include <string>
int main()
{
  std::string str = "12345678901234567890123456789012345678901234567890"
    "12345678901234567890123456789012345678901234567890";
  std::string str2 = "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghij";

  for (int i = 0; i < 20000; i++)
    str.insert(str.size() / 2, str2, 0, std::string::npos);
}

current
-------
20.530u 0.040s 0:20.93 98.2%    0+0k 0+0io 206pf+0w

current + insert patch
----------------------
20.350u 0.060s 0:20.78 98.2%    0+0k 0+0io 204pf+0w

2.95.3
------
20.870u 0.030s 0:21.28 98.2%    0+0k 0+0io 96pf+0w

That is, the cost of the moves dominates and any other improvement is barely
measurable.

On the other hand, if we insert close to the end of the string, we can
consistently obtain a speed similar to that of v2:

#include <string>
int main()
{
  std::string str = "12345678901234567890123456789012345678901234567890"
    "12345678901234567890123456789012345678901234567890";
  std::string str2 = "a";

  for (int i = 0; i < 8000000; i++)
    str.insert(str.size() - 1, str2, 0, std::string::npos);
}

current
-------
8.100u 0.070s 0:08.28 98.6%     0+0k 0+0io 205pf+0w

current + insert patch
----------------------
4.110u 0.030s 0:04.21 98.3%     0+0k 0+0io 203pf+0w

2.95.3
------
3.930u 0.080s 0:04.07 98.5%     0+0k 0+0io 95pf+0w

////////////////////

#include <string>
int main()
{
  std::string str = "12345678901234567890123456789012345678901234567890"
    "12345678901234567890123456789012345678901234567890";
  std::string str2 = "a";

  for (int i = 0; i < 8000000; i++)
    str.insert(str.size() - 100, str2, 0, std::string::npos);
}

current
-------
12.410u 0.060s 0:12.72 98.0%    0+0k 0+0io 205pf+0w

current + insert patch
----------------------
8.520u 0.080s 0:08.74 98.3%     0+0k 0+0io 203pf+0w

2.95.3
------
8.430u 0.060s 0:08.61 98.6%     0+0k 0+0io 95pf+0w

/////////////////

#include <string>
int main()
{
  std::string str = "12345678901234567890123456789012345678901234567890"
    "12345678901234567890123456789012345678901234567890";
  std::string str2 = "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghij";

  for (int i = 0; i < 2000000; i++)
    str.insert(str.size() - 1, str2, 0, std::string::npos);
}

current
-------
3.390u 1.200s 0:04.69 97.8%     0+0k 0+0io 206pf+0w

current + insert patch
----------------------
1.950u 1.310s 0:03.31 98.4%     0+0k 0+0io 204pf+0w

2.95.3
------
1.930u 1.240s 0:03.24 97.8%     0+0k 0+0io 96pf+0w

///////////////////

#include <string>
int main()
{
  std::string str = "12345678901234567890123456789012345678901234567890"
    "12345678901234567890123456789012345678901234567890";
  std::string str2 = "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghij";

  for (int i = 0; i < 2000000; i++)
    str.insert(str.size() - 100, str2, 0, std::string::npos);
}

current
-------
4.250u 1.260s 0:05.60 98.3%     0+0k 0+0io 206pf+0w

current + insert patch
----------------------
2.850u 1.300s 0:04.21 98.5%     0+0k 0+0io 204pf+0w

2.95.3
------
2.890u 1.190s 0:04.16 98.0%     0+0k 0+0io 96pf+0w

///////////////////

Cheers,
Paolo.