Ist die Performance von partiellen oder Curry-Funktionen in Haskell gut definiert?

Question

Im folgenden Code:

ismaxl :: (Ord a) => [a] -> a -> Bool 
ismaxl l x = x == maxel 
      where maxel = maximum l 

main = do 
    let mylist = [1, 2, 3, 5] 
    let ismax = ismaxl mylist 
    --Is each call O(1)? Does each call remember maxel? 
    let c1 = ismax 1 
    let c2 = ismax 2 
    let c3 = ismax 3 
    let c5 = ismax 5 
    putStrLn (show [c1, c2, c3, c5]) 

Ist die Teilfunktion ismax, die maxel berechnen? Konkret kann jemand auf eine Regel über die Komplexität von Teilfunktionen in Haskell hinweisen? MUSS der Compiler im obigen Beispiel nur einmal aufrufen? Anders ausgedrückt, behält eine partielle Funktion die Referenzen früherer Aufrufe für interne where-Klauseln bei?

Ich habe einige CPU-gebundenen Code, der nicht akzeptabel funktioniert, und ich suche nach möglichen Fehlern in meiner Argumentation über die Komplexität.

Answer 1

Als Demonstration dessen, was Sie von der Profilerstellung Ihres Haskell-Codes lernen können, haben wir hier einige kleinere Änderungen an Ihrem Code vorgenommen. Zuerst habe ich mylist durch [0..10000000] ersetzt, um sicherzustellen, dass es eine Weile dauert, das Maximum zu berechnen.

Hier einige Zeilen aus dem Profilausgang, nachdem diese Version ausgeführt wird:

COST CENTRE     MODULE    %time %alloc 

ismaxl       Main     55.8 0.0 
main       Main     44.2 100.0 

                 individual inherited 
COST CENTRE    MODULE   no. entries %time %alloc %time %alloc 

MAIN      MAIN   1   0 0.0 0.0 100.0 100.0 
CAF:main_c5    Main   225   1 0.0 0.0 15.6 0.0 
    main     Main   249   0 0.0 0.0 15.6 0.0 
    ismaxl    Main   250   1 15.6 0.0 15.6 0.0 
CAF:main_c3    Main   224   1 0.0 0.0 15.6 0.0 
    main     Main   246   0 0.0 0.0 15.6 0.0 
    ismaxl    Main   247   1 15.6 0.0 15.6 0.0 
CAF:main_c2    Main   223   1 0.0 0.0 14.3 0.0 
    main     Main   243   0 0.0 0.0 14.3 0.0 
    ismaxl    Main   244   1 14.3 0.0 14.3 0.0 
CAF:main_c1    Main   222   1 0.0 0.0 10.4 0.0 
    main     Main   239   0 0.0 0.0 10.4 0.0 
    ismaxl    Main   240   1 10.4 0.0 10.4 0.0 
CAF:main8    Main   221   1 0.0 0.0 44.2 100.0 
    main     Main   241   0 44.2 100.0 44.2 100.0 

Es ist ziemlich offensichtlich hier die maximale recomputing.

Nun ersetzt ismaxl mit diesem:

ismaxl :: (Ord a) => [a] -> a -> Bool 
ismaxl l = let maxel = maximum l in (== maxel) 

... und Profilierung wieder:

COST CENTRE     MODULE    %time %alloc 

main       Main     60.5 100.0 
ismaxl       Main     39.5 0.0 

                 individual inherited 
COST CENTRE    MODULE   no. entries %time %alloc %time %alloc 

MAIN      MAIN   1   0 0.0 0.0 100.0 100.0 
CAF:main_c5    Main   227   1 0.0 0.0  0.0 0.0 
    main     Main   252   0 0.0 0.0  0.0 0.0 
    ismaxl    Main   253   1 0.0 0.0  0.0 0.0 
CAF:main_c3    Main   226   1 0.0 0.0  0.0 0.0 
    main     Main   249   0 0.0 0.0  0.0 0.0 
    ismaxl    Main   250   1 0.0 0.0  0.0 0.0 
