Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Mergesort output is not uniformly articulated #19

Closed
matthewhammer opened this issue Feb 20, 2015 · 8 comments
Closed

Mergesort output is not uniformly articulated #19

matthewhammer opened this issue Feb 20, 2015 · 8 comments
Assignees
@kyleheadley
Labels
critical path experiment

Comments

@matthewhammer
Copy link
Contributor

We'd like it if mergesort, when given uniformly named and articulated input, will produce uniformly named and articulated output. Further, we'd like it if it roughly preserved whatever distribution of naming and articulation is found in the input.

As it stands, it doesn't work for uniform (fine-grained) names and articulation points. Instead, the initial output of the sort is articulated, and the later parts are not.

To reproduce this behavior, do this:

make test
./experiments.native --experiment Rope_mergesort_name --n 100 --debug-flags --num-changes 0 --gran 1

You'll see this (notice the two really long lines, and how they look different):

You requested experiment: Rope_mergesort_name
0: Initial input:   3533; Name; Art => 4775; Name; Art => 501; Name; Art => 10234; Name; Art => 993; Name; Art => 1831; Name; Art => 7019; Name; Art => 11501; Name; Art => 8734; Name; Art => 6024; Name; Art => 10877; Name; Art => 12727; Name; Art => 9533; Name; Art => 114; Name; Art => 11543; Name; Art => 1845; Name; Art => 4721; Name; Art => 12024; Name; Art => 7059; Name; Art => 3792; Name; Art => 3891; Name; Art => 1748; Name; Art => 1994; Name; Art => 10018; Name; Art => 1021; Name; Art => 8450; Name; Art => 8017; Name; Art => 5413; Name; Art => 822; Name; Art => 12154; Name; Art => 5458; Name; Art => 5066; Name; Art => 6334; Name; Art => 3422; Name; Art => 9038; Name; Art => 11594; Name; Art => 3886; Name; Art => 3405; Name; Art => 7184; Name; Art => 1633; Name; Art => 9918; Name; Art => 1418; Name; Art => 2839; Name; Art => 6015; Name; Art => 1232; Name; Art => 11994; Name; Art => 5231; Name; Art => 4348; Name; Art => 9346; Name; Art => 4160; Name; Art => 2971; Name; Art => 8243; Name; Art => 2175; Name; Art => 2680; Name; Art => 5082; Name; Art => 12294; Name; Art => 11256; Name; Art => 10881; Name; Art => 2230; Name; Art => 3209; Name; Art => 11747; Name; Art => 4612; Name; Art => 5325; Name; Art => 7097; Name; Art => 9948; Name; Art => 10464; Name; Art => 10928; Name; Art => 4519; Name; Art => 11711; Name; Art => 550; Name; Art => 9410; Name; Art => 1401; Name; Art => 3681; Name; Art => 3918; Name; Art => 1828; Name; Art => 9498; Name; Art => 12361; Name; Art => 12122; Name; Art => 4940; Name; Art => 1517; Name; Art => 9998; Name; Art => 10956; Name; Art => 4195; Name; Art => 11448; Name; Art => 1438; Name; Art => 1879; Name; Art => 12535; Name; Art => 12038; Name; Art => 6273; Name; Art => 12408; Name; Art => 657; Name; Art => 394; Name; Art => 5522; Name; Art => 7668; Name; Art => 5003; Name; Art => 9562; Name; Art => 10536; Name; Art => 12754; Name; Art => 4190; Name; Art => 5552; Name; Art => Nil

0: Initial output:  Name; 114; Art => Name; 394; Art => Name; 501; Art => Name; 550; Art => Name; 657; Art => Name; 822; Art => Name; 993; Art => 1021; Name; 1232; Art => Name; 1401; Art => 1418; Name; 1438; Art => Name; 1517; Art => 1633; Name; 1748; Art => Name; 1828; Art => 1831; 1845; 1879; 1994; Name; 2175; Art => 2230; 2680; 2839; Name; 2971; Art => 3209; 3405; Name; 3422; Art => 3533; 3681; 3792; Name; 3886; Art => 3891; 3918; 4160; Name; 4190; Art => 4195; Name; 4348; Art => 4519; 4612; 4721; 4775; 4940; Name; 5003; Art => 5066; 5082; 5231; 5325; 5413; 5458; 5522; Name; 5552; Art => 6015; 6024; 6273; 6334; 7019; 7059; 7097; 7184; 7668; 8017; 8243; 8450; 8734; 9038; 9346; 9410; 9498; 9533; 9562; 9918; 9948; 9998; 10018; 10234; 10464; 10536; 10877; 10881; 10928; 10956; 11256; 11448; 11501; 11543; 11594; 11711; 11747; 11994; 12024; 12038; 12122; 12154; 12294; 12361; 12408; 12535; 12727; 12754; Nil

----------------------------------------------------------------------------------
0:Rope_mergesort_name: Initial run: time:0.0040s (unit cost 663)
0:Rope_mergesort_name: Initial run: {dirty:0; clean:0; eval:475; create:475; tables:2}
--------------------
0:Rope_mergesort_name: No changes requested; Skipping interaction.

Kyle says: "You'll notice that the order changes from Cons-Name-Art to Name-Cons-Art. That's because of what I wrote in list_merge. I have no idea why I did it, and should probably change it back."

It's not yet clear to me if this discrepancy is related to this issue, or just some other (more minor) one.
@matthewhammer
Copy link
Contributor Author

I've looked at the code a little. After first looking at list_to_rope_mergesort as a whole, I started to look at something simpler, using @kyleheadley's new feature to check for uniform output articulation.

I decided to study list_of_rope $$ rope_of_list in isolation. In particular, I wanted to ensure that this composition preserves the uniformity of names and articulations. There was already an experiment written for this test (Rope_iter_name) so I ran it with the debugging flags:

./_build/Source/test/experiments.native --experiment Rope_iter_name --n 100 --debug-flags --num-changes 0
You requested experiment: Rope_iter_name
0: Initial input:   3533; Name; Art => 4775; Name; Art => 501; Name; Art => 10234; Name; Art => 993; Name; Art => 1831; Name; Art => 7019; Name; Art => 11501; Name; Art => 8734; Name; Art => 6024; Name; Art => 10877; Name; Art => 12727; Name; Art => 9533; Name; Art => 114; Name; Art => 11543; Name; Art => 1845; Name; Art => 4721; Name; Art => 12024; Name; Art => 7059; Name; Art => 3792; Name; Art => 3891; Name; Art => 1748; Name; Art => 1994; Name; Art => 10018; Name; Art => 1021; Name; Art => 8450; Name; Art => 8017; Name; Art => 5413; Name; Art => 822; Name; Art => 12154; Name; Art => 5458; Name; Art => 5066; Name; Art => 6334; Name; Art => 3422; Name; Art => 9038; Name; Art => 11594; Name; Art => 3886; Name; Art => 3405; Name; Art => 7184; Name; Art => 1633; Name; Art => 9918; Name; Art => 1418; Name; Art => 2839; Name; Art => 6015; Name; Art => 1232; Name; Art => 11994; Name; Art => 5231; Name; Art => 4348; Name; Art => 9346; Name; Art => 4160; Name; Art => 2971; Name; Art => 8243; Name; Art => 2175; Name; Art => 2680; Name; Art => 5082; Name; Art => 12294; Name; Art => 11256; Name; Art => 10881; Name; Art => 2230; Name; Art => 3209; Name; Art => 11747; Name; Art => 4612; Name; Art => 5325; Name; Art => 7097; Name; Art => 9948; Name; Art => 10464; Name; Art => 10928; Name; Art => 4519; Name; Art => 11711; Name; Art => 550; Name; Art => 9410; Name; Art => 1401; Name; Art => 3681; Name; Art => 3918; Name; Art => 1828; Name; Art => 9498; Name; Art => 12361; Name; Art => 12122; Name; Art => 4940; Name; Art => 1517; Name; Art => 9998; Name; Art => 10956; Name; Art => 4195; Name; Art => 11448; Name; Art => 1438; Name; Art => 1879; Name; Art => 12535; Name; Art => 12038; Name; Art => 6273; Name; Art => 12408; Name; Art => 657; Name; Art => 394; Name; Art => 5522; Name; Art => 7668; Name; Art => 5003; Name; Art => 9562; Name; Art => 10536; Name; Art => 12754; Name; Art => 4190; Name; Art => 5552; Name; Art => Nil

