Slashdot Mirror
OCaml vs. C++ for Dynamic Programming
jcr13 writes "OCaml is nearly as fast (or sometimes even faster) than C, right? At least according to the Computer Language Shootout [alternate] (OCaml supporters often point to these shootout results). My results on a real-world programming problem (optimizing a garden layout using dynamic programming) disagree. On one particular problem instance (a garden of size 7x3), my C++ implementation finished in 1 second, while the OCaml implementation was still running after 16 minutes. Bear in mind that my OCaml implementation was dramatically faster than my equivalent Haskell code. It seems that if you program using a functional style in OCaml (which I did, using map, filter, and other recursive structures in place of loops), it is quite slow. However, most of the shootout OCaml programs rely heavily on OCaml's imperative features (unlike Haskell, OCaml doesn't force you to be a functional purist). If you write OCaml code that is isomorphic to C code, it will be fast---what about if you use OCaml the way it was meant to be used?"
So the OCaml compiler is supposed to figure out that there's a dynamic programming solution to the problem you have specified using higher order operators? That's a great idea. Let me know when you work that out cause I'd love to be able to just write a specification, press a button and get an optimised program. If you do manage to make this though, be sure not to tell those bastards who pay our salaries, they'll probably think we're not working anymore.
How we know is more important than what we know.
That difference is so dramatic that I wonder if you made a mistake in your functional implementation? Or is there something specific about your dynamic program that makes trouble?
Dynamic programming depends basically on memoization (not "memorization", before someone complains about my typo) which inherently means preserving some state. If you don't preserve state, it becomes a good old, likely exponential time, recursive program. Any chance your implementation is not memoizing?
That doesn't mean that ocaml is slow. It means that dynamic programming in a functional programming style in an eager programming language requires a lot of care, or perhaps should even be avoided. A result that wouldn't surprise me the slightest.
You know I've implemented some real world applications recently for a contract job, and the Ocaml applications are actually faster than the C++ equivalents using the STL. So you mileage may vary based on your problem set (or Ocamlfu as the case may be). As for how Ocaml is supposed to be programmed, there's a reason Ocaml supports imperative programming, because you should use the form that is most efficient for your problem. Some programs benefit from a functional approach (and it helps if you implement properly tailrecursive functions, and make intelligent use of arrays and other block data structures). So one can argue Ocaml is not particularly functional, because it more pragmatically allows for multiple styles of programming. You can do functional programming in C++ actually, but depending on the optimizer you end up with stack issues. My experience with maintaining and extending the Ocaml programs over large C++ code bases is a world of difference. Ocaml wins hands down. Even extending the language to support 3rd party libraries, doesn't place sufficient barriers to maintenance. But ymmv... as with all things.
OCaml is a multiparadigm language. C++ is also a multiparadigm programming language - there are libraries that let you write functional programs in C++. So when comparing these two languages there is no excuse for comparing completely different algorithms. The whole point of a multiparadigm language is that it lets you choose the paradigm that fits the problem!
Occam is probably the most scalable language out there, as it was designed for massively parallel systems.
There's a PL/I interface to GCC. I dare someone to write a Gnome or KDE interface for it...
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
I'd like to see the Haskell sources for comparison.
http://minorgems.sf.net/Haskell.hs doesn't exist, though the the C++ and OCaml code are there.
Shae Erisson - ScannedInAvian.com
Usings lists in all circumstances because its functional is not appropriate. Show the ocaml implementation using arrays or an c++ implementation using linked lists for a valid comparision.
The strength of Ocaml is the flexibility it provides to a developer. If your solution is more elegantly coded using imperative constructs, then use them!If you're just looking for speed, try assembly. I hear all the good programmers are using it these days.
In the same kind of vein, has the code been profiled? I'd quite like to see where the time is going.
Did I just enter bizarro world? A "functional" language like OCaml is usually slower. And C++ is not for dynamic programming...?
Hmm, as other posters have pointed out, such a gigantic difference in speed is an implementation or algorithm choice issue, not a difference in language speed.
I bet if you optimize your program properly, it will be on the same order of magnitude in speed.
Note: I'm not suggesting that OCaml (I actually am more familar with Ruby, Lisp, and Haskell) is always slower than C/C++. In fact those higher-level languages often allow you to express your code in such a way that faster solutions become obvious. I.e. they allow you to gain better insight into your program.
I've seen different C compilers with all speed optimizations enabled generate code for the same problem that differed in performance by a factor of 20. This was not consistent with other benchmarks I had seen on the web comparing the same compilers. The benchmark was an html compressor. I'd share more, but unfortunately the code was automatically deleted by XP's chkdsk after a minor crash.
One algorithm is sometimes not enough to accurately judge between compilers. But I guess if it's OCaml, then sure, C++ is faster.
Your C++ code looks more like C code to me.
But now it all seems to be about Arrows. AAARRRGGGHHH!
Too bad. Haskell really is one of the coolest languages around.
I've done a LITTLE experimenting with OCaml in the past and liked what I saw but I don't really OCaml well so I won't try to comment on the actual specifics of your code (I do know C++ well), BUT...
I can absolutely guarantee you that if your OCaml implementation of this algorithm is over 960 times slower than your C++ implementation, something is wrong with your OCaml implementation. There is no chance that the same algorithm is 960 times slower in OCaml than C++. Why not ask for help on the OCaml mailing list (ie, the people who know about this stuff) rather than on Slashdot (ie, the people who don't)? They have been really helpful to me in the past.
Can we see your Haskell code?
Haskell is not known for raw speed, but dynamic programming is probably the one thing it does well, thanks to lazy evaluation. You fill a CAF with unevaluated function calls, and the language engine does the rest. It won't be as fast as the hand-crafted C++ version, most likely, but if your O'Caml code is anything to go by, it might be able to be improved.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
Your problem is that you don't understand how OCaml was meant to be used. We do not have a variety of data structures and imperative features so you can go use lists when arrays are appropriate. This is not Haskell. Furthermore, you redefine numerous standard library functions... and not only that, your versions aren't tail recursive? Why would you do such a silly thing? No wonder your code is so long.
Basically what you need to do is sit down, stop being such a dumbass, read the manual, and don't pretend your false conceptions of how OCaml is "meant to be used" (your code is stylistically and algorithmically awful) are in any way relevant to its actual performance. If you wrote similarly stupid code in C++, it would be just as slow.
You can actually get a constant 8x speedup if you fix your memoization, but the real problem lies in the algorithm itself. Unfortunately, the code is unsalvageably bad.
One of the joys of programming in ML is that you can write most of your code in a really nice, functional way, and (if necessary) put in the effort to write a tight inner loop, perhaps in an imperative style for speed. I don't see this as a disadvantage, and ML compilers often do a better job of optimizing such loops than C compilers, in part because of more information being available in the type system. (And if they don't, it's trivial to invoke C subroutines.) Also, if performance is really an issue, you might try mlton (which is for SML, very similar to Caml); its whole-program approach often produces significantly better code than O'Caml.
However, as an every-day ML user I find it very unlikely that your program would be a thousand times slower if you're using it "the way it's meant to be used." I am guessing that your implementation is asymptotically worse, since using map and fold correctly should really only be a constant factor slower than C, at worst. (mlton can often inline and optimize these into essentially the same code you'd write in C!) How about posting your code?
FFTW is written in O'CaML. What you compile against is the C library O'Caml generates.
Often it's how you use the tool... not the tool itself. I've got C++ code that runs circles around C code.
This will happen don't be surprised.
You should use the Buffer module, or String.concat:If there is a lot of those mistake, no wonder it is so slow...
Well, I tried the code and on my computer it ran in about 10 seconds (ocamlc/bytecode) and in about 7.6 seconds (ocamlopt/machine code). So, what's the problem this discussion is about?
I see nothing wrong in your C++ version, while your ocaml version clearly sucks: you are memoizing using a complex key, and an association list, meaning that accessing memoized information costs a lot.
e n2.ml
If you are concerned by performance, you should use a complete cache, like in your C version.
FYI, I uploaded an ocaml translation of your C code. It doesn't use mutable state except for memoizing, and uses pattern-matching on lists, and recursion rather than for loops, but otherwise it follows closely your code. Performance should be very similar.
http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/gard
You wrote it in pure C! You are comparing Ocaml with C, not C++! You are just using the C in C++.
Try writing your program fully using OO and templates. I dare you.
Another thing: You OCaml code is shity. Im not asking you to tinker with optimisations, but just to use the correct data structures.
It's not fair compare lazy OCaml code to simpleminded C code.
I intend to live forever. So far, so good.
> Here's a laundry list of why your O'Caml program in inefficient:
>
> 1. You use lists. Lists aren't designed to be fast (computationally)
> to use. They're designed to be fast (programmatically) to use. You'll
> be hard pressed to find a production, speed-sensitive Lisp or O'Caml
> program that uses lists.
Okay... but here's my point: Every single example that shows how elegant Haskell and OCaml are uses lists. The 4-line Quicksort example for Haskell uses lists. All of the code that demonstrates easy reuse of functions and functions taken as arguments uses lists (like how easy it is to implement quite complicated algorithms using only map and filter, for example).
So, proponents say "Everyone should use functional languages because they can express complicated problems in elegant ways and result in cleaner, more reusable code."
But what you're saying in #1 above is that in "production," speed-sensitive code, no one is using lists... this would mean that no one is using map, filter, or any other pieces of reusable primitive code. So, they are instead all using mutable data structures... I.e., they are programming with side-effects and loops (random access instead of recursion, even when ever element of an array/list needs to be accessed/processed).
That was my point exactly. If you write elegant OCaml code using all of the lovely (and I mean lovely, really) tricks that they present when they demonstrate why OCaml is cool, you end up with code that is too slow to use in the real world.
I would say that my C++ (or most would call it C) implementation is elegant enough... easy to understand... no messy optimization tricks. Sure, I'm not using objects and templates everywhere, but these structures are hardly needed to solve this simple problem.
> 2. Practically none of your functions are written tail-recursively.
Good point.
> 2.5. You use a list append (@) inside a loop (generateStates).
> List.append is O(m), where m is the length of its first argument. If
> you write an implementation, you'll see why. It probably doesn't make
> much of a difference here (generateStates is only called once) but it's
> something to watch out for.
Of course, as you point out, generateStates has almost no effect on the running time. However, I wonder how you might implement that in an elegant way in OCaml without @. In C, I just looped over all numbers between 0 and 2^stateLength and converted the bit representations for the numbers to cell on/off states.
> 3. For Pete's sake, man, you're using an association list for your
> memos! Surely you know that lookup in an association list is O(n) in
> the size of the list.
I simply Googled for "memoization Ocaml" and found that code:
http://www.emeraldtiger.net/modules.php?op= modload &name=News&file=article&sid=9
The author pointed out how "sweet" polymorphism is... one block of code that can be used to memoize any function. Sweet indeed, and it certainly sped up my OCaml code a lot (without memoization, it was so slow as to be intractable for anything larger than about 4x4).
So... maybe you can re-write higher-order memoization code using more efficient data structures? I would love to see that code, and I'm sure the OCaml community would benefit from having that in their toolbox.
I agree that the memoization code is probably the problem in the OCaml version. However, this code came directly from the OCaml community and was the *only* example of memoization in OCaml that I could find.
For Haskell, I used an infinite list of results that was filled in lazily as the results were needed. This also sped up the algorithm dramatically. However, I cannot get a Haskell compiler to compile itself on my platform, so I was testing all code in the Hugs interpreter, which made it too slow to be practical. Isomorphic compiled OCaml code was hundreds of times fast
Look at the shoot-out with only tests that are all available for C, C++ and O'Caml are included and weighted for both CPU and Memory. It paints quite another picture.
moot actually means debatable. However, in the expression "moot point" it seems to be used in the sense "tangential/unnecessary point"
It all boils down to understanding the complexity of the basic building blocks of your algorithms which can vary considerably with the data structures you choose to implement them.
Have you considered updating that web page - keep the content you have there now, but possibly tack on some of the feedback from here that shows that yes, a very, very bad implementation of an algorithm will run slowly, regardless of the language. It would be a shame of someone ran across the page seeking a realistic comparison, and didn't look deep enough to realize that this "study" is basically the equivalent of comparing the gas mileage of two makes of automobile without informing the readers that one car had a semi-truck chained to the back of it during the trials.
jcr13, I feel your pain. I've hit the exact same wall and bounced in nearly the same fashion.
There are tons of examples of OCaml code out there, but whenever you try and use them you'll find they're written for elegance, not for any real-world metric. It makes for good propaganda, but not much help for anyone trying to do anything real. Asking for help and showing this code in most communities results in a series of curt, bitter responses from many members of the community.
So even though all kinds of arrogant Ocaml and functional programmers are coming after yor for "spreading lies", don't despair. You're not the only one to make this observation about the community.
Slashdot. It's Not For Common Sense
The insert example isn't great. Despite using the same name and similar end results, these are unlikely to have the same performance characteristics, which is likely to be a significant difference in practice.
However, consider a simple function such as map, which fundamentally takes some structured data, and produces a new set of data with the same structure, built from the original elements acted on by some function. This concept is applicable to a wide range of data structures, and writing it polymorphically (not generically) just makes for code that's easier to read and less memory work for the developer.
A more advanced example might be the use of a fold style function directly on lists. A similar concept could be applied to a tree, but you'd have to have some intermediate functionality that defined the ordering you were using to traverse your tree. Still, it can be useful to separate the concepts of the ordered algorithm (fold, or whatever more complex function is using it) from the ordering algorithm (traversing breadth-first, depth-first, etc.), from the connecting and terminal functions used by the fold algorithm specifically but potentially useful elsewhere as well.
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
If you want to program in a functional style, and you need lazy evaluation, you're going to find the standard library that comes with the compiler somewhat limited.
I wrote some extensions for programming in OCaml in the functional style. Check out the OCaml NAE project, and look for the Core Foundation (Cf) package.
jhw
Actually, it is possible to do this. Search for "Algebraic Dynamic Programming" to find some papers describing this. Basically, you specify your problem as a grammar similar to BNF, and supply an evaluation algebra - and DP is added by a simple annotation indicating which parts of the parser should be tabulated. All implemented directly in Haskell.
-kzm <ketil at ii dot uib dot no>
That's a very important point, and I think the effect of the community around a programming language (or indeed a whole paradigm -- functional, OOP, etc.) is often underestimated.
Just look at PERL: it has its merits, but in fairness clarity to newcomers is rarely listed as one of them. And yet, because asking a question on a PERL group tends to result in joyous cries of "TMTOWTDI" followed by an enthusiastic discussion of the relative merits of 17 different ways to solve your problem, even the most unaware newbie is likely to find help and education simply by asking politely.
In contrast, some languages (C and C++, for example) tend to invite technical perfectionists, who are happy to help but only if you're Doing Things Properly(TM). Others (functional languages, LISP dialects, etc.) tend to have quite academic communities, whose response to newbies, sadly, can be less than welcoming.
Now, take a look at those languages I listed, and ask yourself which ones have been the bigger success stories...
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
I am thinking that it very wrong to discuss about language itself. Discussion should be about it's implementation.
As ratboy666 showed example, implementation can be very crucial.
Everyone knows that no usage is better than wrong usage. Andrew Koeing said in C Traps And Pitfalls for C: "The C language is like a carving knife: simple, sharp, and extremely useful in skilled hands. Like any sharp tool, C can injure people who don't know how to handle it."
The same is for C++, OCaml, assembler etc. If you are skilled enough, for examaple in perl, you will do faster things than many people in other languages, even assembler.
For STL library; many people use it wrong. They even don't read documentation about it. I mean good documentation. For example, every book about C++ will show only 10% of STL, but deep secrets are only findable in advanced papers.
Look this example:
1) string s = "test";
2) string s("test");
For ordinary user, there is no difference and many books don't discuss this small issues. Only books from language experts will explicitly note differences (Effective C++ series, Exceptional C++ series etc) and show that 1) example will do 3 calls, but 2) will do only once. Of course, good implementation will optimize 1) to be as same sa 2), but that is another issue.
Also users should be very careful even for STL implementation. STLport will do much faster string handling, than libstdc++ from gcc. Why ? The only solution is to fire up your editor and go deep in implementation itself. Results will be self-explainatory.
So, at the end. Use good books (one good book, even harder for reading, is better than ten bad), and test implementations.
Check out comp.lang.lisp to see for yourself. No one appreciates people asking them to do their work for them but, they're helpful to people earnestly trying to learn.
Someday we'll all be negroes
Here's my first attempt at a version which performs decent in Haskell. It doesn't do any memoization, and isn't particularily dynamic. It ended up being only 35 non-blank lines of code. The 9x3 case takes 26 seconds to complete on my Athlon 1600 compiled with GHC 6.4. Erg. You'll have to grab a copy here as /. thinks my Haskell code has too many 'junk' characters.