CAF:main_c2    Main   225   1 0.0 0.0  0.0 0.0 
    main     Main   246   0 0.0 0.0  0.0 0.0 
    ismaxl    Main   247   1 0.0 0.0  0.0 0.0 
CAF:main_c1    Main   224   1 0.0 0.0  0.0 0.0 
CAF:main_ismax   Main   223   1 0.0 0.0 39.5 0.0 
    main     Main   242   0 0.0 0.0 39.5 0.0 
    ismaxl    Main   243   2 39.5 0.0 39.5 0.0 
CAF:main8    Main   222   1 0.0 0.0 60.5 100.0 
    main     Main   244   0 60.5 100.0 60.5 100.0 

... dieses Mal ist es die meiste Zeit in einem einzigen Aufruf ismaxl verbringt, die anderen sind zu schnell, um es zu bemerken, daher muss das Maximum hier nur einmal berechnet werden.

Answer 2

Ich konnte keine solche Anforderung in der finden, und in der Tat scheint GHC diese Optimierung standardmäßig nicht durchzuführen.

Ich änderte Ihre main Funktion

main = do 
    let mylist = [1..99999] 
    let ismax = ismaxl mylist 
    let c1 = ismax 1 
    let c2 = ismax 2 
    let c3 = ismax 3 
    let c5 = ismax 5 
    putStrLn (show [c1, c2, c3, c5]) 

Einfache Profilierung zeigt (auf meinem alten Pentium 4):

$ ghc a.hs 
$ time ./a.out 
[False,False,False,False] 

real 0m0.313s 
user 0m0.220s 
sys  0m0.044s 

Aber wenn ich ändern, um die Definition von c2, c3 und c5-let c2 = 2 == 99999 etc (c1 wie es ist), bekomme ich

$ ghc a.hs 
$ time ./a.out 
[False,False,False,False] 

real 0m0.113s 
user 0m0.060s 
sys  0m0.028s 

Answer 3

Hier ist eine modifizierte Version des Codes, die Ihnen erlauben, um zu sehen, ob oder nicht maxel wiederverwendet wird:

import Debug.Trace 

ismaxl :: (Ord a) => [a] -> a -> Bool 
ismaxl l x = x == maxel 
      where maxel = trace "Hello" $ maximum l 

main = do 
    let mylist = [1, 2, 3, 5] 
    let ismax = ismaxl mylist 
    --Is each call O(1)? Does each call remember maxel? 
    let c1 = ismax 1 
    let c2 = ismax 2 
    let c3 = ismax 3 
    let c5 = ismax 5 
    putStrLn (show [c1, c2, c3, c5]) 

Sie werden sehen, dass maxel nicht zwischen den Anwendungen ‚erinnert‘.

Im Allgemeinen sollten Sie nicht erwarten, dass Haskell Reduzierungen vornimmt, bis alle der Argumente einer Funktion übergeben wurden.

Auf der anderen Seite, wenn Sie aggressive Optimierung eingeschaltet haben, dann ist es schwer vorherzusagen, was ein bestimmter Compiler tatsächlich tun würde. Aber Sie sollten sich wahrscheinlich nicht auf irgendeinen Teil des Compilers verlassen, der schwer vorherzusagen ist, wenn Sie den Code einfach neu schreiben können, um das zu machen, was Sie explizit wollen.

Answer 4

Aufbauend auf andere gute Antworten, hat GHC diese Art der Optimierung meiner Erfahrung nach nicht gerne durchgeführt. Wenn ich nicht so leicht etwas Punkt frei machen, habe ich Zuflucht oft mit einer Mischung aus gebundenem Vars auf der LHS und ein Lambda zu schreiben:

ismaxl :: (Ord a) => [a] -> a -> Bool 
ismaxl l = \x -> x == maxel 
      where maxel = maximum l 

ich nicht besonders mag diesen Stil, aber es stellt sicher, dass maxel zwischen Aufrufen zu einem teilweise angewandten ismaxl geteilt wird.