7 ms·

"Finally, which version is likely to be the most efficient? Yes, the C++ version, because it does not have to count the argument characters and does not use the

"Finally, which version is likely to be the most efficient? Yes, the C++ version, because it does not have to count the argument characters and does not use the free store (dynamic memory) for short argument strings." I just compiled the C code and the C++ code using: gcc -std=c99 -Wall -Wextra test.c -o test g++ -std=c++11 -Wall -Wextra test.cpp -o test According to valgrind: C: total heap usage: 1 allocs, 1 frees, 21 bytes allocated C++: total heap usage: 4 allocs, 4 frees, 145 bytes allocated Using gcc (Debian 4.7.2-5) [edit] Repeated using gcc 4.9.1 and clang 3.5.0 with -std=c++14. No difference. [edit] Seems with Clang and libc++ it's better than the C implementation as it doesn't do any heap allocation: clang++ -stdlib=libc++ -std=c++14 -Wall -Wextra -g test.cpp -o test total heap usage: 0 allocs, 0 frees, 0 bytes allocated But still, that's only because the C version was explicitly written to use heap allocation. It need not do so.

nly 12y ago
The articles promise is actually terribly dubious. Firstly, in the real world, name+'@'+domain is likely to exceed the capacity for any SSO anyway. Even the example composition, which is 21 chars, may resort to heap allocation under some implementations. It's a bad solution to depend on it for performance. Secondly, as you discovered, the current GNU stdlibc++ implementation of std::string will always allocate for short strings. Even 1 byte. This is for binary back-compat and will hopefully be fixed in GCC 5.0. For now try it with Clang and libc++. See[0] for more information and a comparison of current implementations.... the standard doesn't require SSO at all. Thirdly, and getting to the deeper issue, once the heap is involved the C version is nearly (it needs length params) optimal and will still always be more efficient than the C++ code. Why? The C++ solution uses uses operator+ which is fundamentally performing a different and less general algorithm. For composition it will introduce some amount of repeated work which even the best link-time optimizing compilers probably won't remove, and may, depending on the length of the trailing string segments, and the growth strategy used under the covers, force two allocations. The standard doesn't give complexity guarantees for mutation on std::string at all, so the resulting performance could, on some platforms, be very bad. In all cases you will be able to construct an input that forces more than one allocation (exponentially growing segment sizes). There's also another efficiency issue in the naive op+ approach... C++s allocator specification doesn't provide realloc() so a portable solution will always use more peak memory, on average, when it is forced to reallocate. The C++ solution is just using the wrong algorithm for the job. You can write, and I have toyed with[1], a variadic strcat() function that will be optimal in the generic case. The standard library just lacks one. It's embarrassing, but fairly understandable given that variadic templates didn't come in to the standard until 2011. I'm hoping if they introduce one it'll be called scat() :-) I'm a big C++ fan, but we shouldn't be deluding ourselves here. Fortunately, these things can be fixed within the framework of the current language. [0] https://github.com/elliotgoodrich/SSO-23/blob/master/README.md https://github.com/elliotgoodrich/SSO-23/blob/master/README.... [1] http://codepad.org/rkmNTkIn http://codepad.org/rkmNTkIn
- mike-cardwell 12y ago
  That's the good thing about C. With C++, you don't know what is being allocated, where. With C, it is explicit. You know what's happening if you call malloc. And this compose function could easily be written in C to take the "addr" as an argument to be filled, rather than provide it as a return value. Then it can be entirely stack allocated. The caller would need to make sure that the "addr" array was large enough of course. I started learning C and C++ together at the same time a few years ago. I prefer to code in C++, using the standard template library, but there's always this extremely annoying little voice in the back of my head saying, "you could do this more efficiently if you operated on character arrays instead of a std::string"
  - anthay 12y ago
    On the other hand, I think one of the good things about C++ is that you have a choice. If you wish to write code that explicitly allocates memory for a string of characters you can. You can even wrap it up in a class to make it easy to use.
  - pjmlp 12y ago
    > You know what's happening if you call malloc. You think you know what is happening. There are so many ways to implement malloc across OS and compilers. > "you could do this more efficiently if you operated on character arrays instead of a std::string" A bounds error waiting to happen at every string operation.
  - humanrebar 12y ago
    > That's the good thing about C. With C++, you don't know what is being allocated, where. With C, it is explicit. You're complaining about allocation in the C++ standard library. How many allocations does sqlite3_open_v2 make? How about git_repository_open? C code hides allocation just as much as C++ code does. Only C++ provides simple mechanisms (destructors) to make sure everything gets cleaned up when the stack unwinds. I'll agree that std::string does the wrong thing here. The C++ standard library gets strings wrong in a lot of ways. That's why vector usually provides better examples.
