Who thinks Ocaml or C++ can beat Felix on this one? /* reduce mapmap (x:list[int], f1:int->int, f2:int->int) : map f1 (map f2 x) => map (f1 \circ f2) x ; */
fun add (a:int) (b:int) => a + b; fun sum(x:list[int]) => fold_left add 0 x; var x1 = range 1000000; println$ sum x1; var x3 = map (add 1) (map (add 1) x1); println$ sum x3; ~/felix>flx -c --static --test=build/release rl ; time ./rl 1783293664 1785293664 real 0m5.839s user 0m5.719s sys 0m0.092s Remove the comment to enable the reduction: (note debug print proving the reduction "took"): ~/felix>flx -c --static --test=build/release rl ; time ./rl REDUCTION: FOUND A MATCH, candidate ((map<10487>[int, int] (add<42872> literal[int](1))) ((map<10487>[int, int] (add<42872> literal[int](1))) x1<42881>)) with reduced LHS ((map<10487>[int, int] index_42870<42870>) ((map<10487>[int, int] index_42871<42871>) index_42869<42869>)) 1783293664 1785293664 real 0m3.555s user 0m3.476s sys 0m0.067s [You need the latest Felix] BTW: if you factor the code like this: val x2 = map (add 1) x1; val x3 = map (add 1) x2; The reduction isn't applied. I'm not sure why! My guess: the first pass, it doesn't apply because the pattern doesn't match. Now, if, by lazy evaluation we replace x2 with its initialiser, the pattern WILL match. But the reduction isn't applied. So I guess the optimiser is ALSO inlining the map function "at the same time" as doing the substitution, which of course eliminates the pattern we're looking for. This isn't a bug! There's no known "best order" to apply various optimisations. Reductions are extremely expensive, so the check isn't made after every optimisation. [They're expensive because every subexpression in the whole program has to be compared with every reduction pattern. Even a single comparison is expensive: you're comparing AST trees, and not for equality but specialisation.] -- john skaller skal...@users.sourceforge.net http://felix-lang.org ------------------------------------------------------------------------------ Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_d2d_feb _______________________________________________ Felix-language mailing list Felix-language@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/felix-language
