Hi folks,
I was wondering... How come standard C programming language is used in algorithm research instead of C++ with all its fanciful classes and encapsulations?
How come the MPEG standardization committee release a source code based on standard C instead of C++ ? Of course, I also noticed that most algorithm researchers actually prefer standard C instead of C++?
wkwai
Possibly because C has been around much longer (60's vs. 90's of C++), is much easier to implement compiler-wise and the correlation between the C code that you see / generated machine instructions is very high. And the C language as a simple (ok, in theory) procedural language has a very large "industry standard" label on it's forehead.
I understand that short functions (FFT and such) can be presented with C language just fine but on a large scale, I would prefer an object-oriented C++ approach.
However, if a presentation of an algorithm in C requires arrays and intense pointer arithmetics or resorts to some other trickery, I would prefer to see a container class version of it.
Ian Joyner's famous "C++?? : A Critique of C++" might explain some of the reasons why very many people prefer to avoid the C++ language in all cases if possible.
You can find the HTML version here:
http://burks.brighton.ac.uk/burks/pcinfo/p...pcrit/index.htm (http://burks.brighton.ac.uk/burks/pcinfo/progdocs/cppcrit/index.htm)
IMHO it's a recommended reading for anyone interested in OO programming.
Wouldn't there be computational overheads in using C++ in computationally intensive routines?
wkwai
Wouldn't there be computational overheads in using C++ in computationally intensive routines?
wkwai
Nope. No one forces you to use the "slow constructs" in C++. Just code in a C-style function without objects and virtual functions, apply your own über-SSE2-inline assembler optimizations, and it will be just fast if not faster than it's C equivalent.
I don't understand why everyone hates C++ so deeply. I've read the critique about 100 times, I agree with some points but I still love C++. I must be nuts
Wouldn't there be computational overheads in using C++ in computationally intensive routines?
Probably not. A C-only compiler might be able to optimize more easily than a C++ one because it could make assumptions the latter cannot. But it probably highly depends on quality of implementation and will not make a real difference. Basic OO design is not that interesting for numeric computations since it must carry the usual C++ burden: temporaries. However you could take a look at modern template-oriented implementations like Blitz (http://www.oonumerics.org/blitz/).
Off-topic here but i am interested:
I don't understand why everyone hates C++ so deeply. I've read the critique about 100 times, I agree with some points but I still love C++. I must be nuts
Because C++ is a complex language, and the complexity of its features stems from trade-off that you must know/understand before using them. And most of people just don't care about that, code in C++ like in C with Classes and mess with it, before comparing the whole thing with another language with less apparent complexity they know better.
And I can agree with them depending on their positions. Should I have a bunch of not-so-skilled-neither-very-motivated programmers, I would fear any C++ code they manage to write.
Moreover, people do not know the same C++ language: most of them only know the Java like version, with classes, polymorphism & Co, from before 1995. Few know the one with early template support and STL normalized in 1998. And fewer know the recent template developments implemented in libraries like Boost or Loki and supported by a few compilers. I think the latest C++ specification was made in 1998, and we currently have only one compiler supporting it completely (Comeau). The fact that people use pre-98/broken compilers (like MSVC 6.0 for instance) is likely to have played a great role in this hatred. But the situation is going to change apart for the (debatable)
export thing (MSVC 7.1 is really close to compliance, and GCC 3.2 has made great steps too).
However, I like C++ because of its complexity. Because to learn it you must understand things beyond mere syntactic details or basic OO design. In the end, learning C++ makes you learn things about compiler design and implementation.
Nope. No one forces you to use the "slow constructs" in C++. Just code in a C-style function without objects and virtual functions, apply your own über-SSE2-inline assembler optimizations, and it will be just fast if not faster than it's C equivalent.
I see.. without objects right? Does that mean that these routines should be place within the same class? I did some algorithm programming in OOP sometime ago, I was told that it will be alright as long as "the routines are kept within the same class".. Now this is a problem! For most algorithm, almost all routines are computationally intensive... and I ended up with only one class for the entire program.. This sort of defeat the purpose of encapsulation!
wkwai
The fact that people use pre-98/broken compilers (like MSVC 6.0 for instance) is likely to have played a great role in this hatred.
I have been using MSVC 6.0 for many years.. I do noticed that sometimes, there is some problem compiling codes with it.. I was told that it was most probably caused by me mixing C codes with C++ codes. I was advised to stick to standard C to avoid a lot of compilation problems.
It is great that you have pointed out the problem of pre-98/broken compilers issue.
wkwai
I see.. without objects right? Does that mean that these routines should be place within the same class? I did some algorithm programming in OOP sometime ago, I was told that it will be alright as long as "the routines are kept within the same class".. Now this is a problem! For most algorithm, almost all routines are computationally intensive... and I ended up with only one class for the entire program.. This sort of defeat the purpose of encapsulation!
wkwai
Important Fact: For most computationally intensive applications which are cpu bound (this excludes those which use e.g 3d chipsets), about 95% of the time is spent in tight loops.
Once the algorithm itself cannot be pushed further, the trick is to identify where these frequently-executed loops are, and rewrite (the inner part of) them in assembly.
Now, once you optimized the heck out of these parts, you can afford to lose 0.2% for moving your code into C++ (why not?) nicely-organized classes, methods and improving the design altogether.
In other words: when the inner part of a loop (which is called, say, 10 million times per second) is optimized, one shouldn't worry about losing 30 nanoseconds for a function call which occurs once every second
PS: regarding the original question, I don't think how C++ could be useful for algorithmic research.
I was wondering... How come standard C programming language is used in algorithm research instead of C++ with all its fanciful classes and encapsulations?
How come the MPEG standardization committee release a source code based on standard C instead of C++ ? Of course, I also noticed that most algorithm researchers actually prefer standard C instead of C++?
I can't really speak for anyone but myself, but I think the reasons why C is used is it's simplicity. I find that many of the features C++ delivers aren't really needed. C++ is a huge language, and it's not even strictly object oriented. If I wanted a good object oriented language, I'd probably be using Java or Objective-C, and if I want a language for writing complex math, C introduces virtually no overhead. Plus, there are many portability issues with C++, and even version conflicts due to name mangling. C++ code compile with GCC 2.95, 3.1 and 3.3 aren't binary compatible, for instance.
Properly written C code works
everwhere. For things like math, it allows you to do complex bit fiddling. C's main drawback is that it's highly error prone, but I hear that C++ doesn't quite solve that. With C, a good math algorithm can be implemented in the fastest possible way. There is virtually no overhead; C is just fancy assembler. I believe it's a huge misunderstanding that C++ replaces C. Heck, the C++ language isn't even a direct superset of the C language.
I dislike C++ for the exact same reasons why Trickos likes it. To me, a language is nothing more than a tool, and the language should not have too many syntactic additions. I find something like streams completely redundant; if I want to write to output, object orientation works great in OO languages like Java, and procedures work great in C - no need to add the extra syntactic sugar. I find the best argument against C++ the size of books about it. Can anyone really write 1000 interesting pages about one single language? Simplicity is a virtue - just pick a design philosophy and follow it. IMO the main alternatives to C for algorithms are functional languages. I've just begun learning ML, and I like how something like recursiveness is handled.
Languages are tools, nothing more, nothing less. Pick the one which suits your needs best; they all have their advantages and drawbacks.
danchr: I agree with what you said about C efficiency, simplicity and availability, which explains why it is kept for most of computational libraries (audio/video codecs). I really think that the definitive argument is support for low-end hardware, which is the main target of codecs in the end.
However I disagree with the following statements :
Plus, there are many portability issues with C++, and even version conflicts due to name mangling. C++ code compile with GCC 2.95, 3.1 and 3.3 aren't binary compatible, for instance.
These are GCC issues. Static and dynamic library formats output by MSVC and windows compilers in general have been stable for years, and this is likely to be the same with other compiler vendors.
Properly written C code works everwhere.
The same for C++ . But I understand, you were talking about C compiler availability (especially on specific, low end, hardware platforms).
I find something like streams completely redundant; if I want to write to output, object orientation works great in OO languages like Java, and procedures work great in C - no need to add the extra syntactic sugar
C++ streams are actually classes which probably work like the Java ones (I don't know Java enough to be sure about that). The fact is their interface is a bit obfuscated, because nobody is perfect, and because these streams are highly customizable (output layer, formatting layer, etc...). And I prefer them to C
printf-like functions with varargs and type-unsafe arguments even if the latter happens to be faster.
Simplicity is a virtue - just pick a design philosophy and follow it.
Which is probably the main reason for C++ to exist : pragmatism. I don't want to start useless polemics about Java speed, interpreted vs compiled and such, but, there are many applications which requires multiple programming paradigms. Not everything can be (efficiently) coded in Lisp or scales well in C. There are two solutions to this:
- Use a specialized language in every specialized area. That's a beautiful idea however merging this kind of code is problematic.
- Use a multi-paradigm monster : C++.
I do not advocate for any of these solutions, I just happened to learn C++ in the first place. The current trend, with MS .Net for example, seems to focus on language interoperability to ease the first solution. However, it is not done yet, and I am not sure it is actually more simple than C++.
- Use a multi-paradigm monster : C++.
In which way would you call C++ multi-paradigm? I just call it a monster...
These are GCC issues. Static and dynamic library formats output by MSVC and windows compilers in general have been stable for years, and this is likely to be the same with other compiler vendors.
I second that, but there are other portability issues in MSVC. Specific extensions and broken code allowed to compile are the first problem. Then if you do consider time passing, crazy dependencies of big projects with version-dependant MFC functions, .NET hassles and a different DLL hell for each version of windows become a big drawback.
System-dependant software must be well-written, otherwise it can be dangerous for the vendor (e.g. Easy CD Creator which was basically rewritten to work on winxp !!)
One thing's for sure, the only portable win32 program that can be recompiled in 5 years, is a console-based os-independant C++ project with no resource files and no system calls.
In other words.. a true algorithm without bells and whistles
Any software should contain lots of algorithms and very simple I/O..
ErikS:
In which way would you call C++ multi-paradigm? I just call it a monster...
Some quick citations from the AT&T glossary (http://www.research.att.com/~bs/glossary.html)
multi-paradigm programming - programming applying different styles of programming, such as object-oriented programming and generic programming where they are most appropriate. In particular, programming using combinations of different programming styles (paradigms) to express code more clearly than is possible using only one style
C++ - a general-purpose programming language with a bias towards systems programming that supports procedural programming, data abstraction, object-oriented programming, and generic programming. C++ was designed and originally implemented by Bjarne Stroustrup.
But as Stroustrup said in another interview (http://www.research.att.com/~bs/nantes-interview-english.html):
Bjarne Stroustrup: I think that "paradigm" is an overused word, and I prefer the less pretentious "programming style".
NumLOCK:
System-dependant software must be well-written, otherwise it can be dangerous for the vendor (e.g. Easy CD Creator which was basically rewritten to work on winxp !!)
Do not talk about that, I finally clean the whole Easy CD Creator mess two hours ago (disappearing drives, random freezes...)
I think a big reason why a lot of "reference algorithms" are written in C is because it's easy to insert them into either a C++ or C program. If the reference is in C++ it can be difficult to put them into a project that's already implemented in C.
But for what it's worth, I think statically typed languages are going to eventually go the way of the dinosaur anyway. :-)
NumLOCK:
System-dependant software must be well-written, otherwise it can be dangerous for the vendor (e.g. Easy CD Creator which was basically rewritten to work on winxp !!)
Do not talk about that, I finally clean the whole Easy CD Creator mess two hours ago (disappearing drives, random freezes...)
I know what you mean.. glad you could sort that out
Well at least, *they* had an excuse to rewrite the code (ie: it *had* to work on xp kernel).
On the other hand, take Netscape for example.. they decided to rewrite version 4.0 from scratch.. what a completely stupid idea, which made them waste 1 1/2 years of development ! Needless to say, meanwhile the field was free for Microsoft. And those guys rarely think once (let alone twice) when there's fresh meat to eat
I know, I didn't like Netscape either, but that's not the point
About the topic, I think experience, not the programming language, is the key.
I can do crappy, slow programs in C, Java, Assembly, (...) any day
More interesting stuff mostly comes in experience. And real ideas rarely need a specific language to express themselves. ©
Regards
I think a big reason why a lot of "reference algorithms" are written in C is because it's easy to insert them into either a C++ or C program. If the reference is in C++ it can be difficult to put them into a project that's already implemented in C.
Indeed.
I see, however, other important reasons:
- more than 80% of the today's code was written is C (IIRC)
- any deterministic algorithm can be expressed in C, and...
- C is often one of the shortest ways to express it.
But for what it's worth, I think statically typed languages are going to eventually go the way of the dinosaur anyway. :-)
I don't know about you, but I personally would far prefer being called a dinosaur for the rest of my life, than starting to use Variant types in Visual Basic !
For historical accuracy, I must confess that I first learnt programming in QuickBasic . No it didn't have the infamous variant type, and yes, it provided subroutines and was free of "line number" & "goto" practices
I think Java goes the right way with garbage collection, but again, the faster algorithms will always deal with primitive types (thus needing no one to tidy up their mess)..
One good thing is no-compromise portability. One bad thing is people don't get bitten with sharping-edge pointer problems, caused by their inappropriate thinking.
Void pointer is not the answer B)
I see.. without objects right? Does that mean that these routines should be place within the same class?
Okay, I oversimplified the matters a bit. I was just trying to express that it's possible to write very C-stylish code with C-stylish performance in C++. There is absolutely no reason to ditch OOP completely in C++. The overhead of C++ depends greatly on the structure of your program and the style of your source code. You need to know how different constructs perform and when is the appropriate time to use them. For instance;
- object construction can be slow
- allocating memory from the heap is slow (as in C)
- calling virtual functions is slow, especially with complex class hierarchies
- accessing data or functions through pointers is can be slow (as in C)
It's not that you couldn't use these language constructs; you could and probably should. It just might be best to avoid using them in any performance-critical part of the code, such as in a tight calculation loop.
As for using OOP, go nuts. Create just as many classes as you need. As NumLOCK said, a tight loop in the code could run for 10 hours or so; it doesn't matter if it took 40 nanoseconds longer to start the loop by executing a virtual function instead of a non-virtual one.
I don't know about you, but I personally would far prefer being called a dinosaur for the rest of my life, than starting to use Variant types in Visual Basic! :phear:
I'd rather have toothpicks soaked in sulfuric acid shoved under my fingernails than ever use Visual Basic at all. I'd much rather have something like Perl or Python.
GCC had some issues with compatibility, but it is now gone and will be stable, because it's standard now.
I hope it will be possible to compile foobar2000 plugins with it some day.
My problems with MSVC++ 6 SP 5:
- non-compliant C++ (notorious hacks to support it)
- problems with simple code (check my thread at foobar2000 Developer section (http://www.hydrogenaudio.org/forums/index.php?showtopic=12663&))
Another quite good compiler is Borland C++ (not free). I'll give it a run with foobar plugins.
Another quite good compiler is Borland C++ (not free).
It's also one of the slowest C compilers ever, I reckon.
Code generated with it is rock stable (I.E, doesn't feature some of the instabilities introduced by ICL), but still, runs amazingly slow. I once saw some code that was faster when generated in MSVC debug mode than when generated in BCC release mode. :B
At least, it compiles very quickly...
http://www.willus.com/ccomp_benchmark.shtml?p10 (http://www.willus.com/ccomp_benchmark.shtml?p10)
I think that Fortran and C, probably Algol 66 & Pascal there are languages to express algorithms. C++ and Modula 2 are for express systems. Most algorithms are published in pseudo code anyway.
Another quite good compiler is Borland C++ (not free).
It's also one of the slowest C compilers ever, I reckon.
Code generated with it is rock stable (I.E, doesn't feature some of the instabilities introduced by ICL), but still, runs amazingly slow. I once saw some code that was faster when generated in MSVC debug mode than when generated in BCC release mode. :B
At least, it compiles very quickly...
http://www.willus.com/ccomp_benchmark.shtml?p10 (http://www.willus.com/ccomp_benchmark.shtml?p10)
I think that was some years ago.. I too noticed that.. I did a comparison between codes compiled by BC 3.1 and VC 5.0 and VC 5.0 outperforms BC by many times.. However, my superiors pointed out that VC 5.0 was actually taking advantage of the "improved" floating point performance of the Pentium processor..
That was an old story.. but I am not very sure of the latest Borland Compilers..
wkwai
You need to know how different constructs perform and when is the appropriate time to use them. For instance;
- object construction can be slow
- allocating memory from the heap is slow (as in C)
- calling virtual functions is slow, especially with complex class hierarchies
- accessing data or functions through pointers is can be slow (as in C)
It's not that you couldn't use these language constructs; you could and probably should. It just might be best to avoid using them in any performance-critical part of the code, such as in a tight calculation loop.
Such flexibility is possible with C++ but for other programming languages such as Java, OOP approach is a must.. I implemented a FFT in Java sometime ago and its performance is incredibly slow! There is just no way to completely avoid using Java's language constructs..
I think that was some years ago.. I too noticed that.. I did a comparison between codes compiled by BC 3.1 and VC 5.0 and VC 5.0 outperforms BC by many times.. However, my superiors pointed out that VC 5.0 was actually taking advantage of the "improved" floating point performance of the Pentium processor..
That was an old story.. but I am not very sure of the latest Borland Compilers..
That comparision is using the freely available BCC 5.5.1. I don't know if they have more up-to-date compilers.
And, as you can notice by the flags used, that benchmark is using all optimizations possible! :B
When dist10 (iso demonstration code) was written, there was no C++ compliant compiler.
Even today, you can be quite sure that someone has a C compliant compiler, but you can not be sure about C++ compliance.
Probably not. A C-only compiler might be able to optimize more easily than a C++ one because it could make assumptions the latter cannot.
Actually, it's mostly the opposite. For example, the use of the 'const' keyword helps compilers optimizing. That one was added in C99, but still in C++ you can overload finctions based on const so that each version is as fast as possible given how it will be used.
When dist10 (iso demonstration code) was written, there was no C++ compliant compiler.
Even today, you can be quite sure that someone has a C compliant compiler, but you can not be sure about C++ compliance.
Discussion is silly. For "algorithm research" there's nearly no difference between C++ and C.
Both are relatively useless for an effective research. When testing algorithms, you don't
want to care about memory management, pointers etc.
For "algorithm research" engineers typically use programs like Mathematica or Mathlab.
Often you find the test examples as *.m files. There are a lot of powerful library functions,
you can use this within some seconds. Programming that in C or C++ will take weeks or
months.
For "algorithm research" engineers typically use programs like Mathematica or Mathlab.
Often you find the test examples as *.m files. There are a lot of powerful library functions,
you can use this within some seconds. Programming that in C or C++ will take weeks or
months.
This is not entirely true.
For signal processing purposes, Matlab is great, of course. Digital filter design, matrix operations, plotting (and many more things) are straightforward.
However, as soon as you need iterative algorithms with simple operations (those which can't be parallelized into big matrices), the M scripts become awfully slow (~ 3000 times slower than C) ! For such algorithms I think experimenting in either Quickbasic (QB != VB) or C, is better (depending on your experience).
For algorithms which do few maths and manipulate a lot of data, Java might be a good choice for experimenting: hashtables and a lot of primitives are already there for you.
Of course, this all depends a lot on which languages you're comfortable with.
I remember people still using Fortran to design algorithms.
Why didn't anyone mention Pascal? It's much better than QBasic.
I remember people still using Fortran to design algorithms.
Why didn't anyone mention Pascal? It's much better than QBasic.
You're right, the Borland Turbo Pascal was a great environment !
I was not talking about QBasic though, but about the "pro" version which QuickBasic. With the latter you could create EXE files, and the interpretor mode was much faster than in QBasic.
To draw a vertical greyscale gradient on the screen, just use:
screen 13 : cls
for i% = 0 to 63
OUT &H3C8, i% ' palette index
OUT &H3C9, i% ' RED component
OUT &H3C9, i% ' GREEN component
OUT &H3C9, i% ' BLUE component
next i%
for y%=0 to 199
line(0,y%)-(319,y%),y% mod 64
next y%
All this, by heart.. Ah, memories
I don't understand why people would hate c++. I'm just getting into it, but already it seems much improved over plain c. Take stupid things like I/O. Why should i have to specify the data type I'm going to print TWICE within each printf statement (once as %c/d/lf etc and again when the actual variable is loaded). c++ wisely gets rid of that. Likewise why should there be completely different commands for dealing with strings vs everything else?
Maybe it gets worse once you're in deeper, but c++ just seems better thought out to me.
Oh yes, it makes much more sense to do IO with overloaded freaking BITSHIFT operators whilst at the same time, making any formatting of the output a huge pain in the rear. I swear to God, somebody was on 'shrooms when they came up with that revealation. OTOH, Saying that C++ is better than C is probably true. The single line // comments were definately a nice addition. But it's also like saying "sleeping on a bed of rocks is much less painful than sleeping on a bed of nails."
Now, to be fair, I'm only this ornery about C++ because I've had to use it a lot lately. Also, of the thirty or so languages I've had contact with over the years, there's been only two that I actually liked, and of the remainder, only a few that I didn't actively hate and bitch about.
Why didn't anyone mention Pascal? It's much better than QBasic.
I'd consider and have used Delphi (Object Pascal) for professional work.
IMHO Object Pascal is a lot cleaner than C++
Most of the algorithm books were published at a time when C++ was not a stable language. For what it's worth, many of these algorithms would have been published originally in Fortran or PL/I, which were the linguae francae of the development community before C came along. The same is true of the JPG source code: at the time it was written, the C++ standard was evolving rapidly, and C++ compilers were not available on many DSP and embedded controller platforms.
There is absolutely no reason that C++ code should run any slower than C code, given that C is an almost strict subset of C++.
BC 5.1 is based on very old compiler technology. Although Borland compilers used to compete well with Microsoft compilers, they have been stagnant for quite some time. The bottom line, BC compiler optimization is very poor compared to current generation Microsoft compilers (particularly wrt/ floating point optimizatons, and instruction scheduling optimizations).
Oh yes, it makes much more sense to do IO with overloaded freaking BITSHIFT operators whilst at the same time, making any formatting of the output a huge pain in the rear. I swear to God, somebody was on 'shrooms when they came up with that revealation.
It makes sense when you realize what problem they were trying to solve with all that crap. They wanted a typesafe replacement for printf that could do some compile-time error checking. With printf, you have no way to check at compile time whether the arguments passed to it are of the correct type, or even if you have passed the right number of arguments. The new IO constructs fix this (in the most longwinded way possible).
I agree that the standard IO stuff is way too complicated when working with simple strings; I still use printf in these cases. However, one really cool thing is that since you can overload the bitshift operators for your own classes, you can do stuff like this:
cout << myObject;
And not with just cout, but with anything that can take an ostream.
The bitshift operators were chosen simply because they look pretty and for most objects there is no obvious bitshift operation that can be performed. It's also in keeping with C++ style to further obfuscate code by overloading yet another operator.
There is absolutely no reason that C++ code should run any slower than C code, given that C is an almost strict subset of C++.
That would depends on how you write the code in C++.. There is a lot of what NOT to do in C++ for algorithms.