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?"
Having read the article and looked at your Ocaml code, you do have at least one problem in your implementation. You're using lists. Lists are not for random access and modification. To change the nth element of a list, you need to modify (and reallocate) n elements.
Try using a map instead. I'll send you example Ocaml code in a day or two (I'm moving, so I don't have that much free time to fix other people's bugs that I'm not getting paid to fix). Note that this is true in Haskell as well as Ocaml. Haskell may be just a little bit better at hiding the problem with laziness- but it's still a problem!
Now, for the brutal part of the response: that big of a difference in performance almost certain does mean you've messed something up in your implementation. But, instead of saying "Gee- I wonder what I screwed up?" you said "Gee- Ocaml and functional programming must just suck!" That I still fault you for.
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!Ocaml doesn't support any ad-hoc polymorphism (overloading) whatsoever in functions. Methods on the other hand can be overloaded, but not generic. This sort of thing makes it weaker than even C++ for generic programming, let alone Haskell, though I must admit not having to use template syntax makes me want to claw my eyes out a good deal less when reading it (or my hair when writing). Modules simply don't do it for me. Having to differentiate between HashTable.insert and SkipList.insert sort of defeats the purpose of abstract types, because no one thought to make module signatures themselves first-class (except Alice).
Haskell type families are just elegance and beauty itself, but doing state in Haskell is an exercise in raw tedium. Very localized state (in one function) is easy enough, but anything more pervasive and you soon become more familiar with monads than you ever wanted to be. If you want a haskell program that doesn't suck up more memory than emacs, you have to stay away from many modern features so your program will compile with nhc98.
Ocaml isn't seeing a lot of new work going into it -- the language definition seems to have become cast in stone. Haskell is always evolving, though typically in ways that are really impenetrable to those of us without PhD's in category theory and denotational semantics.
I guess I could search the world over for my holy grail FP language, and always be dissatisfied...
I am no longer wasting my time with slashdot
Not always, not always.
For example, I have seen two different kinds of tree castings made of stone: one, a negative casting made by molten lava that built up as an accretion on a tree (which obviously burned out), and two, a positive casting made through a slow fossilization ("petrification") process.
I would happily come up with a false etymology originating in the parlance of lime-slakers, medieval wall builders, sarcophagus fillers, or even potters discussing cone-10 firing, but you'd probably call me on it.
That being said, it is a weird phrase, that probably belongs with "mute points" and exclaimations like "here here!"
Eloi, Eloi, lema sabachtani?
www.fogbound.net
Yea, you're not kidding.
:= (key, value) :: !table;;
I just looked at the code, and he's memoizing the function results in a associative list:
(* Set up an associative list for memoization *)
let lookup key table = List.assoc key !table;;
let insert key value table = table
Insertion is cheap, but the lookup is a linear table scan! Doh! What was he thinking?
I suspect that a Hashtable or a Map datastructure might be much better suited to the task.
In any case, it would have been very easy for him to post this code to the OCaml newsgroup and ask, "Am I writing good functional code?"
He would of gotten a lot of advice on how he could have sped up his program while still maintaining a functional style.
Lastly, in response to his question, "I could write an OCaml implementation that is isomorphic to the C++ code (using loops and side effects), but what would be the point?" The point is that you can easily mix and match styles in OCaml.
You can write 90% of your code in a functional style and fall back to imperative style if there is an inner loop that would benefit from that.
For this problem though, I suspect that a well written functional version would be pretty close in speed to his C++ version, cleaner, and easier to maintain.
# (/.);;
- : float -> float -> float =
I for one would be interested by how much you could --as a regular ML user-- optimise the code and see what kind of performance you could get. Really there are no slow languages, only slow implementations.
Your CPU is not doing anything else, at least do something.
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.
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.
Only to the extent that all of your production code is speed-sensitive. The hot-spots are generally only 10% of the code. A lot of very complex code (eg: configuration stuff), only gets run very rarely. Using high-level languages has a certain design procedure. You write everything at the high-level, and verify that it works. Then, you look at the optimizer and see what to fix. If your compiler is good, you'll only have to write a fraction of the code at a low-level, and you'll have a net time benefit.
A deep unwavering belief is a sure sign you're missing something...
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.