{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/corefx/issues/2727","labels_url":"https://api.github.com/repos/dotnet/corefx/issues/2727/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/corefx/issues/2727/comments","events_url":"https://api.github.com/repos/dotnet/corefx/issues/2727/events","html_url":"https://github.com/dotnet/corefx/issues/2727","id":100368939,"number":2727,"title":"IsPrime function unnecessary, GetPrime function inefficient.","user":{"login":"SunnyWar","id":4521425,"avatar_url":"https://avatars.githubusercontent.com/u/4521425?v=3","gravatar_id":"","url":"https://api.github.com/users/SunnyWar","html_url":"https://github.com/SunnyWar","followers_url":"https://api.github.com/users/SunnyWar/followers","following_url":"https://api.github.com/users/SunnyWar/following{/other_user}","gists_url":"https://api.github.com/users/SunnyWar/gists{/gist_id}","starred_url":"https://api.github.com/users/SunnyWar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/SunnyWar/subscriptions","organizations_url":"https://api.github.com/users/SunnyWar/orgs","repos_url":"https://api.github.com/users/SunnyWar/repos","events_url":"https://api.github.com/users/SunnyWar/events{/privacy}","received_events_url":"https://api.github.com/users/SunnyWar/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/dotnet/corefx/labels/suggestion","name":"suggestion","color":"207de5"},{"url":"https://api.github.com/repos/dotnet/corefx/labels/System.Collections","name":"System.Collections","color":"d4c5f9"},{"url":"https://api.github.com/repos/dotnet/corefx/labels/up%20for%20grabs","name":"up for grabs","color":"159818"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2015-08-11T17:53:37Z","updated_at":"2015-08-11T20:44:22Z","closed_at":null,"body":"In System.Collections.HashHelpers and System.Collections.NonGeneric\\src\\System\\Collections\\Hashtable and\r\nSystem.Private.DataContractSerialization\\src\\System\\Runtime\\Serialization\\ObjectToIdCache.cs\r\n\r\nthere are copies of the same function: private static bool IsPrime(int candidate)\r\n      \r\nIt is used by: private static int GetPrime(int min)\r\n   \r\nWhich is called by: Initialize, ExpandPrime, and TrimExcess\r\n\r\nThey all use a table in GetPrime: E.g. int[] primes = {3, 7, 17, 37, 89, 197, 431, 919, 1931,...7199369}.\r\nNotice that each successive prime is larger than twice the preceding one. This appears to be because hashtables are doubled in size when they need to be expanded. But they are only allowed to expand up to 2G. The GetPrime function calls IsPrime to find a prime when the search goes above the limit of the primes table. The ExpandPrime function is the most interesting as it more than doubles the size each time:\r\npublic static int ExpandPrime(int oldSize)\r\n        {\r\n            int newSize = 2 * oldSize;\r\n            ....\r\n         return GetPrime(newSize);\r\n\r\nTherefore it appears that we don't need the IsPrime function at all. Instead we simply need to expand the primes table up to 2146435069 (largest prime below 2G).  {..., 7199369, 21598111, 64794337, 194383039, 583149179, 1749447569, 953375459, 2146435069};\r\n\r\nRecommendation:\r\n1) Use a common GetPrime(int min) function instead of having three copies\r\n2) Expand the primes table as described above.\r\n3) Remove the IsPrime function, modify GetPrime to only use the table.\r\n\r\n\r\n\r\n\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/dotnet/corefx/issues/comments/130064102","html_url":"https://github.com/dotnet/corefx/issues/2727#issuecomment-130064102","issue_url":"https://api.github.com/repos/dotnet/corefx/issues/2727","id":130064102,"user":{"login":"weshaggard","id":9010698,"avatar_url":"https://avatars.githubusercontent.com/u/9010698?v=3","gravatar_id":"","url":"https://api.github.com/users/weshaggard","html_url":"https://github.com/weshaggard","followers_url":"https://api.github.com/users/weshaggard/followers","following_url":"https://api.github.com/users/weshaggard/following{/other_user}","gists_url":"https://api.github.com/users/weshaggard/gists{/gist_id}","starred_url":"https://api.github.com/users/weshaggard/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/weshaggard/subscriptions","organizations_url":"https://api.github.com/users/weshaggard/orgs","repos_url":"https://api.github.com/users/weshaggard/repos","events_url":"https://api.github.com/users/weshaggard/events{/privacy}","received_events_url":"https://api.github.com/users/weshaggard/received_events","type":"User","site_admin":false},"created_at":"2015-08-11T20:44:22Z","updated_at":"2015-08-11T20:44:22Z","body":"@vancem @ellismg either of you guys know the reasoning behind the prime table?"}}