- 12y ago
robert_tweed 12y ago
To paraphrase Don Knuth, "I have only proven it correct, I haven't tested it." To be fair, he says "likely to be" and results may vary between compilers. He also makes reference to the speed penalty of calling strlen(), which isn't necessary with std:string because it stores the length. Even with more allocations, it's possible the C++ version runs faster. It should have a lower computational complexity, meaning it would be faster if the input strings were much longer than they are in this example.
BudVVeezer 12y ago
Try it with -stdlib=libc++, since that's what will control the behavior of std::string.
- mike-cardwell 12y ago
  Ooh. Nice: total heap usage: 0 allocs, 0 frees, 0 bytes allocated
pjmlp 12y ago
Your comparison entails the fallacy of using compiler specific behavior for what the standard doesn't specify.
pierrebai 12y ago
This is the archetypal problem with benchmarks: not only are they hard to design, but people will incorrectly nit-pick the results. You count the number of allocations, without looking at the big picture: this is a toy example. It provides the hard-coded input to the function. This results in the C version not having to allocate memory for the hard-coded literals and the function problably being inlined and optimized away and the strlen() calls being equally optimized away as the length of the strings are known at compile time. In the real world, these would come from some input where they would need to be allocated on the heap, just like the C++ version does. It would use just as many allocations, except they will all be hand-rolled, hand-held, error-prone, with every bit of memory management explicit. C++ is superior in every measure here. Only in toy programs and hard-coded strings does C wins. If the goal was to have as few allocations from hard-coded strings, then just write "foo@bar" and avoid the concatenation altogether. That is not the point of the example. (Also, the newer C++ standard support std::string literals, FWIW.)
- mnem 12y ago
  It may not be the point of the example but it's mentioned explicitly by the article's author as a feature. Doesn't that make allocations in the example fair to comment on?
- StephanTLavavej 12y ago
  C++14's "meow"s is syntactic sugar for string("meow"), with identical efficiency.
  - mike-cardwell 12y ago
    If that's the case, then when I do: auto str = "something"; Why is "str" a "const char " rather than a std::string? Tested using "-std=c++14" with both gcc version 4.9.1, clang 3.5.0 and with both libstdc++ and libc++ ? [edit] If you're the guy who does the MSDN videos on C++, thank you*. They've been incredibly useful to me.
    - StephanTLavavej 12y ago
maxlybbert 12y ago
Try it with optimizations on: gcc -std=c99 -O3 -Wall -Wextra test.c -o test g++ -std=c++11 -O3 -Wall -Wextra test.cpp -o test In my experience, C++ compilers are great at eliding temporaries and various constructor calls (and related memory allocations), but only if optimizations are turned on.
- mike-cardwell 12y ago
  Made no difference
  - maxlybbert 12y ago
    Thanks. It was worth a shot. Which version of GCC are we talking about?
    - mike-cardwell 12y ago
      The different versions of gcc and clang that I tried are higher up in this thread: https://news.ycombinator.com/item?id=8722519 https://news.ycombinator.com/item?id=8722519

nly 12y ago

The articles promise is actually terribly dubious. Firstly, in the real world, name+'@'+domain is likely to exceed the capacity for any SSO anyway. Even the example composition, which is 21 chars, may resort to heap allocation under some implementations. It's a bad solution to depend on it for performance. Secondly, as you discovered, the current GNU stdlibc++ implementation of std::string will always allocate for short strings. Even 1 byte. This is for binary back-compat and will hopefully be fixed in GCC 5.0. For now try it with Clang and libc++. See[0] for more information and a comparison of current implementations.... the standard doesn't require SSO at all. Thirdly, and getting to the deeper issue, once the heap is involved the C version is nearly (it needs length params) optimal and will still always be more efficient than the C++ code. Why? The C++ solution uses uses operator+ which is fundamentally performing a different and less general algorithm. For composition it will introduce some amount of repeated work which even the best link-time optimizing compilers probably won't remove, and may, depending on the length of the trailing string segments, and the growth strategy used under the covers, force two allocations. The standard doesn't give complexity guarantees for mutation on std::string at all, so the resulting performance could, on some platforms, be very bad. In all cases you will be able to construct an input that forces more than one allocation (exponentially growing segment sizes). There's also another efficiency issue in the naive op+ approach... C++s allocator specification doesn't provide realloc() so a portable solution will always use more peak memory, on average, when it is forced to reallocate. The C++ solution is just using the wrong algorithm for the job. You can write, and I have toyed with[1], a variadic strcat() function that will be optimal in the generic case. The standard library just lacks one. It's embarrassing, but fairly understandable given that variadic templates didn't come in to the standard until 2011. I'm hoping if they introduce one it'll be called scat() :-) I'm a big C++ fan, but we shouldn't be deluding ourselves here. Fortunately, these things can be fixed within the framework of the current language. [0] https://github.com/elliotgoodrich/SSO-23/blob/master/README.md https://github.com/elliotgoodrich/SSO-23/blob/master/README.... [1] http://codepad.org/rkmNTkIn http://codepad.org/rkmNTkIn

