Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: Efficiency of standard containers
59 views
Skip to first unread message
Alf P. Steinbach
Dec 20, 2016, 6:16:40 PM12/20/16
to
On 20.12.2016 23:37, Stefan Ram wrote:
> The new C++ primer says that the new library containers are
> faster than ever and perform as well or better than
> everything one can hope to write oneself.
>
> Chandler Carruth used to say in 2014 that all the ::std::
> containers have such hindering requirements that one can use
> only ::std::vector when one cares for efficiency, but in
> 2016 he says that because of the impossibility of the
> small-size optimization even ::std::vector is unusable when
> one wants efficient code. He than describes clang's fast
> "SmallVector" implementation, while someone from Facebook
> explains how they made facebook much faster by replacing
> ::std::string with their fbstring, which uses a very
> efficient small-string representation.
For a long while Facebook had Andrei Alexandrescu to do C++ stuff for
them. As I understand it he's now devoting his time to D language
development. But during this long period Facebook had the luxury of
having a superb C++ designer, so they could afford the DIY approach,
while with most any other company it would have ended in tears.
That said, I mostly agree with the sentiment that one can do much better
than the standard library, both in terms of efficiency, code clarity and
readability, and convenience.
This is especially so for strings and formatting.
But in the high circles that lead opinions, this stuff is highly
politicized, possibly about what arguments have been forwarded to make
changes in the standard, and irrational excuses are put forward.
E.g., on SO there was ¹a question whether C++11 disallowed the
copy-on-write optimization for `std::string`. The real answer to that is
yes, because C++ requires indexing to be constant time always, i.e.
unsharing of a buffer can't be put off till indexing time. I provided
that answer and it got 2 downvotes and no upvotes. But the politically
correct answer, accepted on SO with lots of upvotes, is that correct COW
is impossible (that's incorrect) because “calling non-const operator[]
would require making a copy (and invalidating references), which is
disallowed”. That answer is a self-contradiction – because in a correct
implementation there are no references to be invalidated at the time of
a buffer unsharing, it's unshared precisely because the possibility of a
reference looms on the horizon – but in spite of being obvious bollocks,
just a self-contradiction, it's upvoted 86 times.
Cheers!,
- Alf
¹ <url:
http://stackoverflow.com/questions/12199710/legality-of-cow-stdstring-implementation-in-c11>
> The new C++ primer says that the new library containers are
> faster than ever and perform as well or better than
> everything one can hope to write oneself.
>
> Chandler Carruth used to say in 2014 that all the ::std::
> containers have such hindering requirements that one can use
> only ::std::vector when one cares for efficiency, but in
> 2016 he says that because of the impossibility of the
> small-size optimization even ::std::vector is unusable when
> one wants efficient code. He than describes clang's fast
> "SmallVector" implementation, while someone from Facebook
> explains how they made facebook much faster by replacing
> ::std::string with their fbstring, which uses a very
> efficient small-string representation.
For a long while Facebook had Andrei Alexandrescu to do C++ stuff for
them. As I understand it he's now devoting his time to D language
development. But during this long period Facebook had the luxury of
having a superb C++ designer, so they could afford the DIY approach,
while with most any other company it would have ended in tears.
That said, I mostly agree with the sentiment that one can do much better
than the standard library, both in terms of efficiency, code clarity and
readability, and convenience.
This is especially so for strings and formatting.
But in the high circles that lead opinions, this stuff is highly
politicized, possibly about what arguments have been forwarded to make
changes in the standard, and irrational excuses are put forward.
E.g., on SO there was ¹a question whether C++11 disallowed the
copy-on-write optimization for `std::string`. The real answer to that is
yes, because C++ requires indexing to be constant time always, i.e.
unsharing of a buffer can't be put off till indexing time. I provided
that answer and it got 2 downvotes and no upvotes. But the politically
correct answer, accepted on SO with lots of upvotes, is that correct COW
is impossible (that's incorrect) because “calling non-const operator[]
would require making a copy (and invalidating references), which is
disallowed”. That answer is a self-contradiction – because in a correct
implementation there are no references to be invalidated at the time of
a buffer unsharing, it's unshared precisely because the possibility of a
reference looms on the horizon – but in spite of being obvious bollocks,
just a self-contradiction, it's upvoted 86 times.
Cheers!,
- Alf
¹ <url:
http://stackoverflow.com/questions/12199710/legality-of-cow-stdstring-implementation-in-c11>
Marcel Mueller
Dec 20, 2016, 6:31:15 PM12/20/16
to
On 20.12.16 23.37, Stefan Ram wrote:
> The new C++ primer says that the new library containers are
> faster than ever and perform as well or better than
> everything one can hope to write oneself.
>
> Chandler Carruth used to say in 2014 that all the ::std::
> containers have such hindering requirements that one can use
> only ::std::vector when one cares for efficiency, but in
> 2016 he says that because of the impossibility of the
> small-size optimization even ::std::vector is unusable when
> one wants efficient code. He than describes clang's fast
> "SmallVector" implementation, while someone from Facebook
> explains how they made facebook much faster by replacing
> ::std::string with their fbstring, which uses a very
> efficient small-string representation.
As always it depends. For general purpose use the standard containers
> The new C++ primer says that the new library containers are
> faster than ever and perform as well or better than
> everything one can hope to write oneself.
>
> Chandler Carruth used to say in 2014 that all the ::std::
> containers have such hindering requirements that one can use
> only ::std::vector when one cares for efficiency, but in
> 2016 he says that because of the impossibility of the
> small-size optimization even ::std::vector is unusable when
> one wants efficient code. He than describes clang's fast
> "SmallVector" implementation, while someone from Facebook
> explains how they made facebook much faster by replacing
> ::std::string with their fbstring, which uses a very
> efficient small-string representation.
are just fine. For spacial cases individual implementations often
perform better.
In fact I am missing a BTree in most container libraries, including C++.
So I implemented my own one in different languages.
Furthermore, I missed an efficient, strongly thread-safe, immutable and
reference counted string implementation. So again I implemented my own one.
And the intrusive_ptr does not provide strong thread safety too. My own
int_ptr does not share this restriction without a larger memory
footprint (just one slot for the intrinsic reference counter by simply
deriving from a base class and one slot for each pointer instance).
And even more C++ standard containers do not benefit from type erasure.
So the code for containers of smart pointers to different types cannot
share the implementation although their memory layout is binary
compatible. So I ended up by writing some container with a non template
base class and a type safe template wrapper for intrusive reference
counting as well.
It is almost always possible to improve things. But there are also
drawbacks in some use cases. The standard containers prefer to be
general purpose with as less as possible pitfalls. Performance is not
the only criterion.
Marcel
Mr Flibble
Dec 20, 2016, 6:43:44 PM12/20/16
to
std::string s = "foo";
const char& r = s[0];
{
std::string s2 = s; // s now shared
s[0] = "c"; // COW happens
} // s2 destroyed
assert(r == 'c'); // bad UB: r will now refer to garbage
Even if we don't consider the UB case above one may also consider 'r' to
be "invalidated" if it stops referring to s[0] and instead refers to
s2[0] because COW happened.
/Flibble
Marcel Mueller
Dec 20, 2016, 6:51:54 PM12/20/16
to
On 21.12.16 00.43, Mr Flibble wrote:
> Invalidating references is a problem, consider:
>
> std::string s = "foo";
> const char& r = s[0];
> {
> std::string s2 = s; // s now shared
> s[0] = "c"; // COW happens
> } // s2 destroyed
> assert(r == 'c'); // bad UB: r will now refer to garbage
>
> Even if we don't consider the UB case above one may also consider 'r' to
> be "invalidated" if it stops referring to s[0] and instead refers to
> s2[0] because COW happened.
You just pointed out why the Java concept of an immutable String class
> Invalidating references is a problem, consider:
>
> std::string s = "foo";
> const char& r = s[0];
> {
> std::string s2 = s; // s now shared
> s[0] = "c"; // COW happens
> } // s2 destroyed
> assert(r == 'c'); // bad UB: r will now refer to garbage
>
> Even if we don't consider the UB case above one may also consider 'r' to
> be "invalidated" if it stops referring to s[0] and instead refers to
> s2[0] because COW happened.
and a mutable StringBuilder is superior. I prefer this concept wherever
possible.
Marcel
Jerry Stuckle
Dec 20, 2016, 7:17:05 PM12/20/16
to
COW. Why would it point to s2[0]? s[0] has not moved - just gotten a
new value (after the copy).
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstu...@attglobal.net
==================
Alf P. Steinbach
Dec 20, 2016, 7:55:39 PM12/20/16
to
On 21.12.2016 00:43, Mr Flibble wrote:
> On 20/12/2016 23:16, Alf P. Steinbach wrote:
>> [snip]
> On 20/12/2016 23:16, Alf P. Steinbach wrote:
>> This is especially so for strings and formatting.
>>
>> But in the high circles that lead opinions, this stuff is highly
>> politicized, possibly about what arguments have been forwarded to make
>> changes in the standard, and irrational excuses are put forward.
>>
>> E.g., on SO there was ¹a question whether C++11 disallowed the
>> copy-on-write optimization for `std::string`. The real answer to that is
>> yes, because C++ requires indexing to be constant time always, i.e.
>> unsharing of a buffer can't be put off till indexing time. I provided
>> that answer and it got 2 downvotes and no upvotes. But the politically
>> correct answer, accepted on SO with lots of upvotes, is that correct COW
>> is impossible (that's incorrect) because “calling non-const operator[]
>> would require making a copy (and invalidating references), which is
>> disallowed”. That answer is a self-contradiction – because in a correct
>> implementation there are no references to be invalidated at the time of
>> a buffer unsharing, it's unshared precisely because the possibility of a
>> reference looms on the horizon – but in spite of being obvious bollocks,
>> just a self-contradiction, it's upvoted 86 times.
>
> Invalidating references is a problem, consider:
>
> std::string s = "foo";
> const char& r = s[0];
> {
> std::string s2 = s; // s now shared
> s[0] = "c"; // COW happens
> } // s2 destroyed
> assert(r == 'c'); // bad UB: r will now refer to garbage
Yes, that's a problem in two ways:
>>
>> But in the high circles that lead opinions, this stuff is highly
>> politicized, possibly about what arguments have been forwarded to make
>> changes in the standard, and irrational excuses are put forward.
>>
>> E.g., on SO there was ¹a question whether C++11 disallowed the
>> copy-on-write optimization for `std::string`. The real answer to that is
>> yes, because C++ requires indexing to be constant time always, i.e.
>> unsharing of a buffer can't be put off till indexing time. I provided
>> that answer and it got 2 downvotes and no upvotes. But the politically
>> correct answer, accepted on SO with lots of upvotes, is that correct COW
>> is impossible (that's incorrect) because “calling non-const operator[]
>> would require making a copy (and invalidating references), which is
>> disallowed”. That answer is a self-contradiction – because in a correct
>> implementation there are no references to be invalidated at the time of
>> a buffer unsharing, it's unshared precisely because the possibility of a
>> reference looms on the horizon – but in spite of being obvious bollocks,
>> just a self-contradiction, it's upvoted 86 times.
>
> Invalidating references is a problem, consider:
>
> std::string s = "foo";
> const char& r = s[0];
> {
> std::string s2 = s; // s now shared
> s[0] = "c"; // COW happens
> } // s2 destroyed
> assert(r == 'c'); // bad UB: r will now refer to garbage
• It was (is?) a bug in the g++ C++03 implementation of COW strings, and
I suspect that's the main reason for the political aspect of this
particular ungoodness.
Or at least I think that's the reason why people get so wrought up about
it: public unthinking herd behavior happens in general when a group of
fanboys perceive negativity about their sacred COW.
• It prevents a COW implementation that is /both/ really efficient and
correct.
So it's an important case, and IMHO a good argument for immutable strings.
With a correct COW implementation “COW happens” (i.e. unsharing of the
in this case static buffer happens) at the first indexing, i.e. this is
not a problem for a correct COW implementation. It's only a problem for
g++'s implementation. But first of all the O(1) requirement for indexing
prevents a correct implementation in C++11 and later, and secondly, even
if the/a correct implementation were permitted by the C++ standard, the
case that you exemplify means it would generally do copying from string
literal that would not occur in an ideal COW.
> Even if we don't consider the UB case above one may also consider 'r' to
> be "invalidated" if it stops referring to s[0] and instead refers to
> s2[0] because COW happened.
Cheers!,
- Alf
Mr Flibble
Dec 20, 2016, 8:32:53 PM12/20/16
to
have to also stop sharing if any iterators are acquired or if c_str() is
called or if a basic_string_view is obtained.. it is starting to sound a
bit unusable so I am not sure I agree with your analysis that that is
doing COW "correctly".
/Flibble
Alf P. Steinbach
Dec 20, 2016, 9:56:48 PM12/20/16
to
The basic_string_view design is particularly unfortunate: it's made
after C++11 and still it returns inefficient and functionality-limiting
references to characters, rather than just the values.
> it is starting to sound a bit unusable
COW-supporting string class design. But that doesn't mean unusable. It
means the /improvement/ from a non-COW implementation is just less than
optimal, and that depending on the operations mix it can be some percent
slower or some percent faster, instead of ~always faster.
However, even within the standard's limited support there are still ways
to access the contents of a COW-implemented std::basic_string without
incurring unsharing of the buffer, including (what pops up from my
association circuits right now):
• Output to a stream.
• Indexing where the result is just used as an rvalue `Char`.
• The range based `for` loop.
I think supporting indexing with use as rvalue might possible with a
pure library implementation, by detecting the return type via `operator
auto()` (or in C++11 and earlier `operator T` with `T` a template
parameter), but if that turns out to have some problem, e.g. overload
resolution?, then it's certainly possible via the special status of the
standard library: that it can rely on compiler support and compiler
intrinsics and knowledge of the particular concrete compiler behavior,
e.g. as the standard library's `offsetof` macro necessarily does.
The range based `for` loop apparently requires compiler support, but
again, the standard library has that support.
If basic_string_view had been reasonably designed then that would also
be a way to access the contents of a COW-implemented string without
incurring a possible unsharing.
This is already pretty rich functionality for accessing the contents.
But a main thing lacking is a way to obtain a /temporary pointer/ to the
buffer, in order to pass to a function requiring such pointer. Sort of
like `c_str()` except the temporary pointer would also be invalidated by
any operation that obtained a possible reference to the string, except
for the `char` value indexing case noted above. A new version of the
standard could just introduce such an operation, so it's possible for
the standard to turn 180 degrees again and support COW.
> so I am not sure I agree with your analysis that that is
> doing COW "correctly".
text in an inline note): “A reference counted implementation must have
the same semantics as a non-reference counted implementation.”
That effectively means /as if/ a separate buffer is used for each instance.
I.e. “correct” is defined by the external behavior always conforming to
the standard's requirements, modulo requirements that are implicitly
ignored in a given context (such as discussing whether this is possible
without the C++11 O(1) requirement on indexing). And the standard
doesn't require an implementation to be optimal! This notion of
correctness, the one specified by the standard, is the one that's
relevant in a question and answer about what the standard permits.
Cheers!,
- Alf
Daniel
Dec 20, 2016, 11:51:21 PM12/20/16
to
On Tuesday, December 20, 2016 at 9:56:48 PM UTC-5, Alf P. Steinbach wrote:
>
> The basic_string_view design is particularly unfortunate: it's made
> after C++11 and still it returns inefficient and functionality-limiting
> references to characters, rather than just the values.
>
I'm happy to have basic_string_view if only to allow an object that owns text
>
> The basic_string_view design is particularly unfortunate: it's made
> after C++11 and still it returns inefficient and functionality-limiting
> references to characters, rather than just the values.
>
to expose it without having an allocator embedded in it. That offers some
efficiency over a forced copy just because a container's and a client's
allocators differ.
But it seems strange to me that a new string related class would continue to
have those find functions that search over bytes or words, depending on
template parameter. That's not helpful unless you're still in ansii world. I
want to know the length of a string in codepoints, and I want to be able to
access the ith codepoint. We need a new char traits that captures string
semantics. But at least compare mostly works.
Daniel
woodb...@gmail.com
Dec 20, 2016, 11:59:24 PM12/20/16
to
more interesting.
>
> It is almost always possible to improve things. But there are also
> drawbacks in some use cases. The standard containers prefer to be
> general purpose with as less as possible pitfalls. Performance is not
> the only criterion.
>
Brian
Ebenezer Enterprises - So far G-d has helped us.
http://webEbenezer.net
>
> Marcel
Paavo Helde
Dec 21, 2016, 2:05:25 AM12/21/16
to
On 21.12.2016 0:37, Stefan Ram wrote:
> The new C++ primer says that the new library containers are
> faster than ever and perform as well or better than
> everything one can hope to write oneself.
>
> Chandler Carruth used to say in 2014 that all the ::std::
> containers have such hindering requirements that one can use
> only ::std::vector when one cares for efficiency, but in
> 2016 he says that because of the impossibility of the
> small-size optimization even ::std::vector is unusable when
> one wants efficient code. He than describes clang's fast
> "SmallVector" implementation, while someone from Facebook
> explains how they made facebook much faster by replacing
> ::std::string with their fbstring, which uses a very
> efficient small-string representation.
Standard containers are general purpose. Of course, it might well happen
> The new C++ primer says that the new library containers are
> faster than ever and perform as well or better than
> everything one can hope to write oneself.
>
> Chandler Carruth used to say in 2014 that all the ::std::
> containers have such hindering requirements that one can use
> only ::std::vector when one cares for efficiency, but in
> 2016 he says that because of the impossibility of the
> small-size optimization even ::std::vector is unusable when
> one wants efficient code. He than describes clang's fast
> "SmallVector" implementation, while someone from Facebook
> explains how they made facebook much faster by replacing
> ::std::string with their fbstring, which uses a very
> efficient small-string representation.
that in some special circumstances a special handcrafted solution would
work significantly more efficiently. The standard cannot foresee or
provide for all kind of special circumstances.
One is of course entitled to craft one's own container if the app speed
is not sufficient and the profiler shows the bottleneck is in a standard
container. Has not happen to me yet, but YMMV.
While on that topic, don't forget that nowadays a large part of
efficiency is related to the memory allocators. Unlike the prev item,
profiling has shown me bottlenecks in the memory allocator several
times. Using a better or more suitable memory allocator with a standard
container might easily have much larger impact to the efficiency than
anything what can be done at the container level itself.
Juha Nieminen
Dec 21, 2016, 2:18:38 AM12/21/16
to
Stefan Ram <r...@zedat.fu-berlin.de> wrote:
> Chandler Carruth used to say in 2014 that all the ::std::
> containers have such hindering requirements that one can use
> only ::std::vector when one cares for efficiency, but in
> 2016 he says that because of the impossibility of the
> small-size optimization even ::std::vector is unusable when
> one wants efficient code.
"Efficient" in what way?
> Chandler Carruth used to say in 2014 that all the ::std::
> containers have such hindering requirements that one can use
> only ::std::vector when one cares for efficiency, but in
> 2016 he says that because of the impossibility of the
> small-size optimization even ::std::vector is unusable when
> one wants efficient code.
Sure, if you are adding and removing elements from containers,
or even creating and destroying containers, in a tight inner
loop millions of times per second, you have to be aware of how
costly it is to allocate and deallocate memory in C-based
languages (and thus you should be aware when such containers
do such allocations and deallocations).
But that's not the only situation where the word "efficient"
could be applied. It could also be applied to efficiency of
searching, or memory usage, or clarity and safety of your code.
Even how much time you have to spend to write and refactor
your code.
If you have the need to copy std::vector instances around millions
of times, then sure, implement your own more efficient variant.
I find myself in need to do that extremely rarely, and instead
I just require vectors to be accessible very efficiently, which
they are. And the convenience of std::vector over a custom
implementation is vastly greater.
Bo Persson
Dec 21, 2016, 11:26:38 AM12/21/16
to
Chandler Carruth can spend time making the program run 1% faster,
because that saves the company millions of dollars on their server farms.
For the rest of us "efficient" most often means "getting the app out
*this* year". Not running 1% faster next year.
Bo Persson
Bonita Montero
Dec 21, 2016, 12:02:53 PM12/21/16
to
Am 21.12.2016 um 17:26 schrieb Bo Persson:
> For the rest of us "efficient" most often means "getting
> the app out *this* year". Not running 1% faster next year.
It should be very rare that a company tunes for the last 1%.
> For the rest of us "efficient" most often means "getting
> the app out *this* year". Not running 1% faster next year.
Even Twitter and eBay use Java on its servers which hasn't
the repute to be the most efficient language (i.e. the VM).
--
http://facebook.com/bonita.montero/
Alf P. Steinbach
Dec 21, 2016, 1:02:12 PM12/21/16
to
On 21.12.2016 03:56, Alf P. Steinbach wrote:
> [snip]
> [snip]
> I think supporting indexing with use as rvalue might possible with a
> pure library implementation, by detecting the return type via `operator
> auto()` (or in C++11 and earlier `operator T` with `T` a template
> parameter),
Sorry I was not thinking there, or in other words, I was momentarily
> pure library implementation, by detecting the return type via `operator
> auto()` (or in C++11 and earlier `operator T` with `T` a template
> parameter),
stupid: one needs a name for the return type in order to discriminate
the cases. So `auto` is out. An old-fashioned template is the only pure
library way as I see, if it works to implement the observable behavior
exactly (or anyway in a proof of concept implementation):
> but if that turns out to have some problem, e.g. overload
> resolution?, then it's certainly possible via the special status of the
> standard library: that it can rely on compiler support and compiler
> intrinsics and knowledge of the particular concrete compiler behavior,
> e.g. as the standard library's `offsetof` macro necessarily does.
Cheers!,
- Alf
Bo Persson
Dec 21, 2016, 1:22:55 PM12/21/16
to
On 2016-12-21 18:02, Bonita Montero wrote:
> Am 21.12.2016 um 17:26 schrieb Bo Persson:
>
>> For the rest of us "efficient" most often means "getting
>> the app out *this* year". Not running 1% faster next year.
>
> It should be very rare that a company tunes for the last 1%.
> Even Twitter and eBay use Java on its servers which hasn't
> the repute to be the most efficient language (i.e. the VM).
>
Yes, but Facebook and Google might. When a 1% saving on the electricity
> Am 21.12.2016 um 17:26 schrieb Bo Persson:
>
>> For the rest of us "efficient" most often means "getting
>> the app out *this* year". Not running 1% faster next year.
>
> It should be very rare that a company tunes for the last 1%.
> Even Twitter and eBay use Java on its servers which hasn't
> the repute to be the most efficient language (i.e. the VM).
>
bill alone means millions of dollars, it is worth it.
Chandler Carruth and lots of benchmarks could surely trim Goggle's code
by that much.
An average Joe Coder would likely not benefit from writing his own
linked list or a std::vector replacement. It will just take a lot of
work to get something that will likely run slower.
The guys implementing the standard library for the major compilers are
not exactly newbies.
So "not using the standard containers" is not the best advice to achive
"efficiency". Except in *very* special cases.
Bo Persson
Bonita Montero
Dec 21, 2016, 1:43:25 PM12/21/16
to
Am 21.12.2016 um 19:22 schrieb Bo Persson:
> Yes, but Facebook and Google might. When a 1% saving on the electricity
> bill alone means millions of dollars, it is worth it.
You don't know this. It's just your assumption.
> Yes, but Facebook and Google might. When a 1% saving on the electricity
> bill alone means millions of dollars, it is worth it.
Homo oeconomicus is just an illusion.
--
http://facebook.com/bonita.montero/
Richard
Dec 21, 2016, 1:43:25 PM12/21/16
to
[Please do not mail me a copy of your followup]
Marcel Mueller <news.5...@spamgourmet.org> spake the secret code
<o3cevp$anj$1...@gwaiyur.mb-net.net> thusly:
>As always it depends. For general purpose use the standard containers
>are just fine. For spacial cases individual implementations often
>perform better.
...and this isn't unique to C++.
C# and Java have standard general containers. Performance gains can
be made by switching to custom containers that are specific to your
use case.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
Marcel Mueller <news.5...@spamgourmet.org> spake the secret code
<o3cevp$anj$1...@gwaiyur.mb-net.net> thusly:
>As always it depends. For general purpose use the standard containers
>are just fine. For spacial cases individual implementations often
>perform better.
C# and Java have standard general containers. Performance gains can
be made by switching to custom containers that are specific to your
use case.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
Alf P. Steinbach
Dec 21, 2016, 1:56:33 PM12/21/16
to
On 21.12.2016 19:22, Bo Persson wrote:
>
> [snip]
officially part the C++ standard library (I believe, I haven't checked
the details) but a year or two or three ago I answered an SO question a
CPython versus C++ string performance: the OP was amazed how much faster
CPython was. But CPython strings are simple reference counted beasts, so
all that code involved was references. After really fighting to have the
question /undeleted/ (!) [fanboys at work again, jeez we don't like
these facts the OP mentions, let's delete], I posted C++ code that did
the same as the OP's example, only efficiently by returning string
views, i.e. references instead of copying strings, and happily that was
faster than Python -- it needn't be, but it was. :)
Later the code I posted was "corrected" by an associative someone, a
someone who recognized patterns but had no understanding, who introduced
a bug, and it was only by chance that I became aware of it.
That last part is relevant because it shows that by using custom data
structures one may gain e.g. efficiency, or readability, but one may
thereby become an open target for maintenance bug introductions.
Cheers!,
- Alf
>
> [snip]
> So "not using the standard containers" is not the best advice to achive
> "efficiency". Except in *very* special cases.
One such case is returning a referencing string-view. Now that's soon
> "efficiency". Except in *very* special cases.
officially part the C++ standard library (I believe, I haven't checked
the details) but a year or two or three ago I answered an SO question a
CPython versus C++ string performance: the OP was amazed how much faster
CPython was. But CPython strings are simple reference counted beasts, so
all that code involved was references. After really fighting to have the
question /undeleted/ (!) [fanboys at work again, jeez we don't like
these facts the OP mentions, let's delete], I posted C++ code that did
the same as the OP's example, only efficiently by returning string
views, i.e. references instead of copying strings, and happily that was
faster than Python -- it needn't be, but it was. :)
Later the code I posted was "corrected" by an associative someone, a
someone who recognized patterns but had no understanding, who introduced
a bug, and it was only by chance that I became aware of it.
That last part is relevant because it shows that by using custom data
structures one may gain e.g. efficiency, or readability, but one may
thereby become an open target for maintenance bug introductions.
Cheers!,
- Alf
Richard
Dec 21, 2016, 2:00:15 PM12/21/16
to
[Please do not mail me a copy of your followup]
"Alf P. Steinbach" <alf.p.stein...@gmail.com> spake the secret code
<o3ej5p$n07$1...@dont-email.me> thusly:
>That last part is relevant because it shows that by using custom data
>structures one may gain e.g. efficiency, or readability, but one may
>thereby become an open target for maintenance bug introductions.
set of unit tests. Maintenance developers will then have confidence
that they haven't broken anything by rerunning the tests.
Bo Persson
Dec 21, 2016, 4:06:29 PM12/21/16
to
On 2016-12-21 19:43, Bonita Montero wrote:
> Am 21.12.2016 um 19:22 schrieb Bo Persson:
>
>> Yes, but Facebook and Google might. When a 1% saving on the electricity
>> bill alone means millions of dollars, it is worth it.
>
> You don't know this. It's just your assumption.
> Homo oeconomicus is just an illusion.
>
I do know actually, because it is a quote from Andrei Alexandrescu from
> Am 21.12.2016 um 19:22 schrieb Bo Persson:
>
>> Yes, but Facebook and Google might. When a 1% saving on the electricity
>> bill alone means millions of dollars, it is worth it.
>
> You don't know this. It's just your assumption.
> Homo oeconomicus is just an illusion.
>
the time when he worked at Facebook.
Starts at 02:55 in https://www.youtube.com/watch?v=MvFj8qo1iuA
Bo Persson
Marcel Mueller
Dec 21, 2016, 6:07:18 PM12/21/16
to
On 21.12.16 05.59, woodb...@gmail.com wrote:
> If you included links to your projects it would be
> more interesting.
Hmm, most of them should be used in the PM123 audio player for OS/2.
> If you included links to your projects it would be
> more interesting.
https://github.com/maazl/pm123/tree/master/src/utils/cpp
xstring.h, smartptr.h:int_ptr<>, container/btree.h and
container/vector.h:vector_int<> are the classes I mentioned.
No source code to be very proud of. Most of it is designed for the old
IBM VACPP compiler which did not support STL anyway. But it should be
functional, reasonable fast and memory conserving. Unfortunately this
application was never intended to be portable. I have ports of some
classes to other platforms and languages, but sorry, they are not open
source.
>> It is almost always possible to improve things. But there are also
>> drawbacks in some use cases. The standard containers prefer to be
>> general purpose with as less as possible pitfalls. Performance is not
>> the only criterion.
>
> The containers are the weakest part of the STL in my opinion.
Compared to some other languages/class libraries the STL containers are
quite orthogonal. The .NET container classes and first of all the
interfaces are higgledy-piggledy.
Marcel
0 new messages