{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/corefx/issues/11208","repository_url":"https://api.github.com/repos/dotnet/corefx","labels_url":"https://api.github.com/repos/dotnet/corefx/issues/11208/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/corefx/issues/11208/comments","events_url":"https://api.github.com/repos/dotnet/corefx/issues/11208/events","html_url":"https://github.com/dotnet/corefx/pull/11208","id":173647694,"number":11208,"title":"Improve Enumerable.ToArray to avoid excessive copying for lazy enumerables","user":{"login":"jamesqo","id":9159214,"avatar_url":"https://avatars.githubusercontent.com/u/9159214?v=3","gravatar_id":"","url":"https://api.github.com/users/jamesqo","html_url":"https://github.com/jamesqo","followers_url":"https://api.github.com/users/jamesqo/followers","following_url":"https://api.github.com/users/jamesqo/following{/other_user}","gists_url":"https://api.github.com/users/jamesqo/gists{/gist_id}","starred_url":"https://api.github.com/users/jamesqo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jamesqo/subscriptions","organizations_url":"https://api.github.com/users/jamesqo/orgs","repos_url":"https://api.github.com/users/jamesqo/repos","events_url":"https://api.github.com/users/jamesqo/events{/privacy}","received_events_url":"https://api.github.com/users/jamesqo/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/dotnet/corefx/labels/cla-already-signed","name":"cla-already-signed","color":"009800"}],"state":"open","locked":false,"assignee":{"login":"VSadov","id":8218165,"avatar_url":"https://avatars.githubusercontent.com/u/8218165?v=3","gravatar_id":"","url":"https://api.github.com/users/VSadov","html_url":"https://github.com/VSadov","followers_url":"https://api.github.com/users/VSadov/followers","following_url":"https://api.github.com/users/VSadov/following{/other_user}","gists_url":"https://api.github.com/users/VSadov/gists{/gist_id}","starred_url":"https://api.github.com/users/VSadov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/VSadov/subscriptions","organizations_url":"https://api.github.com/users/VSadov/orgs","repos_url":"https://api.github.com/users/VSadov/repos","events_url":"https://api.github.com/users/VSadov/events{/privacy}","received_events_url":"https://api.github.com/users/VSadov/received_events","type":"User","site_admin":false},"assignees":[{"login":"VSadov","id":8218165,"avatar_url":"https://avatars.githubusercontent.com/u/8218165?v=3","gravatar_id":"","url":"https://api.github.com/users/VSadov","html_url":"https://github.com/VSadov","followers_url":"https://api.github.com/users/VSadov/followers","following_url":"https://api.github.com/users/VSadov/following{/other_user}","gists_url":"https://api.github.com/users/VSadov/gists{/gist_id}","starred_url":"https://api.github.com/users/VSadov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/VSadov/subscriptions","organizations_url":"https://api.github.com/users/VSadov/orgs","repos_url":"https://api.github.com/users/VSadov/repos","events_url":"https://api.github.com/users/VSadov/events{/privacy}","received_events_url":"https://api.github.com/users/VSadov/received_events","type":"User","site_admin":false}],"milestone":null,"comments":8,"created_at":"2016-08-28T13:50:41Z","updated_at":"2016-09-18T05:01:15Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/dotnet/corefx/pulls/11208","html_url":"https://github.com/dotnet/corefx/pull/11208","diff_url":"https://github.com/dotnet/corefx/pull/11208.diff","patch_url":"https://github.com/dotnet/corefx/pull/11208.patch"},"body":"The idea that instead of resizing the array (aka throwing it out and allocating a new one) and re-copying the data every time the sequence doesn't fit, we can instead keep the old array around, allocate a new one of size * 2, and just continue reading into the new array at index 0. This will require keeping around a list of arrays we've filled up so far, however the overhead of this list will be substantially less than the size of the data itself.\r\n\r\nA visualization of what I'm talking about for a 300-length enumerable:\r\n\r\n```\r\nFirst array: [items 0-31]\r\n\r\nList of arrays:\r\n[0]: [items 32-63]\r\n[1]: [items 64-127]\r\n[2]: [items 128-255]\r\n\r\nCurrent array: [items 256-299]\r\n```\r\n\r\n(I also put this in the comments to help future readers understand.)\r\n\r\nThen when we need the final array to return from the method, we just calculate `first.Length + list.Sum(a => a.Length) + indexWeFinishedReadingIntoInCurrentArray`, pre-allocate an array of that size, and then copy each of the arrays into that array.\r\n\r\nI opted to only use this algorithm for enumerables of > length 32, since for smaller sizes it will lead to increased fragmentation, and the overhead of the list allocation will probably be noticeable in comparison to, say, 20 elements. ~32 is also the threshold at around which `Array.Copy` starts getting faster than a for-loop.\r\n\r\n## Benchmark results\r\n\r\nhttps://gist.github.com/jamesqo/399b72bf5de8e2cbd83d044836cbefa4 (includes results/source code)\r\n\r\nYou can see that the new implementation consistently has about 2/3 the gen0 collections as the old one.\r\n\r\nThe timings are somewhat inconsistent (disclaimer: I only did 100,000 iterations since the tests were taking way too long to run), but you can see that the new implementation is generally faster/the same speed as the old one. (I suspect it may be hard to measure the differences due to all of the interface invocations that are going on, in addition to the covariant array type checks if T is a reference type.)\r\n\r\ncc @stephentoub @VSadov @JonHanna "},"comment":{"url":"https://api.github.com/repos/dotnet/corefx/issues/comments/247825732","html_url":"https://github.com/dotnet/corefx/pull/11208#issuecomment-247825732","issue_url":"https://api.github.com/repos/dotnet/corefx/issues/11208","id":247825732,"user":{"login":"jamesqo","id":9159214,"avatar_url":"https://avatars.githubusercontent.com/u/9159214?v=3","gravatar_id":"","url":"https://api.github.com/users/jamesqo","html_url":"https://github.com/jamesqo","followers_url":"https://api.github.com/users/jamesqo/followers","following_url":"https://api.github.com/users/jamesqo/following{/other_user}","gists_url":"https://api.github.com/users/jamesqo/gists{/gist_id}","starred_url":"https://api.github.com/users/jamesqo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jamesqo/subscriptions","organizations_url":"https://api.github.com/users/jamesqo/orgs","repos_url":"https://api.github.com/users/jamesqo/repos","events_url":"https://api.github.com/users/jamesqo/events{/privacy}","received_events_url":"https://api.github.com/users/jamesqo/received_events","type":"User","site_admin":false},"created_at":"2016-09-18T05:01:15Z","updated_at":"2016-09-18T05:01:15Z","body":"@VSadov [Here](https://gist.github.com/jamesqo/37d361ec5f13fee3ad06b35d2dbb7756) are the results for some fields which are/contain reference types. I additionally took a look in PerfView and `memmoveGCRefs` seems to be taking up less time than it was before."}}
{"actor":{"display_login":"jamesqo"}}