mike-cardwell 12y ago
That's the good thing about C. With C++, you don't know what is being allocated, where. With C, it is explicit. You know what's happening if you call malloc. And this compose function could easily be written in C to take the "addr" as an argument to be filled, rather than provide it as a return value. Then it can be entirely stack allocated. The caller would need to make sure that the "addr" array was large enough of course. I started learning C and C++ together at the same time a few years ago. I prefer to code in C++, using the standard template library, but there's always this extremely annoying little voice in the back of my head saying, "you could do this more efficiently if you operated on character arrays instead of a std::string"
- anthay 12y ago
  On the other hand, I think one of the good things about C++ is that you have a choice. If you wish to write code that explicitly allocates memory for a string of characters you can. You can even wrap it up in a class to make it easy to use.
- pjmlp 12y ago
  > You know what's happening if you call malloc. You think you know what is happening. There are so many ways to implement malloc across OS and compilers. > "you could do this more efficiently if you operated on character arrays instead of a std::string" A bounds error waiting to happen at every string operation.
- humanrebar 12y ago
  > That's the good thing about C. With C++, you don't know what is being allocated, where. With C, it is explicit. You're complaining about allocation in the C++ standard library. How many allocations does sqlite3_open_v2 make? How about git_repository_open? C code hides allocation just as much as C++ code does. Only C++ provides simple mechanisms (destructors) to make sure everything gets cleaned up when the stack unwinds. I'll agree that std::string does the wrong thing here. The C++ standard library gets strings wrong in a lot of ways. That's why vector usually provides better examples.
12y ago

robert_tweed 12y ago

To paraphrase Don Knuth, "I have only proven it correct, I haven't tested it." To be fair, he says "likely to be" and results may vary between compilers. He also makes reference to the speed penalty of calling strlen(), which isn't necessary with std:string because it stores the length. Even with more allocations, it's possible the C++ version runs faster. It should have a lower computational complexity, meaning it would be faster if the input strings were much longer than they are in this example.

BudVVeezer 12y ago

Try it with -stdlib=libc++, since that's what will control the behavior of std::string.

mike-cardwell 12y ago
Ooh. Nice: total heap usage: 0 allocs, 0 frees, 0 bytes allocated

pjmlp 12y ago

Your comparison entails the fallacy of using compiler specific behavior for what the standard doesn't specify.

pierrebai 12y ago

This is the archetypal problem with benchmarks: not only are they hard to design, but people will incorrectly nit-pick the results. You count the number of allocations, without looking at the big picture: this is a toy example. It provides the hard-coded input to the function. This results in the C version not having to allocate memory for the hard-coded literals and the function problably being inlined and optimized away and the strlen() calls being equally optimized away as the length of the strings are known at compile time. In the real world, these would come from some input where they would need to be allocated on the heap, just like the C++ version does. It would use just as many allocations, except they will all be hand-rolled, hand-held, error-prone, with every bit of memory management explicit. C++ is superior in every measure here. Only in toy programs and hard-coded strings does C wins. If the goal was to have as few allocations from hard-coded strings, then just write "foo@bar" and avoid the concatenation altogether. That is not the point of the example. (Also, the newer C++ standard support std::string literals, FWIW.)

mnem 12y ago
It may not be the point of the example but it's mentioned explicitly by the article's author as a feature. Doesn't that make allocations in the example fair to comment on?
StephanTLavavej 12y ago
C++14's "meow"s is syntactic sugar for string("meow"), with identical efficiency.
- mike-cardwell 12y ago
  If that's the case, then when I do: auto str = "something"; Why is "str" a "const char " rather than a std::string? Tested using "-std=c++14" with both gcc version 4.9.1, clang 3.5.0 and with both libstdc++ and libc++ ? [edit] If you're the guy who does the MSDN videos on C++, thank you*. They've been incredibly useful to me.
  - StephanTLavavej 12y ago

maxlybbert 12y ago

Try it with optimizations on: gcc -std=c99 -O3 -Wall -Wextra test.c -o test g++ -std=c++11 -O3 -Wall -Wextra test.cpp -o test In my experience, C++ compilers are great at eliding temporaries and various constructor calls (and related memory allocations), but only if optimizations are turned on.

mike-cardwell 12y ago
Made no difference
- maxlybbert 12y ago
  Thanks. It was worth a shot. Which version of GCC are we talking about?
  - mike-cardwell 12y ago
    The different versions of gcc and clang that I tried are higher up in this thread: https://news.ycombinator.com/item?id=8722519 https://news.ycombinator.com/item?id=8722519