{"action":"created","issue":{"url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1456","repository_url":"https://api.github.com/repos/Microsoft/visualfsharp","labels_url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1456/labels{/name}","comments_url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1456/comments","events_url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1456/events","html_url":"https://github.com/Microsoft/visualfsharp/pull/1456","id":171912567,"number":1456,"title":"[WIP] New Array.filter - better memory usage","user":{"login":"jackmott","id":4701158,"avatar_url":"https://avatars.githubusercontent.com/u/4701158?v=3","gravatar_id":"","url":"https://api.github.com/users/jackmott","html_url":"https://github.com/jackmott","followers_url":"https://api.github.com/users/jackmott/followers","following_url":"https://api.github.com/users/jackmott/following{/other_user}","gists_url":"https://api.github.com/users/jackmott/gists{/gist_id}","starred_url":"https://api.github.com/users/jackmott/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jackmott/subscriptions","organizations_url":"https://api.github.com/users/jackmott/orgs","repos_url":"https://api.github.com/users/jackmott/repos","events_url":"https://api.github.com/users/jackmott/events{/privacy}","received_events_url":"https://api.github.com/users/jackmott/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":22,"created_at":"2016-08-18T14:19:01Z","updated_at":"2016-08-20T21:08:46Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/Microsoft/visualfsharp/pulls/1456","html_url":"https://github.com/Microsoft/visualfsharp/pull/1456","diff_url":"https://github.com/Microsoft/visualfsharp/pull/1456.diff","patch_url":"https://github.com/Microsoft/visualfsharp/pull/1456.patch"},"body":"The motivation here is to keep the same overall speed as the new Array.filter from a few days ago, without having the greatly increased memory use in scenarios when most of the array elements are filtered.\r\n\r\nThis implementation is similar to the original one which used a ResizeArray, but takes advantage of the fact that the growth of the array is bounded by array.Length so that we never allocate ~2*array.Length.  Additionally, two fast paths exist. If all elements are filtered, nothing is allocated and empty is returned directly. If no elements are filtered, the Array.Copy at the end is skipped, because our resized array is exactly the right size in that case, also improving speed and reducing memory usage.\r\n\r\nOverall, this has similar runtime as the current Array.filter with about 25% to 35% less allocation. The benchmark below shows the results for the current, original, and new filter, when 0, 10, 25, 75, and 90, and 100% of elements remain after filtering.\r\n\r\nThe downside to this approach is it is more complex code.\r\n\r\nIf you like this change, the same logic would be applied to choose.\r\n\r\n```ini\r\n\r\nHost Process Environment Information:\r\nBenchmarkDotNet=v0.9.8.0\r\nOS=Microsoft Windows NT 6.2.9200.0\r\nProcessor=Intel(R) Core(TM) i7-4712HQ CPU 2.30GHz, ProcessorCount=8\r\nFrequency=2240910 ticks, Resolution=446.2473 ns, Timer=TSC\r\nCLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]\r\nGC=Concurrent Workstation\r\nJitModules=clrjit-v4.6.1590.0\r\n\r\nType=CoreBenchmark  Mode=Throughput  Platform=X64  \r\nJit=RyuJit  GarbageCollection=Concurrent Workstation  \r\n\r\n```\r\n  Method | Length | Pct |        Median |     StdDev | Scaled |  Gen 0 | Gen 1 |    Gen 2 | Bytes Allocated/Op |\r\n-------- |------- |---- |-------------- |----------- |------- |------- |------ |--------- |------------------- |\r\n     **Old** | **100000** |   **0** |   **257.9468 us** |  **3.1356 us** |   **1.00** |      **-** |     **-** |        **-** |             **437.56** |\r\n Current | 100000 |   0 |   207.4557 us |  7.2287 us |   0.80 |      - |     - |   569.59 |         168,274.25 |\r\n    New3 | 100000 |   0 |   192.8935 us |  4.2597 us |   0.75 |      - |     - |        - |             223.45 |\r\n     **Old** | **100000** |  **10** |   **388.3678 us** |  **6.3276 us** |   **1.00** | **231.46** |  **9.50** |        **-** |          **87,711.42** |\r\n Current | 100000 |  10 |   323.8600 us |  7.0283 us |   0.83 |      - |     - |   550.66 |         181,880.46 |\r\n    New3 | 100000 |  10 |   371.5841 us |  3.5846 us |   0.96 |      - |     - |   150.93 |          68,134.81 |\r\n     **Old** | **100000** |  **25** |   **649.2728 us** | **15.1429 us** |   **1.00** |      **-** |     **-** |   **257.15** |         **132,033.02** |\r\n Current | 100000 |  25 |   552.9257 us |  8.8261 us |   0.85 |      - |     - |   615.26 |         224,125.63 |\r\n    New3 | 100000 |  25 |   540.5000 us |  9.4800 us |   0.83 |      - |     - |   270.17 |          83,741.20 |\r\n     **Old** | **100000** |  **50** | **1,021.8182 us** | **19.1519 us** |   **1.00** |      **-** |     **-** |   **824.00** |         **320,059.78** |\r\n Current | 100000 |  50 |   756.3990 us |  9.5827 us |   0.74 |      - |     - |   757.50 |         229,800.24 |\r\n    New3 | 100000 |  50 |   803.6203 us | 26.9094 us |   0.79 |      - |     - |   676.62 |         204,549.69 |\r\n     **Old** | **100000** |  **75** | **1,062.5958 us** | **25.0791 us** |   **1.00** | **172.00** |  **1.95** | **1,492.28** |         **563,836.73** |\r\n Current | 100000 |  75 |   484.5561 us | 12.2847 us |   0.46 |      - |     - |   867.11 |         278,742.70 |\r\n    New3 | 100000 |  75 |   658.7146 us | 11.9907 us |   0.62 |      - |     - |   866.10 |         265,235.53 |\r\n     **Old** | **100000** |  **90** |   **960.1716 us** |  **8.5740 us** |   **1.00** | **157.34** | **16.61** | **1,492.28** |         **593,153.20** |\r\n Current | 100000 |  90 |   429.5871 us | 35.2049 us |   0.45 |      - |     - |   961.71 |         331,770.50 |\r\n    New3 | 100000 |  90 |   502.8985 us | 13.9179 us |   0.52 |      - |     - |   991.75 |         308,047.74 |\r\n     **Old** | **100000** | **100** |   **624.1714 us** | **15.1284 us** |   **1.00** |      **-** |     **-** | **1,850.08** |         **628,711.50** |\r\n Current | 100000 | 100 |   399.4854 us | 11.1079 us |   0.64 |      - |     - |   944.05 |         279,019.83 |\r\n    New3 | 100000 | 100 |   465.3832 us |  9.6660 us |   0.75 |      - |     - | 1,113.40 |         328,896.22 |\r\n"},"comment":{"url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/comments/241223874","html_url":"https://github.com/Microsoft/visualfsharp/pull/1456#issuecomment-241223874","issue_url":"https://api.github.com/repos/Microsoft/visualfsharp/issues/1456","id":241223874,"user":{"login":"KevinRansom","id":5175830,"avatar_url":"https://avatars.githubusercontent.com/u/5175830?v=3","gravatar_id":"","url":"https://api.github.com/users/KevinRansom","html_url":"https://github.com/KevinRansom","followers_url":"https://api.github.com/users/KevinRansom/followers","following_url":"https://api.github.com/users/KevinRansom/following{/other_user}","gists_url":"https://api.github.com/users/KevinRansom/gists{/gist_id}","starred_url":"https://api.github.com/users/KevinRansom/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/KevinRansom/subscriptions","organizations_url":"https://api.github.com/users/KevinRansom/orgs","repos_url":"https://api.github.com/users/KevinRansom/repos","events_url":"https://api.github.com/users/KevinRansom/events{/privacy}","received_events_url":"https://api.github.com/users/KevinRansom/received_events","type":"User","site_admin":false},"created_at":"2016-08-20T21:08:45Z","updated_at":"2016-08-20T21:08:45Z","body":"The new algorithm for filter seems like the best choice.\r\n\r\nAre there other places this techniques is employable ... is it generalizable?\r\n\r\nKevin"}}
{"actor":{"display_login":"KevinRansom"}}