Opened 11 years ago

Last modified 7 months ago

#888 new task

Implement the static argument transformation

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

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 11 years ago.
Stream example

Download all attachments as: .zip

Change History (32)

Changed 11 years ago by simonpj

Attachment: Stream.hs added

Stream example

comment:1 Changed 11 years ago by igloo

Milestone: 6.8
Test Case: N/A

comment:2 Changed 11 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 10 years ago by guest

Cc: Bulat.Ziganshin@… added

comment:4 Changed 10 years ago by simonpj

Milestone: 6.8 branch6.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 9 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 9 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 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:8 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple

comment:9 Changed 9 years ago by igloo

Milestone: 6.10 branch6.12 branch

comment:10 Changed 7 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:11 Changed 7 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:12 Changed 7 years ago by tibbe

Cc: johan.tibell@… added
Type of failure: None/Unknown

comment:13 Changed 7 years ago by liyang

Cc: hackage.haskell.org@… added

comment:14 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:15 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:16 Changed 6 years ago by reinerp

Cc: reiner.pope@… added

comment:17 Changed 6 years ago by jmcarthur

Cc: Jake.McArthur@… added

comment:18 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:19 Changed 6 years ago by choenerzs

Cc: choener@… added

comment:20 Changed 6 years ago by dterei

Cc: dterei added

comment:21 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lownormal

comment:22 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:23 Changed 3 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:24 Changed 3 years ago by nomeata

I’m confused. There is -fstatic-argument-transformation. Shouldn’t this be closed? There is also #9374 about the need to make SAT better...

comment:25 Changed 3 years ago by choenerzs

I think this issue tracks work on SAT for stream fusion / concatMap. Probably the more generic case as well, but I think I added myself to CC because of stream fusions concatMap.

comment:26 Changed 3 years ago by simonpj

The current SAT pass has received no love for many years. Its heuristics have not been explored systematically. I opened this ticket to record a set of heuristics that might work better. But I don't think anyone has followed it up.

Probably this could be combined with #9374 though.

Simon

comment:27 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:28 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:29 Changed 23 months ago by maoe

Cc: maoe added

comment:30 Changed 21 months ago by thomie

Milestone: 8.0.1

comment:31 Changed 7 months ago by mpickering

Keywords: StaticArgumentTransformation added
Note: See TracTickets for help on using tickets.