{"action":"created","issue":{"url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1378","repository_url":"https://api.github.com/repos/Microsoft/visualfsharp","labels_url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1378/labels{/name}","comments_url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1378/comments","events_url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1378/events","html_url":"https://github.com/Microsoft/visualfsharp/pull/1378","id":167273226,"number":1378,"title":"More Efficient algorithm for List.groupBy ","user":{"login":"liboz","id":13482895,"avatar_url":"https://avatars.githubusercontent.com/u/13482895?v=3","gravatar_id":"","url":"https://api.github.com/users/liboz","html_url":"https://github.com/liboz","followers_url":"https://api.github.com/users/liboz/followers","following_url":"https://api.github.com/users/liboz/following{/other_user}","gists_url":"https://api.github.com/users/liboz/gists{/gist_id}","starred_url":"https://api.github.com/users/liboz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liboz/subscriptions","organizations_url":"https://api.github.com/users/liboz/orgs","repos_url":"https://api.github.com/users/liboz/repos","events_url":"https://api.github.com/users/liboz/events{/privacy}","received_events_url":"https://api.github.com/users/liboz/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/Microsoft/visualfsharp/labels/cla-already-signed","name":"cla-already-signed","color":"009800"}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":7,"created_at":"2016-07-25T03:01:33Z","updated_at":"2016-07-25T13:22:07Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/Microsoft/visualfsharp/pulls/1378","html_url":"https://github.com/Microsoft/visualfsharp/pull/1378","diff_url":"https://github.com/Microsoft/visualfsharp/pull/1378.diff","patch_url":"https://github.com/Microsoft/visualfsharp/pull/1378.patch"},"body":"Also fixes a related unit test.\r\n\r\nHere's a gist showing the difference: https://gist.github.com/liboz/d1f2ef35c9c46a5019127bd3b4f99d17\r\nNote that I just made a clone of the original List.groupBy called List.groupBy2 for the purposes of the test\r\n\r\nThere seems to be inconsistent inlining in the List module, but I inlined the stuff I did here because the original was inlined.\r\n\r\nWill edit in a benchmark with BenchmarkDotNet in a couple hours.\r\n\r\nEDIT:\r\n\r\nHere's the source code for the BenchmarkDotNet: https://gist.github.com/liboz/d1d513c378aefbc78889f2db27f2800f\r\nand I pasted the results:. It's mostly the same test suite as the fsi gist I have above.\r\n\r\nCLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]\r\nGC=Concurrent Workstation\r\nJitModules=clrjit-v4.6.1080.0\r\n\r\nType=groupBy  Mode=Throughput  GarbageCollection=Concurrent Workstation  \r\n\r\n                 Method |    count |                 Median |              StdDev |     Gen 0 |    Gen 1 |  Gen 2 | Bytes Allocated/Op |\r\n----------------------- |--------- |----------------------- |-------------------- |---------- |--------- |------- |------------------- |\r\n         groupByModulus |       10 |            705.8428 ns |          42.6993 ns |      0.03 |        - |      - |             469.55 |\r\n groupByOriginalModulus |       10 |          1,839.0410 ns |          93.7306 ns |      0.04 |        - |      - |             763.10 |\r\n                groupBy |       10 |          1,255.7102 ns |          61.1925 ns |      0.07 |        - |      - |           1,232.88 |\r\n        groupByOriginal |       10 |          3,987.1858 ns |         160.5903 ns |      0.09 |        - |      - |           1,610.93 |\r\n           groupByMixed |       10 |        582,407.5966 ns |      30,728.3895 ns |      6.92 |     4.30 |      - |         337,104.46 |\r\n   groupByOriginalMixed |       10 |        736,841.4709 ns |      37,799.7629 ns |      8.59 |     5.55 |      - |         379,064.74 |\r\n         groupByModulus |      100 |          4,406.7663 ns |         169.0106 ns |      0.15 |        - |      - |           2,729.34 |\r\n groupByOriginalModulus |      100 |          7,344.0738 ns |         255.2806 ns |      0.20 |        - |      - |           3,557.86 |\r\n                groupBy |      100 |         10,367.8809 ns |         381.3533 ns |      0.62 |        - |      - |          11,856.14 |\r\n        groupByOriginal |      100 |         32,412.6751 ns |       1,597.1644 ns |      0.85 |        - |      - |          16,286.61 |\r\n           groupByMixed |      100 |        572,375.6532 ns |      22,456.2116 ns |      6.59 |     4.49 |      - |         332,997.24 |\r\n   groupByOriginalMixed |      100 |        741,901.9452 ns |      35,264.1825 ns |      5.69 |     4.86 |      - |         288,494.12 |\r\n         groupByModulus |    10000 |        525,283.8138 ns |      28,838.6492 ns |      5.29 |     3.39 |      - |         254,351.92 |\r\n groupByOriginalModulus |    10000 |        664,096.0494 ns |      26,908.3865 ns |      7.44 |     4.89 |      - |         328,690.80 |\r\n                groupBy |    10000 |      2,761,663.8746 ns |      64,557.9006 ns |     17.59 |        - |  17.50 |       1,213,041.70 |\r\n        groupByOriginal |    10000 |      5,317,136.8731 ns |     254,277.2331 ns |     20.54 |     4.88 |  16.69 |       1,516,082.90 |\r\n           groupByMixed |    10000 |      1,300,531.4866 ns |      61,808.7686 ns |     11.74 |    11.40 |      - |         794,595.49 |\r\n   groupByOriginalMixed |    10000 |      1,630,609.7672 ns |      73,949.6140 ns |     16.05 |    11.84 |      - |         896,730.53 |\r\n         groupByModulus |  1000000 |    231,907,137.1163 ns |   4,046,452.1418 ns |    301.91 |   225.42 | 108.98 |      19,284,699.38 |\r\n groupByOriginalModulus |  1000000 |    231,722,288.2738 ns |   2,443,656.7017 ns |    274.10 |   188.98 | 119.02 |      19,670,409.44 |\r\n                groupBy |  1000000 |    804,278,639.9725 ns |  22,017,307.4191 ns |    656.45 |   578.39 | 118.52 |      64,999,778.71 |\r\n        groupByOriginal |  1000000 |  1,191,626,049.8725 ns |  13,775,845.9996 ns |  1,125.25 |   736.46 | 136.33 |      87,812,227.41 |\r\n           groupByMixed |  1000000 |    688,763,766.6713 ns |  21,067,158.4101 ns |    781.33 |   661.33 | 146.00 |      52,232,920.00 |\r\n   groupByOriginalMixed |  1000000 |    635,669,734.7538 ns |  22,632,039.2767 ns |    964.44 |   775.56 | 209.78 |      69,421,290.06 |\r\n         groupByModulus | 10000000 |  2,536,577,746.9513 ns |  62,383,748.7772 ns |  1,919.75 | 3,452.31 | 148.25 |     192,795,744.98 |\r\n groupByOriginalModulus | 10000000 |  2,696,990,104.5825 ns |  58,256,910.0715 ns |  3,744.00 | 3,749.00 | 358.00 |     326,685,879.41 |\r\n                groupBy | 10000000 |  7,250,552,647.7425 ns | 245,053,956.2612 ns |  7,797.71 | 8,358.86 | 212.00 |     808,063,523.82 |\r\n        groupByOriginal | 10000000 | 11,373,338,310.5325 ns | 255,350,492.3006 ns | 11,926.00 | 8,566.67 | 192.00 |     931,257,868.36 |\r\n           groupByMixed | 10000000 |  6,623,608,707.1300 ns | 212,181,053.7540 ns |  6,827.45 | 7,176.06 | 180.74 |     503,127,305.38 |\r\n   groupByOriginalMixed | 10000000 |  6,849,243,043.4850 ns | 134,781,808.1311 ns |  7,022.13 | 7,195.38 | 198.00 |     588,532,280.50 |\r\n"},"comment":{"url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/comments/234951121","html_url":"https://github.com/Microsoft/visualfsharp/pull/1378#issuecomment-234951121","issue_url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1378","id":234951121,"user":{"login":"forki","id":57396,"avatar_url":"https://avatars.githubusercontent.com/u/57396?v=3","gravatar_id":"","url":"https://api.github.com/users/forki","html_url":"https://github.com/forki","followers_url":"https://api.github.com/users/forki/followers","following_url":"https://api.github.com/users/forki/following{/other_user}","gists_url":"https://api.github.com/users/forki/gists{/gist_id}","starred_url":"https://api.github.com/users/forki/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/forki/subscriptions","organizations_url":"https://api.github.com/users/forki/orgs","repos_url":"https://api.github.com/users/forki/repos","events_url":"https://api.github.com/users/forki/events{/privacy}","received_events_url":"https://api.github.com/users/forki/received_events","type":"User","site_admin":false},"created_at":"2016-07-25T13:22:07Z","updated_at":"2016-07-25T13:22:07Z","body":"but it still crashed!? do we ignore that?"}}
{"actor":{"display_login":"forki"}}