Prestandaproblem i Haskell

Jag håller just nu på att lära mig Haskell.

Jag har skrivit en funktion i Haskell för att jämföra strängar approximativt. Information om algoritmen finns på:
http://www.csam.iit.edu/~cs535/dymamic_p3.pdf

--K-approximate string matching
--
--takes two strings and return the minimum number
--of changes needed to make the strings equal
--http://www.csam.iit.edu/~cs535/dymamic_p3.pdf

kCompare    ::  String -> String -> Int

--Boundary conditions
kCompare []      s      =   length s 
kCompare s       []     =   length s
--Recursive case
kCompare (x:xs) (y:ys)  =   min3 ((kCompare xs (y:ys))  + 1)        --Remove one character from x
                                 ((kCompare (x:xs) ys)  + 1)        --Remove one character from y
                                 ((kCompare xs ys)      + equal)    --Change a character (if needed)
                                 where
                                    equal       = if x == y then 0
                                                            else 1
                                    min3 a b c  = min a (min b c)

Men prestandan är extremt dålig. När den körs på strängar med en längd av 17 bokstäver, klarar den inte att producera ett svar på 20 minuter, medans samma funktion i C++ klarar strängar med 1000 bokstäver på en sekund.
Tiden för funtionen är O(nm) där n och m är strängarnas längd. Haskell-funktionen funkar bra för strängar mindre än tio bokstäver.

Haskells syntax är mycket tilltalande, men om det ska vara så här svårt att få ut prestanda så känns det ganska meningslöst att skriva program i Haskell.

Jag är som sagt nybörjare i Haskell och har kanske inte tänkt på någonting, så jag tar gärna emot synpunkter på hur jag ska kunna förbättra min kod.

Haskell är klart segare. Inte minst med tanke på att det handlar om en tolk och inte färdig maskinkod. Men så mycket som 20 minuter tyder på ett gravt fel. Kan det vara den s.k lata evalueringen som gör att din trippla rekursion inte fungerar som du tänkt? Vad kör du i för miljö? Hugs eller nåt annat?

Jag använder GHC som kompilerar till maskinkod. Jag har även nu testat med full optimering påslaget och visserligen märkt en skillnad, men inte av det slaget att det förändrar någonting.

PeW, hur gör jag för att funktionens parametrar ska vara 'strict' jag har för mig att man kan göra något i stil med

f !x !y = ...

men det verkar inte fungera med patterns. Jag får väl göra nån form av wrapper till kCompare.

Men om man hackar för mycket i koden för att den ska gå snabbare, försvinner lite av vitsen men att använda Haskell - den extremt lättöverskådliga koden.

Tilläggas bör kanske att min C++-variant är ganska optimerad, men sådan här enorm skillnad gör att min nyvunna Haskell-entusiasm har mattats något.

Sang-drax skrev:

jag har för mig att man kan göra något i stil med

Det var inte så, utan det var funktionen 'seq' som skulle användas. Detta gav dock inget resultat.

Tja.. jag har inte testat GHC. I den enda kurs jag gått i funktionell programmering använde vi Haskell men i tolkmiljö och då Hugs98. Kan dock erinra mig om att professorn som höll i kursen medgav att vitsen med Haskell är inte att kompilera ned det i maskinkod utan att köra det i en tolk. För om man gör koden statisk förlorar man mycket godis som lazy evaluation.. vidare är såvitt jag förstod GHC långtifrån färdigutvecklat. Så en kodsnutt som rinner på fint i tolken kanske blir rena mardrömmen i GHC. Så tolkade ivf jag det hela. Haskell är annars ett tjusigt språk om man pillar med grammatiker (programspråk t.ex) och matematiska uttryck :)

Ett annat liknande språk som sägs vara enklare att koda i är Lisp. Inte mitt område, men det kanske finns mer utvecklade kompilatorer till Lisp än Haskell?

En av mina kurskamrater på funktionellkursen pratade om att det finns utvecklat bibliotek för VC++ som ger att man kan koda "funktionellt" med C++ (kommer dock inte ihåg vad det hette, men google vet säkert). Huruvida det är intressant för dig eller inte vet jag inte, men det kan ju kanske vara ett tips om man vill åstakomma bättre prestanda men behålla det funktionella 'språket'.

PeW skrev:

För om man gör koden statisk förlorar man mycket godis som lazy evaluation.. vidare är såvitt jag förstod GHC långtifrån färdigutvecklat.

Det stämmer inte att man förlorar features genom att kompilera till maskinkod.

GHC räknas som stable och i dokumentationen står det följande:

Please report any overly-slow GHC-compiled programs. Since GHC doesn't have any credible competition in the performance department these days it's hard to say what overly-slow means, so just use your judgement! Of course, if a GHC compiled program runs slower than the same program compiled with NHC or Hugs, then it's definitely a bug.

Trots detta ska testa med lite andra kompilatorer i morgon, och se om profiling kanske kan ge någonting.

Okej... det bör ju ändå bli en hel del overhead mot vanlig C++ implementation. Vore intressant om du rapporterade vidare hit sen om hur du löste problemet.

Ja, om jag lyckas lösa det vill säga :)

EDIT:
Jag inser nu att jag har tänkt fel när jag skrev koden. Koden i Haskell är inte alls O(nm) som i C++, utan mycket, mycket värre. Jag nöjde mig helt enkelt med att försöka konvertera koden och kontrollera ifall den gav korrekt resultat och sedan gnälla på prestandan.
Det är fortfarande inget fel på koden rent funktionsmässigt, det är bara det att den tar mycket längre tid.
Nu återstår bara att försöka tillhandahålla en korrekt variant.