0: Initial output:  Name; Art => 3533; Name; Art => 4775; Name; Art => 501; Name; Art => 10234; Name; Art => 993; Name; Art => 1831; Name; Art => 7019; Name; Art => 11501; Name; Art => 8734; Name; Art => 6024; Name; Art => 10877; Name; Art => 12727; Name; Art => 9533; Name; Art => 114; Name; Art => 11543; Name; Art => 1845; Name; Art => 4721; Name; Art => 12024; Name; Art => 7059; Name; Art => 3792; Name; Art => 3891; Name; Art => 1748; Name; Art => 1994; Name; Art => 10018; Name; Art => 1021; Name; Art => 8450; Name; Art => 8017; Name; Art => 5413; Name; Art => 822; Name; Art => 12154; Name; Art => 5458; Name; Art => 5066; Name; Art => 6334; Name; Art => 3422; Name; Art => 9038; Name; Art => 11594; Name; Art => 3886; Name; Art => 3405; Name; Art => 7184; Name; Art => 1633; Name; Art => 9918; Name; Art => 1418; Name; Art => 2839; Name; Art => 6015; Name; Art => 1232; Name; Art => 11994; Name; Art => 5231; Name; Art => 4348; Name; Art => 9346; Name; Art => 4160; Name; Art => 2971; Name; Art => 8243; Name; Art => 2175; Name; Art => 2680; Name; Art => 5082; Name; Art => 12294; Name; Art => 11256; Name; Art => 10881; Name; Art => 2230; Name; Art => 3209; Name; Art => 11747; Name; Art => 4612; Name; Art => 5325; Name; Art => 7097; Name; Art => 9948; Name; Art => 10464; Name; Art => 10928; Name; Art => 4519; Name; Art => 11711; Name; Art => 550; Name; Art => 9410; Name; Art => 1401; Name; Art => 3681; Name; Art => 3918; Name; Art => 1828; Name; Art => 9498; Name; Art => 12361; Name; Art => 12122; Name; Art => 4940; Name; Art => 1517; Name; Art => 9998; Name; Art => 10956; Name; Art => 4195; Name; Art => 11448; Name; Art => 1438; Name; Art => 1879; Name; Art => 12535; Name; Art => 12038; Name; Art => 6273; Name; Art => 12408; Name; Art => 657; Name; Art => 394; Name; Art => 5522; Name; Art => 7668; Name; Art => 5003; Name; Art => 9562; Name; Art => 10536; Name; Art => 12754; Name; Art => 4190; Name; Art => 5552; Nil

----------------------------------------------------------------------------------
0:Rope_iter_name: Initial run:  time:0.0033s (unit cost 0)
0:Rope_iter_name: Initial run:  {dirty:0; clean:0; eval:301; create:301; tables:0}
--------------------
0:Rope_iter_name: No changes requested; Skipping interaction.

As we can see, the output is articulated in (nearly) the same uniform manner as the input. The only difference is that the list begins with a Name and Art, rather than ending with one around the final Nil case. Despite this, the articulations are spaced uniformly, as in the input. Furthermore, this works out even though the code for rope_of_list and list_of_rope shuffles around Names and Arts and data elements into and out of the intermediate tree structure.

What does this mean for rope_mergesort? We can view rope_mergesort as a simpler variation on list_of_rope where we don't perform the logic of the list_merge steps.

Since I've confirmed that this simpler composition works, I suggest that something is going wrong in the list_merge logic, or how it's interacting with the other steps. That seems like the next natural place to focus. If possible, it'd be nice to run list_merge on two small random input lists, in isolation.

matthewhammer pushed a commit that referenced this issue Feb 22, 2015
this 'improved' version doesn't yet fix issue #19
76fe106
matthewhammer referenced this issue Feb 22, 2015
wrote rope_mergesort_improved. ran delete-trailing-whitespace in emac…
9de3501 
…s (minor).

The new version seems much faster than the prior version:

Staffs-MacBook-Air% ./_build/Source/test/experiments.native --experiment Rope_mergesort_name
You requested experiment: Rope_mergesort_name

----------------------------------------------------------------------------------
0:Rope_mergesort_name: Initial run:time:0.4014s (unit cost 77894)
0:Rope_mergesort_name: Initial run:{dirty:0; clean:0; eval:35051; create:35051; tables:5001}
--------------------
0:Rope_mergesort_name: Interacting..
0:Rope_mergesort_name: Iteraction time: 6.345172 (sec)
Staffs-MacBook-Air% ./_build/Source/test/experiments.native --experiment Rope_mergesort_improved_name
You requested experiment: Rope_mergesort_improved_name

----------------------------------------------------------------------------------
0:Rope_mergesort_improved_name: Initial run:time:0.4287s (unit cost 77894)
0:Rope_mergesort_improved_name: Initial run:{dirty:0; clean:0; eval:44280; create:44280; tables:2}
--------------------
0:Rope_mergesort_improved_name: Interacting..
0:Rope_mergesort_improved_name: Iteraction time: 0.372463 (sec)
matthewhammer pushed a commit that referenced this issue Feb 22, 2015
more experimentation for issue #19
f4def44
@matthewhammer
Copy link
Contributor Author

Last commit seems to fix the problem for n=100. More experimentation is warranted. I have a bunch of unanswered questions right now. Here's the main one:

  • What happens when we vary n, and the random seed (--sample-num)? Does the improved version continue to work well?

