9 ms·

> write a very simple UNIX-based operating system in C++ (does anyone else smell a contradiction?) I'm going to use this as an opportunity to champion C++ for

> write a very simple UNIX-based operating system in C++ (does anyone else smell a contradiction?) I'm going to use this as an opportunity to champion C++ for systems programming despite the fact that it wasn't really your argument. I feel obligated to do this because I agreed with you for a long time on this but have changed my mind over the past year or two. The argument against C++ as a systems programming language has always been that it gives you too much freedom to hide complexity, but I've written systems code in both C and C++ professionally and it's been my experience that the extra burden of having to write every damn thing over again in C (or use a relatively poorly tested container library, as compared to something like the STL) is not worth the "obvious performance characteristics." I'd further contend that in non-trivial software all perf characteristics are non-trivial, so even though a + b might be doing all kinds of crazy things in C++, you're much more likely to run into problems invoking store_value() which might interact with a number of underlying libraries and system calls. At the end of the day you're hopelessly screwed without profiling and the utility perf works just as well on C++ programs as it does on C programs. Finally, the majority of code in my experience is either slow path or at least not the bottleneck anyway. You can almost always optimize a systems program by making smarter system calls (or hardware invocations), while optimizing CPU is rarely worth it. Even if you're CPU bound, it's likely that it's in doing something like SSL, wherein you're almost definitely wrong to try to jump into a project like OpenSSL with micro-optimizations. With that in mind, why not allow yourself to move faster by creating a std::vector? When you use the proper conventions, it's generally as fast anyway. Just because people can (and have, a lot) misused C++ and created way too much complexity with it doesn't mean that it's not the preferred language in the hands of someone who knows what they're doing. (And yes, it's much harder to learn how C++ works in a meaningful way to avoid these pitfalls, but if it's your job, learn it anyway).

