Re: Cryptarithm solver - Haskell vs. C++
On 18-Sep-1999, Fergus Henderson [EMAIL PROTECTED] wrote: Well, I tried with ghc 2.08 -- admittedly an ancient version, so this is not a fair comparison, but that was what I had on hand. On a 300 MHz DEC Alpha system, I got the following times: LanguageCompiler versionOptions Time Haskell ghc 2.08-O 21.5 seconds Mercury rotd-1999-09-17 -O6 7.5 seconds Mercury rotd-1999-09-17 -O6 --gc none2.2 seconds C++ egcs-1.1.2 -O3 .23 seconds Hmm... a ratio of about 100:10:1 for Haskell:Mercury:C++ is, well, interesting ;-). I wonder how much better ghc 4.x does? I downloaded ghc 4.04 and ran the same test on a 500MHz Pentium-III Linux System, and got the following figures: LanguageCompiler versionOptions Time Haskell ghc 4.04-O2 8.5 seconds Haskell ghc 4.04-O2 -fvia-c 8.6 seconds Mercury rotd-1999-09-17 -O6 2.4 seconds Mercury rotd-1999-09-17 -O6 --gc none1.0 seconds C++ egcs-1.1.2 -O3 .17 seconds So it looks like ghc 4.04 is still a fair way behind, at least as far as this test case is concerned. -- Fergus Henderson [EMAIL PROTECTED] | "I have always known that the pursuit WWW: http://www.cs.mu.oz.au/~fjh | of excellence is a lethal habit" PGP: finger [EMAIL PROTECTED]| -- the last words of T. S. Garp.
Re: Sisal (was: RE: Cryptarithm solver - Haskell vs. C++)
Olivier LeFevre wrote, | "R.S. Nikhil" [EMAIL PROTECTED] wrote, | | Sisal researchers [...] deliberatly chose to avoid higher-order functions, | polymorphism, laziness, etc. | | In a first release, yes, but I believe higher-order functions were included in | Sisal 2.0, which was almost ready for shipping when the Sisal project was | abruptly terminated by LANL management. | | From what I understand, internal LANL politics, not internecine warfare within | the FP community, was the cause of the shutdown. LANL seems to be betting the | farm on C++ (PETE, POOMA). Personally I find the tecniques uased in PETE | interesting but they amount to pushing work that ought to be done by the | compiler (at least IMO) into the libraries and onto the library writers, which | uncharitable souls might call a cop-out. The Sisal project was at LLNL (Lawrence Livermore). PETE and POOMA are indeed LANL (Los Alamos) projects. The Sisal project was funded primarily by the US Department of Energy's Basic Energy Science office, and if I recall correctly, when the DOE funding was lost, Livermore management did manage to keep Sisal going for a time. Cheers, --Joe Joseph H. Fasel, Ph.D. email: [EMAIL PROTECTED] Technology Modeling and Analysisphone: +1 505 667 7158 University of Californiafax:+1 505 667 2960 Los Alamos National Laboratory postal: TSA-7 MS F609 Los Alamos, NM 87545
Re: Cryptarithm solver - Haskell vs. C++
Manuel M. T. Chakravarty wrote: Bart Demoen [EMAIL PROTECTED] wrote, Speed is not the only issue - feasability is an issue as well. I completely agree, but the original poster did not complain about a slight discrepancy in speed, he was puzzled about an unacceptable large gap of several orders of magnitude. Speed is not the only issue, but it definitely is _an_ issue. Another issue is correctness. What can be said about the correctness of the C++ program? the haskell program? What theorems do we get for free with this haskell program? John Atwood
Re: Sisal (was: RE: Cryptarithm solver - Haskell vs. C++)
"R.S. Nikhil" [EMAIL PROTECTED] wrote, From: Manuel M. T. Chakravarty [mailto:[EMAIL PROTECTED]] "R.S. Nikhil" [EMAIL PROTECTED] wrote, ... But it DID offer an important new feature relative to the original Fortran programs it was trying to displace -- completely automatic parallelization for the Cray vector machines that were the main workhorses at Livermore and similar labs. Hmm, good point. So, did they succeed in reaching this goal, compared to the awful guessing and trial error you have to go through before you get any decent performance out of a vectorising Fortran compiler? In the following paper, the Sisal team describes their technical successes, including performance numbers. [...] title = "Retire Fortran? A Debate Rekindled", [...] I know this paper (and its runtime results are very impressive), but IIRC it doesn't really answer the question about how difficult it is to write Sisal code that vectorises well. My experience with vectorising Fortran compilers (with only one, to be honest) is that small variations in coding an algorithm can lead to vastly different execution times and you often have to have accurate knowledge about how a vector processor (and the compiler) works to get it right. It would be interesting to know how much simpler this is in Sisal. In the paper, they "simply" re-coded existing Fortran code in Sisal - I guess the original Fortran code was already streamlined for vector processing. [...] Unfortunately, these choices won them no respect in the FP community (for which, my commentary, shame on the FP community), who chose to look down their noses at Sisal for what were essentially trivial and shallow reasons (Pascal syntax, focus on those "dirty" arrays instead of those "cool" lists, no polymorphism, no higher-order functions, ...). This made it MUCH harder for the Sisal team to sell the language to their Fortran-writing colleagues, who kept hearing negative opinions about Sisal from the FP community. That is sad, indeed - and fires back, I guess, as an outsider will likely attribute the failure to a technical deficiency of FP. Anyway, thank you for outlining the political background, which I was not aware of. Manuel
Re: Sisal (was: RE: Cryptarithm solver - Haskell vs. C++)
Unfortunately, these choices won them no respect in the FP community (for which, my commentary, shame on the FP community), who chose to look down their noses at Sisal for what were essentially trivial and shallow reasons (Pascal syntax, focus on those "dirty" arrays instead of those "cool" lists, no polymorphism, no higher-order functions, ...). This made it MUCH harder for the Sisal team to sell the language to their Fortran-writing colleagues, who kept hearing negative opinions about Sisal from the FP community. Being an old fart, I was around when most of this happened, and will humbly share at least some of the "blame" for this. But in our defense, this was at the time when there was no "standard" FL and we were trying to establish Haskell as such a candidate -- and not selfishly, but for the good of the community, which outsiders viewed as being fragmented and lacking in terms of a standard language. We encouraged the SISAL folks to at least use a subset of Haskell for SISAL, but they did not want to do this -- my strong impression was that they wanted to mark out their own turf. In hindsight both groups should have supported each other more, but hindsight is always 20-20. In any case... This may not have been the exclusive reason why Sisal did not take off, but I have heard members of the Sisal team say, more than once, that this was a major contributor. I seriously question the claim that it was a major contributor. There was, and of course still is, an ungodly amount of FORTRAN code out there, much of which was being reused in the form of libraries, even in parallel applications. Having to rewrite this code, support a new language, re-train programmers, etc. were far greater impediments to the use of SISAL (or any other language instead of Frotran), IMHO. -Paul
Re: Cryptarithm solver - Haskell vs. C++
At 10:41 21/09/99 GMT, Marcin 'Qrczak' Kowalczyk wrote: ... I have to care how fast my programs run. ... I had to write and maintain a boring program calculating lots of numbers from matrices, trying various permutations of rows and columns, joining rows and columns, generating random matrices meeting specific criteria, searching for ones that maximize certain formulae etc. ... Maybe it's simply not possible to compile Haskell more efficiently? It is possible to improve the efficiency of lazy functional languages on matrices considerably. The first thing to be done is to create an efficient representation. As far as I know, to main reason why Clean is faster with matrices than Haskell is due to the different representation. Also in a lazy language many optimisations can be done. We can take a look at the things done in implementations of C (sorry), SISAL, SAC, etc. The high level of abstraction in modern lazy functional languages posses both opportunities and challenges to the compiler builders. We cannot expect the compiler to cope with each situation as good as a cleaver low-level programmer who knows what he is doing, but it should be possible to reduce the price (in execution time) to use a language like Haskell for matrix manipulations. A similar argument holds for C and assembly. Pieter Koopman
Re: Cryptarithm solver - Haskell vs. C++
[EMAIL PROTECTED] (Marcin 'Qrczak' Kowalczyk) writes: I have to care how fast my programs run. I like writing in Haskell very much, it's my favorite general-purpose language, but one of the biggest weak points of Haskell for me is poor efficiency (at least with ghc, I don't know how fast are other compilers). I wonder whether this is the issue of Haskell itself or the compilers, I wonder if I can expect things to go better in future. I don't know what the future holds but, at least with GHC, you already have a range of options, to try to go faster. * You can profile your code and write better "standard" Haskell; * You can drop down to non-standard Haskell, and express your code with (e.g.) unboxed values, bytePrimArray#s, -- i.e. direct access to the machinery that GHC's libraries use; * You can code selected hot spots in C/whatever, and call out from Haskell to do those; if you do enough of this, you end up with the non-Haskell program you would've had to write anyway :-) * You can give your code to the GHC people for benchmarking purposes; be sure to mention, "By the way, this code runs N times faster when compiled by HBC" -- it works wonders. I think it is Very Cool that users have it within their power to claw back arbitrary "performance loss", if they want/need to. Will
Re: Cryptarithm solver - Haskell vs. C++
Bjorn Lisper [EMAIL PROTECTED] wrote, "Manuel M. T. Chakravarty" [EMAIL PROTECTED]: * While Sisal is arguably nice than Fortran, it doesn't really provide a new killer feature - rewriting all this Fortran code, just for getting nice programs is maybe not enough of an incentive. As I remember it, a main argument for Sisal was that the freedom of side effects would simplify the automatic parallelisation. So one important percieved incentive was to actually get better performance than from automatically parallelised Fortran. But, as far as I know, there was never an implementation that actually demonstrated that benefit. IIRC, some programs were a little faster on some Cray vector machines, but that was about it. Manuel
RE: Cryptarithm solver - Haskell vs. C++
-Original Message- From: Manuel M. T. Chakravarty [mailto:[EMAIL PROTECTED]] Sent: Wednesday, September 22, 1999 4:35 AM ... * While Sisal is arguably nice than Fortran, it doesn't really provide a new killer feature - rewriting all this Fortran code, just for getting nice programs is maybe not enough of an incentive. But it DID offer an important new feature relative to the original Fortran programs it was trying to displace -- completely automatic parallelization for the Cray vector machines that were the main workhorses at Livermore and similar labs. Nikhil
Re: Cryptarithm solver - Haskell vs. C++
"Manuel M. T. Chakravarty" [EMAIL PROTECTED]: * While Sisal is arguably nice than Fortran, it doesn't really provide a new killer feature - rewriting all this Fortran code, just for getting nice programs is maybe not enough of an incentive. As I remember it, a main argument for Sisal was that the freedom of side effects would simplify the automatic parallelisation. So one important percieved incentive was to actually get better performance than from automatically parallelised Fortran. Björn Lisper
Re: Cryptarithm solver - Haskell vs. C++
On Wed, Sep 22, 1999 at 09:44:34AM +0200, Bjorn Lisper wrote: Sisal was an attempt to define precisely such a functional language. ... no higher order functions Uhh... have I misunderstood what functional programming is? Isn't higher-order function support a necessary part of every FP language? -- %%% Antti-Juhani Kaijanaho % [EMAIL PROTECTED] % http://www.iki.fi/gaia/ %%% "" (John Cage)
Re: Cryptarithm solver - Haskell vs. C++
Sat, 18 Sep 1999 00:06:37 +0200 (MET DST), Juergen Pfitzenmaier
[EMAIL PROTECTED] pisze:
I dont't care very much how fast a program runs. I care about how
long it takes me to write it. If you take a programming task of
reasonable complexity you will finish *months* earlier using a
--good-- functional language instead of C++.
Use a functional language and buy a faster computer with the saved
money/time.
I have to care how fast my programs run. I like writing in Haskell
very much, it's my favorite general-purpose language, but one of the
biggest weak points of Haskell for me is poor efficiency (at least
with ghc, I don't know how fast are other compilers). I wonder whether
this is the issue of Haskell itself or the compilers, I wonder if I
can expect things to go better in future.
I had to write and maintain a boring program calculating lots of
numbers from matrices, trying various permutations of rows and columns,
joining rows and columns, generating random matrices meeting specific
criteria, searching for ones that maximize certain formulae etc.
I didn't know Haskell that time and I wrote the core in C++, wrapping
it in shell and perl scripts.
It takes a whole night to compute some data on 1000 matrices. Now
I would not write the program in Haskell, even though it would be
much simpler and easier to extend. I can't wait two weeks for results
each time. It's faster to spend one more day of awful coding in C++
because the results are needed as soon as possible.
OK, maybe it's not enough complex to make the difference in development
time bigger, but it's real.
I don't have money yet for a faster computer than my 3 years old
Pentium 133 with 32MB of RAM.
I would be much more happy if Haskell could be compiled to a more
efficient code. "Only 10 times slower than C" may be unacceptable.
Sometimes the speed doesn't matter, sometimes it does. It's not fun
to use a worse language only because a better one is too slow.
IMHO most C and assembler programmers care too much about execution
speed. Here I see the opposite.
Maybe it's simply not possible to compile Haskell more efficiently?
--
__("Marcin Kowalczyk * [EMAIL PROTECTED] http://kki.net.pl/qrczak/
\__/ GCS/M d- s+:-- a22 C++$ UL++$ P+++ L++$ E-
^^W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP-+ t
QRCZAK 5? X- R tv-- b+++ DI D- G+ e h! r--%++ y-
Re: Cryptarithm solver - Haskell vs. C++
Marcin 'Qrczak' Kowalczyk wrote: [snip] Maybe it's simply not possible to compile Haskell more efficiently? Maybe not yet. But someday we'll have enough processing power to do really sophisticated whole-program analysis, including decent region analysis. A lot of the techniques have already been published, but are simply too expensive to do. But when computers are faster, C++ will have to watch out, as theoretically it is much harder to reason about. Also the GHC folk do not alas have huge numbers of people slaving away trying to shave 1% off execution time here and there, which makes a big difference.
Re: Cryptarithm solver - Haskell vs. C++
On 21 Sep 1999, Marcin 'Qrczak' Kowalczyk wrote: Sat, 18 Sep 1999 00:06:37 +0200 (MET DST), Juergen Pfitzenmaier [EMAIL PROTECTED] pisze: I dont't care very much how fast a program runs. I care about how long it takes me to write it. If you take a programming task of reasonable complexity you will finish *months* earlier using a --good-- functional language instead of C++. Use a functional language and buy a faster computer with the saved money/time. I have to care how fast my programs run. I like writing in Haskell very much, it's my favorite general-purpose language, but one of the biggest weak points of Haskell for me is poor efficiency (at least with ghc, I don't know how fast are other compilers). I wonder whether this is the issue of Haskell itself or the compilers, I wonder if I can expect things to go better in future. Hear, hear. Sometimes the problem that you're working on requires such a lot of computation (e.g., typical image processing stuff) that no savings from reduced writing time can by a machine fast enough to compensate for the slow-down. And if you're in research where you need to scrutinise the results of `prototypes' (this isn't quite the word because it implies that once you've produced it you've ironed out almost all the problems issues and are ready to build the `final system') to figure out why the algorithm isn't working on real data and how to improve it. I'm quite open to arguments that maybe you can't make a functional language that's as nice as Haskell (features like lazy evaluation, nice type classes, etc) that's also able to `really hammer until it's totally flat' functional code that implements heavily numerical algorithms. However I'd argue that this is still an area where a functional language which was standard, widely used and compilable into very very efficient code would be of great benefit to many people who work on simulation, image processing problems, control systems, etc. (So I'm happy for the Haskell people to say `We can't make computation intensive programming better because it'd screw up stuff we do well now' but not that `development time shrinkage compensates for run-time growth'.) I would be much more happy if Haskell could be compiled to a more efficient code. "Only 10 times slower than C" may be unacceptable. Sometimes the speed doesn't matter, sometimes it does. It's not fun to use a worse language only because a better one is too slow. The thing that's more annoying is that there seems to be no _standard_ ways of indicating that a certain small patch of the code is the metaphorical `inner loop' and that the compiler should try anything and everything, probably including exhaustive search of exponential search spaces, to generate good code for it. I know that you can twiddle the optimisation with pragmas in ghc files, but that's ad-hoc and doesn't really make the fanatically insane optimization steps that generating efficient computation-intensive code from declarative languages seems to demand. ___cheers,_dave__ email: [EMAIL PROTECTED] "He'd stay up all night inventing an www.cs.bris.ac.uk/~tweed/pi.htm alarm clock to ensure he woke early work tel: (0117) 954-5253 the next morning"-- Terry Pratchett
Re: Cryptarithm solver - Haskell vs. C++
On Tue, 21 Sep 1999, D. Tweed wrote: Sometimes the problem that you're working on requires such a lot of computation (e.g., typical image processing stuff) that no savings from reduced writing time can by a machine fast enough to compensate for the slow-down. I agree. The arguments "you are saving on development time by using _the_ language" or "buy better equipment instead" are quite old actually. I've heard them first time in relation to perceived slowness of Smalltalk. Nothing has changed over the years in this perception, even though computers have become faster and Smalltalk itself has been significantly improved speed-wise; the competing languages have simply taken the same advantage of hardware. Besides, our apetites grow up too and the problems to solve become much more complex than before. What used to be considered an acceptable limitation is not such anymore. The speed is a relative concept: comparing to what? If I compete against delivery time than it matters to me whether I will get my results in 6 versus 12 hours. Just 50% difference, but it counts when impatient client wants it done for "yesterday". And it counts even more if he comes with another bright idea of changing the input a bit and asks me to rerun it again and again. If I use a top of the line commercial software, which has no practical competion (say Ansys), then buying faster equipment obviously helps. But not if I have written my own staff, say in Haskell, which supposes to compete with similar programs written in C. Jan
Re: Cryptarithm solver - Haskell vs. C++
On 18-Sep-1999, Herbert Graeber [EMAIL PROTECTED] wrote: After following the discussion I am not sure if the comparison is fair: ... Second, the C++ algorithm presented uses a permutation generator from the C++ standard library. The times can only be compared, if both programs - the C++ version and the Haskell version - use the same algorithm. I think it is useful to compare the performance of idiomatic Haskell code (Haskell code written using the common idioms that Haskell programmers typically use) with idiomatic C++ code or idiomatic Mercury code. This particular benchmark is not a good choice, since seemingly inconsequential differences in algorithm can affect which order the search space is searched in, and can hence drastically affect the benchmark result. However, if we made the minor change of finding all solutions rather than finding the first solution, it would eliminate that problem. A fair comparison should include the best algorithm suitable for each language I don't think that's the only kind of fair comparison possible. I think comparing the easiest-to-implement or most idiomatic algorithm for each language may give useful insights. -- Fergus Henderson [EMAIL PROTECTED] | "I have always known that the pursuit WWW: http://www.cs.mu.oz.au/~fjh | of excellence is a lethal habit" PGP: finger [EMAIL PROTECTED]| -- the last words of T. S. Garp.
Re: Cryptarithm solver - Haskell vs. C++
Bart Demoen [EMAIL PROTECTED] wrote, Manuel M. T. Chakravarty wrote I get C++ (your program) : 0.31s Haskell (above prgm): 2.63s That's really besides the point - I have a Prolog program (no cheating !) that solves it in 80 ms with Yap (a Prolog interpreter) on a Linux Pentium 166MHz. Whether it is besides the point or not depends somewhat on where you perceive the point to be, I think. My point was to demonstrate to the original poster that by simply removing the _most_obvious_ glitches in his experiment, he arrives at a completely different result. Solving the generic problem is what you want to compete with C on. And feasability, not speed. My point was _neither_ to educate him in the glorious ways of good declarative programming nor in any details of fine tuning Haskell code. Bart Demoen [EMAIL PROTECTED] (in a second message) wrote, The problem with these small problems is that once written in a declarative way - even the generic cryptarithm solver - (be it Haskell, Mercury, Clean or Prolog) it is usually very easy to rewrite them in C(++) and get better speed. Actually, the best way to get the fastest program to solve any given cryptarithm solver, would probably be to write a compiler from cryptarithm problems to C - writing that compiler would be a piece of cake in a declarative language and a can of worms in C(++). With all due respect, I think it is exactly this attitude, which often keeps experienced programmers from trying "declarative languages". I think, we are better off focusing on the problems that people asking us to solve instead of telling them that if they would solve a different (or more general) problem everything would be different anyway. In other words, the goal should be to get reasonable performance and clarity of code on problems which are also easy to solve in imperative languages, and then, to excel on the difficult problems. Otherwise, people might not listen long enough to ever try a declarative language on a non-trivial problem. Speed is not the only issue - feasability is an issue as well. I completely agree, but the original poster did not complain about a slight discrepancy in speed, he was puzzled about an unacceptable large gap of several orders of magnitude. Speed is not the only issue, but it definitely is _an_ issue. Cheers, Manuel
Re: Cryptarithm solver - Haskell vs. C++
Mark Engelberg [EMAIL PROTECTED] wrote on 17 Sep 1999 I decided to test out Haskell by writing a program to solve a cryptarithm [..] The algorithm is pretty straightforward - you just need to consider all possible mappings of letters to digits, and test the equation ... [..] -- import List expand a b c d e f = f + e*10 + d*100 + c*1000 + b*1 + a*10 xs = [0,1..9] -- all the digits answer = head [ [t,h,i,r,y,w,e,l,v,n] | t-xs, e-xs\\[t], h-xs\\[t,e], i-xs\\[t,e,h], [..] There followed the C++ program to compare with the Haskell one, that calls the next_permutation library function. Then, people wrote much on possible Haskell program modification and measurements. First who declared the in-correctness of such comparison was Herbert Graeber [EMAIL PROTECTED]. He wrote [..] Second, the C++ algorithm presented uses a permutation generator from the C++ standard library. The times can only be compared, if both programs - the C++ version and the Haskell version - use the same algorithm. It is easy to speed up the Haskell version simply by using a permutation generator, that starts with the solution. In general even this may be not sufficient, because imperative and pure functional lazy evaluation of the same algorithm may give very different results. A fair comparison should include the best algorithm suitable for each language and much more different inputs for the programs, including very large ones. This is the very point. If this next_permutation, - who's algorithm is not known to us, - starts occasionally right with the needed permutation, then the whole program `answer' may run in C++, say, 0.001 sec. Another example: replacing in the initial program xs = [0..9] with reverse [0..9] may change the time many times - for the same reason. If, studying the algorithm for next_permutation we discover that there exists a good Haskell analog, - which also generates the permutation in the same order, - then with this analog, we could really compare the performance. Otherwise, more subtle reasoning and list of examples are required. Still, i also tried to program this thing: the program is enclosed. Again, changing [0..9] to reverse [0..9] speeds up the program 3 times, but this is only the specific of the given equation and the used permutation generator. `++' takes here 10 steps to evaluate. But it does not effect the performace any essentially - this can be tested easily. Compilation: ghc-4.04 -c -O2 -O2-for-C ... -- Sergey Mechveliani [EMAIL PROTECTED] --- main = putStr $ shows answer "\n" expand a b c d e f = f + e*10 + d*100 + c*1000 + b*1 + a*10 :: Int answer = find (\ [t,h,i,r,y,w,e,l,v,n] - expand t h i r t y + 5 * expand t w e l v e == expand n i n e t y ) $ permutations $ [0..9] permutations :: [Int] - [[Int]] permutations[] = [[]] permutations(j:js) = addOne $ permutations js where addOne [] = [] addOne (ks:pms) = (ao ks)++(addOne pms) ao [] = [[j]] ao (k:ks) = (j:k:ks):(map (k:) $ ao ks)
Re: Cryptarithm solver - Haskell vs. C++
On 17-Sep-1999, Lennart Augustsson [EMAIL PROTECTED] wrote:
Mark Engelberg wrote:
This is a huge difference, and makes Haskell look incredibly slow by
comparison. The speed difference in this case is well worth the extra few
lines of code.
Well, Hugs is an interpreter. Comparing interpreted Haskell with compiled
C++ isn't really fair. Try compiling yout program with a Haskell compiler,
e.g. hbc or ghc.
Well, I tried with ghc 2.08 -- admittedly an ancient version, so
this is not a fair comparison, but that was what I had on hand.
On a 300 MHz DEC Alpha system, I got the following times:
LanguageCompiler versionOptions Time
Haskell ghc 2.08-O 21.5 seconds
Mercury rotd-1999-09-17 -O6 7.5 seconds
Mercury rotd-1999-09-17 -O6 --gc none2.2 seconds
C++ egcs-1.1.2 -O3 .2 seconds
Hmm... a ratio of about 100:10:1 for Haskell:Mercury:C++ is, well,
interesting ;-).
I wonder how much better ghc 4.x does?
Cheers,
Fergus.
P.S.
Here's my Mercury code.
:- module solve_it.
:- interface.
:- import_module io.
:- pred main(io__state::di, io__state::uo) is cc_multi.
:- implementation.
:- import_module list, int.
main -- (if { answer(Answer) } then print(Answer) else print("no")), nl.
expand(A,B,C,D,E,F) = F + E*10 + D*100 + C*1000 + B*1 + A*10.
answer(Answer) :-
permute([0,1,2,3,4,5,6,7,8,9], Answer),
Answer = [T,H,I,R,Y,W,E,L,V,N],
expand(T,H,I,R,T,Y) + 5 * expand(T,W,E,L,V,E) = expand(N,I,N,E,T,Y).
permute([], []).
permute([X|Y], [U|V]) :- del(U, [X|Y], Z), permute(Z, V).
del(A, [A|L], L).
del(X, [A|Z], [A|R]) :- del(X, Z, R).
--
Fergus Henderson [EMAIL PROTECTED] | "I have always known that the pursuit
WWW: http://www.cs.mu.oz.au/~fjh | of excellence is a lethal habit"
PGP: finger [EMAIL PROTECTED]| -- the last words of T. S. Garp.
Re: Cryptarithm solver - Haskell vs. C++
On Fri 17 Sep, Fergus Henderson wrote: On a 300 MHz DEC Alpha system, I got the following times: LanguageCompiler version Options Time Haskell ghc 2.08 -O 21.5 seconds Mercury rotd-1999-09-17 -O67.5 seconds Mercury rotd-1999-09-17 -O6 --gc none 2.2 seconds C++ egcs-1.1.2 -O3 .2 seconds The code below takes about 5 seconds to print [1,9,4,2,5,3,0,7,6,8] using Clean on 233 MHz (I think) G3 PowerMac. This is the closest Clean equivalent to Marks original I could produce. I suspect it has an advantage over the ghc version by providing greater scope for optimisation (because it's all in 1 module). module Main import StdEnv Start = hd [ [t,h,i,r,y,w,e,l,v,n] \\ t-xs, e-xs--[t], h-xs--[t,e], i-xs--[t,e,h] , r-xs--[t,e,h,i], y-xs--[t,e,h,i,r], w-xs--[t,e,h,i,r,y] , l-xs--[t,e,h,i,r,y,w], v-xs--[t,e,h,i,r,y,w,l] , n-xs--[t,e,h,i,r,y,w,l,v] | expand t h i r t y + 5 * expand t w e l v e == expand n i n e t y ] expand a b c d e f = f + e*10 + d*100 + c*1000 + b*1 + a*10 xs = [0,1..9] // all the digits (--) infix 5 (--) xs [] = xs (--) xs [y:ys] = del y xs -- ys del x [] = [] del x [y:ys] = if (x == y) ys [y : del x ys] P.S. Clean [x:xs] = Haskell (x:xs) Regards -- Adrian Hey
Re: Cryptarithm solver - Haskell vs. C++
Oops, I forgot to include the time with optimization: no optopt hbc0.761u0.663u cc 1.055u0.167u -- -- Lennart
Re: Cryptarithm solver - Haskell vs. C++
"Mark Engelberg" [EMAIL PROTECTED] wrote, After reading about the stellar performance of the Haskell entries in the ICFP contest, I started reading the Haskell documentation to learn more about the language. My knowledge of functional programming languages primarily comes from Scheme. [...] This seems like a perfect opportunity to exploit Haskell's list generation and lazy evaluation capabilities. The crux of the problem is to find a concise way of describing the list of all permutations of digits. I don't want to embarrass myself by posting my first attempt here, but I'll show you my second, slightly-less naive approach to writing this program: [Haskell program deleted] Impressively concise, but how does it run? Well, I loaded it into the HUGS interpreter; typed answer, and after a couple minutes, the answer printed out. Not too bad, but how would this compare to a solution in C++? [C++ program deleted] It's a little longer, but not unreasonably so. How does it run? Well, running it inside the debugger, it generated the correct answer within a couple of seconds. This is a huge difference, and makes Haskell look incredibly slow by comparison. The speed difference in this case is well worth the extra few lines of code. After modifying you program a bit: import List expand a b c d e f = f + e*10 + d*100 + c*1000 + b*1 + a*10 xs :: [Int] xs = [0,1..9] -- all the digits answer = head [ [t,h,i,r,y,w,e,l,v,n] | t-xs, let es = delete t xs, e-es, let hs = delete e es, h-hs, let is = delete h hs, i-is, let rs = delete i is, r-rs, let ys = delete r rs, y-ys, let ws = delete y ys, w-ws, let ls = delete w ws, l-ls, let vs = delete l ls, v-vs, let ns = delete v vs, n-ns, expand t h i r t y + 5 * expand t w e l v e == expand n i n e t y] I get C++ (your program) : 0.31s Haskell (above prgm): 2.63s (This was on a 300MHz Celeron running Linux. C++ compiled with egcs-1.1.2 and -O3.) Still slower, but not too bad (given that C++ probably uses inplace array manipulations). So, why the difference to your results: * I used a Haskell _compiler_, not the Hugs interpreter (I used GHC 4.04pl1 and compiled with -O2). * I added a type annotation to the definition of `xs' - Haskell uses overloading on numerals and in your case conservatively assumed that you want to calculate with _arbitrary_precision_ integer arithmetic. * I moved redundant computations out of the inner `loops'. The farther a generator to the right, the further inside a set of nested `loops' (actually recursions) it is. For example, your `n-xs\\[t,e,h,i,r,y,w,l,v]' generator strips `t', `e', `h', `i', `r', `y', `w', and `l' from the list although this was already done in the enclosing generator (the one to its left). If you get to know Haskell a little, the above are fairly straight forward optimisations (ie, nothing surprising). Cheers, Manuel
Re: Cryptarithm solver - Haskell vs. C++
Manuel M. T. Chakravarty wrote I get C++ (your program) : 0.31s Haskell (above prgm): 2.63s That's really besides the point - I have a Prolog program (no cheating !) that solves it in 80 ms with Yap (a Prolog interpreter) on a Linux Pentium 166MHz. Solving the generic problem is what you want to compete with C on. And feasability, not speed. Cheers Bart Demoen
Re: Cryptarithm solver - Haskell vs. C++
So I did a test run too, on a 450MHz Pentuim II running NetBSD. I used Manuel's Haskell code, but I added a type signature for the expand function, and the original C++ code. dogbert% cc c.cc -o c.out -lstdc++ dogbert% time c.out 1942530768 1.043u 0.010s 0:01.05 100.0%0+0k 0+1io 0pf+0w dogbert% hbc h3.hs dogbert% time a.out [1,9,4,2,5,3,0,7,6,8] 0.761u 0.040s 0:00.80 100.0%0+0k 0+0io 0pf+0w dogbert% So if you compile naively with no optimization the Haskell code is actually FASTER than the C++ code. -- -- Lennart
Re: Cryptarithm solver - Haskell vs. C++
After following the discussion I am not sure if the comparison is fair: First, maybe the times measured may include some additional times that are not directly related to the problem solved. For example the initialization of the RTS. Second, the C++ algorithm presented uses a permutation generator from the C++ standard library. The times can only be compared, if both programs - the C++ version and the Haskell version - use the same algorithm. It is easy to speed up the Haskell version simply by using a permutation generator, that starts with the solution. In general even this may be not sufficient, because imperative and pure functional lazy evaluation of the same algorithm may give very different results. A fair comparison should include the best algorithm suitable for each language and much more different inputs for the programs, including very large ones. Herbert Graeber
Re: Cryptarithm solver - Haskell vs. C++
Mark Engelberg wrote: This is a huge difference, and makes Haskell look incredibly slow by comparison. The speed difference in this case is well worth the extra few lines of code. Well, Hugs is an interpreter. Comparing interpreted Haskell with compiled C++ isn't really fair. Try compiling yout program with a Haskell compiler, e.g. hbc or ghc. -- -- Lennart
