CPS versus Pattern Matching performance
Is there a performance penalty to be paid when using CPS instead of pattern matching? CPS often "feels more concise" but I suspect that it incurs a cost because of the accumulating stack that pattern matching wouldn't. When you you use maybe :: b -> (a -> b) -> Maybe a -> b instead of pattern matching a returned Maybe value? Is there something a bit more concrete on this issue? -- Tony Morris http://tmorris.net/
tmorris:
When you you use maybe :: b -> (a -> b) -> Maybe a -> b instead of pattern matching a returned Maybe value?
Is there something a bit more concrete on this issue?
You mean, versus using 'case' or sugar for case? It'll just inline to the same code. For example: maybe 10 (\n -> n + 1) bigexpr => {inline maybe} (\n f x -> case x of Nothing -> n Just x -> f x) 10 (\n -> n + 1) bigexpr => {reduce} case bigexpr of Nothing -> 10 Just x -> x+1 So use 'maybe' if its clearer -- it doesn't cost anything. -- Don
Thanks Don, Is your explanation specific to maybe? Or does that apply to all functions? Suppose the following function for lists: f :: [a] -> b -> (a -> [a] -> b) -> b ...instead of pattern matching [] and (x:xs) Tony Morris http://tmorris.net/ Donald Bruce Stewart wrote:
tmorris:
When you you use maybe :: b -> (a -> b) -> Maybe a -> b instead of pattern matching a returned Maybe value?
Is there something a bit more concrete on this issue?
You mean, versus using 'case' or sugar for case? It'll just inline to the same code.
For example:
maybe 10 (\n -> n + 1) bigexpr
=> {inline maybe}
(\n f x -> case x of Nothing -> n Just x -> f x) 10 (\n -> n + 1) bigexpr
=> {reduce}
case bigexpr of Nothing -> 10 Just x -> x+1
So use 'maybe' if its clearer -- it doesn't cost anything.
-- Don
On Tue, 10 Jul 2007, Tony Morris wrote:
Is your explanation specific to maybe? Or does that apply to all functions?
Suppose the following function for lists:
f :: [a] -> b -> (a -> [a] -> b) -> b
...instead of pattern matching [] and (x:xs)
A foldr without recursion. I use such functions frequently in order to hide constructors of a data type. Does this kind of functions has a common name?
lemming:
On Tue, 10 Jul 2007, Tony Morris wrote:
Is your explanation specific to maybe? Or does that apply to all functions?
Suppose the following function for lists:
f :: [a] -> b -> (a -> [a] -> b) -> b
...instead of pattern matching [] and (x:xs)
A foldr without recursion. I use such functions frequently in order to hide constructors of a data type. Does this kind of functions has a common name?
They're catamorphisms: Bool - cond/if-then-else Maybe - maybe (,) - uncurry [] - foldr -- Don
On Tue, 10 Jul 2007, Donald Bruce Stewart wrote:
lemming:
On Tue, 10 Jul 2007, Tony Morris wrote:
Is your explanation specific to maybe? Or does that apply to all functions?
Suppose the following function for lists:
f :: [a] -> b -> (a -> [a] -> b) -> b
...instead of pattern matching [] and (x:xs)
A foldr without recursion. I use such functions frequently in order to hide constructors of a data type. Does this kind of functions has a common name?
They're catamorphisms:
Bool - cond/if-then-else Maybe - maybe (,) - uncurry [] - foldr
The emphasis was on "without recursion". There is clearly only a difference for lists. So is there a name for "fold without recursion"?
Hello, On Tue, 10 Jul 2007 10:53:35 +0200 (MEST), Henning Thielemann wrote:
On Tue, 10 Jul 2007, Tony Morris wrote:
Is your explanation specific to maybe? Or does that apply to all functions?
Suppose the following function for lists:
f :: [a] -> b -> (a -> [a] -> b) -> b
...instead of pattern matching [] and (x:xs)
A foldr without recursion. I use such functions frequently in order to hide constructors of a data type. Does this kind of functions has a common name?
I think they just called "case analysis"; at least that's the terminology used here: http://www.dcs.st-andrews.ac.uk/~james/RESEARCH/concon.pdf (See the "treeCase" example in Section 3). Cheers, Bruno Oliveira
This might be a feasible appropriation of the term "destructor".
On 7/10/07, Bruno Oliveira
On Tue, 10 Jul 2007 10:53:35 +0200 (MEST), Henning Thielemann wrote:
On Tue, 10 Jul 2007, Tony Morris wrote: A foldr without recursion. I use such functions frequently in order to hide constructors of a data type. Does this kind of functions has a common name?
I think they just called "case analysis"; at least that's the terminology used here:
http://www.dcs.st-andrews.ac.uk/~james/RESEARCH/concon.pdf
(See the "treeCase" example in Section 3).
On Tuesday 10 July 2007, Nicolas Frisby wrote:
This might be a feasible appropriation of the term "destructor".
Co-constructor? <snip> Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs
tmorris:
Thanks Don, Is your explanation specific to maybe? Or does that apply to all functions?
Suppose the following function for lists:
f :: [a] -> b -> (a -> [a] -> b) -> b
...instead of pattern matching [] and (x:xs)
It really depends on the body of 'f'. If they're simple wrappers over case analysis they should be inlined perfectly. -- Don
On Tuesday 10 July 2007, Tony Morris wrote:
Thanks Don, Is your explanation specific to maybe? Or does that apply to all functions?
Suppose the following function for lists:
f :: [a] -> b -> (a -> [a] -> b) -> b
...instead of pattern matching [] and (x:xs)
Of course. GHC doesn't know anything about maybe; all it sees is: 1. One-liner: maybe f x mb = case mb of { Just x' -> f x'; Nothing -> x } 2. Non-recursive And it inlines like crazy. If you had quite a large data type, the number of case alternatives /might/ put you over GHC's inlining threshold, but that (ridiculous) scenario is the only thing that'll keep the argument from generalizing to your use case. <snip> Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs
Thanks for the explanations - fully understood. Tony Morris http://tmorris.net/ Jonathan Cast wrote:
On Tuesday 10 July 2007, Tony Morris wrote:
Thanks Don, Is your explanation specific to maybe? Or does that apply to all functions?
Suppose the following function for lists:
f :: [a] -> b -> (a -> [a] -> b) -> b
...instead of pattern matching [] and (x:xs)
Of course. GHC doesn't know anything about maybe; all it sees is:
1. One-liner:
maybe f x mb = case mb of { Just x' -> f x'; Nothing -> x }
2. Non-recursive
And it inlines like crazy. If you had quite a large data type, the number of case alternatives /might/ put you over GHC's inlining threshold, but that (ridiculous) scenario is the only thing that'll keep the argument from generalizing to your use case.
<snip>
Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
I've recently been wondering (in a more general context than just haskell)
about optimisations along the lines of
foo x y z = if complicated thing then Cons1 a b c
else if other complicated thing then Cons2 d e
else Cons3 f
bar some args = case foo perhaps different args of
Cons1 a b c -> code for case one
Cons2 a b -> code for case two
Cons3 a -> code for case three
into
foo x y z k1 k2 k3 =
if complicated thing then k1 a b c
else if other complicated thing then k2 d e
else k3 f
bar some args = foo perhaps different args
(\ a b c -> code for case one)
(\ a b -> code for case two)
(\ a -> code for case three)
Such that you save a cons (unless the compiler can return the value in
registers or on the stack) and a case analysis branch, but a normal
function return (predictable by the CPU) is replaced by a less-predictable
indirect jump. Does anyone have references to a paper that discusses an
optimisation like this for any language, not just Haskell?
Tony.
--
f.a.n.finch
On 7/11/07, Tony Finch
Does anyone have references to a paper that discusses an optimisation like this for any language, not just Haskell?
Section 4.8 of "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine." by Simon Peyton Jones, contains some references to papers about transformation to Continuation-Passing-Style. It also discusses the difference between CPS and the STG language: http://research.microsoft.com/users/simonpj/papers/spineless-tagless-gmachin... regards, Bas van Dijk
On Wed, Jul 11, 2007 at 11:14:20AM +0100, Tony Finch wrote:
registers or on the stack) and a case analysis branch, but a normal function return (predictable by the CPU) is replaced by a less-predictable indirect jump. Does anyone have references to a paper that discusses an
GHC does not use calls and returns. To quote a recent paper on this subject: 7.1 Using call/return instructions As we mentioned in Section 2, GHC generates code that manages the Haskell stack entirely separately from the system-supported C stack. As a result, a case expression must explicitly push a return address, or continuation, onto the Haskell stack; and the "return" takes the form of an indirect jump to this address. There is a lost op- portunity here, because every processor has built-in CALL and RET instructions that help the branch-prediction hardware make good predictions: a RET instruction conveys much more information than an arbitrary indirect jump. Nevertheless, for several tiresome reasons, GHC cannot readily make use of these instructions: * The Haskell stack is allocated in the heap. GHC generates code to check for stack overflow, and relocates the stack if necessary. In this way GHC can support zillions of little stacks (one per thread), each of which may be only a few hundred bytes long. However, operating systems typically take signals on the user stack, and do no limit checking. It is often possible to arrange that signals are executed on a separate stack, however. * The code for a case continuation is normally preceded by an info table that describes its stack frame layout. This arrangement is convenient because the stack frame looks just like a heap closure, which we described in Section 2. The garbage collector can now use the info table to distinguish the point- ers from non-pointers in the stack frame closure. This changes if the scrutinee is evaluated using a CALL instruction: when the called procedure is done, it RETurns to the instruction right after the call. This means that the info table can no longer be placed before a continuation. Thus the possible benefits of a CALL/RET scheme must outweigh the performance penalty of abandoning the current (efficient) info table layout. Stefan
participants (9)
-
Bas van Dijk -
Bruno Oliveira -
dons＠cse.unsw.edu.au -
Henning Thielemann -
Jonathan Cast -
Nicolas Frisby -
Stefan O'Rear -
Tony Finch -
Tony Morris