Why do std::string operations perform poorly?

It's not that std::string performs poorly (as much as I dislike C++), it's that string handling is so heavily optimized for those other languages.

It's not that std::string performs poorly (as much as I dislike C++), it's that string handling is so heavily optimized for those other languages. Your comparisons of string performance are misleading, and presumptuous if they are intended to represent more than just that. I know for a fact that Python string objects are completely implemented in C, and indeed on Python 2.7, numerous optimizations exist due to the lack of separation between unicode strings and bytes.

If you ran this test on Python 3. X you will find it considerably slower. Javascript has numerous heavily optimized implementations.It's to be expected that string handling is excellent here.

Your Java result may be due to proper string handling, or some other poor case. I expect that a Java expert could step in and fix this test with a few changes.As for your C++ example, I'd expect performance to slightly exceed the Python version. It does the same operations, with less interpreter overhead.

This is reflected in your results. Preceding the test with s. Reserve(limit); would remove reallocation overhead.

I'll repeat that you're only testing a single facet of the languages implementations. The results for this test do not reflect the overall language speed. I've provided a C version to show how silly such pissing contests can be: #define _GNU_SOURCE #include #include void test() { int limit = 102 * 1024; char slimit; size_t size = 0; while (size.

2 FWIW the difference between Python 2.7 and 3.2 is just under 10%. It is possible that PEP 393 will remove that difference in Python 3.3. Also it might be worth mentioned that searching strings in Python uses a form of Boyer-Moore so when the string gets longer it should gain an advantage over languages that do a plain search. – Duncan Nov 29 at 12:20 @Matt: Well, the C program is too extreme... I didn't tried to make a battle or contest between languages, for each language has its optimization in different ways.

I just want to find a language that can proceed strings with quite good efficiency. The program just described a case that a program reads from an input(console or socket), maybe decrypts it then, and searches through the string for a specified pattern.My test program simplified the procedure and was just a demo, of course. The result just reminds me C++ is not always the sharpest knife.

And thanks anyway :) – Wu Shu Nov 29 at 14:01 1 @Wu Shu: If the specific pattern to search for is fixed and predetermined, you can construct an automaton to search for the pattern. This will be much faster than repeated calls to std::string::find. – swegi Nov 29 at 15:43 2 @WuShu: actually, C and C++ are probably the sharpest knives.

It's just that Python and Node. Js may be chainsaws. It's heavy and sometimes overkill, but when you tire in C++ you appreciate the "batteries included" approach they took in Python.

– Matthieu M. Nov 29 at 20:38 1 In java, using StringBuilder instead of String speeds it up (on my machine) aproximately 4 times, rest is searching. In java, string is immutable, so what he is doing is atrociously wrong string manipulation in java.

Then there is issue of timing VM start instead of timing usefulactions (it is issue for all languages on VM, not just java) – user470365 Nov 30 at 12:02.

So I went and played a bit with this on ideone.org. Here a slightly modified version of your original C++ program, but with the appending in the loop eliminated, so it only measures the call to std::string::find(). Note that I had to cut the number of iterations to ~40%, otherwise ideone.Org would kill the process.

#include #include int main() { const std::string::size_type limit = 42 * 1024; unsigned int found = 0; //std::string s; std::string s(limit, 'X'); for (std::string::size_type I = 0; I 0) std::cout Org are time: 3.37s. (Of course, this is highly questionably, but indulge me for a moment and wait for the other result. ) Now we take this code and swap the commented lines, to test appending, rather than finding.

Note that, this time, I had increased the number of iterations tenfold in trying to see any time result at all. #include #include int main() { const std::string::size_type limit = 1020 * 1024; unsigned int found = 0; std::string s; //std::string s(limit, 'X'); for (std::string::size_type I = 0; I 0) std::cout Org, despite the tenfold increase in iterations, are time: 0s. My conclusion: This benchmark is, in C++, highly dominated by the searching operation, the appending of the character in the loop has no influence on the result at all.

Was that really your intention?

Very weird. +1. – MikeNakis Nov 29 at 12:33 3 @sbi: and that is when one notes than in C++ find is O(N), while in Python indexOf uses Boyer-Moore (as noted by Duncan in a comment).

Once again, "batteries included". – Matthieu M. Nov 29 at 12:56 3 @Matthieu M.

: Boyer-Moore does not gain you anything here, because the first character of the search-for string is not found at all in the search-into string. On the contrary, it may be adding some overhead, needlessly processing the search-for string in every iteration of the loop. – MikeNakis Nov 29 at 16:06 1 Are we sure that string::find(const char*) isn't just implemented in terms of string::find(const string&)?

If it was, memory allocations could be expensive here. – Kylotan Nov 29 at 18:19 @Kylotan: I tested both. No visible difference.

– Matthieu M. Nov 29 at 20:34.

