GitHub PullRequestReviewCommentEvent at 2014-07-15 12:08:05
Repository: elixir
Actor: josevalim
Payload: {"action":"created","comment":{"url":"https://api.github.com/repos/elixir-lang/elixir/pulls/comments/14930226","id":14930226,"diff_hunk":"@@ -1143,6 +1143,73 @@ defmodule String do\n     nbytes\n   end\n \n+  # \"lb\" stands for known lower bound\n+  defp do_slice_neg_lb(nil, str, first, pos, count, bytes) do\n+    cond do\n+      pos < first+1 ->\n+        # starting position is out of bounds\n+        \"\"\n+      pos-count < first ->\n+        # the negative right bound is out of bounds\n+        \"\"\n+      true ->\n+        {bytes, _, start_bytes} = bytes\n+        len_bytes = sum_bytes(bytes, count-1)\n+        binary_part(str, start_bytes, byte_size(str)-start_bytes-len_bytes)\n+    end\n+  end\n+\n+  defp do_slice_neg_lb({char, rest}, str, first, pos, count, bytes) do\n+    bytes = update_bytes(bytes, char, first, pos, count)\n+    do_slice_neg_lb(next_grapheme(rest), str, first, pos+1, count, bytes)\n+  end\n+\n+  # both bounds are negative\n+  defp do_slice_neg(nil, str, first, last, count, pos, bytes) do\n+    # get positive bounds\n+    if first < 0, do: first = pos + first\n+    if last < 0, do: last = pos + last\n+    cond do\n+      first < 0 or first > last ->\n+        # negative left bound is out of bounds\n+        \"\"\n+      true ->\n+        {bytes, _, _} = bytes\n+        str_bytes = byte_size(str)\n+        start_bytes = str_bytes - sum_bytes(bytes, count)\n+        last = min(last, pos-1)\n+        len_bytes =\n+          bytes |> drop_bytes(pos-last-1) |> sum_bytes(last-first+1)\n+        binary_part(str, start_bytes, min(len_bytes, str_bytes-start_bytes))\n+    end\n+  end\n+\n+  defp do_slice_neg({char, rest}, str, first, last, count, pos, bytes) do\n+    bytes = update_bytes(bytes, char, 0, 0, count)\n+    do_slice_neg(next_grapheme(rest), str, first, last, count, pos+1, bytes)\n+  end\n+\n+  defp init_bytes(), do: {[], 0, 0}\n+\n+  defp sum_bytes(bytes, count) do\n+    bytes |> Enum.take(count) |> Enum.sum\n+  end\n+\n+  defp drop_bytes(bytes, count) do\n+    Enum.drop(bytes, count)\n+  end\n+\n+  defp update_bytes({bytes, n, start_bytes}, char, first, pos, cnt) do\n+    char_bytes = byte_size(char)\n+    if pos < first do","path":"lib/elixir/lib/string.ex","position":114,"original_position":114,"commit_id":"46e97481826c79778fbc518a7637dc97bee9b98e","original_commit_id":"46e97481826c79778fbc518a7637dc97bee9b98e","user":{"login":"josevalim","id":9582,"avatar_url":"https://avatars.githubusercontent.com/u/9582?","gravatar_id":"e837f6b7fd146ab16ed3d663476c063e","url":"https://api.github.com/users/josevalim","html_url":"https://github.com/josevalim","followers_url":"https://api.github.com/users/josevalim/followers","following_url":"https://api.github.com/users/josevalim/following{/other_user}","gists_url":"https://api.github.com/users/josevalim/gists{/gist_id}","starred_url":"https://api.github.com/users/josevalim/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/josevalim/subscriptions","organizations_url":"https://api.github.com/users/josevalim/orgs","repos_url":"https://api.github.com/users/josevalim/repos","events_url":"https://api.github.com/users/josevalim/events{/privacy}","received_events_url":"https://api.github.com/users/josevalim/received_events","type":"User","site_admin":false},"body":"Maybe we can do those checks at the end instead of on every operation?","created_at":"2014-07-15T12:08:05Z","updated_at":"2014-07-15T12:08:05Z","html_url":"https://github.com/elixir-lang/elixir/pull/2538#discussion_r14930226","pull_request_url":"https://api.github.com/repos/elixir-lang/elixir/pulls/2538","_links":{"self":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/comments/14930226"},"html":{"href":"https://github.com/elixir-lang/elixir/pull/2538#discussion_r14930226"},"pull_request":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/2538"}}},"pull_request":{"url":"https://api.github.com/repos/elixir-lang/elixir/pulls/2538","id":18402871,"html_url":"https://github.com/elixir-lang/elixir/pull/2538","diff_url":"https://github.com/elixir-lang/elixir/pull/2538.diff","patch_url":"https://github.com/elixir-lang/elixir/pull/2538.patch","issue_url":"https://api.github.com/repos/elixir-lang/elixir/issues/2538","number":2538,"state":"open","title":"Do not traverse the string twice in String.slice(<str>, <range>)","user":{"login":"alco","id":207748,"avatar_url":"https://avatars.githubusercontent.com/u/207748?","gravatar_id":"96f31e49f44b5ba166999c4576c43c41","url":"https://api.github.com/users/alco","html_url":"https://github.com/alco","followers_url":"https://api.github.com/users/alco/followers","following_url":"https://api.github.com/users/alco/following{/other_user}","gists_url":"https://api.github.com/users/alco/gists{/gist_id}","starred_url":"https://api.github.com/users/alco/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alco/subscriptions","organizations_url":"https://api.github.com/users/alco/orgs","repos_url":"https://api.github.com/users/alco/repos","events_url":"https://api.github.com/users/alco/events{/privacy}","received_events_url":"https://api.github.com/users/alco/received_events","type":"User","site_admin":false},"body":"The approach I've taken here is to keep byte sizes of each codepoint in a list until we reach the end of the string, then we calculate byte offsets and call `binary_part` once.\r\n\r\nThis uses the amount of memory proportional to the absolute value of the smallest offset in the range just to keep the byte sizes. I can't say exactly how much more memory it uses compared to keeping an accumulator on master.\r\n\r\nI've tried replacing lists with binary arithmetic and queues. Both techniques showed worse performance than master.\r\n\r\nFeel free to reject this PR as it adds more complexity to the code with not as much gain as I had hoped.\r\n\r\nSome graphs (benchmark code – https://gist.github.com/alco/330d7b8a601bfed057dc). The dark green bars are master, the lighter green bars are this PR. The Y axis is execution time in microseconds.\r\n![slice_left](https://cloud.githubusercontent.com/assets/207748/3584137/490364a8-0c14-11e4-87e6-a147556fca72.png)\r\n![slice_right](https://cloud.githubusercontent.com/assets/207748/3584139/5093a46c-0c14-11e4-9378-d9f13b05553f.png)\r\n![slice_both](https://cloud.githubusercontent.com/assets/207748/3584141/54d5b04c-0c14-11e4-8e24-525244a734f3.png)\r\n","created_at":"2014-07-15T11:45:39Z","updated_at":"2014-07-15T12:08:05Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0e0792849bbf9c2d5ec1fe8d32c3bdeeda6616ba","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/elixir-lang/elixir/pulls/2538/commits","review_comments_url":"https://api.github.com/repos/elixir-lang/elixir/pulls/2538/comments","review_comment_url":"https://api.github.com/repos/elixir-lang/elixir/pulls/comments/{number}","comments_url":"https://api.github.com/repos/elixir-lang/elixir/issues/2538/comments","statuses_url":"https://api.github.com/repos/elixir-lang/elixir/statuses/46e97481826c79778fbc518a7637dc97bee9b98e","head":{"label":"alco:string-slice-opt","ref":"string-slice-opt","sha":"46e97481826c79778fbc518a7637dc97bee9b98e","user":{"login":"alco","id":207748,"avatar_url":"https://avatars.githubusercontent.com/u/207748?","gravatar_id":"96f31e49f44b5ba166999c4576c43c41","url":"https://api.github.com/users/alco","html_url":"https://github.com/alco","followers_url":"https://api.github.com/users/alco/followers","following_url":"https://api.github.com/users/alco/following{/other_user}","gists_url":"https://api.github.com/users/alco/gists{/gist_id}","starred_url":"https://api.github.com/users/alco/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alco/subscriptions","organizations_url":"https://api.github.com/users/alco/orgs","repos_url":"https://api.github.com/users/alco/repos","events_url":"https://api.github.com/users/alco/events{/privacy}","received_events_url":"https://api.github.com/users/alco/received_events","type":"User","site_admin":false},"repo":{"id":3815790,"name":"elixir","full_name":"alco/elixir","owner":{"login":"alco","id":207748,"avatar_url":"https://avatars.githubusercontent.com/u/207748?","gravatar_id":"96f31e49f44b5ba166999c4576c43c41","url":"https://api.github.com/users/alco","html_url":"https://github.com/alco","followers_url":"https://api.github.com/users/alco/followers","following_url":"https://api.github.com/users/alco/following{/other_user}","gists_url":"https://api.github.com/users/alco/gists{/gist_id}","starred_url":"https://api.github.com/users/alco/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alco/subscriptions","organizations_url":"https://api.github.com/users/alco/orgs","repos_url":"https://api.github.com/users/alco/repos","events_url":"https://api.github.com/users/alco/events{/privacy}","received_events_url":"https://api.github.com/users/alco/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/alco/elixir","description":"A modern approach to programming for the Erlang VM","fork":true,"url":"https://api.github.com/repos/alco/elixir","forks_url":"https://api.github.com/repos/alco/elixir/forks","keys_url":"https://api.github.com/repos/alco/elixir/keys{/key_id}","collaborators_url":"https://api.github.com/repos/alco/elixir/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/alco/elixir/teams","hooks_url":"https://api.github.com/repos/alco/elixir/hooks","issue_events_url":"https://api.github.com/repos/alco/elixir/issues/events{/number}","events_url":"https://api.github.com/repos/alco/elixir/events","assignees_url":"https://api.github.com/repos/alco/elixir/assignees{/user}","branches_url":"https://api.github.com/repos/alco/elixir/branches{/branch}","tags_url":"https://api.github.com/repos/alco/elixir/tags","blobs_url":"https://api.github.com/repos/alco/elixir/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/alco/elixir/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/alco/elixir/git/refs{/sha}","trees_url":"https://api.github.com/repos/alco/elixir/git/trees{/sha}","statuses_url":"https://api.github.com/repos/alco/elixir/statuses/{sha}","languages_url":"https://api.github.com/repos/alco/elixir/languages","stargazers_url":"https://api.github.com/repos/alco/elixir/stargazers","contributors_url":"https://api.github.com/repos/alco/elixir/contributors","subscribers_url":"https://api.github.com/repos/alco/elixir/subscribers","subscription_url":"https://api.github.com/repos/alco/elixir/subscription","commits_url":"https://api.github.com/repos/alco/elixir/commits{/sha}","git_commits_url":"https://api.github.com/repos/alco/elixir/git/commits{/sha}","comments_url":"https://api.github.com/repos/alco/elixir/comments{/number}","issue_comment_url":"https://api.github.com/repos/alco/elixir/issues/comments/{number}","contents_url":"https://api.github.com/repos/alco/elixir/contents/{+path}","compare_url":"https://api.github.com/repos/alco/elixir/compare/{base}...{head}","merges_url":"https://api.github.com/repos/alco/elixir/merges","archive_url":"https://api.github.com/repos/alco/elixir/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/alco/elixir/downloads","issues_url":"https://api.github.com/repos/alco/elixir/issues{/number}","pulls_url":"https://api.github.com/repos/alco/elixir/pulls{/number}","milestones_url":"https://api.github.com/repos/alco/elixir/milestones{/number}","notifications_url":"https://api.github.com/repos/alco/elixir/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/alco/elixir/labels{/name}","releases_url":"https://api.github.com/repos/alco/elixir/releases{/id}","created_at":"2012-03-24T07:48:47Z","updated_at":"2014-06-22T15:15:40Z","pushed_at":"2014-07-15T11:34:27Z","git_url":"git://github.com/alco/elixir.git","ssh_url":"git@github.com:alco/elixir.git","clone_url":"https://github.com/alco/elixir.git","svn_url":"https://github.com/alco/elixir","homepage":"http://elixir-lang.org/","size":30690,"stargazers_count":13,"watchers_count":13,"language":"Elixir","has_issues":true,"has_downloads":true,"has_wiki":true,"forks_count":0,"mirror_url":null,"open_issues_count":1,"forks":0,"open_issues":1,"watchers":13,"default_branch":"master"}},"base":{"label":"elixir-lang:master","ref":"master","sha":"e3a89050f295d5c0b747649571661798e4ba5bba","user":{"login":"elixir-lang","id":1481354,"avatar_url":"https://avatars.githubusercontent.com/u/1481354?","gravatar_id":"4c5c2c297ed9f4664cfbe7733a011fb2","url":"https://api.github.com/users/elixir-lang","html_url":"https://github.com/elixir-lang","followers_url":"https://api.github.com/users/elixir-lang/followers","following_url":"https://api.github.com/users/elixir-lang/following{/other_user}","gists_url":"https://api.github.com/users/elixir-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/elixir-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/elixir-lang/subscriptions","organizations_url":"https://api.github.com/users/elixir-lang/orgs","repos_url":"https://api.github.com/users/elixir-lang/repos","events_url":"https://api.github.com/users/elixir-lang/events{/privacy}","received_events_url":"https://api.github.com/users/elixir-lang/received_events","type":"Organization","site_admin":false},"repo":{"id":1234714,"name":"elixir","full_name":"elixir-lang/elixir","owner":{"login":"elixir-lang","id":1481354,"avatar_url":"https://avatars.githubusercontent.com/u/1481354?","gravatar_id":"4c5c2c297ed9f4664cfbe7733a011fb2","url":"https://api.github.com/users/elixir-lang","html_url":"https://github.com/elixir-lang","followers_url":"https://api.github.com/users/elixir-lang/followers","following_url":"https://api.github.com/users/elixir-lang/following{/other_user}","gists_url":"https://api.github.com/users/elixir-lang/gists{/gist_id}","starred_url":"https://api.github.com/users/elixir-lang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/elixir-lang/subscriptions","organizations_url":"https://api.github.com/users/elixir-lang/orgs","repos_url":"https://api.github.com/users/elixir-lang/repos","events_url":"https://api.github.com/users/elixir-lang/events{/privacy}","received_events_url":"https://api.github.com/users/elixir-lang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/elixir-lang/elixir","description":"Elixir is a functional, meta-programming aware language built on top of the Erlang VM. It is a dynamic language that focuses on tooling to leverage Erlang's abilities to build concurrent, distributed and fault-tolerant applications with hot code upgrades","fork":false,"url":"https://api.github.com/repos/elixir-lang/elixir","forks_url":"https://api.github.com/repos/elixir-lang/elixir/forks","keys_url":"https://api.github.com/repos/elixir-lang/elixir/keys{/key_id}","collaborators_url":"https://api.github.com/repos/elixir-lang/elixir/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/elixir-lang/elixir/teams","hooks_url":"https://api.github.com/repos/elixir-lang/elixir/hooks","issue_events_url":"https://api.github.com/repos/elixir-lang/elixir/issues/events{/number}","events_url":"https://api.github.com/repos/elixir-lang/elixir/events","assignees_url":"https://api.github.com/repos/elixir-lang/elixir/assignees{/user}","branches_url":"https://api.github.com/repos/elixir-lang/elixir/branches{/branch}","tags_url":"https://api.github.com/repos/elixir-lang/elixir/tags","blobs_url":"https://api.github.com/repos/elixir-lang/elixir/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/elixir-lang/elixir/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/elixir-lang/elixir/git/refs{/sha}","trees_url":"https://api.github.com/repos/elixir-lang/elixir/git/trees{/sha}","statuses_url":"https://api.github.com/repos/elixir-lang/elixir/statuses/{sha}","languages_url":"https://api.github.com/repos/elixir-lang/elixir/languages","stargazers_url":"https://api.github.com/repos/elixir-lang/elixir/stargazers","contributors_url":"https://api.github.com/repos/elixir-lang/elixir/contributors","subscribers_url":"https://api.github.com/repos/elixir-lang/elixir/subscribers","subscription_url":"https://api.github.com/repos/elixir-lang/elixir/subscription","commits_url":"https://api.github.com/repos/elixir-lang/elixir/commits{/sha}","git_commits_url":"https://api.github.com/repos/elixir-lang/elixir/git/commits{/sha}","comments_url":"https://api.github.com/repos/elixir-lang/elixir/comments{/number}","issue_comment_url":"https://api.github.com/repos/elixir-lang/elixir/issues/comments/{number}","contents_url":"https://api.github.com/repos/elixir-lang/elixir/contents/{+path}","compare_url":"https://api.github.com/repos/elixir-lang/elixir/compare/{base}...{head}","merges_url":"https://api.github.com/repos/elixir-lang/elixir/merges","archive_url":"https://api.github.com/repos/elixir-lang/elixir/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/elixir-lang/elixir/downloads","issues_url":"https://api.github.com/repos/elixir-lang/elixir/issues{/number}","pulls_url":"https://api.github.com/repos/elixir-lang/elixir/pulls{/number}","milestones_url":"https://api.github.com/repos/elixir-lang/elixir/milestones{/number}","notifications_url":"https://api.github.com/repos/elixir-lang/elixir/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/elixir-lang/elixir/labels{/name}","releases_url":"https://api.github.com/repos/elixir-lang/elixir/releases{/id}","created_at":"2011-01-09T08:43:57Z","updated_at":"2014-07-15T10:02:39Z","pushed_at":"2014-07-15T08:56:43Z","git_url":"git://github.com/elixir-lang/elixir.git","ssh_url":"git@github.com:elixir-lang/elixir.git","clone_url":"https://github.com/elixir-lang/elixir.git","svn_url":"https://github.com/elixir-lang/elixir","homepage":"http://elixir-lang.org/","size":49569,"stargazers_count":2510,"watchers_count":2510,"language":"Elixir","has_issues":true,"has_downloads":true,"has_wiki":true,"forks_count":367,"mirror_url":null,"open_issues_count":21,"forks":367,"open_issues":21,"watchers":2510,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/2538"},"html":{"href":"https://github.com/elixir-lang/elixir/pull/2538"},"issue":{"href":"https://api.github.com/repos/elixir-lang/elixir/issues/2538"},"comments":{"href":"https://api.github.com/repos/elixir-lang/elixir/issues/2538/comments"},"review_comments":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/2538/comments"},"review_comment":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/elixir-lang/elixir/pulls/2538/commits"},"statuses":{"href":"https://api.github.com/repos/elixir-lang/elixir/statuses/46e97481826c79778fbc518a7637dc97bee9b98e"}}}}