haskell - Why would eta expansion degrade the performance of fib? -


i read this article says eta expansion degrade performance of fib, code below, fib1 faster other implementations. explains in slower versions, fib' redefined every argument x. don't it. give more detailed explanation? 

import system.environment import control.monad  main =     (mode:num:_) <- liftm (map read) getargs     case mode of       1 -> print $ fib1 num       2 -> print $ fib2 num       3 -> print $ fib3 num       4 -> print $ fib4 num  fib1 :: int->integer fib1 = (map fib' [0..] !!)   fib' 0 = 1         fib' 1 = 1         fib' n = fib1 (n-1) + fib1 (n-2) fib2 :: int->integer fib2 x = map fib' [0..] !! x   fib' 0 = 1         fib' 1 = 1         fib' n = fib2 (n-1) + fib2 (n-2) fib3 :: int->integer fib3 = (map fib' [0..] !!)   fib' 0 = 1         fib' 1 = 1         fib' n = fib' (n-1) + fib' (n-2) fib4 :: int->integer fib4 x = map fib' [0..] !! x   fib' 0 = 1         fib' 1 = 1         fib' n = fib' (n-1) + fib' (n-2)

i tested code above.

compiled ghc --make fib.hs, fib1 faster others. compile ghc -o2 fib.hs, fib1 , fib2 of same performance, while fib3 , fib4 slower.

it seems -o2 flag, fib2 further optimized, tested ghc --make fib.hs -ddump-simpl see going on, , generated code 2 functions below

rec { fib1 [occ=loopbreaker] :: int -> integer [gblid, str=dmdtype] fib1 =   !!     @ integer     (map        @ int        @ integer        (\ (ds_d10b :: int) ->           case ds_d10b of wild_x6 { ghc.types.i# ds1_d10c ->           case ds1_d10c of _ [occ=dead] {             __default ->               + @ integer                 ghc.num.$fnuminteger                 (fib1 (- @ int ghc.num.$fnumint wild_x6 (ghc.types.i# 1)))                 (fib1 (- @ int ghc.num.$fnumint wild_x6 (ghc.types.i# 2)));             0 -> __integer 1;             1 -> __integer 1           }           })        (enumfrom @ int ghc.enum.$fenumint (ghc.types.i# 0))) end rec }  rec { fib2 [occ=loopbreaker] :: int -> integer [gblid, arity=1, str=dmdtype] fib2 =   \ (x_ay6 :: int) ->     !!       @ integer       (map          @ int          @ integer          (\ (ds_d10x :: int) ->             case ds_d10x of wild_x8 { ghc.types.i# ds1_d10y ->             case ds1_d10y of _ [occ=dead] {               __default ->                 + @ integer                   ghc.num.$fnuminteger                   (fib2 (- @ int ghc.num.$fnumint wild_x8 (ghc.types.i# 1)))                   (fib2 (- @ int ghc.num.$fnumint wild_x8 (ghc.types.i# 2)));               0 -> __integer 1;               1 -> __integer 1             }             })          (enumfrom @ int ghc.enum.$fenumint (ghc.types.i# 0)))       x_ay6 end rec }

after read code ghc -make -ddump-simpl fib.hs generated, write 2 new function test it. compiled ghc --make fib.hs, fib5 still faster fib6, think these 2 functions make easier analyze.

fib5 :: int->integer fib5 = (!!)          (map (\n->                 case n of                    0 -> 1                   1 -> 1                   _ -> fib5 (n-1) + fib5 (n-2))              [0..]) fib6 :: int->integer fib6 = \x->         (!!) (map (\n->                 case n of                    0 -> 1                   1 -> 1                   _ -> fib6 (n-1) + fib6 (n-2))               [0..])               x

looking @ linked article, seems it's difference between

fibs = let fibs' = ... in (\ x -> map fibs [0..] !! x)

verses

fibs = \ x -> let fibs' = ... in map fibs [0..] !! x

as can see, in first version fibs' global constant never changes, , you're indexing that. in second version, fibs function constructs "new", different fibs' every value of x. , that's performance difference.


Comments

Post a Comment

Popular posts from this blog

php - failed to open stream: HTTP request failed! HTTP/1.0 400 Bad Request -

this code i'm using find latitude , longitude of place: function coords($address){ echo $url="http://maps.googleapis.com/maps/api/geocode/json?address=".$address; $json = file_get_contents(urlencode($url)); $data = json_decode($json, true); print_r($data['results'][0]['geometry']['location']['lat']); print_r($data['results'][0]['geometry']['location']['lng']); } however returns warning: failed open stream: http request failed! http/1.0 400 bad request if use above code in simple procedure works fine not in function. note: have tried curl_init()... method produced same result? instead of encoding whole url encode address part. following code work fine $add='jamshoro phase 2'; $url="http://maps.googleapis.com/maps/api/geocode/json?address=".urlencode($add); $json = file_get_contents($url); $data = json_decode($json, true); print_r($data['r
Read more

java - How to filter a backspace keyboard input -

i have code gives message when key number pressed: txtvalueofclause.addeventfilter(keyevent.key_typed, new eventhandler<keyevent>() { @override public void handle(keyevent t) { char ar[] = t.getcharacter().tochararray(); char ch = ar[t.getcharacter().tochararray().length - 1]; if (!(ch >= '0' && ch <= '9')) { system.out.println("the char entered not number"); t.consume(); } } }); now if press on wrong button , press backspace remove it, error message. how can add backspace input if statement? i have found answer: txtvalueofclause.addeventfilter(keyevent.key_typed, new eventhandler<keyevent>() { @override public void handle(keyevent t) { char ar[] = t.getcharacter().tochararray(); char ch = ar[t.getcharacter().tochar
Read more

java - Show Soft Keyboard when EditText Appears -

i have code in android app, alert dialog , keyboard, , when dialog shown want keyboard appear. not , not sure why? here code: final alertdialog.builder alert = new alertdialog.builder(this); alert.settitle("title"); alert.setmessage("message"); final edittext input = new edittext(this); input.setinputtype(inputtype.type_class_number); alert.setview(input); input.setonfocuschangelistener(new view.onfocuschangelistener() { @override public void onfocuschange(view v, boolean hasfocus) { if (hasfocus) { log.i(tag, "in focus"); inputmethodmanager inputmethodmanager = (inputmethodmanager) getsystemservice(context.input_method_service); inputmethodmanager.showsoftinput(input, inputmethodmanager.show_implicit); } } }); but keyboard not appear though edit text in focus, , tell appear why, doesn't come up? thanks in advance.
Read more