8 ms·

I stopped reading after the first example, which once again (as in the last post in the series) demonstrated that the author doesn't really know what he's talki

by wheels 14y ago

I stopped reading after the first example, which once again (as in the last post in the series) demonstrated that the author doesn't really know what he's talking about. The code would be written as: std::list<person> Not: std::list<person *> ...which avoids the double malloc and presents a nicer API to boot. Not to mention that in that case, a C++ programmer would either use a struct or would need to write accessors. C++ has a lot of warts, and the author seems to have written some non-trivial software in it, but his critiques of it reveal that there are a lot of gaps in his knowledge of the language and a lot of his criticisms are based on falsehoods. (However, a totally valid criticism of C++ is the amount of idiosyncrasies the language has and how relatively difficult it is to master.)

epsylon 14y ago
In practice lists have such poor memory locality that they should almost never be used. Use vectors. EDIT: See for example Stroustrup's discussion on the matter at the 44th minute of this video : http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style http://channel9.msdn.com/Events/GoingNative/GoingNative-2012... On modern architectures, cache misses are performance killers, and a list is a cache-miss machine. Moving memory is cheaper than doing a linear search through a list. What used to be true 20 years ago isn't true anymore, let's stop using those lists already !
- rumcajz 14y ago
  With vectors erase is O(1) anyway.
  - tptacek 14y ago
    Only from the edge of the collection. A vector is a resizable array, and deletion from the middle of one is O(n).
    - astrodust 14y ago
      Is it O(n/2) if the deletion point is half-way? I thought it was proportional to how much data had to be moved.
      - lolcraft 14y ago
        O(n/2) = O(n), so you're right. However... f(n) being O(n) means: there's a N and an x such that, for all n > x, N*n > f(n). By this definition, O(n/2) is the same as O(n) is the same as O(n/42). You just choose a different N. But it's better form to write O(n).
        astrodust 14y ago
        I suppose O(n/(m-n)) time is the appropriate measure, where m is the deletion point and n is the number of items in the vector. The removal time seems to be O(1) for the last element and only slightly higher for the second-last, but for the first it is O(n).
        beagle3 14y ago
        O(..) notation for complexity is usually qualified with "worst case" or "average case". Either way, "best case" behavior of O(1) is not really interesting.
        dkersten 14y ago
        The removal time seems to be O(1) for the last element and only slightly higher for the second-last The removal time for the second-last element is still O(1). There is no slightly higher here. O() does not count steps or cost or anything like that - it counts worst case or asymptotic complexity. O(1) means constant time/space/whatever-you-are-measuring complexity. Removing the last element of a non-empty vector always takes the same amount of time (since we are talking about time complexity in this case) no matter how many elements are in are in the vector. Similarly, removing the second-last element always takes the same number of steps regardless how many elements are in the vector (as long as there are at least 2) - still O(1). That doesn't mean that they take equally long - the second-last element does indeed take longer to remove (by some constant factor), but complexity does not care about that, it only cares about the relative difference in respect to n (usually the size of the input) and the worst case (usually; you can also look up θ(..) and Ω(..) and others, but generally worst case is much more useful than best case, though sometimes average case is good to know too). Note also that a O(n) algorithm may actually execute faster than a O(1) algorithm, at least, for small values of n. For example, finding an item in a hash table may be O(1), but finding an item in an array, O(n), may actually be a lot lot faster, eg, if the entire array fits into L2 cache. On the other hand, if the array is so big that it swaps to disk, the hash table's O(1) will really shine.
  - deleted 14y ago
    [deleted]
luriel 14y ago
That most C++ programmers are so confused about how to properly use their language says quite a lot about C++ itself.
- tptacek 14y ago
  Is your point that programmers in other languages automatically make good choices about data structures and memory usage? Because that seems, respectfully, to be a dumb point. They do not.
  - luriel 14y ago
    No, but in other languages there seems to be much more consensus about what features one should use, how and when. In C++ it seems everyone has completely different views.
    - aidenn0 14y ago
      I agree its a problem with C++, but IMO it is an inevitable consequence of its strengths: namely that it is regularly used across a very wide range of domains than other languages. I've sen it used on 16-bit microcontrollers, where templates and exceptions were considered harmful, and in large applications, where those features were considered essential.
      - rumcajz 14y ago
        How would you implement an O(1) list without breaking encapsulation then?
        tptacek 14y ago
        What do you mean, "O(1) list"?
        tg3 14y ago
        I assume he meant "a list from which an element can be removed in constant time."