The idiomatic C++ solution would be: #include #include #include int main() { const int limit = 102 * 1024; std::string s; s. Reserve(limit); const std::string pattern("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); for (int I = 0; I "; } std::cout.

Confirmed. G++ 4.4.3. In my test 5s for search, 12.5s for find (both in the same exe; my test times are longer as I pre-created the string with std::string s(limit,'X'); I.e.

Search and find had more work to do. ) CONCLUSION: stdlib find() on g++ has lots of potential for optimization! – Darren Cook Dec 1 at 1:15 Wow; added a memmem() version, and it is 0.75s (using the same string, accessed via c_str()).(Actually, it was 0; the whole loop seemed to get optimized away; so I added some minor computation to the loop to stop that.) NEW CONCLUSION: find() and search() are doing something weird, that even -O3 cannot optimize, or memmem is using some special CPU feature.

Fascinating! – Darren Cook Dec 1 at 1:35 4 The reason std::search is faster than std::string::search is the because (by convention?) std::search is implemented in the header which gives the compiler much more room to optimise. Std::string::search on the other hand is not.(And because this is calling the function so many times, it makes a big different) – Heptic Dec 1 at 22:29.

That is the most obvious one: please try to do s. Reserve(limit); before main loop. Documentation is here.

I should mention that direct usage of standard classes in C++ in the same way you are used to do it in Java or Python will often give you sub-par performance if you are unaware of what is done behind the desk. There is no magical performance in language itself, it just gives you right tools.

On my machine adding s. Reserve(limit) before the loop makes no perceptible difference to performance. – aix Nov 29 at 11:44 I agree with what you are saying in general, but have you tested this?

With gcc 4.6 I don't get any speedup when using string::reserve. Can you show how to do the concatenation in a fast way, exploiting the knowledge of how the classes work in the background? – Szabolcs Nov 29 at 11:48 Is that really an issue here?

Each string::operator++ is only appending a single character, so memory reallocation and copying shouldn't be a big drain. – Steve314 Nov 29 at 11:48 Yes I tried s. Reserve(102 * 1024), but no help.It's about 5.895s and little improvement.

I think the bottle neck is in string search. – Wu Shu Nov 29 at 11:49 1 Well, checked this in practice. Replacing s += "X" with string s(102*1024, 'X'); made enormous speed improvement ( real 0m0.003s in my VBox ).

Std::string::reserve not helping though, despite what I have said ( should have had same effect in my opinion though ). Need to investigate a bit more. Edited: lol, only now have paid attention to the way for loop is stated :) ok, rollback everything – Михаил Страшун Nov 29 at 12:24.

For C++, try to use std::string for "ABCDEFGHIJKLMNOPQRSTUVWXYZ" - in my implementation string::find(const charT* s, size_type pos = 0) const calculates length of string argument.

I tried it, and it does not make any difference. – MikeNakis Nov 29 at 13:14.

What you are missing here is the inherent complexity of the find search. You are executing the search 102 * 1024 (104 448) times. A naive search algorithm will, each time, try to match the pattern starting from the first character, then the second, etc... Therefore, you have a string that is going from length 1 to N, and at each step you search the pattern against this string, which is a linear operation in C++.

That is N * (N+1) / 2 = 5 454 744 576 comparisons. I am not as surprised as you are that this would take some time... Let us verify the hypothesis by using the overload of find that searches for a single A: Original: 6.94938e+06 ms Char : 2.10709e+06 ms About 3 times faster, so we are within the same order of magnitude. Therefore the use of a full string is not really interesting.

Conclusion? Maybe that find could be optimized a bit. But the problem is not worth it.

Note: and to those who tout Boyer Moore, I am afraid that the needle is too small, so it won't help much. May cut an order of magnitude (26 characters), but no more.

There is no A in the hay-stack, so it should just check each character in the string that it is not found and not look at the other characters of the pattern. You seem to be describing find_any_of method, which again should find the 'X' very fast here. – UncleBens Nov 29 at 17:11 @UncleBens: not at all, I am talking about find, which even for a string pattern should stop on the first character of the pattern if it does not match and move on in the haystack.

The fact that looking for a single character A (the first character of the pattern) is only 3 times faster confirms my suspicion that it is not the pattern search that is slow, but simply that looking for a pattern in such a long string so many times is plain slow in itself. – Matthieu M. Nov 29 at 20:32.

My first thought is that there isn't a problem. C++ gives second-best performance, nearly ten times faster than Java. Maybe all but Java are running close to the best performance achievable for that functionality, and you should be looking at how to fix the Java issue (hint - StringBuilder).

