<div dir="auto"><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Date: Wed, 13 Apr 2022 08:59:06 +0200<br>
From: Andreas Klebinger <<a href="mailto:klebinger.andreas@gmx.at" target="_blank" rel="noreferrer">klebinger.andreas@gmx.at</a>><br>
To: <a href="mailto:ghc-devs@haskell.org" target="_blank" rel="noreferrer">ghc-devs@haskell.org</a><br>
Subject: Re: Absence info at run-time<br>
Message-ID: <<a href="mailto:a577aa9c-6c96-945d-85f6-eb207f88b5b3@gmx.at" target="_blank" rel="noreferrer">a577aa9c-6c96-945d-85f6-eb207f88b5b3@gmx.at</a>><br>
Content-Type: text/plain; charset=UTF-8; format=flowed<br>
<br>
W/W should transform such a function into one who takes one less<br>
argument removing any runtime overhead at least for fully applied functions.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">Fully applied functions are definitely not what I'm talking about.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I suppose your suggestion is then if we an expression`f x` where bar<br>
takes multiple arguments, but doesn't use the current argument then GHC<br>
should:<br>
<br>
* Inspect f, check if the first argument to f is used<br>
* If we can determine it isn't used instead of creating a PAP capturing<br>
`f` and `x` instead only capture `f` and record this in the PAP closure<br>
somehow.<br>
* Once the PAP is fully applied pass a dummy argument instead of `x` to f.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">Yes, that's the idea. The "somehow" is described below.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
If f is a known call that seems doable, although adding a bitmap to paps<br>
might require us to increase the size of all PAP closures, making this<br>
optimization less useful.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto"> Every PAP has to carry its arity. I just looked it up:</div><div dir="auto"><br></div><div dir="auto">typedef struct {</div><div dir="auto"> StgHeader header;</div><div dir="auto"> StgHalfWord arity; // number of arguments left to apply, if zero this is an AP closure</div><div dir="auto"> StgHalfWord n_args; // number of applied arguments</div><div dir="auto"> StgClosure *fun; // guaranteed to point to a FUN closure</div><div dir="auto"> StgClosure *payload[];</div><div dir="auto">} StgPAP;</div><div dir="auto"><br></div><div dir="auto">On a 64-bit machine, we can combine arity and absence info for functions of up to 31 arguments into half a word. Specifically, set the lowest bit to indicate whether the first argument is used, etc. Then bitwise-or that with 1 `shiftL` arity. Each partial application performed shifts right by the number of arguments applied; if the result is 1, we know it's fully applied.</div><div dir="auto"><br></div><div dir="auto">(Any idea why we need the number of arguments that have been applied in the PAP? If that's actually only need for AP, then we might be able to make things a little more compact.)</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
If `f` is a unknown function there is currently no way to get<br>
absent/used info for it's arguments at runtime. And changing that would<br>
be a major change which seems unlikely to pay off.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">I described a mechanism for encoding this concisely above. The same encoding could be used for functions that haven't been partially applied. I don't know where their arities are stashed. In their info tables?</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
So I think this would be theoretically possible, but it would rarely pay<br>
off.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">I'm not sure it's so rare. We end up having to work around this issue in libraries, with varying levels of effort and success.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Also do you have an example where `(const a) b` leads to stupid thunks?<br>
It seems to me const should always be inlined in such a case, avoiding a<br>
PAP allocation.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">There won't be a PAP allocation if const inlines. The stupid thunk is a thunk to apply (\ _ -> a) to b. Suppose we define `fmap` for plain arrays (I know; probably not the best example), and let <$ take its default implementation:</div><div dir="auto"><br></div><div dir="auto"> (<$) a = fmap (const a)</div><div dir="auto"><br></div><div dir="auto">If we calculate x <$ arr, that will fill an array with thunks, each of them retaining an element of the original array which will never be used.</div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Am 12/04/2022 um 23:02 schrieb David Feuer:<br>
> Suppose `f` doesn't use its first argument. When forming the thunk (or<br>
> partial application) `f a`, we don't need to record `a`. What if<br>
> instead of arity, we store a bitmap used/absent arguments, terminated<br>
> by a 1 bit? Could we then get rid of "stupid thunks" like `(const a) b`?<br>
><br>
> _______________________________________________<br>
> ghc-devs mailing list<br>
> <a href="mailto:ghc-devs@haskell.org" target="_blank" rel="noreferrer">ghc-devs@haskell.org</a><br>
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
<br>
<br>
------------------------------<br>
<br>
Message: 3<br>
Date: Wed, 13 Apr 2022 08:21:25 +0000<br>
From: "Sebastian Graf" <<a href="mailto:sgraf1337@gmail.com" target="_blank" rel="noreferrer">sgraf1337@gmail.com</a>><br>
To: "GHC Devs" <<a href="mailto:ghc-devs@haskell.org" target="_blank" rel="noreferrer">ghc-devs@haskell.org</a>><br>
Subject: Markup language/convention for Notes?<br>
Message-ID: <eme97afb2c-f674-4ed3-9d50-52c6482169d0@sebastian-pc><br>
Content-Type: text/plain; charset="utf-8"; Format="flowed"<br>
<br>
Hi Devs,<br>
<br>
When writing Notes, I find myself using markdown-inspired or <br>
haddock-inspired features. The reason is that I keep telling myself<br>
<br>
> In 5 years time, we'll surely have an automated tool that renders <br>
Notes referenced under the cursor in a popup in our IDE<br>
<br>
And I might not be completely wrong about that, after all the strong <br>
conventions about Note declaration syntax allow me to do <br>
jump-to-definition on Note links in my IDE already (thanks to a shell <br>
script written by Zubin!).<br>
Still, over the years I kept drifting between markdown and haddock <br>
syntax, sometimes used `backticked inline code` or haddock 'ticks' to <br>
refer to functions in the compiler (sometimes even <br>
'GHC.Fully.Qualified.ticks') and for code blocks I used all of the <br>
following forms:<br>
<br>
Haddock "code quote"<br>
<br>
> id :: a -> a<br>
> id x = x<br>
<br>
Markdown triple backticks<br>
<br>
```hs<br>
id :: a -> a<br>
id x = x<br>
```<br>
<br>
Indentation by spaces<br>
<br>
id :: a -> a<br>
id x = x<br>
<br>
And so on.<br>
<br>
I know that at least Simon was thrown off in the past about my use of <br>
"tool-aware markup", perhaps also because I kept switching the targetted <br>
tool. I don't like that either. So I wonder<br>
Do you think it is worth optimising Notes for post-processing by an <br>
external tool?I think it's only reasonable if we decide for a target <br>
syntax. Which syntax should it be?<br>
Cheers,<br>
Sebastian<br>
-------------- next part --------------<br>
An HTML attachment was scrubbed...<br>
URL: <<a href="http://mail.haskell.org/pipermail/ghc-devs/attachments/20220413/84549293/attachment-0001.html" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/pipermail/ghc-devs/attachments/20220413/84549293/attachment-0001.html</a>><br>
<br>
------------------------------<br>
<br>
Subject: Digest Footer<br>
<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank" rel="noreferrer">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
<br>
<br>
------------------------------<br>
<br>
End of ghc-devs Digest, Vol 224, Issue 10<br>
*****************************************<br>
</blockquote></div></div></div>