deleted 13y ago
[deleted]
Peaker 13y ago
You can have generalized containers in C, using the intrusive pattern. For example, Linux's list.h has an intrusive list that is far better than the abysmal std::list from the STL.
- cheez 13y ago
  Any C++ programmer knows not to use std::list anyway.
  - dkersten 13y ago
    How about: Any C or C++ programmer knows not to use linked lists anyway.
    - Peaker 13y ago
      If you really think that, you've missed CS 101. Or maybe std::list is the only linked list implementation you've seen. In that case, I agree, one should never use std::list. Linux's list.h is extremely useful, and for a wide variety of circumstances, is the most efficient way to manage your data.
      - dkersten 13y ago
        Ok, I'll elaborate, especially since my view is at odds with your statement "for a wide variety of circumstances". As I see it, the only use case where linked lists are superior to other types of lists, like, perhaps, ArrayList in java or vector/deque in C++, is if the following conditions are met: 1: you care about ordering - often you don't care about ordering and in that case, there is no need for a linked list because you can achieve O(1) insertion & removal then too: insertion can always be at the end, removal can be a "swap with end element, remove end element" operation. 2: inserting and/or removing from the middle of the list is a common operation, if it is not a common operation, then the added cost of doing so with a vector may still be outweighed by a vectors other advantages 3: you do not require random access - lists do not provide random access and lookup is O(n). At the expense of additional complexity in implementation and more memory overhead, you could reduce lookup to, OTOH, O(log n) by using a skip-list 4: you do not iterate through the list often - if you do, you are likely going to blow the cache and mess up prefetching due to poor cache locality. Iterating through an array-based data structure can be much faster in this case. I would say that for a list to make sense, you MUST have 1 and 2 and probably should have 3. 4 is optional, but if true, should make you consider if there might not be a more suitable data structure. In my own personal experience, this is rare. In fact, in my own personal experience, usually, code either does not require 1 or requires 1 but not 2 - either way, lists are not the appropriate data structure in those cases. Basically, the short version is that they have very poor cache locality, an (IMHO) narrow use case where other data structures don't have superior performance and they take up more memory per node than a lot of other types of lists. You linked to a stackoverflow question in another comment saying that they attribute std::list's flaws to linked lists as a whole. The biggest issue they seemed to mention, though, was cache locality - I fail to see how intrusive linked lists solve this. The only solution would be to preallocate nodes in consecutive memory locations, but you still take a hit as the links take up memory (whereas in array-based lists you do not need to store links for each node) and if you need to insert/delete in the middle (why are you using linked lists if this isn't the case?) then you end up jumping around the preallocated nodes anyway and after a while will lose any cache-friendliness you may have had. Maybe you can elaborate what you meant? To end with an appeal to authority ;-) I'll quote tptacek[1]: 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. EDIT: I guess I missed an anti-condition: if you don't care about performance, then use whatever models your problem best, which may well be a linked list (though the same is true for std::list). [1] https://news.ycombinator.com/item?id=4455676 https://news.ycombinator.com/item?id=4455676

deleted 13y ago

[deleted]

Peaker 13y ago

You can have generalized containers in C, using the intrusive pattern. For example, Linux's list.h has an intrusive list that is far better than the abysmal std::list from the STL.

cheez 13y ago
Any C++ programmer knows not to use std::list anyway.
- dkersten 13y ago
  How about: Any C or C++ programmer knows not to use linked lists anyway.
  - Peaker 13y ago
    If you really think that, you've missed CS 101. Or maybe std::list is the only linked list implementation you've seen. In that case, I agree, one should never use std::list. Linux's list.h is extremely useful, and for a wide variety of circumstances, is the most efficient way to manage your data.
    - dkersten 13y ago
      Ok, I'll elaborate, especially since my view is at odds with your statement "for a wide variety of circumstances". As I see it, the only use case where linked lists are superior to other types of lists, like, perhaps, ArrayList in java or vector/deque in C++, is if the following conditions are met: 1: you care about ordering - often you don't care about ordering and in that case, there is no need for a linked list because you can achieve O(1) insertion & removal then too: insertion can always be at the end, removal can be a "swap with end element, remove end element" operation. 2: inserting and/or removing from the middle of the list is a common operation, if it is not a common operation, then the added cost of doing so with a vector may still be outweighed by a vectors other advantages 3: you do not require random access - lists do not provide random access and lookup is O(n). At the expense of additional complexity in implementation and more memory overhead, you could reduce lookup to, OTOH, O(log n) by using a skip-list 4: you do not iterate through the list often - if you do, you are likely going to blow the cache and mess up prefetching due to poor cache locality. Iterating through an array-based data structure can be much faster in this case. I would say that for a list to make sense, you MUST have 1 and 2 and probably should have 3. 4 is optional, but if true, should make you consider if there might not be a more suitable data structure. In my own personal experience, this is rare. In fact, in my own personal experience, usually, code either does not require 1 or requires 1 but not 2 - either way, lists are not the appropriate data structure in those cases. Basically, the short version is that they have very poor cache locality, an (IMHO) narrow use case where other data structures don't have superior performance and they take up more memory per node than a lot of other types of lists. You linked to a stackoverflow question in another comment saying that they attribute std::list's flaws to linked lists as a whole. The biggest issue they seemed to mention, though, was cache locality - I fail to see how intrusive linked lists solve this. The only solution would be to preallocate nodes in consecutive memory locations, but you still take a hit as the links take up memory (whereas in array-based lists you do not need to store links for each node) and if you need to insert/delete in the middle (why are you using linked lists if this isn't the case?) then you end up jumping around the preallocated nodes anyway and after a while will lose any cache-friendliness you may have had. Maybe you can elaborate what you meant? To end with an appeal to authority ;-) I'll quote tptacek[1]: 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. EDIT: I guess I missed an anti-condition: if you don't care about performance, then use whatever models your problem best, which may well be a linked list (though the same is true for std::list). [1] https://news.ycombinator.com/item?id=4455676 https://news.ycombinator.com/item?id=4455676