{"action":"created","issue":{"url":"https://api.github.com/repos/scala/scala/issues/6316","repository_url":"https://api.github.com/repos/scala/scala","labels_url":"https://api.github.com/repos/scala/scala/issues/6316/labels{/name}","comments_url":"https://api.github.com/repos/scala/scala/issues/6316/comments","events_url":"https://api.github.com/repos/scala/scala/issues/6316/events","html_url":"https://github.com/scala/scala/pull/6316","id":295514577,"number":6316,"title":"Reduce allocation and CPU usage in distinct","user":{"login":"pkukielka","id":1519649,"avatar_url":"https://avatars2.githubusercontent.com/u/1519649?v=4","gravatar_id":"","url":"https://api.github.com/users/pkukielka","html_url":"https://github.com/pkukielka","followers_url":"https://api.github.com/users/pkukielka/followers","following_url":"https://api.github.com/users/pkukielka/following{/other_user}","gists_url":"https://api.github.com/users/pkukielka/gists{/gist_id}","starred_url":"https://api.github.com/users/pkukielka/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pkukielka/subscriptions","organizations_url":"https://api.github.com/users/pkukielka/orgs","repos_url":"https://api.github.com/users/pkukielka/repos","events_url":"https://api.github.com/users/pkukielka/events{/privacy}","received_events_url":"https://api.github.com/users/pkukielka/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"szeiger","id":54262,"avatar_url":"https://avatars3.githubusercontent.com/u/54262?v=4","gravatar_id":"","url":"https://api.github.com/users/szeiger","html_url":"https://github.com/szeiger","followers_url":"https://api.github.com/users/szeiger/followers","following_url":"https://api.github.com/users/szeiger/following{/other_user}","gists_url":"https://api.github.com/users/szeiger/gists{/gist_id}","starred_url":"https://api.github.com/users/szeiger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/szeiger/subscriptions","organizations_url":"https://api.github.com/users/szeiger/orgs","repos_url":"https://api.github.com/users/szeiger/repos","events_url":"https://api.github.com/users/szeiger/events{/privacy}","received_events_url":"https://api.github.com/users/szeiger/received_events","type":"User","site_admin":false},"assignees":[{"login":"szeiger","id":54262,"avatar_url":"https://avatars3.githubusercontent.com/u/54262?v=4","gravatar_id":"","url":"https://api.github.com/users/szeiger","html_url":"https://github.com/szeiger","followers_url":"https://api.github.com/users/szeiger/followers","following_url":"https://api.github.com/users/szeiger/following{/other_user}","gists_url":"https://api.github.com/users/szeiger/gists{/gist_id}","starred_url":"https://api.github.com/users/szeiger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/szeiger/subscriptions","organizations_url":"https://api.github.com/users/szeiger/orgs","repos_url":"https://api.github.com/users/szeiger/repos","events_url":"https://api.github.com/users/szeiger/events{/privacy}","received_events_url":"https://api.github.com/users/szeiger/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/scala/scala/milestones/68","html_url":"https://github.com/scala/scala/milestone/68","labels_url":"https://api.github.com/repos/scala/scala/milestones/68/labels","id":2719693,"number":68,"title":"2.12.5","description":"Release lead: @lrytz. For feature development, please target 2.13.x. 2.12 is now restricted to bug fixes.\r\n\r\n2.12.5 status thread: https://contributors.scala-lang.org/t/getting-ready-for-2-12-5/1618","creator":{"login":"adriaanm","id":91083,"avatar_url":"https://avatars2.githubusercontent.com/u/91083?v=4","gravatar_id":"","url":"https://api.github.com/users/adriaanm","html_url":"https://github.com/adriaanm","followers_url":"https://api.github.com/users/adriaanm/followers","following_url":"https://api.github.com/users/adriaanm/following{/other_user}","gists_url":"https://api.github.com/users/adriaanm/gists{/gist_id}","starred_url":"https://api.github.com/users/adriaanm/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/adriaanm/subscriptions","organizations_url":"https://api.github.com/users/adriaanm/orgs","repos_url":"https://api.github.com/users/adriaanm/repos","events_url":"https://api.github.com/users/adriaanm/events{/privacy}","received_events_url":"https://api.github.com/users/adriaanm/received_events","type":"User","site_admin":false},"open_issues":5,"closed_issues":138,"state":"open","created_at":"2017-08-23T23:46:19Z","updated_at":"2018-03-12T11:53:20Z","due_on":"2018-03-09T08:00:00Z","closed_at":null},"comments":14,"created_at":"2018-02-08T13:37:21Z","updated_at":"2018-03-12T12:31:11Z","closed_at":null,"author_association":"NONE","pull_request":{"url":"https://api.github.com/repos/scala/scala/pulls/6316","html_url":"https://github.com/scala/scala/pull/6316","diff_url":"https://github.com/scala/scala/pull/6316.diff","patch_url":"https://github.com/scala/scala/pull/6316.patch"},"body":"<sup>THE FOLLOWING DISCLAIMER APPLIES TO ALL SOFTWARE CODE AND OTHER MATERIALS CONTRIBUTED IN CONNECTION WITH THIS SOFTWARE:\r\nTHIS SOFTWARE IS LICENSED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE AND ANY WARRANTY OF NON-INFRINGEMENT, ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THIS SOFTWARE MAY BE REDISTRIBUTED TO OTHERS ONLY BY EFFECTIVELY USING THIS OR ANOTHER EQUIVALENT DISCLAIMER IN ADDITION TO ANY OTHER REQUIRED LICENSE TERMS.\r\nONLY THE SOFTWARE CODE AND OTHER MATERIALS CONTRIBUTED IN CONNECTION WITH THIS SOFTWARE, IF ANY, THAT ARE ATTACHED TO (OR OTHERWISE ACCOMPANY) THIS SUBMISSION (AND ORDINARY COURSE CONTRIBUTIONS OF FUTURES PATCHES THERETO) ARE TO BE CONSIDERED A CONTRIBUTION. NO OTHER SOFTWARE CODE OR MATERIALS ARE A CONTRIBUTION.</sup>\r\n\r\nOur analyse of [method calls](https://github.com/pkukielka/scala-collections-usage/tree/master/run1) during compilation of akka-actor shows that `distinct` is quite often used in scalac .\r\nLooking at `distinct` implementation one can see some optimization potential.\r\nIndeed, our [benchmarks](https://gist.github.com/pkukielka/99415b405bbff46e63db0e24706674f9) shows that [some implementations](https://github.com/rorygraves/scalac_perf/compare/e12ac748cda072a42c67cfd0a0151947fc9c36e3...be3b71ce16bb03947ca4e22afbc4beda4d9c94fa) can be often few times faster than orginal.\r\n\r\nWith minimal changes it's possible to apply three optimizations:\r\n- in case of empty or one-element collection return the same collection\r\n- add element to hashmap and check if it was already present in one method call\r\n- rewrite for loop to while loop\r\n\r\nThis results in significant performance improvement for both small and big collection with different dupplication patterns:\r\n\r\n\r\n**For quick insight look at the `Improvement` column which should percentage change between old and new implementation.**\r\n\r\n[Mode: avgt, Samples: 20, Unit: ns/op]\r\n\r\n**Data set**|**Score**|**Score Error (99.9%)**|**Improved Score**|**Improved Score Error (99.9%)**|**collectionType**|**size**|**How many times better**\r\n:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:\r\ntestDistinct|119.124387|3.782612|5.473815|0.465669|List|0|21.76258916\r\ntestDistinct|131.299917|0.659902|6.806075|0.009184|List|1|19.29157657\r\ntestDistinct|419.346876|1.182202|111.085705|1.785557|List|2|3.774985053\r\ntestDistinct|651.38351|239.789497|205.369536|4.922485|List|5|3.17176307\r\ntestDistinct|1143.236763|528.276372|342.405162|3.023563|List|10|3.338842079\r\ntestDistinct|1488.195073|9.139275|959.674248|2.418931|List|20|1.550729402\r\ntestDistinct|6956.963326|2629.908008|2659.404221|14.693761|List|50|2.615985667\r\ntestDistinct|19447.08487|47.531198|8287.893915|104.333954|List|100|2.346444714\r\ntestDistinct|243925.5283|1467.593679|99091.87734|1807.973507|List|1000|2.461609719\r\ntestDistinct|149.871507|0.370222|9.315466|0.005927|Vector|0|16.08846052\r\ntestDistinct|280.244666|1.235416|9.188745|0.574197|Vector|1|30.49868791\r\ntestDistinct|257.486692|55.398885|116.549719|1.189176|Vector|2|2.209243353\r\ntestDistinct|722.771906|243.722688|185.44772|1.318112|Vector|5|3.897442934\r\ntestDistinct|562.767071|43.87787|298.561493|1.332823|Vector|10|1.884928513\r\ntestDistinct|3957.371712|73.244357|797.385485|10.303355|Vector|20|4.962934222\r\ntestDistinct|9979.052671|123.242694|3522.165186|9.682687|Vector|50|2.833215407\r\ntestDistinct|19817.48244|307.433012|7517.95571|14.016549|Vector|100|2.63602011\r\ntestDistinct|246771.4508|2031.381824|97305.00248|537.546439|Vector|1000|2.536061297\r\ntestFirstDuplicated|212.249697|54.39969|102.382118|0.253651|List|1|2.073112973\r\ntestFirstDuplicated|441.36795|1.26052|138.002328|0.306794|List|2|3.198264525\r\ntestFirstDuplicated|665.73307|246.229021|243.622922|3.11787|List|5|2.732637243\r\ntestFirstDuplicated|1785.399952|4.37311|417.027034|9.616366|List|10|4.281257104\r\ntestFirstDuplicated|1455.120544|4.730661|974.694262|51.995152|List|20|1.492899467\r\ntestFirstDuplicated|6902.173029|2718.231134|3240.682612|343.48382|List|50|2.129851595\r\ntestFirstDuplicated|19561.32407|48.516768|7425.096883|15.699116|List|100|2.634487385\r\ntestFirstDuplicated|240365.8931|492.714976|101477.8673|1669.08497|List|1000|2.368653378\r\ntestFirstDuplicated|243.529946|57.938633|149.689588|2.288673|Vector|1|1.626899701\r\ntestFirstDuplicated|291.76678|47.187571|172.794061|0.310895|Vector|2|1.688523195\r\ntestFirstDuplicated|471.328125|20.670341|249.05323|1.295457|Vector|5|1.892479471\r\ntestFirstDuplicated|1340.84428|599.580399|386.730292|1.696513|Vector|10|3.467130214\r\ntestFirstDuplicated|4080.841558|54.36155|923.73217|18.834701|Vector|20|4.417775726\r\ntestFirstDuplicated|10065.68949|32.664908|3630.918958|22.030211|Vector|50|2.772215411\r\ntestFirstDuplicated|19939.59795|149.62367|7808.358933|153.52384|Vector|100|2.553622102\r\ntestFirstDuplicated|244611.2962|4981.028841|96336.71664|2097.386163|Vector|1000|2.539128432\r\ntestInterleavedDuplication|114.895024|1.523093|5.803648|0.097148|List|0|19.79703524\r\ntestInterleavedDuplication|281.400133|0.537693|114.72468|0.63568|List|1|2.452829966\r\ntestInterleavedDuplication|495.931129|4.344683|176.708331|0.92745|List|2|2.806495462\r\ntestInterleavedDuplication|1065.30471|10.695993|356.819876|2.149827|List|5|2.985553165\r\ntestInterleavedDuplication|859.165568|12.742563|656.601214|5.05204|List|10|1.308504385\r\ntestInterleavedDuplication|2159.832263|84.121183|1509.527801|4.822354|List|20|1.430799924\r\ntestInterleavedDuplication|17482.80791|87.0037|5512.622554|240.416536|List|50|3.171413921\r\ntestInterleavedDuplication|34929.92933|123.885887|10234.555|1384.04829|List|100|3.412940704\r\ntestInterleavedDuplication|412378.9812|1690.82269|136513.8509|544.622241|List|1000|3.020784912\r\ntestInterleavedDuplication|150.590868|1.035151|9.327966|0.015526|Vector|0|16.14401982\r\ntestInterleavedDuplication|314.915394|11.349894|149.634182|1.000295|Vector|1|2.104568554\r\ntestInterleavedDuplication|370.375975|0.96853|195.724444|9.237389|Vector|2|1.89233377\r\ntestInterleavedDuplication|535.564215|42.294279|361.885647|2.528104|Vector|5|1.479926655\r\ntestInterleavedDuplication|872.242236|43.875729|622.503737|2.341339|Vector|10|1.401183935\r\ntestInterleavedDuplication|6978.079848|56.344489|1594.292837|20.293621|Vector|20|4.37691225\r\ntestInterleavedDuplication|17791.9082|115.652917|5318.002869|9.04746|Vector|50|3.345599586\r\ntestInterleavedDuplication|34941.26812|158.698846|9163.83438|82.942034|Vector|100|3.812952817\r\ntestInterleavedDuplication|425170.6373|3218.648832|134233.3339|542.83717|Vector|1000|3.167399818\r\ntestLastDuplicated|272.300284|0.51746|102.197482|0.127542|List|1|2.664451987\r\ntestLastDuplicated|442.967792|4.068168|137.590444|0.269233|List|2|3.219466259\r\ntestLastDuplicated|685.463462|227.160124|257.12077|2.327267|List|5|2.665920229\r\ntestLastDuplicated|1250.331211|467.195299|405.985246|1.853387|List|10|3.079745442\r\ntestLastDuplicated|1480.03147|9.875511|938.898859|7.856041|List|20|1.57634814\r\ntestLastDuplicated|6788.608236|2735.504537|2600.056078|19.690071|List|50|2.610946854\r\ntestLastDuplicated|19576.3761|78.155975|7475.169284|66.649266|List|100|2.618853883\r\ntestLastDuplicated|241823.0104|859.158335|100522.8587|685.90708|List|1000|2.405651942\r\ntestLastDuplicated|309.098464|3.732318|146.628249|0.465306|Vector|1|2.108041705\r\ntestLastDuplicated|345.236399|1.895398|174.619845|3.875954|Vector|2|1.977074249\r\ntestLastDuplicated|353.639946|3.42118|270.822248|4.879046|Vector|5|1.30580094\r\ntestLastDuplicated|657.243835|4.408845|394.964648|7.754474|Vector|10|1.664057374\r\ntestLastDuplicated|4140.453165|80.873441|930.513606|15.442861|Vector|20|4.449642798\r\ntestLastDuplicated|10091.01293|29.096688|3674.934723|16.249434|Vector|50|2.745902631\r\ntestLastDuplicated|19511.18417|45.673976|7800.335083|176.481875|Vector|100|2.501326413\r\ntestLastDuplicated|242025.3832|2343.536965|96009.02256|1520.852319|Vector|1000|2.520860819\r\ntestSequentialDuplication|143.564341|48.191949|5.676425|0.293955|List|0|25.29133055\r\ntestSequentialDuplication|152.27668|1.296187|101.788634|0.442254|List|1|1.49600868\r\ntestSequentialDuplication|473.724937|6.726859|153.101322|2.667712|List|2|3.094192335\r\ntestSequentialDuplication|1037.105222|2.451904|324.258859|1.57431|List|5|3.1983867\r\ntestSequentialDuplication|769.944841|3.599434|558.406558|2.84739|List|10|1.378824854\r\ntestSequentialDuplication|2068.105679|7.760031|1363.43695|41.434367|List|20|1.516832648\r\ntestSequentialDuplication|16595.62694|54.668626|4626.562572|154.118451|List|50|3.587031773\r\ntestSequentialDuplication|32890.22446|131.804702|8328.726537|685.625435|List|100|3.94901001\r\ntestSequentialDuplication|380103.5703|810.993503|117674.6947|1562.0622|List|1000|3.230121575\r\ntestSequentialDuplication|155.767004|3.623653|9.353921|0.114174|Vector|0|16.65258922\r\ntestSequentialDuplication|406.801776|89.80307|146.881459|0.379238|Vector|1|2.769592424\r\ntestSequentialDuplication|359.047721|1.927116|191.828954|0.895973|Vector|2|1.871707652\r\ntestSequentialDuplication|1137.33621|525.866721|320.877715|0.6919|Vector|5|3.544453718\r\ntestSequentialDuplication|2044.567858|1039.802297|537.001067|2.636652|Vector|10|3.80738137\r\ntestSequentialDuplication|6922.492889|187.575248|1366.110962|35.571966|Vector|20|5.06729913\r\ntestSequentialDuplication|16905.23725|54.094223|4806.313655|12.637983|Vector|50|3.517297968\r\ntestSequentialDuplication|33323.07682|103.70706|8985.496771|654.795642|Vector|100|3.708540293\r\ntestSequentialDuplication|385329.0531|1115.129476|113590.9835|395.455652|Vector|1000|3.392250346\r\n\r\n\r\n[s: waiting for update, need to return a copy for mutable collecitons]"},"comment":{"url":"https://api.github.com/repos/scala/scala/issues/comments/372293671","html_url":"https://github.com/scala/scala/pull/6316#issuecomment-372293671","issue_url":"https://api.github.com/repos/scala/scala/issues/6316","id":372293671,"user":{"login":"szeiger","id":54262,"avatar_url":"https://avatars3.githubusercontent.com/u/54262?v=4","gravatar_id":"","url":"https://api.github.com/users/szeiger","html_url":"https://github.com/szeiger","followers_url":"https://api.github.com/users/szeiger/followers","following_url":"https://api.github.com/users/szeiger/following{/other_user}","gists_url":"https://api.github.com/users/szeiger/gists{/gist_id}","starred_url":"https://api.github.com/users/szeiger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/szeiger/subscriptions","organizations_url":"https://api.github.com/users/szeiger/orgs","repos_url":"https://api.github.com/users/szeiger/repos","events_url":"https://api.github.com/users/szeiger/events{/privacy}","received_events_url":"https://api.github.com/users/szeiger/received_events","type":"User","site_admin":false},"created_at":"2018-03-12T12:31:11Z","updated_at":"2018-03-12T12:31:11Z","author_association":"CONTRIBUTOR","body":"I've pushed an update so we can get this merged."}}
{"actor":{"display_login":"szeiger"}}