In the C++ case, there are some things to try to improve performance a bit. In particular... s += 'X'; rather than s += "X"; Declare string searchpattern ("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); outside the loop, and pass this for the find calls. An std::string instance knows it's own length, whereas a C string requires a linear-time check to determine that, and this may (or may not) be relevant to std::string::find performance.

Try using std::stringstream, for a similar reason to why you should be using StringBuilder for Java, though most likely the repeated conversions back to string will create more problems. Overall, the result isn't too surprising though. JavaScript, with a good JIT compiler, may be able to optimise a little better than C++ static compilation is allowed to in this case.

With enough work, you should always be able to optimise C++ better than JavaScript, but there will always be cases where that doesn't just naturally happen and where it may take a fair bit of knowledge and effort to achieve that.

The performance is bounded by the find call, not the allocation. For example, testing the 2nd point, there is just not difference (at all). – Matthieu M.

Nov 29 at 13:07 @Matthieu - well, I didn't say any of my ideas would definitely make a difference. However, the second point is all about the find call. The point is to use a different overload of find which takes the search pattern as an std::string rather than as a C string, and thus (possibly but not definitely) avoid strlen calls within the find call.

Another thought is that since the search pattern is constant, a compiled-pattern approach may work faster (Boyer-Moore string search, for example), but that's cheating - unless e.g. JavaScript optimizers are much smarter than I'd expect. – Steve314 Nov 29 at 13:55 I tested a naive Boyer-Moore (building the table at each step) and it performed worse. The needle is very small (26 characters) compared to the size of the haystack (104448 characters), so the extra complexity balances the speed-up that could be expected.

I guess that building the table outside could help... but maybe not as much as expected. – Matthieu M. Nov 29 at 14:00 1 Stringstream will not give any performance improvements here.

Std::string is already mutable and can insert in constant amortized time. – Billy ONeal Dec 1 at 7:49.

I just tested the C++ example myself. If I remove the the call to std::sting::find, the program terminates in no time. Thus the allocations during string concatenation is no problem here.

If I add a variable sdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" and replace the occurence of "ABC...XYZ" in the call of std::string::find, the program needs almost the same time to finish as the original example. This again shows that allocation as well as computing the string's length does not add much to the runtime. Therefore, it seems that the string search algorithm used by libstdc++ is not as fast for your example as the search algorithms of javascript or python.

Maybe you want to try C++ again with your own string search algorithm which fits your purpose better.

Well, if you remove string::find, this is just string concatenation, and this would be no much difference between languages/runtimes optimized for string: string in C++ is also much more optimized than in C (string as an array of char). String::find is not just a test for searching algorithm, but also a test for traversing string. I'll make another test.

– Wu Shu Nov 29 at 14:48.

It seems that in nodejs better algorithm for search substrings. You can implement self and try it.

Your test code is checking a pathological scenario of excessive string concatenation. (The string-search part of the test could have probably been omitted, I bet you it contributes almost nothing to the final results. ) Excessive string concatenation is a pitfall that most languages warn very strongly against, and provide very well known alternatives for, (i.e.

StringBuilder,) so what you are essentially testing here is how badly these languages fail under scenarios of perfectly expected failure. That's pointless. An example of a similarly pointless test would be to compare the performance of various languages when throwing and catching an exception in a tight loop.

All languages warn that exception throwing and catching is abysmally slow. They do not specify how slow, they just warn you not to expect anything. Therefore, to go ahead and test precisely that, would be pointless.So, it would make a lot more sense to repeat your test substituting the mindless string concatenation part (s += "X") with whatever construct is offered by each one of these languages precisely for avoiding string concatenation.

(Such as class StringBuilder. ).

1 I have just checked the example code myself, and it turns out that almost all of the runtime is spend during string search. – swegi Nov 29 at 12:07 o_O -- OK, then there is something totally weird going on. Prior to posting my answer I checked the documentation of all the find() and indexOf() methods in all of the above languages to make sure that they all perform straight non-regex, case-sensitive search.So, if search is the problem despite the triviality of the task, I do not know what to say.

– MikeNakis Nov 29 at 12:19 Well, I checked only the C++ example, I think you are right for the really poor performance of the Java example. – swegi Nov 29 at 12:21 1 @swegi which languages did you check? I expect it may vary between them.

With Python 2.7 the code as written takes 13.1s on my system, removing the find call it takes 0.019s. So the string concatenation (at least on Python) is the irrelevant part of the test. This is probably only true because the C version of Python uses reference counting and can do the concatenation in-place when it can detect that there is only one reference to the string.

– Duncan Nov 29 at 12:31 3 std::string::operator+= is the construct offered by C++ for avoiding the thing that in Java causes String concatenation to be slow. Std::string is a mutable class, same as StringBuilder. TBH I think it's a bit confusing that the question is "why is C++ slow?

", but includes Java results that are waaay slower, prompting various people to explain why the Java results are slow. Which is irrelevant to the question ;-) – Steve Jessop Nov 29 at 12:43.

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.