This is not in any way a principle of OOP. That MI may not be appropriate in many cases where it is used is true. It is just as true, however, that it is absolutely essential in other cases. Just because Java has used interfaces as a poor substitute for MI, does not mean that MI is useless.
For more details, have a look at Andrei Alexandrescu's Modern C++ design. This book is an absolute eye-opener and it has done exactly that for a large part of the C++ community.
I have not worked much with threaded applications, but I have encountered the problems with multiple inheritance.
What I've ended up doing in hard cases (where printf will not help) is create local pointers to the parent classes and examine them from gdb. Once the problem is solved, the extra variables are gone, too.
Of course, this will not help when your hierarchy is more than a couple of levels deep and things get even more complicated when the parent class is actually a template argument.
I hope, however, that this is just a very-hard-to-fix bug in gdb, as opposed to an even deeper design problem (as I think is the case with threaded code). So there might still be hope.
There's always the possibility that he meant that gprof in particular is useless. I know that for programs that are dependent on good cache behavior to get the performance they need, gprof totally messes up the results.
So, maybe he said that profiling should not be done with gprof. It's still a weird statement, however.
Electricity will only find the shortest path. This is an n^2 operation. Maybe it does it faster than that, but it is an n^2 operation with computers, which is pretty cheap.
The travelling salesman problem on the other hand, which is not what the article talks about, imposes additional constraints: the path must visit all nodes and it must form a cycle (ie end where it began). These additional constraints are what make this an NP-complete problem. But unless the article is missing critical information, they have not found a way to impose those constraints.
The links you mention are about the TSP, not the shortest path problem.
First, shortest path algorithms do NOT consider every possible route. Instead, they consider the best extention to an already known shortest path (starting with the shortest path to the beginning, which is obviously 0). [roughly -- Dijsktra's algorithm is slightly more complicated, but not much].
Second, if the number of operations increases polynomially, how does the problem get classified as NP complete? Never mind the fact that a lower bound alone is not enough to put a problem in a specific class, if the complexity is actually O(n^2), then the problem is clearly in P, not NP.
Other than a nice hack, this article does not describe any important breakthrough.
I did not say that someone recommended that. I'm sure even the original poster did not mean to recommend it. But it is possible that someone can misinterpret that post, that's why I replied.
Besides, many novices often make the mistake of thinking that containers _are_ interchangable like that and they end up learning the hard way that they are not.
Regarding conversion at least, there have been some interesting discussions lately on the boost list (in part in response to the requirements set forth by the meeting of c++ working group in Curacao).
One of the suggestions was a traits-based smart pointer. Since you would have only one smart pointer class, which modifies its behavior based on the type it points to, there would be no conversion issue. Of course, without having read the discussions in detail, it seems to me it limits you to one type of smart pointer per type.
You may also want to consider whether you really want to convert between a shared_ptr and a cyclic_ptr. They handle the memory differently and while a cyclic_ptr may decide to delete an object, a shared_ptr will not know it.
If you're talking about interfaces, this problem can be solved if you make the functions (member or free, does not matter) and the classes take template arguments and use a policy-based smart pointer. I'm talking about something like:
instead of template(typename T) void foo(shared_ptr(T));
(where P is an aggregate of all the policies for your smart pointer) (replace parentheses with less-than and greater-than)
As for error messages, I think we need to wait a bit for these things to become standardized enough that compilers can detect (mis-)uses of them and report appropriate, clear error messages.
Not so magically. If you consider all the operations that lists support but vectors don't (and vice versa), pretty much all you can do with code that converts "magically" between list and vector is iterate using begin() and end(). No constant time insertions and removals at any place, no modifications without invalidating iterators (list), no constant time access to any element in the container (vector) and more.
The view template library, at http://www.zib.de/weiser/vtl/ provides all the database-like operations you would want. But it is only a first attempt at the design of such a library, so I think that there is already something else in the works that supercedes it.
For garbage collection, you might want to check out the boost files section and look for cyclic_ptr. It's a nice smart pointer implementation that actually handles cyclic references (that's the only thing a garbage collector can do that a smart pointer like boost's shared_ptr does not do).
And of course, there's always Hans Boehm's garbage collector at http://www.hpl.hp.com/personal/Hans_Boehm/gc/, but I guess you were referring to something that is integrated into the language.
The community right now seems to think that COW is ok for single-threaded uses, but the locking overhead is too high in multithreaded uses and you may prefer to avoid it in those situations. Actually performing an allocation+copy turns out to be faster than locking and unlocking the shared representation.
Of course, using the atomic increment/decrement primitives may nullify (or at least significantly decrease) the cost of locking.
Well, you don't care about the implementation. But you do care what kind of operation you are performing. You don't really want to "encapsulate" away that you will perform a linear time lookup instead of log-time lookup when you use a list versus a set.
Think of them as different operations that one container supports and the other does not.
Not exactly the same thing, but I read recently on the boost mailing list that someone had created an extention to gcc that allowed him to 'instruct' the compiler to not emit these awful errors. So instead of a couple of pages of error messages that essentially tell you that you have not defined operator== (or something that trivial), you get a single message like "need to define operator== for class Foo when passing it to library Bar"
It was very cool and people seemed to like it. Let's hope that the standards body considers something like it non-intrusive enough to include. Of course someone would have to actually write up the proposal, too. So it may remain a gcc-only feature, if it even appears in mainline gcc.
This response seems like you did not even read the post you replied to. C# and the rest of the mainstream languages (java, python, perl, whatever) can do none of the thigs that c++ can do.
In c++ they look ugly, but at least they are doable. What the original poster wished for is a successor language to c++, which will support all the new programming techiniques that were made possible in c++, but in a much cleaner way.
Of course, for all we know, the new language might as well be called c++ 2005. It's like the old saying "I don't know what language we'll be using in 20 years, but I know it's going to be called FORTRAN" (I forget who said it, though).
Even though you have it right that it is a misconception that C++ is slower than C, you miss one very importatnt point: the supposedly slower features of C++ (like virtual functions) do not have an equivalent in C. In fact, in order to achieve the same functionality in C, you will have to hand code what the compiler already does for you in C++. But we already know that compilers are better than humans in avoiding errors and applying the same solution over and over with good efficiency.
Moreover, because the compiler knows what you're actually trying to do, it can often perform optimizations that are not possible in C. For the example of virtual function calls, the equivalent in C (both in terms of functionality and efficiency) is calls using function pointers. The difference is that in C++ the compiler often knows the dynamic type of an object (if it's an actual object and not a pointer or reference) and can optimize away the virtual function call and replace it with a static call (or even inline the function). The C compiler is unable to do that.
So yes, there are features in C++ that have a performance penalty, but they have no equivalent in C, so the comparison is invalid.
As for ocaml or other FP languages, I think it's a good idea to try them. Besides the productivity and maintainability gains, you may also have actual efficiency benefits. Again, because the compiler knows what you're trying to do in a high(er) level language, sometimes it can perform obscure but very effective optimizations that can beat what an average or even good C programmer can do.
On, say, a P3 1Ghz.... I guess it would talk around 0.000000 sec, if you use some of the older algorithms. That is, times() is not accurate enough to measure how long it would take.
That would be even faster for newer and better algorithms.
These numbers are nice, but ignore the fact that the current algorithms for solving SAT can routinely solve random 250-variable problems in subsecond times and even larger structured problems. zChaff, the fastest solver currently has even solved some 1-million variable problems (of course it probably took a few days, but it's still better than the multiple-universe-lifetimes prediction of 2^n).
Slashdot Mirror
http://bofh.be/clusterknoppix/ seems nice. Don't know if it does all you want, though.
www.boost.org
The documentation for the tuple library is here
Comeau rejects it as well.
This is not in any way a principle of OOP. That MI may not be appropriate in many cases where it is used is true. It is just as true, however, that it is absolutely essential in other cases. Just because Java has used interfaces as a poor substitute for MI, does not mean that MI is useless.
For more details, have a look at Andrei Alexandrescu's Modern C++ design. This book is an absolute eye-opener and it has done exactly that for a large part of the C++ community.
I have not worked much with threaded applications, but I have encountered the problems with multiple inheritance.
What I've ended up doing in hard cases (where printf will not help) is create local pointers to the parent classes and examine them from gdb. Once the problem is solved, the extra variables are gone, too.
Example:
Base1 *b1 = dynamic_cast[Base1*](this);
Base2 *b2 = dynamic_cast[Base2*](this);
(change [] to less-than and greater-than).
Of course, this will not help when your hierarchy is more than a couple of levels deep and things get even more complicated when the parent class is actually a template argument.
I hope, however, that this is just a very-hard-to-fix bug in gdb, as opposed to an even deeper design problem (as I think is the case with threaded code). So there might still be hope.
I think you've got it backwards. gprof uses code instrumentation, not sampling. Other profilers, such as jprof and (I think) oprofile use sampling.
(that's why you need to compile your code -pg, not -g, when you want to generate profiling info: the compiler has to instrument the code)
There's always the possibility that he meant that gprof in particular is useless. I know that for programs that are dependent on good cache behavior to get the performance they need, gprof totally messes up the results.
So, maybe he said that profiling should not be done with gprof. It's still a weird statement, however.
NTP adjusts to network delays, so this should not be a problem.
And what I am trying to say is that the article does NOT deal with TSP, it deals with shortest path.
Electricity will only find the shortest path. This is an n^2 operation. Maybe it does it faster than that, but it is an n^2 operation with computers, which is pretty cheap.
The travelling salesman problem on the other hand, which is not what the article talks about, imposes additional constraints: the path must visit all nodes and it must form a cycle (ie end where it began). These additional constraints are what make this an NP-complete problem. But unless the article is missing critical information, they have not found a way to impose those constraints.
The links you mention are about the TSP, not the shortest path problem.
First, shortest path algorithms do NOT consider every possible route. Instead, they consider the best extention to an already known shortest path (starting with the shortest path to the beginning, which is obviously 0). [roughly -- Dijsktra's algorithm is slightly more complicated, but not much].
Second, if the number of operations increases polynomially, how does the problem get classified as NP complete? Never mind the fact that a lower bound alone is not enough to put a problem in a specific class, if the complexity is actually O(n^2), then the problem is clearly in P, not NP.
Other than a nice hack, this article does not describe any important breakthrough.
gcc linked at compiled time to the kernel...
this is hilarious...
I did not say that someone recommended that. I'm sure even the original poster did not mean to recommend it. But it is possible that someone can misinterpret that post, that's why I replied.
Besides, many novices often make the mistake of thinking that containers _are_ interchangable like that and they end up learning the hard way that they are not.
Regarding conversion at least, there have been some interesting discussions lately on the boost list (in part in response to the requirements set forth by the meeting of c++ working group in Curacao).
One of the suggestions was a traits-based smart pointer. Since you would have only one smart pointer class, which modifies its behavior based on the type it points to, there would be no conversion issue. Of course, without having read the discussions in detail, it seems to me it limits you to one type of smart pointer per type.
You may also want to consider whether you really want to convert between a shared_ptr and a cyclic_ptr. They handle the memory differently and while a cyclic_ptr may decide to delete an object, a shared_ptr will not know it.
If you're talking about interfaces, this problem can be solved if you make the functions (member or free, does not matter) and the classes take template arguments and use a policy-based smart pointer. I'm talking about something like:
template(typename T, typename P)
void foo(smart_ptr(T, P));
instead of
template(typename T)
void foo(shared_ptr(T));
(where P is an aggregate of all the policies for your smart pointer)
(replace parentheses with less-than and greater-than)
As for error messages, I think we need to wait a bit for these things to become standardized enough that compilers can detect (mis-)uses of them and report appropriate, clear error messages.
Not so magically. If you consider all the operations that lists support but vectors don't (and vice versa), pretty much all you can do with code that converts "magically" between list and vector is iterate using begin() and end(). No constant time insertions and removals at any place, no modifications without invalidating iterators (list), no constant time access to any element in the container (vector) and more.
The view template library, at http://www.zib.de/weiser/vtl/ provides all the database-like operations you would want. But it is only a first attempt at the design of such a library, so I think that there is already something else in the works that supercedes it.
perpendicular: The preferred term is orthogonal :)
For garbage collection, you might want to check out the boost files section and look for cyclic_ptr. It's a nice smart pointer implementation that actually handles cyclic references (that's the only thing a garbage collector can do that a smart pointer like boost's shared_ptr does not do).
And of course, there's always Hans Boehm's garbage collector at http://www.hpl.hp.com/personal/Hans_Boehm/gc/, but I guess you were referring to something that is integrated into the language.
The community right now seems to think that COW is ok for single-threaded uses, but the locking overhead is too high in multithreaded uses and you may prefer to avoid it in those situations. Actually performing an allocation+copy turns out to be faster than locking and unlocking the shared representation.
Of course, using the atomic increment/decrement primitives may nullify (or at least significantly decrease) the cost of locking.
Well, you don't care about the implementation. But you do care what kind of operation you are performing. You don't really want to "encapsulate" away that you will perform a linear time lookup instead of log-time lookup when you use a list versus a set.
Think of them as different operations that one container supports and the other does not.
Not exactly the same thing, but I read recently on the boost mailing list that someone had created an extention to gcc that allowed him to 'instruct' the compiler to not emit these awful errors. So instead of a couple of pages of error messages that essentially tell you that you have not defined operator== (or something that trivial), you get a single message like "need to define operator== for class Foo when passing it to library Bar"
It was very cool and people seemed to like it. Let's hope that the standards body considers something like it non-intrusive enough to include. Of course someone would have to actually write up the proposal, too. So it may remain a gcc-only feature, if it even appears in mainline gcc.
This response seems like you did not even read the post you replied to. C# and the rest of the mainstream languages (java, python, perl, whatever) can do none of the thigs that c++ can do.
In c++ they look ugly, but at least they are doable. What the original poster wished for is a successor language to c++, which will support all the new programming techiniques that were made possible in c++, but in a much cleaner way.
Of course, for all we know, the new language might as well be called c++ 2005. It's like the old saying "I don't know what language we'll be using in 20 years, but I know it's going to be called FORTRAN" (I forget who said it, though).
Even though you have it right that it is a misconception that C++ is slower than C, you miss one very importatnt point: the supposedly slower features of C++ (like virtual functions) do not have an equivalent in C. In fact, in order to achieve the same functionality in C, you will have to hand code what the compiler already does for you in C++. But we already know that compilers are better than humans in avoiding errors and applying the same solution over and over with good efficiency.
Moreover, because the compiler knows what you're actually trying to do, it can often perform optimizations that are not possible in C. For the example of virtual function calls, the equivalent in C (both in terms of functionality and efficiency) is calls using function pointers. The difference is that in C++ the compiler often knows the dynamic type of an object (if it's an actual object and not a pointer or reference) and can optimize away the virtual function call and replace it with a static call (or even inline the function). The C compiler is unable to do that.
So yes, there are features in C++ that have a performance penalty, but they have no equivalent in C, so the comparison is invalid.
As for ocaml or other FP languages, I think it's a good idea to try them. Besides the productivity and maintainability gains, you may also have actual efficiency benefits. Again, because the compiler knows what you're trying to do in a high(er) level language, sometimes it can perform obscure but very effective optimizations that can beat what an average or even good C programmer can do.
You're talking about the bsod module of xscreensaver, right?
On, say, a P3 1Ghz.... I guess it would talk around 0.000000 sec, if you use some of the older algorithms. That is, times() is not accurate enough to measure how long it would take.
That would be even faster for newer and better algorithms.
These numbers are nice, but ignore the fact that the current algorithms for solving SAT can routinely solve random 250-variable problems in subsecond times and even larger structured problems. zChaff, the fastest solver currently has even solved some 1-million variable problems (of course it probably took a few days, but it's still better than the multiple-universe-lifetimes prediction of 2^n).