<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
p.Code, li.Code, div.Code
{mso-style-name:Code;
mso-style-link:"Code Char";
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Courier New";
color:#1F497D;}
span.CodeChar
{mso-style-name:"Code Char";
mso-style-link:Code;
font-family:"Courier New";
color:#1F497D;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
.MsoPapDefault
{mso-style-type:export-only;
margin-top:6.0pt;
margin-right:0cm;
margin-bottom:6.0pt;
margin-left:0cm;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:435831334;
mso-list-type:hybrid;
mso-list-template-ids:-231831212 134807553 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1
{mso-list-id:1490830607;
mso-list-type:hybrid;
mso-list-template-ids:691587408 134807553 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-GB" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">You’ve described the problem well. Indeed I think you should make a wiki page to articulate the problem, and point to this email (perhaps
among others) for more detail. It’s so easy to lose track of email, and so helpful to have a wiki page that always reflects the latest understanding.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">You say a little bit about the problem you are trying to solve, but not enough. (You can do this on the wiki page.) For example:<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo1"><![if !supportLists]><span style="font-size:11.0pt;font-family:Symbol;color:#1F497D;mso-fareast-language:EN-US"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">You say you don’t care about binaries. (Good, but why?)<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo1"><![if !supportLists]><span style="font-size:11.0pt;font-family:Symbol;color:#1F497D;mso-fareast-language:EN-US"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Do you care about multi-threaded GHC? (I think no)<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo1"><![if !supportLists]><span style="font-size:11.0pt;font-family:Symbol;color:#1F497D;mso-fareast-language:EN-US"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Do you care about what happens if you recompile GHC, say with different optimisation settings? (I think no) That would
affect order of evaluation, and hence the order of allocation of uniques.<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo1"><![if !supportLists]><span style="font-size:11.0pt;font-family:Symbol;color:#1F497D;mso-fareast-language:EN-US"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Do you care about recompiling the same source file with different environments; e.g. different compiler flags, changes in
imported interface files. (I think no; these changes should require recompilation)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">So can you characterise exactly what you DO care about? It might be something like “when using GHC as a library, with a single “session”,
and I recompile an unchanged source file in an unchanged environment I want to get the same result”. But I think even that is wrong.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><br>
The reason I’m confused is when you say “<i>What happens is that if you already have an interface file for a target you're trying to build the computation will proceed differently</i>”. But what do you mean by “you already have an interface file”? In batch
mode, we always load interface files; and with the same source and flags we almost certainly load them in the same order. So perhaps you mean in –make mode?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">I’ll hypothesise that you mean<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo2"><![if !supportLists]><span style="font-size:11.0pt;font-family:Symbol;color:#1F497D;mso-fareast-language:EN-US"><span style="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">In –make mode, with unchanged source I want to get the same output from compiling M.hs if M’s imported interface files have
not changed.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">But even then I’m confused. Under those circumstances, why are we recompiling at all?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Do you see what I mean about characterising the problem?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Depending on exactly what the problem is, one “solution” might be to not use –make mode.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">But I think I’ve gone as far as I can without a clearer understanding of the problem. (I suggest responding by writing the wiki page,
and sending a link.)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">On the UniqFM question, in a finite map,
<i>the way in which keys are compared really, really should not matter</i>. When you turn a UniqFM into a list you may need to canonicalise the list in some way But we shouldn’t mess up finite maps themselves in service of this goal. Better to focus on
the canonicalization process; which as you point out may be hard or even impossible as things stand.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Many thanks<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif"> ghc-devs [mailto:ghc-devs-bounces@haskell.org]
<b>On Behalf Of </b>Bartosz Nitka<br>
<b>Sent:</b> 14 September 2015 18:04<br>
<b>To:</b> ghc-devs@haskell.org<br>
<b>Subject:</b> Making compilation results deterministic (#4012)<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Hello,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
For the past couple of weeks I've been working on making compilation results deterministic.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
What I'm focusing on right now is the interface file determinism, I don't care about binaries being deterministic.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
I'd like to give a status update and ask for some advice, since I'm running into issues that I don't have a good way of solving.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
The first question anyone might ask is how did nondeterminism creep into the compiler. If we're compiling with a single thread there's no reason for the computation to proceed in non deterministic way. I'm fairly certain that the issue originates from lazy
loading of interface files. Relevant function: <a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fdiffusion%2fGHC%2fbrowse%2fmaster%2fcompiler%2ftypecheck%2fTcRnMonad.hs%3b12098c2e70b2a432f4ed675ed72b53a396cb2842%241414-1421&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=RHe15k8A1wE9hP7yrgAXFWcunZkNIDrc%2fnlV7uazZBk%3d">
https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/typecheck/TcRnMonad.hs;12098c2e70b2a432f4ed675ed72b53a396cb2842$1414-1421</a>. What happens is that if you already have an interface file for a target you're trying to build the computation
will proceed differently. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Why does lazy loading matter? As you load the interface file it needs to get type-checked and that means it needs to pull some Uniques from a global UniqSupply. It does that in different order resulting in different Unique assignment. As far as I can tell,
lazy loading is required for performance, so I abandoned the idea of fixing it. I haven't looked at parallel compilation yet, but I'd expect it to result in different Unique assignment as well.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
I believe up to this point we're ok. Uniques are non-deterministic, but it shouldn't be a big deal. Uniques should be opaque enough to not affect the order of computation, for example the order of binds considered. But they aren't.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Uniques are used in different ways throughout the compiler and they end up reordering things:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
1) They have an `Ord` instance: <a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fdiffusion%2fGHC%2fbrowse%2fmaster%2fcompiler%2fbasicTypes%2fUnique.hs%3b12098c2e70b2a432f4ed675ed72b53a396cb2842%24190-195&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=b2GCvMA9dNAWLcGINcDM0pQ8PO7tlty98k%2fBcZcd%2bcQ%3d">
https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/basicTypes/Unique.hs;12098c2e70b2a432f4ed675ed72b53a396cb2842$190-195</a>.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
So far the places it impacts the most are places that use `stronglyConnCompFromEdgedVertices`, because Unique is used as a Node key and the result depends on the order of Nodes being considered. Some examples:
<a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fdiffusion%2fGHC%2fbrowse%2fmaster%2fcompiler%2fsimplCore%2fOccurAnal.hs%3b12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c%24183%2c646%2c681%2c846&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Db92ho6TpI%2fAj3UIdLbrAjRrVpL%2fK2QVzvClFlRxGhs%3d">
https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/simplCore/OccurAnal.hs;12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c$183,646,681,846</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fdiffusion%2fGHC%2fbrowse%2fmaster%2fcompiler%2frename%2fRnSource.hs%3b12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c%241365&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=KL%2b8Q9ltuChQ8OIkXd1bCsp%2beDFfcFE9hL71GSWT7TE%3d">https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/rename/RnSource.hs;12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c$1365</a>
(because Ord for Name uses Unique <a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fdiffusion%2fGHC%2fbrowse%2fmaster%2fcompiler%2fbasicTypes%2fName.hs%3b12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c%24410-411&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=HTKDZejS%2bA%2fNAjc3jPYmuvJ8cNknHiyK4fLLZaZ1T1k%3d">
https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/basicTypes/Name.hs;12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c$410-411</a>)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
I've tried to see what removing it would entail and the changes would be far reaching:
<a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fP62&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=f2WW1C1rj9UGsoufDY2KYzBPM6%2frgHiqZDar%2bXg0p3Q%3d">
https://phabricator.haskell.org/P62</a>.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
2) VarEnv, NameEnv are implemented in terms of UniqFM, which is just Data.IntMap with keys being the Unique integer values.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
The way this bites us is that when UniqFM's get converted to a list they end up being sorted on Unique value. This problem is more widespread than the `stronglyConnCompFromEdgedVertices` issue, there's even a place where it's implicitly depended on:
<a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fdiffusion%2fGHC%2fbrowse%2fmaster%2fcompiler%2fnativeGen%2fRegAlloc%2fLiveness.hs%3b12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c%24837-842&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=UQ6Xel6diiS%2bTjx0OTUdzw9ar32Log%2bYlLAbzWiPYBg%3d">
https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/nativeGen/RegAlloc/Liveness.hs;12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c$837-842</a>.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
I've tried to fix it by making `toList` return the elements in the order of insertion (<a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fP63&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=XFUGV5jRPA8ft%2fNLYCi5zv4ynYIfcAzDfNFa8r753Zw%3d">https://phabricator.haskell.org/P63</a>),
but that turned out to have significant cost. My unscientific benchmark on aeson and text showed 10% compilation time increase. It's possible it can be done in less expensive way, I've tried a couple of approaches, but all of them resulted in 10% time increase.
I've also considered to split UniqFM to two different types, one that keeps the ordering, and one that can't `toList`, but I suspect that the cut will not be clean, so I haven't tried that.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
In some cases we got away with ordering things by OccName where needed: (<a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fD1073&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=g4LN6fOun9LW%2bFaQL6pZfGM6GH6rVJ3XZG9JlLgowrg%3d">https://phabricator.haskell.org/D1073</a>,
<a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fD1192&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=nHSOQ07L1u4kM2cvATfosvJjBVw17dbaLcuil5V%2bFEU%3d">
https://phabricator.haskell.org/D1192</a>), but OccName's don't have to be unique in every case and if we try to make them unique that would make them longer and probably result in even greater slowdown.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
The instance I've recently looked at doesn't look like it can be solved by sorting by OccName.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
The code that triggers the problem (simplified from haskell-src-exts):<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
data Decl l = Boring l<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
deriving (Eq)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
data Binds l<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
= BDecls l [Decl l] -- ^ An ordinary binding group<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
| IPBinds l [IPBind l] -- ^ A binding group for implicit parameters<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
deriving (Eq)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
data IPBind l = Boring2 l<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
deriving (Eq)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
The end result is:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
4449fe3f8368a2c47b2499a1fb033b6a<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
$fEqBinds_$c==$Binds :: Eq l => Binds l -> Binds l -> Bool<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
{- Arity: 1, HasNoCafRefs, Strictness: <L,U(C(C1(U)),A)>,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Unfolding: (\ @ l $dEq :: Eq l -><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
let {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
$dEq1 :: Eq (Decl l) = $fEqDecl @ l $dEq<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
} in<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
let {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
$dEq2 :: Eq (IPBind l) = $fEqIPBind @ l $dEq<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
} in<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
\ ds :: Binds l ds1 :: Binds l -><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
case ds of wild {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
BDecls a1 a2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-> case ds1 of wild1 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
BDecls b1 b2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-> case == @ l $dEq a1 b1 of wild2 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
False -> False True -> $fEq[]_$c== @ (Decl l) $dEq1 a2 b2 }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
IPBinds ipv ipv1 -> False }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
IPBinds a1 a2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-> case ds1 of wild1 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
BDecls ipv ipv1 -> False<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
IPBinds b1 b2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-> case == @ l $dEq a1 b1 of wild2 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
False -> False<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
True -> $fEq[]_$c== @ (IPBind l) $dEq2 a2 b2 } } }) -}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
vs<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
bb525bf8c0145a5379b3c29e8adb4b18<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
$fEqBinds_$c==$Binds :: Eq l => Binds l -> Binds l -> Bool<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
{- Arity: 1, HasNoCafRefs, Strictness: <L,U(C(C1(U)),A)>,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Unfolding: (\ @ l $dEq :: Eq l -><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
let {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
$dEq1 :: Eq (IPBind l) = $fEqIPBind @ l $dEq<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
} in<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
let {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
$dEq2 :: Eq (Decl l) = $fEqDecl @ l $dEq<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
} in<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
\ ds :: Binds l ds1 :: Binds l -><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
case ds of wild {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
BDecls a1 a2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-> case ds1 of wild1 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
BDecls b1 b2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-> case == @ l $dEq a1 b1 of wild2 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
False -> False True -> $fEq[]_$c== @ (Decl l) $dEq2 a2 b2 }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
IPBinds ipv ipv1 -> False }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
IPBinds a1 a2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-> case ds1 of wild1 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
BDecls ipv ipv1 -> False<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
IPBinds b1 b2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-> case == @ l $dEq a1 b1 of wild2 {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
False -> False<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
True -> $fEq[]_$c== @ (IPBind l) $dEq1 a2 b2 } } }) -}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
This happens because when desugaring dictionaries we do an SCC on Uniques that ends up reordering lets (<a href="https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fphabricator.haskell.org%2fdiffusion%2fGHC%2fbrowse%2fmaster%2fcompiler%2fdeSugar%2fDsBinds.hs%3b12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c%24835&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7ca4459b8986e1464920d808d2bd2690ca%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=txZxE5yjDCvvZnvedGPqHJuaNoA64bqGUPynIwZkoyo%3d">https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/deSugar/DsBinds.hs;12b0bb6f15caa5b4b01d0330a7a8d23e3c10842c$835</a>)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Now all of the dictionaries have OccName of Eq. I could probably reach deeper into the term to extract enough information (in this instance, the constructor name) to get deterministic ordering, but this feels very ad-hoc and I don't expect it to scale to the
whole codebase.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Another problem with fixing things in this ad-hoc manner is keeping them fixed. There's nothing preventing people from introducing nondeterminism. One idea that makes it more testable is to test it with different UniqSupply allocation patterns. I've found it
useful to compare against UniqSupply that starts at a big number and allocates in decreasing order. Gray codes could be used to generate non-sequential order.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
The reason I'm posting this is to get some ideas, because at this point I feel stuck, I don't see a good way of achieving the end goal. I hope someone with more intimate GHC knowledge can point out a wrong assumption I've made or suggest an approach I haven't
thought of.<br>
<br>
Cheers,<br>
Bartosz<o:p></o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>