Re: Benchmarks: STL's string vs. C string

Jyrki Saarinen wrote:
Niklas Holsti <niklas.holsti@xxxxxxxxxxxxxxx> wrote:

Perhaps STL keeps track of the length of each string object, so that the catenation operator does not have to scan for the final null byte of the destination string, and can just copy the source string into the right position.

In your test, the strcat loop has a quadratic complexity in the number of iterations because the "buffer" string grows by a fixded amount on each iteration, so the scan for the final null grows longer in proportion to the iteration number.

If STL knows the length of "stlBuffer", each iteration of the STL loop takes the same time and the overall loop has linear complexity in the number of iterations.

This was the reason, indeed. Not being programmed C strings for a while,
I didn't think of this at all. I had the intuition that strcat() has some wisdom about the terminating byte in the buffer, which is of course more than ridiculous.. :)

Anyway, the point of this little excercise was to prove Dijkstra's claim about STL being 50x slower in string concatenation, false.

Such a claim is meaningless, because the outcome of such a comparison depends very much on how the C and std:string version of the test are implemented, the compiler being used and last but not least which standard library implementation is being used (the C++ standard does not dictate how the standard library is to be implemented, multiple implementations do exist). It is easy to prove that the std:string is faster than C style string manipulation, or the other way around.

Relevant Pages

  • Re: how to replace a substring in a string using C?
    ... the loop to use strstr less wastefully would introduce redundant iteration over the string whilst copying, for which arguments similar to the above apply. ... The iteration of my version is no more redundant than the fact that you have do a memcmpon the first byte, then a copy if it doesn't match works). ...
  • Re: Benchmarks: STLs string vs. C string
    ... STL impl. ... Perhaps STL keeps track of the length of each string object, ... longer in proportion to the iteration number. ...
  • Re: URI Escape/Unescape Library?
    ... >> I also replaced the loop and length with DOTIMES. ... > binding of var on each iteration or whether it establishes a ... characters instead of iterating over the string. ...
  • Re: Get_Line problem (GNAT bug?)
    ... If the behavior is defined to support iteration ... A while loop, probably, or something in this area. ... I am using exceptions for parsing sources. ... But Get_Line already has a result, which is a string. ...
  • Re: Weird double parsing
    ... bool systemOk = true; ... Console.WriteLine("Testing with string comparison..."); ... On iteration #1016. ... This allows a format string to be ...