Re: Really bad code for single method dictionaries?
On 27/03/2009, at 18:32, Don Stewart wrote: I don't think this is still the case. Roman, do you remember? Hmm, not really. I recall that there was some sort of problem which I didn't have time to investigate then but it's been so long... Roman ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Really bad code for single method dictionaries?
2009/3/26 Jason Dusek jason.du...@gmail.com: I was reading the stream fusion code today and came across a comment stating that single element dictionaries interacted poorly with GHC's optimizer: class Unlifted a where [...] expose [...] -- | This makes GHC's optimiser happier; it sometimes produces really bad -- code for single-method dictionaries -- unlifted_dummy [...] A cursory search on GHC's Trac shows no corresponding bug; is this no longer a problem? A small problem? I would like to know more about it. I'm not sure if there is a bad interaction with rewrite rules (which I assume was the complaint) but single method dictionaries tend to be faster because they are represented by a coercion in the Core language, which means that packing and unpacking the dictionary is free at runtime. Cheers, Max ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: compilation of pattern-matching?
| It would be nice if we could first reach a common understanding, so | that I can actually report the right problem, not just isolated symptoms. It's quite simple. The Reports specifies the semantics, not the operational behaviour. Any implementation that behaves as the Report specifies is OK. GHC violates that rule, as we can demonstrate: newtype N = N Int deriving (Show,Eq) Until this moment I believed that GHC respected the Report, and our discussion related solely to performance. But your diligent persistence has indeed uncovered a bug. Thank you! You deserve an accolade. The problem you have uncovered is this. Consider case (x,y) of (0, 'x') - ... (1, 'y') - ... (0, 'p') - ... Then it's fine for GHC to combine the two tests on 0, thus: case x of 0 - case y of ... 1 - case y of ... But in doing the *combining* I also allowed the two to be *re-ordered*. That is fine for data constructors, and it's fine if 'fromInteger' is injective, but it is NOT fine in general. Thank you for finding this. I'll fix it. And in fixing it I may as well arrange not to re-order constructors too, which will make you happier. Happier, not happy, because I make no guarantees of what may happen downstream! thanks Claus. Since you discovered it, would you like to have the dubious honour of opening a Trac report, which I'll then fix? Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: compilation of pattern-matching?
Lennart Augustsson wrote: Sorting by constructor tag is perfectly safe when done right. You can read about how to do it in my 1985 FPCA paper or in Simon's book. When pattern matching against against things that that are not constructors (like literals etc) it's much trickier to reorder them since you have to prove harder pattern commutation properties. I don't think there is any controversy at all about Haskell pattern matching semantics. As you say, it's pretty clearly spelled out. (It wouldn't hurt to have it written down as a denotational semantics, though.) And ghc happens to have a bug. Just thought I'd mention this other bug in the same area: http://hackage.haskell.org/trac/ghc/ticket/246 (Wrong pat-match order for records) Cheers, Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: compilation of pattern-matching?
Claus Reinke wrote: You are right that this doesn't help my performance argument, as performance issues are outside the language definition (not observable in the language definition sense). It was merely an answer to the vehement claims that pattern order is irrelevant. The order of branches in a case expression *in Core* is irrelevant (except that GHC assumes DEFAULT comes first). The order of pattern matches in a Haskell expression is, of course, semantically significant. Nobody is claiming you can change the order of pattern matches in Haskell in general without it changing the meaning. |It's not that GHC deliberately re-orders case alternatives, |it's that it doesn't deliberately not do it. no longer is a safe default strategy (actually, it never was, as the bug shows;-). Neither is sorting patterns by constructor tag, as seems to happen on the way to Core. I was talking about Core. I thought you were too - sorry. Since what you wanted was the order of tests to somehow remain fixed from Haskell through to assembly code, that would imply not reordering them through Core, which GHC does not guarantee not to do. The order of branches in a case expression has no semantic significance in Core. Cheers, Simon PS. nice bug. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: compilation of pattern-matching?
Ticket is http://hackage.haskell.org/trac/ghc/ticket/3126 . Sorting by constructor tag is perfectly safe when done right. You can read about how to do it in my 1985 FPCA paper or in Simon's book. I did, long ago. I learned functional programming by implementing a small functional language, using the Kiel Reduction Language (remember that one? It not only took programming with functions to a level not yet available with modern implementations, it also had a pattern-match sublanguage and engine that was as complex as the rest of it taken together, so we were encouraged to read up on pattern matching in general), C, and your papers. Which made this discussion interesting, as I'm easily intimidated by strongly expressed opinions from people who wrote about this stuff when I was still learning about it;-) When pattern matching against against things that that are not constructors (like literals etc) it's much trickier to reorder them since you have to prove harder pattern commutation properties. Good that we now seem to agree on things. Simon: there aren't really any patterns to combine in the test case, so I assume the reordering happens when combining a single pattern? Fill the fix you envisioned also cover the IsString variant? Claus ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Under OS X 10.5.6: GHC 6.10.1 Release Candidate 1
Ian Lynagh wrote: On Wed, Mar 18, 2009 at 06:51:31AM -0400, Gregory Wright wrote: Unexpected failures: 2469(ghci) This is http://hackage.haskell.org/trac/ghc/ticket/2789 (which is fixed in the new build system). apirecomp001(normal) This is failing because of ld: atom sorting error for ... on OS X http://hackage.haskell.org/trac/ghc/ticket/2578 (I'd love for someone to fix that). bits genUpTo These are fixed. num009 num012 These still need to be fixed, but I'm pretty sure they aren't regressions. I have a fix for num012 (the test is broken), but I still don't know what's going on with num009. Cheers, Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: compilation of pattern-matching?
| Simon: there aren't really any patterns to combine in the test case, | so I assume the reordering happens when combining a single | pattern? Fill the fix you envisioned also cover the IsString variant? yes it will. S ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Under OS X 10.5.6: GHC 6.10.1 Release Candidate 1
2009/3/27 Simon Marlow marlo...@gmail.com: I have a fix for num012 (the test is broken), but I still don't know what's going on with num009. num009 has been broken on OS X for as long as I can remember :-). I opened a ticket about it on Trac way back: http://hackage.haskell.org/trac/ghc/ticket/2370 (not that that ticket has any useful information in it...) Cheers, Max ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Under OS X 10.5.6: GHC 6.10.1 Release Candidate 1
Max Bolingbroke batterseapo...@hotmail.com wrote: 2009/3/27 Simon Marlow marlo...@gmail.com: I have a fix for num012 (the test is broken), but I still don't know what's going on with num009. num009 has been broken on OS X for as long as I can remember :-). If it is any help, I can confirm that num009 works correctly on a PowerPC Mac with both ghc-6.8.2 and 6.10.1, but it fails on an Intel Mac at least as far back as ghc-6.8.3. Regards, Malcolm ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Int vs Word performance?
Hello, sorry for breaking the thread, I just got in the list. Simon Peyton-Jones simonpj at microsoft.com : PS: in the case that no one gets around to creating such a patch, creating a ticket that documents the problem and points to the needed specialisations would be a start Was this created? I could not find something about it in the GHC trac. Greetings. -- marcot http://marcot.iaaeee.org/ ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Int vs Word performance?
Simon Peyton-Jones simonpj at microsoft.com : PS: in the case that no one gets around to creating such a patch, creating a ticket that documents the problem and points to the needed specialisations would be a start Was this created? I could not find something about it in the GHC trac. Yes: http://hackage.haskell.org/trac/ghc/ticket/3055 Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users Does anyone know why this mailing list archive loses thread links when they cross month boundaries? That is rather inconvenient for catching up with old threads or providing links to information in them (from tickets, etc.). Claus ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Loop unrolling + fusion ?
I can't see any issues with this version of the spec.
Thanks. From the silence, we seemed to have lost the innocent
bystanders? Anyway, for those who haven't noticed, there is now
a feature request ticket (for that good feeling of closing it when this
is finally implemented;-) as well as a wiki page describing the issues,
spec, and examples:
http://hackage.haskell.org/trac/ghc/ticket/3123
http://hackage.haskell.org/trac/ghc/wiki/Inlining
I think in the implementation it makes most sense to do this as a
core2core pass at an early stage in the pipeline, probably via plugins
(so will have to wait until I get those into HEAD).
What are the plans for plugin support? I do think plugins will be
useful, but inlining is pretty central to the existing optimizer
transformations,
isn't it? Would the transformation code differ much between in-GHC
and via-plugins? Perhaps the transformation pass could be implemented
now, and later moved out into a plugin, possibly along with other passes.
I have also been wondering about the relation between rewrite RULES
and plugins. Assuming we can find a more convenient syntax, aren't
plugin+syb-based rewrites going to be more expressive, with more
control than RULES? Or is the syntactic/compiletime overhead going
to remain so high that both RULES and plugins will be kept in GHC?
(cf the recent thread on optimization and rewrite rules questions
http://www.haskell.org/pipermail/glasgow-haskell-users/2009-February/016702.html
)
In the case of
PEEL, we don't want to identify all call sites directly and do the
substitution in the pass so we should just output some bindings which
will certainly be inlined into call sites later on. So, the
transformation should be bottom up on the Core syntax tree and when it
meets a recursive group of bindings we should do something like this:
{-# INLINE f g PEEL 3 UNROLL 2 #-}
f = ... g ... f ... h ...
g = ... g ... f ... h ...
h = ... g ... f ... h ...
=(my pass)=
-- Temporary copies of f and g - dead code
f_old = ... g_old ... f_old ... h ...
g_old = ... g_old ... f_old ... h ...
-- H unchanged for now, might get PEELed stuff inlined later
h = ... g .. f ... h ...
You mean UNROLLed stuff (PEEL is only for entries into the group).
-- Top level unrolled definiiton - if we weren't doing peeling, these
would be the new f and g
f_unrolled = ... g_unrolled_1 ... f_unrolled_1 ... h ...
g_unrolled = ... g_unrolled_1 ... f_unrolled_1 ... h ...
-- Unrolled iteration. Will get inlined into f_unrolled / g_unrolled soon
{-# INLINE f_unrolled_1 g_unrolled_1 #-}
f_unrolled_1 = ... g_unrolled ... f_unrolled ... h ...
g_unrolled_1 = ... g_unrolled ... f_unrolled ... h ...
Ah, yes, we need to be unambiguous about the interpretation of the
counters:-) I was thinking of n+1 (adding n copies to the original), you
are thinking of n (adding copies until there are n).
-- One level of peeling
{-# INLINE f_1 g_1 #-}
f_1 = ... g_unrolled ... f_unrolled ... h ...
g_1 = ... g_unrolled ... f_unrolled ... h ...
-- Second level of peeling
{-# INLINE f_2 g_2 #-}
f_2 = ... g_1 ... f_1 ... h ...
g_2 = ... g_1 ... f_1 ... h ...
-- Final level of peeling and new definitions for f and g. Inline pragmas
-- make sure all of this gets inlined at the call site
{-# INLINE f g #-}
f = ... g_2 ... f_2 ... h ...
g = ... g_2 ... f_2 ... h ...
Wait, now you are counting to n+1 for PEEL and to n for UNROLL?
=(after the simplifier has run - effectively - there are a few
harmless lies here)=
-- NB: I haven't shown inlining of the new f and g here, but it /will/ happen
h = ... g .. f ... h ...
Since we are interpreting recursive groups as single entities, and there
is usually no inlining into definitions that will get inlined, we will have to
specify this carefully.
-- I've inlined the inner unrolled iteration at every /call site/
within the top level unrolled iteration, as per
-- the pragmas. Noone actualy calls this unrolled thing directly
though, since we used PEEL as well
f_unrolled = ... (... g_unrolled ... f_unrolled ... h ...) ... (...
g_unrolled ... f_unrolled ... h ...) ... h ...
g_unrolled = ... (... g_unrolled ... f_unrolled ... h ...) ... (...
g_unrolled ... f_unrolled ... h ...) ... h ...
Again, we have to make sure of this interpretation.
-- This huge chunk of code gets inlined at every call site, which in
turn call through to the unrolled bodies
{-# INLINE f g #-}
f = ... (... (... g_unrolled ... f_unrolled ... h ...) ... (...
g_unrolled ... f_unrolled ... h ...) ... h ...) ... (... (...
g_unrolled ... f_unrolled ... h ...) ... (... g_unrolled ...
f_unrolled ... h ...) ... h ...) ... h ...
g = ... (... (... g_unrolled ... f_unrolled ... h ...) ... (...
g_unrolled ... f_unrolled ... h ...) ... h ...) ... (... (...
g_unrolled ... f_unrolled ... h ...) ... (... g_unrolled ...
f_unrolled ... h ...) ... h ...) ... h ...
So this would be the result of inlining all the PEEL instances into 'f' and 'g'.
By ensuring that f and g are tagged