deleted 14y ago
[deleted]
forgotusername 14y ago
A reasonable response, although the problem with this is that it's impossible to manipulate persons without causing their values to be copied (which might not even be possible given the other members of the type - which might not even be under the author's control, e.g. 3rd party libs). Additionally without extra complexity, simple pointer swapping tasks like moving a person between list suddenly starts to involve memory allocation, etc.
- agwa 14y ago
  std::list<T>::splice() lets you move elements between lists without copies or allocations. Before C++11, it was a problem that inserting an element into a std::list required a copy (that's the only place though - once in the list there are no more copies). C++11 adds move semantics and also std::list<T>::emplace(), which eliminate the need to copy.
- justinsb 14y ago
  Right, but the same trade-offs apply to C; C++ is actually superior here: if something shouldn't be copied, you can enforce that in C++, but not in C. The author was arguing that writing in C++/STL meant your code was necessarily less efficient than C; that just seems incorrect. Edit: If you're referring to copying the person values when they're returned from the list: a reference is returned; the compiler will optimize that "pointer" away. Most C++ compilers can even do this when the value itself is returned and avoid the copy. My rule with C++ is that the compiler is stupid, but never where you expect. You need to optimize based on a profiler.
- 430gj9j 14y ago
  No copying here: struct person { int age; }; std::list<person> people; people.push_back(person()); people.back().age = 42;
  - archangel_one 14y ago
    It copies on the third line prior to C++0x, and unfortunately not everyone can rely on move semantics yet.
tptacek 14y ago
I had to fight the urge to stop there too; it's also more idiomatic and probably both more economic and performant to use a vector in this situation; "lists" in C++, at least on the projects I worked on, tended to be a code smell. I think this is a very big problem with C++: most of the funnel of new developers for C++ are C programmers, and transliterating C idioms to C++ (and, worse, the C++ standard library) usually produces pessimal C++ code.
- ajross 14y ago
  To the first part: I guess it's true that if you see someone using a STL list for "just a bucket of stuff" that this is bad form. But they're general purpose doubly-linked lists and absolutely should be there in the API for situations where they're needed (i.e. something where order is important, the size is likely to be large, and you need to mutate in the middle). The second point I think is just isomorphic to "breadth is good". A Ruby or Python programmer coming to C++ is going to avoid a lot of the mistakes of the C programmer, but will likewise miss a lot of the core ideas and generate equally pessimal code, just for different reasons.
  - tptacek 14y ago
    I'm not saying C++ shouldn't have a doubly linked list. I'm saying that C programmers are trained to use linked lists. They are the first variable-length containers most programmers come into contact with and so C programmers tend to be imprinted on them like ducklings. Linked lists are a poor general purpose container.
- itsboring 14y ago
  I've been putting myself through C++ "boot camp". I got a copy of Bjarne's "The C++ Programming Language" and I'm doing every exercise. I'm up to 302 at last count, and only a couple more chapters to go. It's been grueling, but very well worth the time. It helps me avoid a lot of mistakes I would have made had I just jumped in from C and C#. Unfortunately, the 4th edition (which presumably covers C++11) doesn't come out until Feb.
  - 14y ago
rumcajz 14y ago
That works only for simple datatypes. Any not trivial object (containing large amount of memory, handles, file descriptors etc.) is non-copyable. Thus list<person> won't work (according to STL, "person" has to be model of Assignable concept.)
dkhenry 14y ago
before C++11 you would use <person *> to prevent additional allocations on insertion. C++11 is a little bit smarter about not wasting allocations for temporary objects, but requires you to have move operators for any classes you make. In C land no one cares since there are no temporary objects to even worry about, you would be passing around the memory anyway. Maybe you should read the rest of his article.
- agwa 14y ago
  > requires you to have move operators for any classes you make Actually, in the specific case of std::list<T>, T can be both unmovable and uncopyable. Instead of using push_back() and insert() to insert elements, you use emplace_back(), and emplace() to construct the elements in place. Also, the compiler is pretty good about auto-generating move constructors when all the members of a class are safely movable, so classes you write will probably be movable without you needing to do anything.
  - beagle3 14y ago
    emplace_* is C++11 - which is rather new, with support on many platforms still lacking. They started ZeroMQ in 2007 (or even earlier? can't quickly find a reference). So, yes - some of the problems that they faced in ZeroMQ have been addressed years later (although the solution is not yet widely available). I believe this is a point FOR his conclusion that he should have used C, rather than a rebuttal.
    - agwa 14y ago
      Yeah, they're C++11-only. I probably should have mentioned that in my comment, but I didn't because the parent comment was specifically about C++11. I can completely understand why C++11 is not a usable solution for many people at this point.
  - IsTom 14y ago
    Also push_back() and insert() are actually emplace_back() and emplace() when used on rvalues.
qdog 14y ago
Just the discussion of std::list<person> vs std::list<person *> that follows your comment makes my head hurt. It's like not only is c++ a language from a committee, any line of c++ code could be analyzed and argued over by a committee. I think I'll tend to stick to C most of the time, thanks. Even the C++ people probably can easily analyze and reason out the C implementation without much effort or dissent, apparently not so with C++.
- pjkundert 14y ago
  This is the argument that comes up every time a C vs. C++ discussion occurs. It is faulty, because it assumes a false premise -- that the C and C++ implementations will be largely of the same complexity. Unfortunately, in the C implementation of anything beyond a trivial application with no large-scale data structures, the majority of the "reasoning" being done will revolve around basic data structure implementations! The very containers, memory allocation structures, and such that require virtually NO reasoning in the C++ implementation, because they are proven. After you've implemented the same basic structures again, and again for the hundredth time in large-scale C programs, C++ is a breath of fresh air. Unfortunately, many people approach C++ before they have many miles on their programming chassis; this is like handing an infant a revolver. Bad things are likely to happen. This is not a problem with the revolver; it is a parenting issue. Don't let a junior programmer use a language requiring significant reasoning skills, before they have earned the right -- by developing those skills, repeatedly implementing the very structures they'll be accessing in the C++ implementation! We wouldn't let a first-year civil engineering student develop a bridge design, without first gaining many, many years of experience developing -- and failing -- on much simpler designs. Why should we expect wide-spread success, allowing junior programmers access to a spectacularly powerful and complex programming tool?
batista 14y ago
>I stopped reading after the first example I stopped reading your comment at "I stopped reading" too. I've _never_ read an intelligent comment starting with "I stopped reading". These kind of comments always try to show how "clever" the commenter is, and how he doesn't tolerate fools, etc, while 90% of the time they miss the point. Have you continued, you would have seen: "Assume that the object to be contained in the list is non-Assignable as is the case with any non-trivial objects, for example those holding large memory buffers, file descriptors, handles etc. If the object is Assignable simple std::list<person> would do and there is no problem." And even if you read the post _before_ he added the above clarification, if you didn't have the knee jerk reaction you could probably have seen that this (object being non assignable) could be a potential problem in your solution too.
- wheels 14y ago
  He did add that clarification afterwards; that was before the first example. I read up to the first example. However, his clarification, and your proviso are also invalid. First, your proviso, that it's non-assignable -- his type was unusable; that it's non-assignable simply seemed to be an error. In C++ the default permissions for a class are private (not so in a struct, as I hinted at in my post, in fact, such is the only difference between a class and a struct in C++). Now, onto his clarification: The baked in assumption is that in a non-trivial C project that one would not be using a standard set of container abstractions as well. Such is generally not the case. See, for example, GList [1]. The replacement for a template based container in C++ is generally going to be a macro based container abstraction in C, whereas the replacement for a container of pointers in C++ is going to be a void * based generic container implementation (like GList) in C. Both sets of generic implementations are going to have broadly the same performance characteristics (specifically, they're going to have the same number of mallocs of about the same size). In both languages, if one needs specific performance characteristics -- specifically if mallocs are so critical that they must be restricted as much as possible -- one will use a special purpose data structure. That however is a somewhat rare case for structs which are composed of non-POD types. [1] http://developer.gnome.org/glib/2.33/glib-Doubly-Linked-Lists.html http://developer.gnome.org/glib/2.33/glib-Doubly-Linked-List...
jongraehl 14y ago
He's not a great C++ programmer. Whether or not it's worth becomming a great C++ programmer is debatable, but it's worked for me. He could also use http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/usage.html http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/usag... for exactly the "C" layout he wants.

by wheels 14y ago

epsylon 14y ago

In practice lists have such poor memory locality that they should almost never be used. Use vectors. EDIT: See for example Stroustrup's discussion on the matter at the 44th minute of this video : http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style http://channel9.msdn.com/Events/GoingNative/GoingNative-2012... On modern architectures, cache misses are performance killers, and a list is a cache-miss machine. Moving memory is cheaper than doing a linear search through a list. What used to be true 20 years ago isn't true anymore, let's stop using those lists already !

rumcajz 14y ago
With vectors erase is O(1) anyway.
- tptacek 14y ago
  Only from the edge of the collection. A vector is a resizable array, and deletion from the middle of one is O(n).
  - astrodust 14y ago
    Is it O(n/2) if the deletion point is half-way? I thought it was proportional to how much data had to be moved.
    - lolcraft 14y ago
      O(n/2) = O(n), so you're right. However... f(n) being O(n) means: there's a N and an x such that, for all n > x, N*n > f(n). By this definition, O(n/2) is the same as O(n) is the same as O(n/42). You just choose a different N. But it's better form to write O(n).
      - astrodust 14y ago
        I suppose O(n/(m-n)) time is the appropriate measure, where m is the deletion point and n is the number of items in the vector. The removal time seems to be O(1) for the last element and only slightly higher for the second-last, but for the first it is O(n).
        beagle3 14y ago
        O(..) notation for complexity is usually qualified with "worst case" or "average case". Either way, "best case" behavior of O(1) is not really interesting.
        dkersten 14y ago
        The removal time seems to be O(1) for the last element and only slightly higher for the second-last The removal time for the second-last element is still O(1). There is no slightly higher here. O() does not count steps or cost or anything like that - it counts worst case or asymptotic complexity. O(1) means constant time/space/whatever-you-are-measuring complexity. Removing the last element of a non-empty vector always takes the same amount of time (since we are talking about time complexity in this case) no matter how many elements are in are in the vector. Similarly, removing the second-last element always takes the same number of steps regardless how many elements are in the vector (as long as there are at least 2) - still O(1). That doesn't mean that they take equally long - the second-last element does indeed take longer to remove (by some constant factor), but complexity does not care about that, it only cares about the relative difference in respect to n (usually the size of the input) and the worst case (usually; you can also look up θ(..) and Ω(..) and others, but generally worst case is much more useful than best case, though sometimes average case is good to know too). Note also that a O(n) algorithm may actually execute faster than a O(1) algorithm, at least, for small values of n. For example, finding an item in a hash table may be O(1), but finding an item in an array, O(n), may actually be a lot lot faster, eg, if the entire array fits into L2 cache. On the other hand, if the array is so big that it swaps to disk, the hash table's O(1) will really shine.
- deleted 14y ago
  [deleted]

luriel 14y ago

That most C++ programmers are so confused about how to properly use their language says quite a lot about C++ itself.

tptacek 14y ago
Is your point that programmers in other languages automatically make good choices about data structures and memory usage? Because that seems, respectfully, to be a dumb point. They do not.
- luriel 14y ago
  No, but in other languages there seems to be much more consensus about what features one should use, how and when. In C++ it seems everyone has completely different views.
  - aidenn0 14y ago
    I agree its a problem with C++, but IMO it is an inevitable consequence of its strengths: namely that it is regularly used across a very wide range of domains than other languages. I've sen it used on 16-bit microcontrollers, where templates and exceptions were considered harmful, and in large applications, where those features were considered essential.
    - rumcajz 14y ago
      How would you implement an O(1) list without breaking encapsulation then?
      - tptacek 14y ago
        What do you mean, "O(1) list"?
        tg3 14y ago
        I assume he meant "a list from which an element can be removed in constant time."

deleted 14y ago

[deleted]

forgotusername 14y ago

A reasonable response, although the problem with this is that it's impossible to manipulate persons without causing their values to be copied (which might not even be possible given the other members of the type - which might not even be under the author's control, e.g. 3rd party libs). Additionally without extra complexity, simple pointer swapping tasks like moving a person between list suddenly starts to involve memory allocation, etc.

agwa 14y ago
std::list<T>::splice() lets you move elements between lists without copies or allocations. Before C++11, it was a problem that inserting an element into a std::list required a copy (that's the only place though - once in the list there are no more copies). C++11 adds move semantics and also std::list<T>::emplace(), which eliminate the need to copy.
justinsb 14y ago
Right, but the same trade-offs apply to C; C++ is actually superior here: if something shouldn't be copied, you can enforce that in C++, but not in C. The author was arguing that writing in C++/STL meant your code was necessarily less efficient than C; that just seems incorrect. Edit: If you're referring to copying the person values when they're returned from the list: a reference is returned; the compiler will optimize that "pointer" away. Most C++ compilers can even do this when the value itself is returned and avoid the copy. My rule with C++ is that the compiler is stupid, but never where you expect. You need to optimize based on a profiler.
430gj9j 14y ago
No copying here: struct person { int age; }; std::list<person> people; people.push_back(person()); people.back().age = 42;
- archangel_one 14y ago
  It copies on the third line prior to C++0x, and unfortunately not everyone can rely on move semantics yet.

tptacek 14y ago

I had to fight the urge to stop there too; it's also more idiomatic and probably both more economic and performant to use a vector in this situation; "lists" in C++, at least on the projects I worked on, tended to be a code smell. I think this is a very big problem with C++: most of the funnel of new developers for C++ are C programmers, and transliterating C idioms to C++ (and, worse, the C++ standard library) usually produces pessimal C++ code.

ajross 14y ago
To the first part: I guess it's true that if you see someone using a STL list for "just a bucket of stuff" that this is bad form. But they're general purpose doubly-linked lists and absolutely should be there in the API for situations where they're needed (i.e. something where order is important, the size is likely to be large, and you need to mutate in the middle). The second point I think is just isomorphic to "breadth is good". A Ruby or Python programmer coming to C++ is going to avoid a lot of the mistakes of the C programmer, but will likewise miss a lot of the core ideas and generate equally pessimal code, just for different reasons.
- tptacek 14y ago
  I'm not saying C++ shouldn't have a doubly linked list. I'm saying that C programmers are trained to use linked lists. They are the first variable-length containers most programmers come into contact with and so C programmers tend to be imprinted on them like ducklings. Linked lists are a poor general purpose container.
itsboring 14y ago
I've been putting myself through C++ "boot camp". I got a copy of Bjarne's "The C++ Programming Language" and I'm doing every exercise. I'm up to 302 at last count, and only a couple more chapters to go. It's been grueling, but very well worth the time. It helps me avoid a lot of mistakes I would have made had I just jumped in from C and C#. Unfortunately, the 4th edition (which presumably covers C++11) doesn't come out until Feb.
- 14y ago

rumcajz 14y ago

That works only for simple datatypes. Any not trivial object (containing large amount of memory, handles, file descriptors etc.) is non-copyable. Thus list<person> won't work (according to STL, "person" has to be model of Assignable concept.)

dkhenry 14y ago

before C++11 you would use <person *> to prevent additional allocations on insertion. C++11 is a little bit smarter about not wasting allocations for temporary objects, but requires you to have move operators for any classes you make. In C land no one cares since there are no temporary objects to even worry about, you would be passing around the memory anyway. Maybe you should read the rest of his article.

agwa 14y ago
> requires you to have move operators for any classes you make Actually, in the specific case of std::list<T>, T can be both unmovable and uncopyable. Instead of using push_back() and insert() to insert elements, you use emplace_back(), and emplace() to construct the elements in place. Also, the compiler is pretty good about auto-generating move constructors when all the members of a class are safely movable, so classes you write will probably be movable without you needing to do anything.
- beagle3 14y ago
  emplace_* is C++11 - which is rather new, with support on many platforms still lacking. They started ZeroMQ in 2007 (or even earlier? can't quickly find a reference). So, yes - some of the problems that they faced in ZeroMQ have been addressed years later (although the solution is not yet widely available). I believe this is a point FOR his conclusion that he should have used C, rather than a rebuttal.
  - agwa 14y ago
    Yeah, they're C++11-only. I probably should have mentioned that in my comment, but I didn't because the parent comment was specifically about C++11. I can completely understand why C++11 is not a usable solution for many people at this point.
- IsTom 14y ago
  Also push_back() and insert() are actually emplace_back() and emplace() when used on rvalues.

qdog 14y ago

Just the discussion of std::list<person> vs std::list<person *> that follows your comment makes my head hurt. It's like not only is c++ a language from a committee, any line of c++ code could be analyzed and argued over by a committee. I think I'll tend to stick to C most of the time, thanks. Even the C++ people probably can easily analyze and reason out the C implementation without much effort or dissent, apparently not so with C++.

pjkundert 14y ago
This is the argument that comes up every time a C vs. C++ discussion occurs. It is faulty, because it assumes a false premise -- that the C and C++ implementations will be largely of the same complexity. Unfortunately, in the C implementation of anything beyond a trivial application with no large-scale data structures, the majority of the "reasoning" being done will revolve around basic data structure implementations! The very containers, memory allocation structures, and such that require virtually NO reasoning in the C++ implementation, because they are proven. After you've implemented the same basic structures again, and again for the hundredth time in large-scale C programs, C++ is a breath of fresh air. Unfortunately, many people approach C++ before they have many miles on their programming chassis; this is like handing an infant a revolver. Bad things are likely to happen. This is not a problem with the revolver; it is a parenting issue. Don't let a junior programmer use a language requiring significant reasoning skills, before they have earned the right -- by developing those skills, repeatedly implementing the very structures they'll be accessing in the C++ implementation! We wouldn't let a first-year civil engineering student develop a bridge design, without first gaining many, many years of experience developing -- and failing -- on much simpler designs. Why should we expect wide-spread success, allowing junior programmers access to a spectacularly powerful and complex programming tool?

batista 14y ago

>I stopped reading after the first example I stopped reading your comment at "I stopped reading" too. I've _never_ read an intelligent comment starting with "I stopped reading". These kind of comments always try to show how "clever" the commenter is, and how he doesn't tolerate fools, etc, while 90% of the time they miss the point. Have you continued, you would have seen: "Assume that the object to be contained in the list is non-Assignable as is the case with any non-trivial objects, for example those holding large memory buffers, file descriptors, handles etc. If the object is Assignable simple std::list<person> would do and there is no problem." And even if you read the post _before_ he added the above clarification, if you didn't have the knee jerk reaction you could probably have seen that this (object being non assignable) could be a potential problem in your solution too.

wheels 14y ago
He did add that clarification afterwards; that was before the first example. I read up to the first example. However, his clarification, and your proviso are also invalid. First, your proviso, that it's non-assignable -- his type was unusable; that it's non-assignable simply seemed to be an error. In C++ the default permissions for a class are private (not so in a struct, as I hinted at in my post, in fact, such is the only difference between a class and a struct in C++). Now, onto his clarification: The baked in assumption is that in a non-trivial C project that one would not be using a standard set of container abstractions as well. Such is generally not the case. See, for example, GList [1]. The replacement for a template based container in C++ is generally going to be a macro based container abstraction in C, whereas the replacement for a container of pointers in C++ is going to be a void * based generic container implementation (like GList) in C. Both sets of generic implementations are going to have broadly the same performance characteristics (specifically, they're going to have the same number of mallocs of about the same size). In both languages, if one needs specific performance characteristics -- specifically if mallocs are so critical that they must be restricted as much as possible -- one will use a special purpose data structure. That however is a somewhat rare case for structs which are composed of non-POD types. [1] http://developer.gnome.org/glib/2.33/glib-Doubly-Linked-Lists.html http://developer.gnome.org/glib/2.33/glib-Doubly-Linked-List...

jongraehl 14y ago

He's not a great C++ programmer. Whether or not it's worth becomming a great C++ programmer is debatable, but it's worked for me. He could also use http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/usage.html http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/usag... for exactly the "C" layout he wants.