How efficient is std::string compared to null-terminated strings?
Well there are definitely known problems regarding the performance of strings and other containers. Most of them have to do with temporaries and unnecessary copies.
Well there are definitely known problems regarding the performance of strings and other containers. Most of them have to do with temporaries and unnecessary copies. It's not too hard to use it right, but it's also quite easy to Do It Wrong.
For example, if you see your code accepting strings by value where you don't need a modifyable parameter, you Do It Wrong: // you do it wrong void setMember(string a) { this->a = a; // better: swap(this->a, a); } You better had taken that by const reference or done a swap operation inside, instead of yet another copy. Performance penalty increases for a vector or list in that case. However, you are right definitely that there are known problems.
For example in this: // let's add a Foo into the vector v. Push_back(Foo(a, b)); We are creating one temporary foo just to add a new Foo into our vector. In a manual solution, that might create the foo directly into the vector.
And if the vector reaches its capacity limit, it has to reallocate a larger memory buffer for its elements. What does it do? It copies each element separately to their new place using their copy constructor.
A manual solution might behave more intelligent if it knows the type of the elements before-hand. Another common problem is introduced temporaries. Have a look at this string a = be + c + e; There are loads of temporaries created, which you might avoid in a custom solution that you actually optimize onto performance.
Back then, the interface of std::string was designed to be copy-on-write friendly. However, with threads becoming more popular, transparent copy on write strings have problems keeping their state consistent. Recent implementations tend to avoid copy on write strings and instead apply other tricks where appropriate.
Most of those problems are solved however for the next version of the Standard. For example instead of push_back, you can use emplace_back to directly create a Foo into your vector v. Emplace_back(a, b); And instead of creating copies in a concatenation above, std::string will regognize when it concatenates temporaries and optimize for those cases.
Reallocation will also avoid making copies, but will move elements where appropriate to their new places. For an excellent read, consider Move Constructors by Andrei Alexandrescu. Sometimes, however, comparisons also tend to be unfair.
Standard containers have to support the features they have to support. For example if your container does not keep map element references valid while adding/removing elements from your map, then comparing your "faster" map to the standard map can become unfair, because the standard map has to ensure that elements keep being valid. That was just an example, of course, and there are many such cases that you have to keep in mind when stating "my container is faster than standard ones!".
My apologies - I significantly edited the question after posting. I wanted to discuss std::vector in a separate question. Anyway, I changed my test according to your suggestion, and got a 50 times slowdown.
Anytime you reach the memcpy() in an implementation, you're in trouble, I reckon. – Tim Cooper Mar 12 '09 at 9:37 class C { std::string foo; public: void set(const std::string& _foo) { foo = _foo; } }; To completely avoid the memcpy(), I'd have to declare foo as a pointer, isn't that right? Which means I need to worry about memory allocation, just like with char*'s?
– Tim Cooper Mar 12 '09 at 9:42 in that particular case taking the string by value and then using foo. Swap(_foo); may be better. I meant to generally talk about parameter passing if you just want to pass some parameter in but don't need to take a copy for modifications.
– Johannes Schaub - litb Mar 12 '09 at 10:31 also as far as I know msvc uses a small string optimization: for small strings, it keeps data in a buffer statically allocated as a member array, instead of using the heap. Also try to use things like . Reserve as much as possible.
– Johannes Schaub - litb Mar 12 '09 at 10:35 you may like the video over here: video.google.com/videoplay? Docid=-562129216565760352 it's alexandrescu talking about his string class using policies for COW/noCOW and small-string-optimization. Interesting watch – Johannes Schaub - litb Mar 12 '09 at 10:36.
It looks like you're misusing char* in the code you pasted. If you have std::string a = "this is a"; std::string be = "this is b" a = b; you're performing a string copy operation. If you do the same with char*, you're performing a pointer copy operation.
The std::string assignment operation allocates enough memory to hold the contents of be in a, then copies each character one by one. In the case of char*, it does not do any memory allocation or copy the individual characters one by one, it just says "a now points to the same memory that be is pointing to. " My guess is that this is why std::string is slower, because it's actually copying the string, which appears to be what you want.To do a copy operation on a char* you'd need to use the strcpy() function to copy into a buffer that's already appropriately sized.
Then you'll have an accurate comparison. But for the purposes of your program you should almost definitely use std::string instead.
You are most certainly doing something wrong, or at least not comparing "fairly" between STL and your own code. Of course, it's hard to be more specific without code to look at. It could be that you're structuring your code using STL in a way that causes more constructors to run, or not re-using allocated objects in a way that matches what you do when you implement the operations yourself, and so on.
When writing C++ code using any utility class (whether STL or your own) instead of eg. Good old C null terminated strings, you need to rememeber a few things. If you benchmark without compiler optimisations on (esp. Function inlining), classes will lose.
They are not built-ins, even stl. They are implemented in terms of method calls.Do not create unnesessary objects. Do not copy objects if possible.
Pass objects as references, not copies, if possible, Use more specialised method and functions and higher level algorithms.Eg. : std::string a = "String a" std::string be = "String b" // Use a. Swap(b); // Instead of std::string tmp = a; a = b; be = tmp; And a final note.
When your C-like C++ code starts to get more complex, you need to implement more advanced data structures like automatically expanding arrays, dictionaries, efficient priority queues. And suddenly you realise that its a lot of work and your classes are not really faster then stl ones. Just more buggy.
If used correctly, std::string is as efficient as char*, but with the added protection. If you are experiencing performance problems with the STL, it's likely that you are doing something wrong. Additionally, STL implementations are not standard across compilers.
I know that SGI's STL and STLPort perform generally well. That said, and I am being completely serious, you could be a C++ genius and have devised code that is far more sophisticated than the STL. It's not likely , but who knows, you could be the LeBron James of C++.
If you have an indication of the eventual size of your vector you can prevent excessive resizes by calling reserve() before filling it up.
My apologies, I significantly edited the question after posting to focus on std::string's. But why doesn't STL automatically reserve extra space if it sees you creating a vector using push_back()? – Tim Cooper Mar 12 '09 at 9:43 2 @Tim: Most implementations of vector do -- when space runs out, they reallocate to twice the original size.
This way, adding n elements leads to at most log(n) reallocations, and you never waste more than 50% memory. – j_random_hacker Mar 12 '09 at 10:00.
Good performance isn't always easy with STL, but generally, it is designed to give you the power. I found Scott Meyers' "Effective STL" an eye-opener for understanding how to deal with the STL efficiently. Read!
As others said, you are probably running into frequent deep copies of the string, and compare that to a pointer assignment / reference counting implementation. Generally, any class designed towards your specific needs, will beat a generic class that's designed for the general case. But learn to use the generic class well, and learn to ride the 80:20 rules, and you will be much more efficient than someone rolling everything on their own.
One specific drawback of std::string is that it doesn't give performance guarantees, which makes sense. As Tim Cooper mentioned, STL does not say whether a string assignment creates a deep copy. That's good for a generic class, because reference counting can become a real killer in highly concurrent applications, even though it's usually the best way for a single threaded app.
The main rules of optimization: Rule 1: Don't do it. Rule 2: (For experts only) Don't do it yet. Are you sure that you have proven that it is really the STL that is slow, and not your algorithm?
They didn't go wrong. STL implementation is generally speaking better than yours. I'm sure that you can write something better for a very particular case, but a factor of 2 is too much... you really must be doing something wrong.
I would say that STL implementations are better than the traditional implementations. Also did you try using a list instead of a vector, because vector is efficient for some purpose and list is efficient for some other.
A large part of the reason might be the fact that reference-counting is no longer used in modern implementations of STL. Here's the story (someone correct me if I'm wrong): in the beginning, STL implementations used reference counting, and were fast but not thread-safe - the implementors expected application programmers to insert their own locking mechanisms at higher levels, to make them thread-safe, because if locking was done at 2 levels then this would slow things down twice as much. However, the programmers of the world were too ignorant or lazy to insert locks everywhere.
For example, if a worker thread in a multi-threaded program needed to read a std::string commandline parameter, then a lock would be needed even just to read the string, otherwise crashes could ensue. (2 threads increment the reference count simultaneously on different CPU's (+1), but decrement it separately (-2), so the reference count goes down to zero, and the memory is freed. ) So implementors ditched reference counting and instead had each std::string always own its own copy of the string.
More programs worked, but they were all slower. So now, even a humble assignment of one std::string to another, (or equivalently, passing a std::string as a parameter to a function), takes about 400 machine code instructions instead of the 2 it takes to assign a char*, a slowdown of 200 times. I tested the magnitude of the inefficiency of std::string on one major program, which had an overall slowdown of about 100% compared with null-terminated strings.
I also tested raw std::string assignment using the following code, which said that std::string assignment was 100-900 times slower. (I had trouble measuring the speed of char* assignment). I also debugged into the std::string operator=() function - I ended up knee deep in the stack, about 7 layers deep, before hitting the 'memcpy()'.
I'm not sure there's any solution. Perhaps if you need your program to be fast, use plain old C++, and if you're more concerned about your own productivity, you should use Java. #define LIMIT 800000000 clock_t start; std::string foo1 = " std::string foo2 = " yeah you too"; std::string f; start = clock(); for (int i=0; I.
You are comparing apples with oranges. In the second case you are just changing some pointers. The equivalent to the first code will be to call strcpy().
Also, I believe you didn't copy-pasted all the code – Ionut Anghelcovici Mar 12 '09 at 8:33 1 Wrong, seriously wrong. Locking objects against concurrent access is still needed today. But with reference counting, you had to lock all strings that could possibly be a copy of the one you're working with.
Furthermore, the performace of COW was measured to be slower, see google for details. – MSalters Mar 12 '09 at 8:52 MSalters, my apologies if I implied somewhere that removing reference counting from std::string removed the need to lock any objects against concurrent access. – Tim Cooper Mar 12 '09 at 10:20 Ionut Anghelcovici: I realise that char* involves copying only pointers.
I guess my point is that I would rather do that than copy the full string. – Tim Cooper Mar 12 '09 at 12:10 If you would rather copy pointers, then just copy pointers to std::string. Otherwise it is simply not a meaningful comparison.
– Vagrant Mar 12 '097 at 6:36.
I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.