{"action":"created","comment":{"url":"https://api.github.com/repos/scala-js/scala-js/pulls/comments/88723532","pull_request_review_id":9291002,"id":88723532,"diff_hunk":"@@ -302,9 +302,212 @@ final class RuntimeLong(val lo: Int, val hi: Int)\n \n   @inline\n   def *(b: RuntimeLong): RuntimeLong = {\n+    /* The following algorithm is based on the decomposition in 32-bit and then\n+     * 16-bit subproducts of the unsigned interpretation of operands.\n+     *\n+     * We are looking to compute\n+     * a *[64] b = (a * b) % 2^64","path":"library/src/main/scala/scala/scalajs/runtime/RuntimeLong.scala","position":8,"original_position":8,"commit_id":"1b9697b15e361726458af940563e237272549555","original_commit_id":"1b9697b15e361726458af940563e237272549555","user":{"login":"sjrd","id":535934,"avatar_url":"https://avatars.githubusercontent.com/u/535934?v=3","gravatar_id":"","url":"https://api.github.com/users/sjrd","html_url":"https://github.com/sjrd","followers_url":"https://api.github.com/users/sjrd/followers","following_url":"https://api.github.com/users/sjrd/following{/other_user}","gists_url":"https://api.github.com/users/sjrd/gists{/gist_id}","starred_url":"https://api.github.com/users/sjrd/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sjrd/subscriptions","organizations_url":"https://api.github.com/users/sjrd/orgs","repos_url":"https://api.github.com/users/sjrd/repos","events_url":"https://api.github.com/users/sjrd/events{/privacy}","received_events_url":"https://api.github.com/users/sjrd/received_events","type":"User","site_admin":false},"body":"> of the unsigned interpretation of operands\r\n\r\nYes","created_at":"2016-11-18T19:31:37Z","updated_at":"2016-11-18T19:31:37Z","html_url":"https://github.com/scala-js/scala-js/pull/2652#discussion_r88723532","pull_request_url":"https://api.github.com/repos/scala-js/scala-js/pulls/2652","_links":{"self":{"href":"https://api.github.com/repos/scala-js/scala-js/pulls/comments/88723532"},"html":{"href":"https://github.com/scala-js/scala-js/pull/2652#discussion_r88723532"},"pull_request":{"href":"https://api.github.com/repos/scala-js/scala-js/pulls/2652"}}},"pull_request":{"url":"https://api.github.com/repos/scala-js/scala-js/pulls/2652","id":93435022,"html_url":"https://github.com/scala-js/scala-js/pull/2652","diff_url":"https://github.com/scala-js/scala-js/pull/2652.diff","patch_url":"https://github.com/scala-js/scala-js/pull/2652.patch","issue_url":"https://api.github.com/repos/scala-js/scala-js/issues/2652","number":2652,"state":"open","locked":false,"title":"Shorter and faster `Long` multiplication.","user":{"login":"sjrd","id":535934,"avatar_url":"https://avatars.githubusercontent.com/u/535934?v=3","gravatar_id":"","url":"https://api.github.com/users/sjrd","html_url":"https://github.com/sjrd","followers_url":"https://api.github.com/users/sjrd/followers","following_url":"https://api.github.com/users/sjrd/following{/other_user}","gists_url":"https://api.github.com/users/sjrd/gists{/gist_id}","starred_url":"https://api.github.com/users/sjrd/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sjrd/subscriptions","organizations_url":"https://api.github.com/users/sjrd/orgs","repos_url":"https://api.github.com/users/sjrd/repos","events_url":"https://api.github.com/users/sjrd/events{/privacy}","received_events_url":"https://api.github.com/users/sjrd/received_events","type":"User","site_admin":false},"body":"The key insight was that we do not need to compute the `hi` products by 16-bit components. The `hi` part is basically\r\n\r\n    a.lo*b.hi + a.hi*b.hi + carry_from_lo_*\r\n\r\nso only the carry from multiplying `a.lo*b.lo` needs to be computed by 16-bit components. The resulting algorithm is significantly shorter, and we can afford to completely inline it.\r\n\r\nSubsequently, we can use the 16-bit products computed for the hi part to also compute the lo part, removing one multiplication.\r\n\r\nThe fact that we can now inline the whole algorithm allows it to benefit from call-site optimizations on the underlying `Int` arithmetics. This mostly happens when one side is constant and/or the `hi` part of operands is 0. The whole thing collapses particularly well when `a` is a constant in the range `0 <= a <= 0xffff`, which happens for mundane things like `10 * x`.\r\n\r\nThis improved implementation is significantly faster. A benchmark based on `BigInteger.multiply` exhibits > 2x improvement.\r\n\r\nThe benchmark code is the following:\r\n```scala\r\n  def benchmarkBigInteger(): Unit = {\r\n\r\n    println(\"Bench BigInteger\")\r\n    import java.math.BigInteger\r\n\r\n    // generate a prime number each time is too long, so here's one:\r\n    val modHexa = \"8600638d58155caded48cb45a1258593d775a03fe82679f62c62ec6c75e62e76fcb4e565f74675abe6cf6602939f6b4a159f56843f02f3f825e0f176a8df9f04f41eaa1cf60e598ca892670e30ea5b2d7002fb500b84e331d238708f600a14ec791dec30afc0fad2e5a0338847b0505f6d0a839516c892c06f4015362fbce145\"\r\n\r\n    val rand = new java.util.Random()\r\n    val aHexa =  new BigInteger(1024, rand).toString(16)\r\n    val bHexa =  new BigInteger(1024, rand).toString(16)\r\n\r\n    println(\"Hexa String version\")\r\n    println(\"mod = \" + modHexa)\r\n    println(\"a = \" + aHexa)\r\n    println(\"b = \" + bHexa)\r\n\r\n    val mod =  new BigInteger(modHexa, 16)\r\n    val a =  new BigInteger(aHexa, 16)\r\n    val b =  new BigInteger(bHexa, 16)\r\n\r\n    println(\"BigInteger version\")\r\n    println(\"mod = \" + mod.toString(16))\r\n    println(\"a = \" + a.toString(16))\r\n    println(\"b = \" + b.toString(16))\r\n\r\n    println(\"--------------------------\")\r\n    println(\"Do multiplication\")\r\n\r\n    var t0, t1:Long = 0\r\n    val nbLoop = 100000\r\n    var mutRes:BigInteger = null\r\n    t0 = System.currentTimeMillis()\r\n    for(i <- 0 until nbLoop) {\r\n      mutRes = a multiply b\r\n    }\r\n    t1 = System.currentTimeMillis()\r\n    val tBigInteger = (t1 - t0) * 1.0 / nbLoop\r\n    println(\"--------------------------\")\r\n    println(\"BigInteger result = \" + mutRes.toString(16))\r\n    println(\"\" + tBigInteger + \" ms\")\r\n    println(\"--------------------------\")\r\n  }\r\n```","created_at":"2016-11-12T10:25:58Z","updated_at":"2016-11-18T19:31:37Z","closed_at":null,"merged_at":null,"merge_commit_sha":"3f6b9867cc2ccfdc1a169e03faeabc3a8e5a4073","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/scala-js/scala-js/pulls/2652/commits","review_comments_url":"https://api.github.com/repos/scala-js/scala-js/pulls/2652/comments","review_comment_url":"https://api.github.com/repos/scala-js/scala-js/pulls/comments{/number}","comments_url":"https://api.github.com/repos/scala-js/scala-js/issues/2652/comments","statuses_url":"https://api.github.com/repos/scala-js/scala-js/statuses/1b9697b15e361726458af940563e237272549555","head":{"label":"sjrd:better-long-mul","ref":"better-long-mul","sha":"1b9697b15e361726458af940563e237272549555","user":{"login":"sjrd","id":535934,"avatar_url":"https://avatars.githubusercontent.com/u/535934?v=3","gravatar_id":"","url":"https://api.github.com/users/sjrd","html_url":"https://github.com/sjrd","followers_url":"https://api.github.com/users/sjrd/followers","following_url":"https://api.github.com/users/sjrd/following{/other_user}","gists_url":"https://api.github.com/users/sjrd/gists{/gist_id}","starred_url":"https://api.github.com/users/sjrd/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sjrd/subscriptions","organizations_url":"https://api.github.com/users/sjrd/orgs","repos_url":"https://api.github.com/users/sjrd/repos","events_url":"https://api.github.com/users/sjrd/events{/privacy}","received_events_url":"https://api.github.com/users/sjrd/received_events","type":"User","site_admin":false},"repo":{"id":8660284,"name":"scala-js","full_name":"sjrd/scala-js","owner":{"login":"sjrd","id":535934,"avatar_url":"https://avatars.githubusercontent.com/u/535934?v=3","gravatar_id":"","url":"https://api.github.com/users/sjrd","html_url":"https://github.com/sjrd","followers_url":"https://api.github.com/users/sjrd/followers","following_url":"https://api.github.com/users/sjrd/following{/other_user}","gists_url":"https://api.github.com/users/sjrd/gists{/gist_id}","starred_url":"https://api.github.com/users/sjrd/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sjrd/subscriptions","organizations_url":"https://api.github.com/users/sjrd/orgs","repos_url":"https://api.github.com/users/sjrd/repos","events_url":"https://api.github.com/users/sjrd/events{/privacy}","received_events_url":"https://api.github.com/users/sjrd/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/sjrd/scala-js","description":"Scala.js, a Scala to JavaScript compiler","fork":true,"url":"https://api.github.com/repos/sjrd/scala-js","forks_url":"https://api.github.com/repos/sjrd/scala-js/forks","keys_url":"https://api.github.com/repos/sjrd/scala-js/keys{/key_id}","collaborators_url":"https://api.github.com/repos/sjrd/scala-js/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/sjrd/scala-js/teams","hooks_url":"https://api.github.com/repos/sjrd/scala-js/hooks","issue_events_url":"https://api.github.com/repos/sjrd/scala-js/issues/events{/number}","events_url":"https://api.github.com/repos/sjrd/scala-js/events","assignees_url":"https://api.github.com/repos/sjrd/scala-js/assignees{/user}","branches_url":"https://api.github.com/repos/sjrd/scala-js/branches{/branch}","tags_url":"https://api.github.com/repos/sjrd/scala-js/tags","blobs_url":"https://api.github.com/repos/sjrd/scala-js/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/sjrd/scala-js/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/sjrd/scala-js/git/refs{/sha}","trees_url":"https://api.github.com/repos/sjrd/scala-js/git/trees{/sha}","statuses_url":"https://api.github.com/repos/sjrd/scala-js/statuses/{sha}","languages_url":"https://api.github.com/repos/sjrd/scala-js/languages","stargazers_url":"https://api.github.com/repos/sjrd/scala-js/stargazers","contributors_url":"https://api.github.com/repos/sjrd/scala-js/contributors","subscribers_url":"https://api.github.com/repos/sjrd/scala-js/subscribers","subscription_url":"https://api.github.com/repos/sjrd/scala-js/subscription","commits_url":"https://api.github.com/repos/sjrd/scala-js/commits{/sha}","git_commits_url":"https://api.github.com/repos/sjrd/scala-js/git/commits{/sha}","comments_url":"https://api.github.com/repos/sjrd/scala-js/comments{/number}","issue_comment_url":"https://api.github.com/repos/sjrd/scala-js/issues/comments{/number}","contents_url":"https://api.github.com/repos/sjrd/scala-js/contents/{+path}","compare_url":"https://api.github.com/repos/sjrd/scala-js/compare/{base}...{head}","merges_url":"https://api.github.com/repos/sjrd/scala-js/merges","archive_url":"https://api.github.com/repos/sjrd/scala-js/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/sjrd/scala-js/downloads","issues_url":"https://api.github.com/repos/sjrd/scala-js/issues{/number}","pulls_url":"https://api.github.com/repos/sjrd/scala-js/pulls{/number}","milestones_url":"https://api.github.com/repos/sjrd/scala-js/milestones{/number}","notifications_url":"https://api.github.com/repos/sjrd/scala-js/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/sjrd/scala-js/labels{/name}","releases_url":"https://api.github.com/repos/sjrd/scala-js/releases{/id}","deployments_url":"https://api.github.com/repos/sjrd/scala-js/deployments","created_at":"2013-03-08T21:32:59Z","updated_at":"2016-10-25T12:36:13Z","pushed_at":"2016-11-18T14:33:45Z","git_url":"git://github.com/sjrd/scala-js.git","ssh_url":"git@github.com:sjrd/scala-js.git","clone_url":"https://github.com/sjrd/scala-js.git","svn_url":"https://github.com/sjrd/scala-js","homepage":"http://www.scala-js.org/","size":13234,"stargazers_count":13,"watchers_count":13,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":0,"forks":1,"open_issues":0,"watchers":13,"default_branch":"master"}},"base":{"label":"scala-js:master","ref":"master","sha":"55312885135540edf953dd361fed458bfcfaf208","user":{"login":"scala-js","id":6039724,"avatar_url":"https://avatars.githubusercontent.com/u/6039724?v=3","gravatar_id":"","url":"https://api.github.com/users/scala-js","html_url":"https://github.com/scala-js","followers_url":"https://api.github.com/users/scala-js/followers","following_url":"https://api.github.com/users/scala-js/following{/other_user}","gists_url":"https://api.github.com/users/scala-js/gists{/gist_id}","starred_url":"https://api.github.com/users/scala-js/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scala-js/subscriptions","organizations_url":"https://api.github.com/users/scala-js/orgs","repos_url":"https://api.github.com/users/scala-js/repos","events_url":"https://api.github.com/users/scala-js/events{/privacy}","received_events_url":"https://api.github.com/users/scala-js/received_events","type":"Organization","site_admin":false},"repo":{"id":8272315,"name":"scala-js","full_name":"scala-js/scala-js","owner":{"login":"scala-js","id":6039724,"avatar_url":"https://avatars.githubusercontent.com/u/6039724?v=3","gravatar_id":"","url":"https://api.github.com/users/scala-js","html_url":"https://github.com/scala-js","followers_url":"https://api.github.com/users/scala-js/followers","following_url":"https://api.github.com/users/scala-js/following{/other_user}","gists_url":"https://api.github.com/users/scala-js/gists{/gist_id}","starred_url":"https://api.github.com/users/scala-js/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scala-js/subscriptions","organizations_url":"https://api.github.com/users/scala-js/orgs","repos_url":"https://api.github.com/users/scala-js/repos","events_url":"https://api.github.com/users/scala-js/events{/privacy}","received_events_url":"https://api.github.com/users/scala-js/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/scala-js/scala-js","description":"Scala.js, the Scala to JavaScript compiler","fork":false,"url":"https://api.github.com/repos/scala-js/scala-js","forks_url":"https://api.github.com/repos/scala-js/scala-js/forks","keys_url":"https://api.github.com/repos/scala-js/scala-js/keys{/key_id}","collaborators_url":"https://api.github.com/repos/scala-js/scala-js/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/scala-js/scala-js/teams","hooks_url":"https://api.github.com/repos/scala-js/scala-js/hooks","issue_events_url":"https://api.github.com/repos/scala-js/scala-js/issues/events{/number}","events_url":"https://api.github.com/repos/scala-js/scala-js/events","assignees_url":"https://api.github.com/repos/scala-js/scala-js/assignees{/user}","branches_url":"https://api.github.com/repos/scala-js/scala-js/branches{/branch}","tags_url":"https://api.github.com/repos/scala-js/scala-js/tags","blobs_url":"https://api.github.com/repos/scala-js/scala-js/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/scala-js/scala-js/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/scala-js/scala-js/git/refs{/sha}","trees_url":"https://api.github.com/repos/scala-js/scala-js/git/trees{/sha}","statuses_url":"https://api.github.com/repos/scala-js/scala-js/statuses/{sha}","languages_url":"https://api.github.com/repos/scala-js/scala-js/languages","stargazers_url":"https://api.github.com/repos/scala-js/scala-js/stargazers","contributors_url":"https://api.github.com/repos/scala-js/scala-js/contributors","subscribers_url":"https://api.github.com/repos/scala-js/scala-js/subscribers","subscription_url":"https://api.github.com/repos/scala-js/scala-js/subscription","commits_url":"https://api.github.com/repos/scala-js/scala-js/commits{/sha}","git_commits_url":"https://api.github.com/repos/scala-js/scala-js/git/commits{/sha}","comments_url":"https://api.github.com/repos/scala-js/scala-js/comments{/number}","issue_comment_url":"https://api.github.com/repos/scala-js/scala-js/issues/comments{/number}","contents_url":"https://api.github.com/repos/scala-js/scala-js/contents/{+path}","compare_url":"https://api.github.com/repos/scala-js/scala-js/compare/{base}...{head}","merges_url":"https://api.github.com/repos/scala-js/scala-js/merges","archive_url":"https://api.github.com/repos/scala-js/scala-js/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/scala-js/scala-js/downloads","issues_url":"https://api.github.com/repos/scala-js/scala-js/issues{/number}","pulls_url":"https://api.github.com/repos/scala-js/scala-js/pulls{/number}","milestones_url":"https://api.github.com/repos/scala-js/scala-js/milestones{/number}","notifications_url":"https://api.github.com/repos/scala-js/scala-js/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/scala-js/scala-js/labels{/name}","releases_url":"https://api.github.com/repos/scala-js/scala-js/releases{/id}","deployments_url":"https://api.github.com/repos/scala-js/scala-js/deployments","created_at":"2013-02-18T16:33:55Z","updated_at":"2016-11-18T04:29:07Z","pushed_at":"2016-11-18T17:05:17Z","git_url":"git://github.com/scala-js/scala-js.git","ssh_url":"git@github.com:scala-js/scala-js.git","clone_url":"https://github.com/scala-js/scala-js.git","svn_url":"https://github.com/scala-js/scala-js","homepage":"https://www.scala-js.org/","size":16126,"stargazers_count":2687,"watchers_count":2687,"language":"Scala","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":238,"mirror_url":null,"open_issues_count":105,"forks":238,"open_issues":105,"watchers":2687,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/scala-js/scala-js/pulls/2652"},"html":{"href":"https://github.com/scala-js/scala-js/pull/2652"},"issue":{"href":"https://api.github.com/repos/scala-js/scala-js/issues/2652"},"comments":{"href":"https://api.github.com/repos/scala-js/scala-js/issues/2652/comments"},"review_comments":{"href":"https://api.github.com/repos/scala-js/scala-js/pulls/2652/comments"},"review_comment":{"href":"https://api.github.com/repos/scala-js/scala-js/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/scala-js/scala-js/pulls/2652/commits"},"statuses":{"href":"https://api.github.com/repos/scala-js/scala-js/statuses/1b9697b15e361726458af940563e237272549555"}}}}
{"actor":{"display_login":"sjrd"}}