{"action":"created","issue":{"url":"https://api.github.com/repos/golang/go/issues/16213","repository_url":"https://api.github.com/repos/golang/go","labels_url":"https://api.github.com/repos/golang/go/issues/16213/labels{/name}","comments_url":"https://api.github.com/repos/golang/go/issues/16213/comments","events_url":"https://api.github.com/repos/golang/go/issues/16213/events","html_url":"https://github.com/golang/go/issues/16213","id":162967336,"number":16213,"title":"math/rand: speed up Int31n with multiply/shift instead of modulo","user":{"login":"josharian","id":67496,"avatar_url":"https://avatars.githubusercontent.com/u/67496?v=3","gravatar_id":"","url":"https://api.github.com/users/josharian","html_url":"https://github.com/josharian","followers_url":"https://api.github.com/users/josharian/followers","following_url":"https://api.github.com/users/josharian/following{/other_user}","gists_url":"https://api.github.com/users/josharian/gists{/gist_id}","starred_url":"https://api.github.com/users/josharian/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/josharian/subscriptions","organizations_url":"https://api.github.com/users/josharian/orgs","repos_url":"https://api.github.com/users/josharian/repos","events_url":"https://api.github.com/users/josharian/events{/privacy}","received_events_url":"https://api.github.com/users/josharian/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/golang/go/labels/Go2","name":"Go2","color":"ffaaaa"}],"state":"open","locked":false,"assignee":{"login":"josharian","id":67496,"avatar_url":"https://avatars.githubusercontent.com/u/67496?v=3","gravatar_id":"","url":"https://api.github.com/users/josharian","html_url":"https://github.com/josharian","followers_url":"https://api.github.com/users/josharian/followers","following_url":"https://api.github.com/users/josharian/following{/other_user}","gists_url":"https://api.github.com/users/josharian/gists{/gist_id}","starred_url":"https://api.github.com/users/josharian/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/josharian/subscriptions","organizations_url":"https://api.github.com/users/josharian/orgs","repos_url":"https://api.github.com/users/josharian/repos","events_url":"https://api.github.com/users/josharian/events{/privacy}","received_events_url":"https://api.github.com/users/josharian/received_events","type":"User","site_admin":false},"assignees":[{"login":"josharian","id":67496,"avatar_url":"https://avatars.githubusercontent.com/u/67496?v=3","gravatar_id":"","url":"https://api.github.com/users/josharian","html_url":"https://github.com/josharian","followers_url":"https://api.github.com/users/josharian/followers","following_url":"https://api.github.com/users/josharian/following{/other_user}","gists_url":"https://api.github.com/users/josharian/gists{/gist_id}","starred_url":"https://api.github.com/users/josharian/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/josharian/subscriptions","organizations_url":"https://api.github.com/users/josharian/orgs","repos_url":"https://api.github.com/users/josharian/repos","events_url":"https://api.github.com/users/josharian/events{/privacy}","received_events_url":"https://api.github.com/users/josharian/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/golang/go/milestones/6","html_url":"https://github.com/golang/go/milestones/Unplanned","labels_url":"https://api.github.com/repos/golang/go/milestones/6/labels","id":1055141,"number":6,"title":"Unplanned","description":"No plan to fix in any specific release.\r\n","creator":{"login":"rsc","id":104030,"avatar_url":"https://avatars.githubusercontent.com/u/104030?v=3","gravatar_id":"","url":"https://api.github.com/users/rsc","html_url":"https://github.com/rsc","followers_url":"https://api.github.com/users/rsc/followers","following_url":"https://api.github.com/users/rsc/following{/other_user}","gists_url":"https://api.github.com/users/rsc/gists{/gist_id}","starred_url":"https://api.github.com/users/rsc/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rsc/subscriptions","organizations_url":"https://api.github.com/users/rsc/orgs","repos_url":"https://api.github.com/users/rsc/repos","events_url":"https://api.github.com/users/rsc/events{/privacy}","received_events_url":"https://api.github.com/users/rsc/received_events","type":"User","site_admin":false},"open_issues":1333,"closed_issues":428,"state":"open","created_at":"2015-04-06T20:47:19Z","updated_at":"2016-06-29T16:15:47Z","due_on":"2099-12-31T05:00:00Z","closed_at":null},"comments":2,"created_at":"2016-06-29T16:15:47Z","updated_at":"2016-06-29T18:05:52Z","closed_at":null,"body":"See http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ for details.\r\n\r\nMarking as Go2, since the compatibility guarantee prevents us from changing the output of Int31n given a seed.\r\n\r\nWe can still use this in the runtime, though; there are several places where we do `fastrand1() % n`. I will send a CL for this for Go 1.8 and have it update this issue.\r\n\r\ncc @dgryski \r\n"},"comment":{"url":"https://api.github.com/repos/golang/go/issues/comments/229439182","html_url":"https://github.com/golang/go/issues/16213#issuecomment-229439182","issue_url":"https://api.github.com/repos/golang/go/issues/16213","id":229439182,"user":{"login":"josharian","id":67496,"avatar_url":"https://avatars.githubusercontent.com/u/67496?v=3","gravatar_id":"","url":"https://api.github.com/users/josharian","html_url":"https://github.com/josharian","followers_url":"https://api.github.com/users/josharian/followers","following_url":"https://api.github.com/users/josharian/following{/other_user}","gists_url":"https://api.github.com/users/josharian/gists{/gist_id}","starred_url":"https://api.github.com/users/josharian/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/josharian/subscriptions","organizations_url":"https://api.github.com/users/josharian/orgs","repos_url":"https://api.github.com/users/josharian/repos","events_url":"https://api.github.com/users/josharian/events{/privacy}","received_events_url":"https://api.github.com/users/josharian/received_events","type":"User","site_admin":false},"created_at":"2016-06-29T18:05:52Z","updated_at":"2016-06-29T18:05:52Z","body":"Here's the obvious fastrandn for the runtime package\r\n\r\n```go\r\nfunc fastrandn(n uint32) uint32 {\r\n\t// See http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/.\r\n\t// Note that we use >> 31 instead of >> 32 because fastrand only produces 31 bit numbers.\r\n\treturn uint32((uint64(n) * uint64(fastrand())) >> 31)\r\n}\r\n```\r\n\r\nUnfortunately, the additional function call (instead of an inline `%`) more than obviates the performance gains. This means implementing fastrandn in assembly and copy/pasting the core of fastrand, which is a pity.\r\n\r\nResults on amd64, with an assembly implementation:\r\n\r\nname         old time/op  new time/op  delta\r\nFastrandnNonConstant-8  5.90ns ±18%  4.62ns ±13%  -21.63%  (p=0.008 n=5+5)\r\nFastrandnConstantNonPowerOfTwo-8  5.24ns ± 8%  5.14ns ±25%   ~     (p=0.052 n=24+25)\r\nFastrandnConstantPowerOfTwo-8  3.49ns ±11%  4.65ns ± 4%  +33.47%  (p=0.000 n=22+23)\r\n\r\nWorth doing for the non-constant case. This might get delayed going in, though, since I lack hardware (ppc, mips, s390x) to test asm implementations on other platforms.\r\n\r\n\r\n"}}
{"actor":{"display_login":"josharian"}}