Opened 8 years ago

Last modified 20 months ago

#888 new task

Implement the static argument transformation

Reported by: simonpj Owned by:
Priority: normal Milestone: 7.6.2
Component: Compiler Version: 6.4.2
Keywords: Cc: Bulat.Ziganshin@…, johan.tibell@…, hackage.haskell.org@…, reiner.pope@…, Jake.McArthur@…, choener@…, dterei
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty: Unknown
Test Case: N/A Blocked By:
Blocking: Related Tickets:

Description

The Static Argument transformation optimises

  f x y = ....f x' y...

into

  f x y = let g x = ....g x'...
          in g x

Instead of passing y along unchanged, we make it into a free variable of a local function definition g.

Unfortunately, it's not always a win. Andre Santos gives a discussion, and quite a few numbers in his thesis.

But sometimes it is a pretty big win. Here's the example that recently motivated me, which Roman Leshchinskiy showed me. You need the attached file Stream.hs, and then try compiling

  import Stream
  foo :: (a -> b) -> [a] -> [c]
  foo f = mapL f

Thus inspired, I think I have a set of criteria that would make the static arg transformation into a guaranteed win:

  • there is only one (external) call to the function
  • OR its RHS is small enough to inline
  • OR it is marked INLINE (?)

So I'd like to try this idea out.

Attachments (1)

Stream.hs (3.9 KB) - added by simonpj 8 years ago.
Stream example

Download all attachments as: .zip

Change History (23)

Changed 8 years ago by simonpj

Stream example

comment:1 Changed 8 years ago by igloo

  • Milestone set to 6.8
  • Test Case set to N/A

comment:2 Changed 7 years ago by simonpj

Here's another exampe, transferred from #1094 (Azmo):

The current version of Data.List.foldl' is:

foldl'           :: (a -> b -> a) -> a -> [b] -> a
foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

which for some reason is faster if removing the first parameter, e.g:

foldl2'           :: (a -> b -> a) -> a -> [b] -> a
foldl2' f = loop
  where loop a []     = a
        loop a (x:xs) = let a' = f a x in a' `seq` loop a' xs

----

Testing speed difference:

module Main (main) where

import System (getArgs)

sumFoldl' :: Int -> Int
sumFoldl' n = foldl' (+) 0 [1..n]

sumFoldl2' :: Int -> Int
sumFoldl2' n = foldl2' (+) 0 [1..n]

-- copy of Data.List.foldl'
foldl'           :: (a -> b -> a) -> a -> [b] -> a
foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

-- altered version of foldl'
foldl2'           :: (a -> b -> a) -> a -> [b] -> a
foldl2' f = loop
  where loop a []     = a
        loop a (x:xs) = let a' = f a x in a' `seq` loop a' xs

main = do
  [v,n] <- getArgs
  case v of
    "1" -> print (sumFoldl' (read n))
    "2" -> print (sumFoldl2' (read n))

I have no idea how the optimization of loops is done, but the request is
that this kind of loop rewriting should be done by the compiler, not by
the user (to get a faster loop).
It seems to just be a matter of finding and removing constants
(identifiers just passed along).

comment:3 Changed 7 years ago by guest

  • Cc Bulat.Ziganshin@… added

comment:4 Changed 6 years ago by simonpj

  • Milestone changed from 6.8 branch to 6.10 branch

Not for 6.8, but I'll keep it on the table for 6.10. A nice self-contained project for someone!

Simon

comment:5 Changed 6 years ago by batterseapower

The SAT patch currently in the compiler does get "foldl'", but not "foo". I'm not sure what you were expecting to happen with "foo": only the function unstream is recursive, and it is not amenable to the SAT. Presumably you wanted some combination of functions to undergo SATing, but which one?

comment:6 Changed 6 years ago by batterseapower

I'm currently investigating using the SAT to get stream fusion working properly, as per the ICFP07 paper. This probably just requires moving the SAT pass to a late stage in the pipeline (post-constructor specialisation) but I'm awaiting experimental results.

comment:7 Changed 6 years ago by simonmar

  • Architecture changed from Unknown to Unknown/Multiple

comment:8 Changed 6 years ago by simonmar

  • Operating System changed from Unknown to Unknown/Multiple

comment:9 Changed 5 years ago by igloo

  • Milestone changed from 6.10 branch to 6.12 branch

comment:10 Changed 4 years ago by igloo

  • Milestone changed from 6.12 branch to 6.12.3

comment:11 Changed 4 years ago by igloo

  • Milestone changed from 6.12.3 to 6.14.1
  • Priority changed from normal to low

comment:12 Changed 4 years ago by tibbe

  • Cc johan.tibell@… added
  • Type of failure set to None/Unknown

comment:13 Changed 3 years ago by liyang

  • Cc hackage.haskell.org@… added

comment:14 Changed 3 years ago by igloo

  • Milestone changed from 7.0.1 to 7.0.2

comment:15 Changed 3 years ago by igloo

  • Milestone changed from 7.0.2 to 7.2.1

comment:16 Changed 3 years ago by reinerp

  • Cc reiner.pope@… added

comment:17 Changed 3 years ago by jmcarthur

  • Cc Jake.McArthur@… added

comment:18 Changed 3 years ago by igloo

  • Milestone changed from 7.2.1 to 7.4.1

comment:19 Changed 2 years ago by choenerzs

  • Cc choener@… added

comment:20 Changed 2 years ago by dterei

  • Cc dterei added

comment:21 Changed 2 years ago by igloo

  • Milestone changed from 7.4.1 to 7.6.1
  • Priority changed from low to normal

comment:22 Changed 20 months ago by igloo

  • Milestone changed from 7.6.1 to 7.6.2
Note: See TracTickets for help on using tickets.