(drop)CommonPrefix: ccs call implementation

Maarten Faddegon

5 Jun 2014 5 Jun '14

2:46 a.m.

Dear list, I am reading up on cost centre stacks. Simon Marlow's "solving an old problem"-slides is the more recent resource I could find. On slide 43 he describes a call function implemented as:

...

call Sapp Slam = foldr push Spre Slam’ where (Spre, Sapp’, Slam’) = commonPrefix Sapp Slam

However in rts/profiling.c the following is written:

...

Set CCCS when entering a function.

The algorithm is as follows.

ccs ++> ccsfn = ccs ++ dropCommonPrefix ccs ccsfn

where

dropCommonPrefix A B -- returns the suffix of B after removing any prefix common -- to both A and B.

e.g.

++> <> = ++> <d> = ++> = ++> = ++> =

For the given examples Simon's proposal would result in different stacks: <>, <d>, , and . Has the implementation changed since Simon Marlow gave his talk? If so, is there something I can read on the motivation behind this change? Or do I maybe misinterpret the slides? Thank you, Maarten Faddegon

Show replies by date

Ömer Sinan Ağacan

5 Jun 5 Jun

4:57 a.m.

Hi Maarten, Where did you find that slides? I have slides for same talk(also attached) but mine has a different definition for call: (on page 39) call sapp slam = sapp ++ slam' where (spre, sapp', slam') = commonPrefix sapp slam This one works same with the implementation. --- Ömer Sinan Ağacan http://osa1.net

Simon Marlow

6 Jun 6 Jun

5:39 a.m.

The motivation for this design is to make it so that let f = \x . E in ... f y ... Gives the same call stack as ... (\x . E) y ... That is, inlining a function does not change the call stack. GHC assumes that this is valid, so the call stack semantics should reflect that. Intuitively it works like this: in the first version, the CCS attached to the closure for f is some prefix of the CCS that will be in force at the call site, and in that case we don't want to push anything on the stack for the call. However, we might have: let f = scc "f" (\x . E) in ... f y ... and in this case we want to push "f" on the stack. I don't claim that this always works (recursion in particular causes problems) but it behaves in a sensible way in most cases, and it was the best formulation I was able to find. It remains to be seen whether there's a semantics that allows the inlining equivalence to be formally proven; if you can do that I think it would be a significant step forwards. Cheers, Simon On 05/06/2014 09:57, Ömer Sinan Ağacan wrote:

...

Hi Maarten,

Where did you find that slides? I have slides for same talk(also attached) but mine has a different definition for call: (on page 39)

call sapp slam = sapp ++ slam' where (spre, sapp', slam') = commonPrefix sapp slam

This one works same with the implementation.

--- Ömer Sinan Ağacan http://osa1.net

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

Maarten Faddegon

11 Jun 11 Jun

6:14 a.m.

Hi Simon, Thank you for the explanation, I begin to understand the reasoning behind your definition now. I have another question though: If inlining sets the call site's stack as prefix, I would say that the following definition: call sApp sLam = sApp ++ sLam' | sApp `isPrefixOf` sLam = sLam | otherwise = sApp ++ sLam Gives the same result as your definition: call sApp sLam = sApp ++ sLam' where (sPre,sApp',sLam') = commonPrefix sApp sLam Is that correct or are there situation where sApp' is non-empty? Cheers, Maarten On 06/06/14 10:39, Simon Marlow wrote:

...

The motivation for this design is to make it so that

let f = \x . E in ... f y ...

Gives the same call stack as

... (\x . E) y ...

That is, inlining a function does not change the call stack. GHC assumes that this is valid, so the call stack semantics should reflect that.

Intuitively it works like this: in the first version, the CCS attached to the closure for f is some prefix of the CCS that will be in force at the call site, and in that case we don't want to push anything on the stack for the call. However, we might have:

let f = scc "f" (\x . E) in ... f y ...

and in this case we want to push "f" on the stack.

I don't claim that this always works (recursion in particular causes problems) but it behaves in a sensible way in most cases, and it was the best formulation I was able to find.

It remains to be seen whether there's a semantics that allows the inlining equivalence to be formally proven; if you can do that I think it would be a significant step forwards.

Cheers, Simon

On 05/06/2014 09:57, Ömer Sinan Ağacan wrote:

...
Hi Maarten,

Where did you find that slides? I have slides for same talk(also attached) but mine has a different definition for call: (on page 39)

call sapp slam = sapp ++ slam' where (spre, sapp', slam') = commonPrefix sapp slam

This one works same with the implementation.

--- Ömer Sinan Ağacan http://osa1.net

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

3997

Age (days ago)

4003

Last active (days ago)

List overview

Download

3 comments

3 participants

participants (3)

Maarten Faddegon
Simon Marlow
Ömer Sinan Ağacan