(drop)CommonPrefix: ccs call implementation

Maarten Faddegon ghc-dev at maartenfaddegon.nl
Thu Jun 5 06:46:29 UTC 2014


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.
>
>      <a,b,c> ++> <>      = <a,b,c>
>      <a,b,c> ++> <d>     = <a,b,c,d>
>      <a,b,c> ++> <a,b>   = <a,b,c>
>      <a,b>   ++> <a,b,c> = <a,b,c>
>      <a,b,c> ++> <a,b,d> = <a,b,c,d>

For the given examples Simon's proposal would result in different 
stacks: <>, <d>,  <a,b>, <a,b,c> and <a,b,d>.
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


More information about the ghc-devs mailing list