In particular, I recommend writing a debugging check that automatically checks that the maximum gap between Name cases in the output is the same as the maximum gap in the input. (perhaps it's also worth checking the same property for Arts too). This is one way to formalize our notion of "granularity preservation". Then, we can script these tests and be more confident about how our code performs.

Once we confirm (by testing) that this always gives a uniformly articulated output, I think we can close this issue and move on to more experiments that go deeper.

@matthewhammer matthewhammer mentioned this issue Feb 22, 2015
Closed
@matthewhammer
Copy link
Contributor Author

Plan: After adding the check proposed above, let's close this issue and move on to these issues, in this order:

@kyleheadley kyleheadley mentioned this issue Feb 22, 2015
Closed
@kyleheadley
Copy link
Contributor

The improved merge sort doesn't seem to maintain granularity. For example:
./experiments.native --experiment Rope_mergesort_improved_name --n 1000 --gran 9 --num-changes 0 --debug-flags
has an extremely coarse-grained input and an extremely fine-grained output

@matthewhammer
Copy link
Contributor Author

Rope_mergesort_name

Initial output: Art => Name; 27; Art => Name; 386; Art => 519; Name; 554; Art => Name; 657; Art => Name; 683; Art => 737; 749; 753; 954; 1083; 1140; 1349; 1517; 1573; 1633; 1676; 1754; 1831; 1922; 2145; 2442; 2478; 2596; 2627; 2907; 2971; 3050; 3169; 3572; 3735; 3792; 3996; 4153; 4163; 4195; 4409; 4564; 4593; 4598; 4630; 5048; 5103; 5141; 5190; 5830; 5834; 5938; 6247; 6258; 6306; 6351; 6395; 6435; 6602; 6891; 6974; 6988; 7073; 7107; 7344; 8171; 8213; 8350; 8373; 8777; 8877; 9011; 9101; 9109; 9173; 9251; 9357; 9448; 9533; 9630; 9785; 9992; 10018; 10203; 10257; 10406; 10461; 10653; 10853; 11021; 11060; 11129; 11603; 11890; 11994; 12154; 12182; 12235; 12294; 12357; 12408; 12587; 12668; 12839; 12902; 12943; 13076; 13482; 13510; 13599; 13622; 13688; 13704; 13806; 13821; 13863; 13984; 14039; 14046; 14090; 14201; 14205; 14257; 14347; 14563; 15061; 15152; 15382; 15401; 15429; 15644; 16015; 16298; 16355; 16516; 16580; 16612; 16685; 16718; 16750; 16768; 16865; 16957; 16980; 17007; 17293; 17628; 17644; 17779; 17811; 17863; 17906; 17981; 18213; 18240; 18486; 18487; 18509; 18594; 18815; 19082; 19205; 19222; 19230; 19264; 19438; 19443; 19611; 19667; 19897; 19956; 20076; 20279; 20331; 20447; 20735; 20851; 20957; 20994; 21352; 21427; 21455; 21514; 21525; 21534; 21669; 21699; 21951; 22122; 22331; 22444; 22525; 22585; 22609; 22613; 22788; 23066; 23514; 23681; 23729; 23756; 23836; 24078; 24251; 24392; 24409; 24424; 24462; 24486; 24662; 24735; 24782; 24832; 25002; 25022; 25518; 25528; 25637; 25748; 25822; 25924; 25990; 26250; 26413; 26434; 26699; 26725; 26738; 26832; 27084; 27220; 27255; 27407; 27558; 27807; 27811; 27869; 27979; 28377; 28654; 28769; 28905; 28950; 29059; 29192; 29425; 29540; 29672; 29733; 29921; 30375; 30383; 30630; 30958; 31013; 31030; 31052; 31171; 31176; 31244; 31280; 31296; 31545; 31833; 32100; 32184; 32212; 32382; 32431; 32453; 32541; 32553; 32572; 32659; 32824; 32886; 32917; 33010; 33175; 33233; 33445; 33455; 33817; 33843; 34268; 34891; 35000; 35010; 35020; 35021; 35057; 35162; 35205; 35823; 36212; 36248; 36297; 36314; 36474; 36481; 36551; 36698; 37048; 37205; 37213; 37507; 37531; 37709; 37892; 38026; 38308; 38327; 38549; 38693; 38901; 38950; 39174; 39230; 39662; 39899; 40319; 40321; 40350; 40589; 40806; 40876; 40896; 41116; 41271; 41765; 41907; 42114; 42194; 42291; 42841; 42851; 42874; 43158; 43232; 43343; 43631; 43712; 43725; 43783; 43934; 43949; 44023; 44209; 44217; 44239; 44384; 44437; 44564; 44673; 44715; 45047; 45419; 45475; 45563; 45689; 45843; 46094; 46213; 46340; 46391; 46425; 46426; 46497; 46742; 46847; 46937; 47007; 47042; 47124; 47207; 47222; 47264; 47305; 47437; 47604; 47906; 48190; 48231; 48267; 48313; 48323; 48348; 48747; 48864; 48891; 48895; 48936; 49062; 49286; 49347; 49486; 49690; 49836; 49893; 49901; 49961; 50111; 50117; 50133; 50225; 50355; 50406; 50424; 50438; 50522; 50677; 50822; 51154; 51180; 51434; 52038; 52129; 52226; 52296; 52440; 52609; 52687; 52869; 52948; 53293; 53358; 53486; 53526; 53645; 53825; 53967; 54151; 54180; 54281; 54379; 54409; 54605; 54733; 54796; 54798; 54868; 54870; 54923; 55049; 55238; 55434; 55547; 55548; 55641; 55663; 55909; 55946; 56075; 56085; 56282; 56612; 56736; 56752; 56954; 56982; 56993; 57139; 57141; 57550; 57612; 57929; 58011; 58210; 58282; 58383; 58418; 58636; 58743; 58950; 58982; 59027; 59141; 59172; 59217; 59244; 59371; 59720; 59870; 60094; 60282; 60452; 60533; 60535; 60546; 60553; 60569; 60680; 60705; 60877; 61126; 61157; 61348; 61375; 61480; 61898; 62039; 62090; 62332; 62410; 62487; 62723; 62766; 62797; 63221; 63346; 63552; 63813; 63955; 63970; 64133; 64316; 65166; 65232; 65245; 65252; 65293; 65316; 65713; 66060; 66070; 66204; 66238; 66357; 66391; 66680; 66720; 66727; 66754; 66851; 66946; 67195; 67554; 67681; 67953; 68148; 68190; 68394; 68519; 68543; 68612; 68760; 68806; 69081; 69103; 69378; 69989; 70024; 70172; 70334; 70385; 70391; 70509; 70618; 70633; 70647; 70863; 71105; 71255; 71363; 71365; 71407; 71466; 71489; 71552; 71783; 71882; 71998; 72040; 72450; 72574; 72866; 72891; 73188; 73241; 73345; 73418; 73488; 73720; 74017; 74160; 74246; 74404; 74440; 74693; 74721; 75018; 75079; 75096; 75188; 75464; 75470; 75512; 75728; 75897; 75941; 76156; 76401; 76535; 76710; 76727; 76764; 76832; 76944; 77019; 77200; 77342; 77702; 78263; 78419; 78628; 78645; 78832; 78840; 79022; 79290; 79540; 79540; 79578; 79637; 79795; 80097; 80255; 80286; 80297; 80356; 80390; 80510; 80568; 80644; 81055; 81411; 81435; 81532; 81571; 81606; 81740; 82258; 82283; 82322; 82352; 82353; 82674; 82886; 83014; 83085; 83367; 83376; 83392; 83653; 83816; 83886; 83977; 83981; 83984; 84016; 84157; 84336; 84523; 84767; 84926; 84932; 85007; 85633; 86086; 86281; 86298; 86408; 86594; 86716; 86888; 86907; 87304; 87304; 87315; 87622; 87677; 87692; 88056; 88196; 88281; 88412; 88551; 88566; 88850; 88878; 88938; 89161; 89184; 89216; 89226; 89325; 89598; 89621; 89933; 90002; 90019; 90213; 90243; 90325; 90663; 90720; 90803; 90903; 90938; 91012; 91158; 91227; 91357; 91372; 91430; 91479; 91775; 91830; 92105; 92274; 92350; 92449; 92488; 92512; 92733; 92802; 92884; 93022; 93066; 93244; 93486; 93760; 94235; 94390; 94394; 94488; 94521; 94603; 94661; 94889; 94974; 95116; 95119; 95142; 95214; 95258; 95390; 95610; 95798; 95839; 95918; 95929; 96024; 96245; 96551; 96609; 97160; 97223; 97508; 97626; 97784; 97906; 97931; 97967; 98110; 98115; 98120; 98276; 98362; 98420; 98468; 98770; 98824; 98892; 98977; 99056; 99098; 99112; 99447; 99518; 100005; 100094; 100244; 100254; 100331; 100359; 100376; 100466; 100653; 100657; 100684; 100767; 101143; 101179; 101238; 101527; 101608; 101883; 101893; 101985; 102090; 102129; 102402; 102468; 102727; 102794; 102994; 103002; 103014; 103108; 103231; 103310; 103393; 103453; 103475; 103551; 103699; 103838; 103977; 103978; 104192; 104450; 104550; 104700; 104844; 105101; 105174; 105307; 105358; 105397; 105639; 105851; 105952; 105999; 106066; 106143; 106810; 106947; 107248; 107297; 107484; 107523; 107647; 108129; 108345; 108527; 108620; 108650; 108664; 108750; 108790; 109296; 109531; 109548; 109694; 109752; 110149; 110154; 110331; 110434; 110512; 110548; 110866; 111201; 111216; 111366; 111438; 111485; 111495; 111949; 112260; 112274; 112347; 112398; 112415; 112471; 112804; 112939; 113141; 113194; 113198; 113356; 113425; 113440; 113591; 113611; 113640; 114147; 114154; 114167; 114399; 114566; 114714; 114748; 114752; 115015; 115097; 115162; 115248; 115252; 115314; 115672; 115720; 115829; 116018; 116022; 116088; 116114; 116141; 116566; 116618; 116860; 117194; 117223; 117348; 117582; 117615; 117705; 117719; 117763; 117804; 117880; 117974; 118039; 118221; 118544; 118655; 118698; 118703; 118788; 118833; 119018; 119087; 119131; 119230; 119260; 119282; 119621; 119775; 119828; 119921; 120014; 120096; 120182; 120232; 120266; 120456; 120575; 120735; 120767; 120768; 120924; 120955; 120984; 121270; 121284; 121371; 121498; 121806; 121948; 122155; 122330; 122353; 122636; 122722; 122748; 122868; 122956; 123050; 123084; 123135; 123187; 123555; 123603; 123629; 123832; 124016; 124050; 124080; 124136; 124237; 124486; 124572; 124605; 124674; 124688; 124974; 125222; 125340; 125369; 125434; 125543; 125875; 126128; 126174; 126243; 126372; 126408; 126461; 126517; 126781; 126794; 127033; 127106; Nil

Improved version

I see output that is consistent with your characterization "extremely fine-grained":

0: Initial output:  Art => Name; 27; Art => Name; 386; Art => Name; 519; Art => Name; 554; Art => Name; 657; Art => Name; 683; Art => Name; 737; Art => Name; 749; Art => Name; 753; Art => Name; 954; Art => Name; 1083; Art => Name; 1140; Art => Name; 1349; Art => Name; 1517; Art => 1573; Name; 1633; Art => Name; 1676; Art => Name; 1754; Art => Name; 1831; Art => Name; 1922; Art => 2145; Name; 2442; Art => Name; 2478; Art => Name; 2596; Art => Name; 2627; Art => Name; 2907; Art => Name; 2971; Art => Name; 3050; Art => Name; 3169; Art => Name; 3572; Art => Name; 3735; Art => Name; 3792; Art => Name; 3996; Art => Name; 4153; Art => Name; 4163; Art => Name; 4195; Art => Name; 4409; Art => Name; 4564; Art => Name; 4593; Art => 4598; Name; 4630; Art => Name; 5048; Art => Name; 5103; Art => Name; 5141; Art => Name; 5190; Art => Name; 5830; Art => Name; 5834; Art => Name; 5938; Art => Name; 6247; Art => Name; 6258; Art => Name; 6306; Art => Name; 6351; Art => Name; 6395; Art => Name; 6435; Art => Name; 6602; Art => Name; 6891; Art => Name; 6974; Art => 6988; Name; 7073; Art => Name; 7107; Art => Name; 7344; Art => Name; 8171; Art => Name; 8213; Art => Name; 8350; Art => Name; 8373; Art => Name; 8777; Art => Name; 8877; Art => Name; 9011; Art => Name; 9101; Art => Name; 9109; Art => Name; 9173; Art => Name; 9251; Art => Name; 9357; Art => Name; 9448; Art => Name; 9533; Art => Name; 9630; Art => Name; 9785; Art => Name; 9992; Art => Name; 10018; Art => Name; 10203; Art => Name; 10257; Art => Name; 10406; Art => Name; 10461; Art => Name; 10653; Art => Name; 10853; Art => Name; 11021; Art => Name; 11060; Art => 11129; Name; 11603; Art => Name; 11890; Art => Name; 11994; Art => Name; 12154; Art => Name; 12182; Art => Name; 12235; Art => Name; 12294; Art => Name; 12357; Art => Name; 12408; Art => Name; 12587; Art => Name; 12668; Art => Name; 12839; Art => Name; 12902; Art => 12943; Name; 13076; Art => Name; 13482; Art => Name; 13510; Art => Name; 13599; Art => Name; 13622; Art => Name; 13688; Art => Name; 13704; Art => Name; 13806; Art => Name; 13821; Art => Name; 13863; Art => Name; 13984; Art => Name; 14039; Art => 14046; Name; 14090; Art => Name; 14201; Art => Name; 14205; Art => Name; 14257; Art => Name; 14347; Art => Name; 14563; Art => Name; 15061; Art => Name; 15152; Art => Name; 15382; Art => Name; 15401; Art => Name; 15429; Art => Name; 15644; Art => Name; 16015; Art => Name; 16298; Art => Name; 16355; Art => Name; 16516; Art => Name; 16580; Art => Name; 16612; Art => Name; 16685; Art => Name; 16718; Art => Name; 16750; Art => Name; 16768; Art => Name; 16865; Art => Name; 16957; Art => 16980; Name; 17007; Art => Name; 17293; Art => Name; 17628; Art => Name; 17644; Art => Name; 17779; Art => Name; 17811; Art => Name; 17863; Art => Name; 17906; Art => Name; 17981; Art => Name; 18213; Art => Name; 18240; Art => Name; 18486; Art => Name; 18487; Art => Name; 18509; Art => Name; 18594; Art => Name; 18815; Art => Name; 19082; Art => Name; 19205; Art => Name; 19222; Art => Name; 19230; Art => Name; 19264; Art => Name; 19438; Art => Name; 19443; Art => Name; 19611; Art => Name; 19667; Art => Name; 19897; Art => 19956; Name; 20076; Art => Name; 20279; Art => Name; 20331; Art => Name; 20447; Art => Name; 20735; Art => Name; 20851; Art => Name; 20957; Art => Name; 20994; Art => Name; 21352; Art => Name; 21427; Art => 21455; Name; 21514; Art => Name; 21525; Art => Name; 21534; Art => Name; 21669; Art => Name; 21699; Art => Name; 21951; Art => Name; 22122; Art => Name; 22331; Art => Name; 22444; Art => Name; 22525; Art => Name; 22585; Art => Name; 22609; Art => Name; 22613; Art => Name; 22788; Art => 23066; Name; 23514; Art => Name; 23681; Art => Name; 23729; Art => 23756; Name; 23836; Art => Name; 24078; Art => 24251; Name; 24392; Art => Name; 24409; Art => Name; 24424; Art => 24462; Name; 24486; Art => Name; 24662; Art => Name; 24735; Art => Name; 24782; Art => Name; 24832; Art => Name; 25002; Art => Name; 25022; Art => Name; 25518; Art => Name; 25528; Art => Name; 25637; Art => Name; 25748; Art => Name; 25822; Art => Name; 25924; Art => Name; 25990; Art => Name; 26250; Art => Name; 26413; Art => Name; 26434; Art => Name; 26699; Art => Name; 26725; Art => Name; 26738; Art => Name; 26832; Art => Name; 27084; Art => Name; 27220; Art => Name; 27255; Art => Name; 27407; Art => Name; 27558; Art => Name; 27807; Art => 27811; Name; 27869; Art => Name; 27979; Art => Name; 28377; Art => Name; 28654; Art => Name; 28769; Art => Name; 28905; Art => 28950; Name; 29059; Art => Name; 29192; Art => Name; 29425; Art => Name; 29540; Art => Name; 29672; Art => Name; 29733; Art => Name; 29921; Art => Name; 30375; Art => Name; 30383; Art => Name; 30630; Art => Name; 30958; Art => Name; 31013; Art => Name; 31030; Art => 31052; Name; 31171; Art => Name; 31176; Art => Name; 31244; Art => Name; 31280; Art => Name; 31296; Art => Name; 31545; Art => Name; 31833; Art => Name; 32100; Art => Name; 32184; Art => Name; 32212; Art => Name; 32382; Art => Name; 32431; Art => Name; 32453; Art => Name; 32541; Art => Name; 32553; Art => Name; 32572; Art => Name; 32659; Art => Name; 32824; Art => Name; 32886; Art => Name; 32917; Art => Name; 33010; Art => Name; 33175; Art => Name; 33233; Art => Name; 33445; Art => Name; 33455; Art => Name; 33817; Art => Name; 33843; Art => Name; 34268; Art => Name; 34891; Art => Name; 35000; Art => Name; 35010; Art => Name; 35020; Art => Name; 35021; Art => Name; 35057; Art => Name; 35162; Art => 35205; Name; 35823; Art => Name; 36212; Art => Name; 36248; Art => Name; 36297; Art => Name; 36314; Art => Name; 36474; Art => Name; 36481; Art => Name; 36551; Art => Name; 36698; Art => Name; 37048; Art => Name; 37205; Art => Name; 37213; Art => Name; 37507; Art => Name; 37531; Art => Name; 37709; Art => 37892; Name; 38026; Art => Name; 38308; Art => Name; 38327; Art => Name; 38549; Art => Name; 38693; Art => Name; 38901; Art => Name; 38950; Art => Name; 39174; Art => Name; 39230; Art => Name; 39662; Art => Name; 39899; Art => Name; 40319; Art => Name; 40321; Art => Name; 40350; Art => Name; 40589; Art => Name; 40806; Art => Name; 40876; Art => Name; 40896; Art => Name; 41116; Art => Name; 41271; Art => Name; 41765; Art => Name; 41907; Art => Name; 42114; Art => Name; 42194; Art => Name; 42291; Art => Name; 42841; Art => Name; 42851; Art => Name; 42874; Art => Name; 43158; Art => Name; 43232; Art => Name; 43343; Art => Name; 43631; Art => Name; 43712; Art => Name; 43725; Art => Name; 43783; Art => Name; 43934; Art => 43949; Name; 44023; Art => Name; 44209; Art => Name; 44217; Art => Name; 44239; Art => Name; 44384; Art => Name; 44437; Art => Name; 44564; Art => Name; 44673; Art => Name; 44715; Art => Name; 45047; Art => Name; 45419; Art => 45475; Name; 45563; Art => Name; 45689; Art => Name; 45843; Art => Name; 46094; Art => Name; 46213; Art => Name; 46340; Art => Name; 46391; Art => 46425; Name; 46426; Art => Name; 46497; Art => Name; 46742; Art => Name; 46847; Art => Name; 46937; Art => Name; 47007; Art => 47042; Name; 47124; Art => Name; 47207; Art => Name; 47222; Art => Name; 47264; Art => Name; 47305; Art => Name; 47437; Art => Name; 47604; Art => Name; 47906; Art => Name; 48190; Art => Name; 48231; Art => 48267; Name; 48313; Art => Name; 48323; Art => Name; 48348; Art => Name; 48747; Art => Name; 48864; Art => Name; 48891; Art => Name; 48895; Art => Name; 48936; Art => Name; 49062; Art => Name; 49286; Art => Name; 49347; Art => Name; 49486; Art => Name; 49690; Art => Name; 49836; Art => 49893; Name; 49901; Art => Name; 49961; Art => Name; 50111; Art => Name; 50117; Art => 50133; Name; 50225; Art => Name; 50355; Art => Name; 50406; Art => Name; 50424; Art => Name; 50438; Art => Name; 50522; Art => Name; 50677; Art => Name; 50822; Art => Name; 51154; Art => Name; 51180; Art => Name; 51434; Art => Name; 52038; Art => Name; 52129; Art => Name; 52226; Art => Name; 52296; Art => Name; 52440; Art => Name; 52609; Art => Name; 52687; Art => Name; 52869; Art => Name; 52948; Art => Name; 53293; Art => Name; 53358; Art => Name; 53486; Art => Name; 53526; Art => Name; 53645; Art => Name; 53825; Art => Name; 53967; Art => Name; 54151; Art => 54180; Name; 54281; Art => Name; 54379; Art => Name; 54409; Art => Name; 54605; Art => Name; 54733; Art => Name; 54796; Art => Name; 54798; Art => Name; 54868; Art => 54870; Name; 54923; Art => Name; 55049; Art => Name; 55238; Art => Name; 55434; Art => Name; 55547; Art => Name; 55548; Art => 55641; Name; 55663; Art => Name; 55909; Art => Name; 55946; Art => Name; 56075; Art => Name; 56085; Art => Name; 56282; Art => Name; 56612; Art => Name; 56736; Art => Name; 56752; Art => Name; 56954; Art => Name; 56982; Art => Name; 56993; Art => Name; 57139; Art => Name; 57141; Art => Name; 57550; Art => Name; 57612; Art => Name; 57929; Art => Name; 58011; Art => Name; 58210; Art => Name; 58282; Art => Name; 58383; Art => Name; 58418; Art => Name; 58636; Art => Name; 58743; Art => Name; 58950; Art => Name; 58982; Art => Name; 59027; Art => Name; 59141; Art => Name; 59172; Art => Name; 59217; Art => Name; 59244; Art => Name; 59371; Art => Name; 59720; Art => Name; 59870; Art => Name; 60094; Art => Name; 60282; Art => Name; 60452; Art => Name; 60533; Art => Name; 60535; Art => Name; 60546; Art => Name; 60553; Art => Name; 60569; Art => 60680; Name; 60705; Art => Name; 60877; Art => Name; 61126; Art => Name; 61157; Art => Name; 61348; Art => Name; 61375; Art => Name; 61480; Art => Name; 61898; Art => Name; 62039; Art => Name; 62090; Art => Name; 62332; Art => Name; 62410; Art => Name; 62487; Art => Name; 62723; Art => Name; 62766; Art => Name; 62797; Art => Name; 63221; Art => Name; 63346; Art => Name; 63552; Art => Name; 63813; Art => Name; 63955; Art => Name; 63970; Art => Name; 64133; Art => Name; 64316; Art => 65166; Name; 65232; Art => Name; 65245; Art => Name; 65252; Art => Name; 65293; Art => Name; 65316; Art => Name; 65713; Art => Name; 66060; Art => Name; 66070; Art => Name; 66204; Art => Name; 66238; Art => Name; 66357; Art => Name; 66391; Art => Name; 66680; Art => Name; 66720; Art => Name; 66727; Art => Name; 66754; Art => Name; 66851; Art => Name; 66946; Art => Name; 67195; Art => Name; 67554; Art => Name; 67681; Art => Name; 67953; Art => Name; 68148; Art => Name; 68190; Art => Name; 68394; Art => Name; 68519; Art => Name; 68543; Art => Name; 68612; Art => 68760; Name; 68806; Art => Name; 69081; Art => Name; 69103; Art => Name; 69378; Art => Name; 69989; Art => Name; 70024; Art => Name; 70172; Art => Name; 70334; Art => Name; 70385; Art => Name; 70391; Art => Name; 70509; Art => Name; 70618; Art => Name; 70633; Art => Name; 70647; Art => Name; 70863; Art => Name; 71105; Art => Name; 71255; Art => Name; 71363; Art => Name; 71365; Art => Name; 71407; Art => 71466; Name; 71489; Art => Name; 71552; Art => Name; 71783; Art => Name; 71882; Art => Name; 71998; Art => Name; 72040; Art => Name; 72450; Art => Name; 72574; Art => Name; 72866; Art => Name; 72891; Art => Name; 73188; Art => Name; 73241; Art => Name; 73345; Art => Name; 73418; Art => Name; 73488; Art => Name; 73720; Art => Name; 74017; Art => Name; 74160; Art => 74246; Name; 74404; Art => Name; 74440; Art => Name; 74693; Art => Name; 74721; Art => Name; 75018; Art => 75079; 75096; Name; 75188; Art => Name; 75464; Art => Name; 75470; Art => Name; 75512; Art => Name; 75728; Art => Name; 75897; Art => 75941; Name; 76156; Art => Name; 76401; Art => Name; 76535; Art => Name; 76710; Art => Name; 76727; Art => Name; 76764; Art => Name; 76832; Art => Name; 76944; Art => Name; 77019; Art => Name; 77200; Art => Name; 77342; Art => Name; 77702; Art => Name; 78263; Art => Name; 78419; Art => Name; 78628; Art => Name; 78645; Art => Name; 78832; Art => Name; 78840; Art => Name; 79022; Art => Name; 79290; Art => Name; 79540; Art => Name; 79540; Art => Name; 79578; Art => Name; 79637; Art => Name; 79795; Art => Name; 80097; Art => Name; 80255; Art => Name; 80286; Art => Name; 80297; Art => 80356; Name; 80390; Art => Name; 80510; Art => 80568; Name; 80644; Art => Name; 81055; Art => Name; 81411; Art => Name; 81435; Art => Name; 81532; Art => Name; 81571; Art => Name; 81606; Art => Name; 81740; Art => Name; 82258; Art => Name; 82283; Art => Name; 82322; Art => Name; 82352; Art => Name; 82353; Art => Name; 82674; Art => Name; 82886; Art => Name; 83014; Art => Name; 83085; Art => Name; 83367; Art => Name; 83376; Art => Name; 83392; Art => Name; 83653; Art => Name; 83816; Art => Name; 83886; Art => Name; 83977; Art => Name; 83981; Art => Name; 83984; Art => Name; 84016; Art => Name; 84157; Art => Name; 84336; Art => Name; 84523; Art => Name; 84767; Art => Name; 84926; Art => Name; 84932; Art => 85007; Name; 85633; Art => Name; 86086; Art => Name; 86281; Art => Name; 86298; Art => Name; 86408; Art => Name; 86594; Art => Name; 86716; Art => Name; 86888; Art => Name; 86907; Art => Name; 87304; Art => Name; 87304; Art => Name; 87315; Art => Name; 87622; Art => Name; 87677; Art => Name; 87692; Art => Name; 88056; Art => Name; 88196; Art => Name; 88281; Art => Name; 88412; Art => Name; 88551; Art => Name; 88566; Art => Name; 88850; Art => Name; 88878; Art => Name; 88938; Art => Name; 89161; Art => Name; 89184; Art => Name; 89216; Art => Name; 89226; Art => Name; 89325; Art => Name; 89598; Art => Name; 89621; Art => Name; 89933; Art => Name; 90002; Art => 90019; Name; 90213; Art => Name; 90243; Art => Name; 90325; Art => Name; 90663; Art => Name; 90720; Art => Name; 90803; Art => Name; 90903; Art => Name; 90938; Art => Name; 91012; Art => Name; 91158; Art => Name; 91227; Art => Name; 91357; Art => Name; 91372; Art => Name; 91430; Art => Name; 91479; Art => Name; 91775; Art => Name; 91830; Art => Name; 92105; Art => Name; 92274; Art => Name; 92350; Art => Name; 92449; Art => Name; 92488; Art => Name; 92512; Art => Name; 92733; Art => Name; 92802; Art => Name; 92884; Art => Name; 93022; Art => Name; 93066; Art => Name; 93244; Art => Name; 93486; Art => Name; 93760; Art => Name; 94235; Art => Name; 94390; Art => Name; 94394; Art => Name; 94488; Art => Name; 94521; Art => Name; 94603; Art => Name; 94661; Art => 94889; Name; 94974; Art => Name; 95116; Art => Name; 95119; Art => Name; 95142; Art => Name; 95214; Art => Name; 95258; Art => Name; 95390; Art => Name; 95610; Art => Name; 95798; Art => Name; 95839; Art => Name; 95918; Art => Name; 95929; Art => Name; 96024; Art => Name; 96245; Art => 96551; Name; 96609; Art => Name; 97160; Art => Name; 97223; Art => Name; 97508; Art => Name; 97626; Art => Name; 97784; Art => Name; 97906; Art => 97931; Name; 97967; Art => 98110; 98115; Name; 98120; Art => Name; 98276; Art => Name; 98362; Art => Name; 98420; Art => Name; 98468; Art => Name; 98770; Art => Name; 98824; Art => Name; 98892; Art => Name; 98977; Art => Name; 99056; Art => Name; 99098; Art => Name; 99112; Art => Name; 99447; Art => Name; 99518; Art => Name; 100005; Art => Name; 100094; Art => Name; 100244; Art => Name; 100254; Art => Name; 100331; Art => Name; 100359; Art => Name; 100376; Art => Name; 100466; Art => 100653; 100657; Name; 100684; Art => Name; 100767; Art => Name; 101143; Art => Name; 101179; Art => 101238; Name; 101527; Art => Name; 101608; Art => Name; 101883; Art => Name; 101893; Art => Name; 101985; Art => Name; 102090; Art => Name; 102129; Art => Name; 102402; Art => 102468; Name; 102727; Art => Name; 102794; Art => Name; 102994; Art => Name; 103002; Art => Name; 103014; Art => Name; 103108; Art => Name; 103231; Art => Name; 103310; Art => Name; 103393; Art => Name; 103453; Art => Name; 103475; Art => Name; 103551; Art => Name; 103699; Art => Name; 103838; Art => Name; 103977; Art => Name; 103978; Art => Name; 104192; Art => Name; 104450; Art => Name; 104550; Art => Name; 104700; Art => Name; 104844; Art => Name; 105101; Art => Name; 105174; Art => Name; 105307; Art => 105358; Name; 105397; Art => Name; 105639; Art => Name; 105851; Art => Name; 105952; Art => 105999; Name; 106066; Art => Name; 106143; Art => Name; 106810; Art => Name; 106947; Art => Name; 107248; Art => Name; 107297; Art => Name; 107484; Art => Name; 107523; Art => Name; 107647; Art => Name; 108129; Art => Name; 108345; Art => Name; 108527; Art => Name; 108620; Art => Name; 108650; Art => Name; 108664; Art => 108750; Name; 108790; Art => Name; 109296; Art => Name; 109531; Art => Name; 109548; Art => Name; 109694; Art => Name; 109752; Art => Name; 110149; Art => Name; 110154; Art => Name; 110331; Art => Name; 110434; Art => Name; 110512; Art => Name; 110548; Art => Name; 110866; Art => Name; 111201; Art => Name; 111216; Art => Name; 111366; Art => Name; 111438; Art => Name; 111485; Art => Name; 111495; Art => Name; 111949; Art => Name; 112260; Art => Name; 112274; Art => Name; 112347; Art => Name; 112398; Art => Name; 112415; Art => Name; 112471; Art => Name; 112804; Art => Name; 112939; Art => Name; 113141; Art => Name; 113194; Art => Name; 113198; Art => Name; 113356; Art => Name; 113425; Art => Name; 113440; Art => Name; 113591; Art => Name; 113611; Art => Name; 113640; Art => Name; 114147; Art => Name; 114154; Art => Name; 114167; Art => Name; 114399; Art => Name; 114566; Art => Name; 114714; Art => Name; 114748; Art => Name; 114752; Art => Name; 115015; Art => Name; 115097; Art => Name; 115162; Art => Name; 115248; Art => Name; 115252; Art => Name; 115314; Art => Name; 115672; Art => Name; 115720; Art => Name; 115829; Art => Name; 116018; Art => Name; 116022; Art => Name; 116088; Art => Name; 116114; Art => Name; 116141; Art => Name; 116566; Art => Name; 116618; Art => Name; 116860; Art => Name; 117194; Art => Name; 117223; Art => Name; 117348; Art => Name; 117582; Art => Name; 117615; Art => Name; 117705; Art => Name; 117719; Art => Name; 117763; Art => Name; 117804; Art => Name; 117880; Art => Name; 117974; Art => Name; 118039; Art => Name; 118221; Art => Name; 118544; Art => Name; 118655; Art => Name; 118698; Art => Name; 118703; Art => Name; 118788; Art => Name; 118833; Art => Name; 119018; Art => Name; 119087; Art => Name; 119131; Art => Name; 119230; Art => Name; 119260; Art => Name; 119282; Art => Name; 119621; Art => Name; 119775; Art => Name; 119828; Art => Name; 119921; Art => 120014; Name; 120096; Art => Name; 120182; Art => Name; 120232; Art => Name; 120266; Art => Name; 120456; Art => Name; 120575; Art => Name; 120735; Art => Name; 120767; Art => Name; 120768; Art => Name; 120924; Art => Name; 120955; Art => Name; 120984; Art => Name; 121270; Art => Name; 121284; Art => Name; 121371; Art => Name; 121498; Art => Name; 121806; Art => Name; 121948; Art => Name; 122155; Art => Name; 122330; Art => Name; 122353; Art => Name; 122636; Art => 122722; Name; 122748; Art => Name; 122868; Art => Name; 122956; Art => Name; 123050; Art => Name; 123084; Art => Name; 123135; Art => 123187; Name; 123555; Art => Name; 123603; Art => Name; 123629; Art => Name; 123832; Art => Name; 124016; Art => Name; 124050; Art => Name; 124080; Art => Name; 124136; Art => Name; 124237; Art => Name; 124486; Art => Name; 124572; Art => Name; 124605; Art => Name; 124674; Art => Name; 124688; Art => Name; 124974; Art => Name; 125222; Art => Name; 125340; Art => Name; 125369; Art => Name; 125434; Art => Name; 125543; Art => Name; 125875; Art => Name; 126128; Art => Name; 126174; Art => 126243; Name; 126372; Art => Name; 126408; Art => Name; 126461; Art => Name; 126517; Art => Name; 126781; Art => Name; 126794; Art => Name; 127033; Art => 127106; Nil

Updated variation of "improved"

I just tried a change to the Bin case of mergesort:
7a8a215

This looks closer to what seems desirable (fine at the start, coarser later in the list):

Art => Name; 27; Art => Name; 386; Art => 519; Name; 554; Art => Name; 657; Art => Name; 683; Art => 737; Name; 749; Art => 753; Name; 954; Art => 1083; Name; 1140; Art => Name; 1349; Art => 1517; 1573; 1633; 1676; 1754; 1831; Name; 1922; Art => 2145; 2442; 2478; 2596; 2627; 2907; 2971; 3050; 3169; 3572; 3735; 3792; 3996; 4153; Name; 4163; Art => 4195; 4409; Name; 4564; Art => Name; 4593; Art => 4598; 4630; 5048; 5103; 5141; 5190; 5830; 5834; 5938; 6247; 6258; 6306; 6351; 6395; 6435; 6602; 6891; 6974; 6988; 7073; 7107; 7344; 8171; 8213; 8350; 8373; 8777; 8877; 9011; 9101; 9109; 9173; 9251; 9357; 9448; 9533; 9630; 9785; 9992; 10018; 10203; 10257; 10406; 10461; 10653; 10853; 11021; 11060; 11129; 11603; 11890; 11994; 12154; 12182; 12235; 12294; 12357; 12408; 12587; 12668; 12839; 12902; 12943; Name; 13076; Art => 13482; 13510; 13599; 13622; 13688; 13704; 13806; 13821; 13863; 13984; 14039; 14046; 14090; 14201; 14205; 14257; 14347; 14563; 15061; 15152; 15382; 15401; 15429; 15644; 16015; 16298; 16355; 16516; 16580; 16612; 16685; 16718; 16750; 16768; 16865; 16957; 16980; 17007; 17293; 17628; Name; 17644; Art => 17779; 17811; 17863; 17906; 17981; 18213; 18240; 18486; 18487; 18509; 18594; 18815; 19082; 19205; 19222; 19230; 19264; 19438; 19443; 19611; 19667; 19897; 19956; 20076; 20279; 20331; 20447; 20735; 20851; 20957; 20994; 21352; 21427; 21455; 21514; 21525; 21534; 21669; 21699; 21951; 22122; 22331; 22444; 22525; 22585; 22609; Name; 22613; Art => 22788; 23066; 23514; 23681; 23729; 23756; 23836; 24078; 24251; 24392; 24409; 24424; 24462; 24486; 24662; 24735; 24782; 24832; 25002; 25022; 25518; 25528; 25637; 25748; 25822; 25924; 25990; 26250; 26413; 26434; 26699; 26725; 26738; 26832; 27084; 27220; 27255; 27407; 27558; 27807; 27811; 27869; 27979; 28377; 28654; 28769; 28905; 28950; 29059; 29192; 29425; 29540; 29672; 29733; 29921; 30375; 30383; 30630; 30958; 31013; 31030; 31052; 31171; 31176; 31244; 31280; 31296; 31545; 31833; 32100; 32184; 32212; 32382; 32431; 32453; 32541; 32553; 32572; 32659; 32824; 32886; 32917; 33010; 33175; 33233; 33445; 33455; 33817; 33843; 34268; 34891; 35000; 35010; 35020; 35021; 35057; 35162; 35205; 35823; 36212; 36248; 36297; 36314; 36474; 36481; 36551; 36698; 37048; 37205; 37213; 37507; 37531; 37709; 37892; 38026; 38308; 38327; 38549; 38693; 38901; 38950; 39174; 39230; 39662; 39899; 40319; 40321; 40350; 40589; 40806; 40876; 40896; 41116; 41271; 41765; 41907; 42114; 42194; 42291; 42841; 42851; 42874; 43158; 43232; 43343; 43631; 43712; 43725; 43783; 43934; 43949; 44023; 44209; 44217; 44239; 44384; 44437; 44564; 44673; 44715; 45047; 45419; 45475; 45563; 45689; 45843; 46094; 46213; 46340; 46391; 46425; 46426; 46497; 46742; 46847; 46937; 47007; 47042; 47124; 47207; 47222; Name; 47264; Art => 47305; 47437; 47604; Name; 47906; Art => 48190; 48231; 48267; 48313; 48323; 48348; 48747; 48864; 48891; 48895; 48936; 49062; 49286; 49347; 49486; 49690; 49836; 49893; 49901; 49961; 50111; 50117; 50133; 50225; 50355; 50406; 50424; 50438; 50522; 50677; 50822; 51154; 51180; 51434; 52038; 52129; 52226; 52296; 52440; 52609; 52687; 52869; 52948; 53293; 53358; 53486; 53526; 53645; 53825; 53967; 54151; 54180; 54281; 54379; 54409; 54605; 54733; 54796; 54798; 54868; 54870; 54923; 55049; 55238; 55434; 55547; 55548; 55641; 55663; 55909; 55946; 56075; 56085; 56282; 56612; 56736; 56752; 56954; 56982; 56993; 57139; 57141; 57550; 57612; 57929; 58011; 58210; 58282; 58383; 58418; 58636; 58743; 58950; 58982; 59027; 59141; 59172; 59217; 59244; 59371; 59720; 59870; 60094; 60282; 60452; 60533; 60535; 60546; 60553; 60569; 60680; 60705; 60877; 61126; 61157; 61348; 61375; 61480; 61898; 62039; 62090; 62332; 62410; 62487; 62723; 62766; 62797; 63221; 63346; 63552; 63813; 63955; 63970; 64133; Name; 64316; Art => 65166; 65232; 65245; 65252; 65293; 65316; 65713; 66060; 66070; 66204; 66238; 66357; 66391; 66680; 66720; 66727; 66754; 66851; 66946; 67195; 67554; 67681; 67953; 68148; 68190; 68394; 68519; 68543; 68612; 68760; 68806; 69081; 69103; 69378; 69989; 70024; 70172; 70334; 70385; 70391; 70509; 70618; 70633; 70647; 70863; 71105; 71255; 71363; 71365; 71407; 71466; 71489; 71552; 71783; 71882; 71998; 72040; 72450; 72574; 72866; 72891; 73188; 73241; 73345; 73418; 73488; 73720; 74017; 74160; 74246; 74404; 74440; 74693; 74721; 75018; 75079; 75096; 75188; 75464; 75470; 75512; 75728; 75897; 75941; 76156; 76401; 76535; 76710; 76727; 76764; 76832; 76944; 77019; 77200; 77342; 77702; 78263; 78419; 78628; 78645; 78832; 78840; 79022; 79290; 79540; 79540; 79578; 79637; 79795; 80097; 80255; 80286; Name; 80297; Art => 80356; 80390; 80510; 80568; 80644; 81055; 81411; 81435; 81532; 81571; 81606; 81740; 82258; 82283; 82322; 82352; 82353; 82674; 82886; 83014; 83085; 83367; 83376; 83392; 83653; 83816; 83886; 83977; 83981; 83984; 84016; 84157; 84336; 84523; 84767; 84926; 84932; 85007; 85633; 86086; 86281; 86298; 86408; 86594; 86716; 86888; 86907; 87304; 87304; 87315; 87622; 87677; 87692; 88056; 88196; 88281; 88412; 88551; 88566; 88850; 88878; 88938; 89161; 89184; 89216; 89226; 89325; 89598; 89621; 89933; 90002; 90019; 90213; 90243; 90325; 90663; 90720; 90803; 90903; 90938; 91012; 91158; 91227; 91357; 91372; 91430; 91479; 91775; 91830; 92105; 92274; 92350; 92449; 92488; 92512; 92733; 92802; 92884; 93022; 93066; 93244; 93486; 93760; 94235; 94390; 94394; 94488; 94521; 94603; 94661; 94889; 94974; 95116; 95119; 95142; 95214; 95258; 95390; 95610; 95798; 95839; 95918; 95929; 96024; 96245; 96551; 96609; 97160; 97223; 97508; 97626; 97784; 97906; 97931; 97967; 98110; 98115; 98120; 98276; 98362; 98420; 98468; 98770; 98824; 98892; 98977; 99056; 99098; 99112; 99447; 99518; 100005; 100094; 100244; 100254; 100331; 100359; 100376; 100466; 100653; 100657; 100684; 100767; 101143; 101179; 101238; 101527; 101608; 101883; 101893; 101985; 102090; 102129; 102402; 102468; 102727; 102794; 102994; 103002; 103014; 103108; 103231; 103310; 103393; 103453; 103475; 103551; 103699; 103838; 103977; 103978; 104192; 104450; 104550; 104700; 104844; 105101; 105174; 105307; 105358; 105397; 105639; 105851; 105952; 105999; 106066; 106143; 106810; 106947; 107248; 107297; 107484; 107523; 107647; 108129; 108345; 108527; 108620; 108650; 108664; 108750; 108790; 109296; 109531; 109548; 109694; 109752; 110149; 110154; 110331; 110434; 110512; 110548; 110866; 111201; 111216; 111366; 111438; 111485; 111495; 111949; 112260; 112274; 112347; 112398; 112415; 112471; 112804; 112939; 113141; 113194; 113198; 113356; 113425; 113440; 113591; 113611; 113640; 114147; 114154; 114167; 114399; 114566; 114714; 114748; 114752; 115015; 115097; 115162; 115248; 115252; 115314; 115672; 115720; 115829; 116018; 116022; 116088; 116114; 116141; 116566; 116618; 116860; 117194; 117223; 117348; 117582; 117615; 117705; 117719; 117763; 117804; 117880; 117974; 118039; 118221; 118544; 118655; 118698; 118703; 118788; 118833; Name; 119018; Art => 119087; 119131; 119230; 119260; 119282; 119621; 119775; 119828; 119921; 120014; 120096; 120182; 120232; 120266; 120456; 120575; 120735; 120767; 120768; 120924; 120955; 120984; 121270; 121284; 121371; 121498; 121806; 121948; 122155; 122330; 122353; 122636; 122722; 122748; 122868; 122956; 123050; 123084; 123135; 123187; 123555; 123603; 123629; 123832; 124016; 124050; 124080; 124136; 124237; 124486; 124572; 124605; 124674; 124688; 124974; 125222; 125340; 125369; 125434; 125543; 125875; 126128; 126174; 126243; Name; 126372; Art => 126408; 126461; 126517; 126781; 126794; 127033; 127106; Nil

@kyleheadley
Copy link
Contributor

Really, I think we just need to keep the names with their corresponding data items. Since list_merge is going to rearrange things, merge_sort would need to pass the name in the Name case rather than create a nart(this is what list_merge does). I think merge_sort can get by without any narts because list_merge is going to have one for every name.

matthewhammer referenced this issue Feb 24, 2015
coarser use of annotations in Rope_mergesort_improved
7a8a215
@kyleheadley
Copy link
Contributor

To update my previous comment: complex functions returning articulated data can't 'get by' without narts, because narts return an articulation point that suspends computation. Without it, even if there's an inner lazy function, the outer function will be fully computed. The inner function doesn't suspend everything, it returns a suspension of it's own computation.

@kyleheadley
Copy link
Contributor

commit de68251 and some later ones solved most of our issues with merge sort uniformity. There has not been a debug check, but composing merge sort with rope_length to get 'median' has the trend we expect to see with uniform articulation.

The problem was that we needed names in the rope's tree structure for it to remain lazy, and we needed names in the output list to be uniformly distributed for composability. Since the rope's data and tree structure are independent, it seemed like we needed more deterministic names for computation than the input or output had.

The solution presented is the realization that it is not Name's that we need more of, but Art's. We use Names as seeds to create new Arts, but it is not necessary for efficient computation to reseed. That is, in cases where a data-paired art was needed, we use Name(n,Art(...)), while with tree-paired arts, we used Art(...) and carried the available name as a parameter into a later recursion that needed a data-paired art. Unpaired Arts are dissolved on later recursive passes, removing the extra arts from the final output.

I'm closing this issue soon and continuing any conversation in issue #20 which deals with optimizing the median experiment.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@kyleheadley kyleheadley

Labels
critical path experiment
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@matthewhammer @kyleheadley