{"action":"created","issue":{"url":"https://api.github.com/repos/golang/go/issues/25137","repository_url":"https://api.github.com/repos/golang/go","labels_url":"https://api.github.com/repos/golang/go/issues/25137/labels{/name}","comments_url":"https://api.github.com/repos/golang/go/issues/25137/comments","events_url":"https://api.github.com/repos/golang/go/issues/25137/events","html_url":"https://github.com/golang/go/issues/25137","id":318545918,"number":25137,"title":"proposal: sort: Stable with better asymptotic time complexity","user":{"login":"nsajko","id":4944410,"avatar_url":"https://avatars3.githubusercontent.com/u/4944410?v=4","gravatar_id":"","url":"https://api.github.com/users/nsajko","html_url":"https://github.com/nsajko","followers_url":"https://api.github.com/users/nsajko/followers","following_url":"https://api.github.com/users/nsajko/following{/other_user}","gists_url":"https://api.github.com/users/nsajko/gists{/gist_id}","starred_url":"https://api.github.com/users/nsajko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nsajko/subscriptions","organizations_url":"https://api.github.com/users/nsajko/orgs","repos_url":"https://api.github.com/users/nsajko/repos","events_url":"https://api.github.com/users/nsajko/events{/privacy}","received_events_url":"https://api.github.com/users/nsajko/received_events","type":"User","site_admin":false},"labels":[{"id":236419512,"url":"https://api.github.com/repos/golang/go/labels/Proposal","name":"Proposal","color":"ededed","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/golang/go/milestones/30","html_url":"https://github.com/golang/go/milestone/30","labels_url":"https://api.github.com/repos/golang/go/milestones/30/labels","id":1373555,"number":30,"title":"Proposal","description":"Proposals that are pending (not yet accepted/rejected).\r\n","creator":{"login":"rsc","id":104030,"avatar_url":"https://avatars1.githubusercontent.com/u/104030?v=4","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":177,"closed_issues":493,"state":"open","created_at":"2015-10-24T01:40:49Z","updated_at":"2018-05-01T21:20:38Z","due_on":null,"closed_at":null},"comments":9,"created_at":"2018-04-27T20:51:10Z","updated_at":"2018-05-01T23:55:24Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"The proposed change does not add any new API and is backwards compatible.\r\n\r\nThe current implementation of Stable is very simple, but not satisfactorily performant and executes in O(n*log(n)*log(n)) time.\r\n\r\nI propose implementing Stable using an O(n*log(n)) algorithm which is, though, much more complex. See https://go-review.googlesource.com/c/go/+/101415\r\n\r\nCode complexity: the following functions with noted cyclomatic complexities are added:\r\n\r\nCyclomatic complexity | function\r\n------|------------------------------------\r\n118 | sort stable sort.go:918:1\r\n19   | sort merge sort.go:666:1\r\n16   | sort findBDSAndCountDistinctElementsNear sort.go:420:1\r\n13   | sort findBDSFarAndCountDistinctElements sort.go:497:1\r\n8     | sort simpleMergeBufBigSmall sort.go:625:1\r\n4     | sort distinctElementCount sort.go:389:1\r\n3     | sort extractDist sort.go:573:1\r\n3     | sort equalRange sort.go:562:1\r\n3     | sort max sort.go:333:1\r\n3     | sort lessBlocks sort.go:613:1\r\n2     | sort maxDepth sort.go:223:1\r\n1     | sort searchLess sort.go:328:1\r\n1     | sort isqrter sort.go:348:1\r\n\r\nPerformance: \r\n\r\nBenchmark results using func bench (it sorts pseudorandom data) from sort_test.go (benchmark names include input array size):\r\n\r\nBenchmark         |        Improvement\r\n------------------------|--------------------------\r\nStable1e4           |    10%    (from 110 ms to 100 ms)\r\nStable1e6           |    31%    (from 23 s to 16 s)\r\nStable1e7           |    36%    (from 1.9 min to 1.2 min)\r\nStable1e8           |    43%    (from 64 min to 36 min)\r\n\r\nThe code in master is faster for input arrays with very many identical elements, but those are fast to sort anyways (in both the old and new code they are orders of magnitude faster to sort than random data)."},"comment":{"url":"https://api.github.com/repos/golang/go/issues/comments/385824345","html_url":"https://github.com/golang/go/issues/25137#issuecomment-385824345","issue_url":"https://api.github.com/repos/golang/go/issues/25137","id":385824345,"user":{"login":"ancaemanuel","id":3100847,"avatar_url":"https://avatars1.githubusercontent.com/u/3100847?v=4","gravatar_id":"","url":"https://api.github.com/users/ancaemanuel","html_url":"https://github.com/ancaemanuel","followers_url":"https://api.github.com/users/ancaemanuel/followers","following_url":"https://api.github.com/users/ancaemanuel/following{/other_user}","gists_url":"https://api.github.com/users/ancaemanuel/gists{/gist_id}","starred_url":"https://api.github.com/users/ancaemanuel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ancaemanuel/subscriptions","organizations_url":"https://api.github.com/users/ancaemanuel/orgs","repos_url":"https://api.github.com/users/ancaemanuel/repos","events_url":"https://api.github.com/users/ancaemanuel/events{/privacy}","received_events_url":"https://api.github.com/users/ancaemanuel/received_events","type":"User","site_admin":false},"created_at":"2018-05-01T23:55:24Z","updated_at":"2018-05-01T23:55:24Z","author_association":"NONE","body":"Ok. The complexity of the algorithm looks good, adding papers to that increase the confidence that you are doing an great job, but the amount of code added really worth it ? \r\nI think, in some cases it will. But is not my decision. "}}
{"actor":{"display_login":"ancaemanuel"}}