{"action":"created","comment":{"url":"https://api.github.com/repos/twitter/cassovary/pulls/comments/23587719","id":23587719,"diff_hunk":"@@ -0,0 +1,206 @@\n+package com.twitter.cassovary.graph\n+\n+import com.twitter.cassovary.graph.node.DynamicNode\n+import it.unimi.dsi.fastutil.ints.IntArrayList\n+import scala.collection.mutable.ArrayBuffer\n+import StoredGraphDir._\n+import com.twitter.cassovary.util.FastUtilUtils\n+\n+/**\n+ * A dynamic directed graph, implemented using an ArrayBuffer of IntArrayList\n+ * (from the fastutil library).  If n nodes are used, O(n) objects are created,\n+ * independent of the number of edges.\n+ *\n+ * For efficiency, it's recommended that ids be sequentially numbered, as\n+ * an internal array is stored which is longer than the maximum id seen.\n+ *\n+ * This class is not threadsafe.  If multiple thread access it simultaneously\n+ * and at least one mutates it, synchronization should be used.\n+ */\n+class ArrayBasedDynamicDirectedGraph(override val storedGraphDir: StoredGraphDir)\n+    extends DynamicDirectedGraph {\n+  // outboundLists(id) contains the outbound neighbors of the given id,\n+  // or null if the id is not in this graph.\n+  // If we aren't storing outbound neighbors, outboundLists will always remain size 0.\n+  private val outboundLists = new ArrayBuffer[IntArrayList]\n+  // (See above note on outboundLists)\n+  private val inboundLists = new ArrayBuffer[IntArrayList]\n+\n+  private var nodeCount_ = 0","path":"cassovary-core/src/main/scala/com/twitter/cassovary/graph/ArrayBasedDynamicDirectedGraph.scala","position":29,"original_position":29,"commit_id":"1ee4c8aecd446b839886e8d5f24bec2bac2dd315","original_commit_id":"1ee4c8aecd446b839886e8d5f24bec2bac2dd315","user":{"login":"pankajgupta","id":71128,"avatar_url":"https://avatars.githubusercontent.com/u/71128?v=3","gravatar_id":"","url":"https://api.github.com/users/pankajgupta","html_url":"https://github.com/pankajgupta","followers_url":"https://api.github.com/users/pankajgupta/followers","following_url":"https://api.github.com/users/pankajgupta/following{/other_user}","gists_url":"https://api.github.com/users/pankajgupta/gists{/gist_id}","starred_url":"https://api.github.com/users/pankajgupta/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pankajgupta/subscriptions","organizations_url":"https://api.github.com/users/pankajgupta/orgs","repos_url":"https://api.github.com/users/pankajgupta/repos","events_url":"https://api.github.com/users/pankajgupta/events{/privacy}","received_events_url":"https://api.github.com/users/pankajgupta/received_events","type":"User","site_admin":false},"body":"scala doesn't use the _ convention too much.","created_at":"2015-01-27T05:16:51Z","updated_at":"2015-01-27T05:16:51Z","html_url":"https://github.com/twitter/cassovary/pull/135#discussion_r23587719","pull_request_url":"https://api.github.com/repos/twitter/cassovary/pulls/135","_links":{"self":{"href":"https://api.github.com/repos/twitter/cassovary/pulls/comments/23587719"},"html":{"href":"https://github.com/twitter/cassovary/pull/135#discussion_r23587719"},"pull_request":{"href":"https://api.github.com/repos/twitter/cassovary/pulls/135"}}},"pull_request":{"url":"https://api.github.com/repos/twitter/cassovary/pulls/135","id":28072144,"html_url":"https://github.com/twitter/cassovary/pull/135","diff_url":"https://github.com/twitter/cassovary/pull/135.diff","patch_url":"https://github.com/twitter/cassovary/pull/135.patch","issue_url":"https://api.github.com/repos/twitter/cassovary/issues/135","number":135,"state":"open","locked":false,"title":"Array Based Dynamic Graph","user":{"login":"plofgren","id":6324377,"avatar_url":"https://avatars.githubusercontent.com/u/6324377?v=3","gravatar_id":"","url":"https://api.github.com/users/plofgren","html_url":"https://github.com/plofgren","followers_url":"https://api.github.com/users/plofgren/followers","following_url":"https://api.github.com/users/plofgren/following{/other_user}","gists_url":"https://api.github.com/users/plofgren/gists{/gist_id}","starred_url":"https://api.github.com/users/plofgren/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/plofgren/subscriptions","organizations_url":"https://api.github.com/users/plofgren/orgs","repos_url":"https://api.github.com/users/plofgren/repos","events_url":"https://api.github.com/users/plofgren/events{/privacy}","received_events_url":"https://api.github.com/users/plofgren/received_events","type":"User","site_admin":false},"body":"I've implemented a dynamic directed graph, using an ArrayBuffer of IntArrayList (from the fastutil library). If n nodes are used, O(n) objects are created, independent of the number of edges.\r\n\r\nComparison to the current class: Note that the current dynamic graph class SynchronizedDynamicGraph uses a ConcurrentHashMap to store nodes, which has more overhead than an ArrayBuffer when the nodes are mostly sequential.  Also, each node stores an ArrayBuffer[Int], which I belive boxes the ints into objects, creating overhead relative to fastutil's IntArrayList.  It also has non-trivial synchronization overhead; in particular when iterating over the neighbors of a node, the neighbors are first copied into a new array, then an iterator to the new array is returned.  The current class is better when the node Ids are very non-sequential or when automatic synchronization is needed, but otherwise I believe the new class is more efficient.  In a very informal comparison on a graph with several hundred million edges, the currrent class wouldn't load using 30GB of heap, while the new class fit the graph in 7.3 GB of RAM.\r\n\r\n@pankajgupta Could you take a look at this, or point me to someone else? \r\n\r\nThanks!","created_at":"2015-01-27T00:02:15Z","updated_at":"2015-01-27T05:16:51Z","closed_at":null,"merged_at":null,"merge_commit_sha":"5dbd64dde5ed519e412ebc0305609736f24f44a2","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/twitter/cassovary/pulls/135/commits","review_comments_url":"https://api.github.com/repos/twitter/cassovary/pulls/135/comments","review_comment_url":"https://api.github.com/repos/twitter/cassovary/pulls/comments/{number}","comments_url":"https://api.github.com/repos/twitter/cassovary/issues/135/comments","statuses_url":"https://api.github.com/repos/twitter/cassovary/statuses/1ee4c8aecd446b839886e8d5f24bec2bac2dd315","head":{"label":"plofgren:master","ref":"master","sha":"1ee4c8aecd446b839886e8d5f24bec2bac2dd315","user":{"login":"plofgren","id":6324377,"avatar_url":"https://avatars.githubusercontent.com/u/6324377?v=3","gravatar_id":"","url":"https://api.github.com/users/plofgren","html_url":"https://github.com/plofgren","followers_url":"https://api.github.com/users/plofgren/followers","following_url":"https://api.github.com/users/plofgren/following{/other_user}","gists_url":"https://api.github.com/users/plofgren/gists{/gist_id}","starred_url":"https://api.github.com/users/plofgren/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/plofgren/subscriptions","organizations_url":"https://api.github.com/users/plofgren/orgs","repos_url":"https://api.github.com/users/plofgren/repos","events_url":"https://api.github.com/users/plofgren/events{/privacy}","received_events_url":"https://api.github.com/users/plofgren/received_events","type":"User","site_admin":false},"repo":{"id":29319928,"name":"cassovary","full_name":"plofgren/cassovary","owner":{"login":"plofgren","id":6324377,"avatar_url":"https://avatars.githubusercontent.com/u/6324377?v=3","gravatar_id":"","url":"https://api.github.com/users/plofgren","html_url":"https://github.com/plofgren","followers_url":"https://api.github.com/users/plofgren/followers","following_url":"https://api.github.com/users/plofgren/following{/other_user}","gists_url":"https://api.github.com/users/plofgren/gists{/gist_id}","starred_url":"https://api.github.com/users/plofgren/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/plofgren/subscriptions","organizations_url":"https://api.github.com/users/plofgren/orgs","repos_url":"https://api.github.com/users/plofgren/repos","events_url":"https://api.github.com/users/plofgren/events{/privacy}","received_events_url":"https://api.github.com/users/plofgren/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/plofgren/cassovary","description":"Cassovary is a simple big graph processing library for the JVM","fork":true,"url":"https://api.github.com/repos/plofgren/cassovary","forks_url":"https://api.github.com/repos/plofgren/cassovary/forks","keys_url":"https://api.github.com/repos/plofgren/cassovary/keys{/key_id}","collaborators_url":"https://api.github.com/repos/plofgren/cassovary/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/plofgren/cassovary/teams","hooks_url":"https://api.github.com/repos/plofgren/cassovary/hooks","issue_events_url":"https://api.github.com/repos/plofgren/cassovary/issues/events{/number}","events_url":"https://api.github.com/repos/plofgren/cassovary/events","assignees_url":"https://api.github.com/repos/plofgren/cassovary/assignees{/user}","branches_url":"https://api.github.com/repos/plofgren/cassovary/branches{/branch}","tags_url":"https://api.github.com/repos/plofgren/cassovary/tags","blobs_url":"https://api.github.com/repos/plofgren/cassovary/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/plofgren/cassovary/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/plofgren/cassovary/git/refs{/sha}","trees_url":"https://api.github.com/repos/plofgren/cassovary/git/trees{/sha}","statuses_url":"https://api.github.com/repos/plofgren/cassovary/statuses/{sha}","languages_url":"https://api.github.com/repos/plofgren/cassovary/languages","stargazers_url":"https://api.github.com/repos/plofgren/cassovary/stargazers","contributors_url":"https://api.github.com/repos/plofgren/cassovary/contributors","subscribers_url":"https://api.github.com/repos/plofgren/cassovary/subscribers","subscription_url":"https://api.github.com/repos/plofgren/cassovary/subscription","commits_url":"https://api.github.com/repos/plofgren/cassovary/commits{/sha}","git_commits_url":"https://api.github.com/repos/plofgren/cassovary/git/commits{/sha}","comments_url":"https://api.github.com/repos/plofgren/cassovary/comments{/number}","issue_comment_url":"https://api.github.com/repos/plofgren/cassovary/issues/comments/{number}","contents_url":"https://api.github.com/repos/plofgren/cassovary/contents/{+path}","compare_url":"https://api.github.com/repos/plofgren/cassovary/compare/{base}...{head}","merges_url":"https://api.github.com/repos/plofgren/cassovary/merges","archive_url":"https://api.github.com/repos/plofgren/cassovary/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/plofgren/cassovary/downloads","issues_url":"https://api.github.com/repos/plofgren/cassovary/issues{/number}","pulls_url":"https://api.github.com/repos/plofgren/cassovary/pulls{/number}","milestones_url":"https://api.github.com/repos/plofgren/cassovary/milestones{/number}","notifications_url":"https://api.github.com/repos/plofgren/cassovary/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/plofgren/cassovary/labels{/name}","releases_url":"https://api.github.com/repos/plofgren/cassovary/releases{/id}","created_at":"2015-01-15T21:49:58Z","updated_at":"2015-01-26T23:28:29Z","pushed_at":"2015-01-26T23:28:29Z","git_url":"git://github.com/plofgren/cassovary.git","ssh_url":"git@github.com:plofgren/cassovary.git","clone_url":"https://github.com/plofgren/cassovary.git","svn_url":"https://github.com/plofgren/cassovary","homepage":"http://twitter.com/cassovary","size":2666,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"twitter:master","ref":"master","sha":"004f2ac8fbbd014c8627fd1a7ff77b1338af40cc","user":{"login":"twitter","id":50278,"avatar_url":"https://avatars.githubusercontent.com/u/50278?v=3","gravatar_id":"","url":"https://api.github.com/users/twitter","html_url":"https://github.com/twitter","followers_url":"https://api.github.com/users/twitter/followers","following_url":"https://api.github.com/users/twitter/following{/other_user}","gists_url":"https://api.github.com/users/twitter/gists{/gist_id}","starred_url":"https://api.github.com/users/twitter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/twitter/subscriptions","organizations_url":"https://api.github.com/users/twitter/orgs","repos_url":"https://api.github.com/users/twitter/repos","events_url":"https://api.github.com/users/twitter/events{/privacy}","received_events_url":"https://api.github.com/users/twitter/received_events","type":"Organization","site_admin":false},"repo":{"id":3509388,"name":"cassovary","full_name":"twitter/cassovary","owner":{"login":"twitter","id":50278,"avatar_url":"https://avatars.githubusercontent.com/u/50278?v=3","gravatar_id":"","url":"https://api.github.com/users/twitter","html_url":"https://github.com/twitter","followers_url":"https://api.github.com/users/twitter/followers","following_url":"https://api.github.com/users/twitter/following{/other_user}","gists_url":"https://api.github.com/users/twitter/gists{/gist_id}","starred_url":"https://api.github.com/users/twitter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/twitter/subscriptions","organizations_url":"https://api.github.com/users/twitter/orgs","repos_url":"https://api.github.com/users/twitter/repos","events_url":"https://api.github.com/users/twitter/events{/privacy}","received_events_url":"https://api.github.com/users/twitter/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/twitter/cassovary","description":"Cassovary is a simple big graph processing library for the JVM","fork":false,"url":"https://api.github.com/repos/twitter/cassovary","forks_url":"https://api.github.com/repos/twitter/cassovary/forks","keys_url":"https://api.github.com/repos/twitter/cassovary/keys{/key_id}","collaborators_url":"https://api.github.com/repos/twitter/cassovary/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/twitter/cassovary/teams","hooks_url":"https://api.github.com/repos/twitter/cassovary/hooks","issue_events_url":"https://api.github.com/repos/twitter/cassovary/issues/events{/number}","events_url":"https://api.github.com/repos/twitter/cassovary/events","assignees_url":"https://api.github.com/repos/twitter/cassovary/assignees{/user}","branches_url":"https://api.github.com/repos/twitter/cassovary/branches{/branch}","tags_url":"https://api.github.com/repos/twitter/cassovary/tags","blobs_url":"https://api.github.com/repos/twitter/cassovary/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/twitter/cassovary/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/twitter/cassovary/git/refs{/sha}","trees_url":"https://api.github.com/repos/twitter/cassovary/git/trees{/sha}","statuses_url":"https://api.github.com/repos/twitter/cassovary/statuses/{sha}","languages_url":"https://api.github.com/repos/twitter/cassovary/languages","stargazers_url":"https://api.github.com/repos/twitter/cassovary/stargazers","contributors_url":"https://api.github.com/repos/twitter/cassovary/contributors","subscribers_url":"https://api.github.com/repos/twitter/cassovary/subscribers","subscription_url":"https://api.github.com/repos/twitter/cassovary/subscription","commits_url":"https://api.github.com/repos/twitter/cassovary/commits{/sha}","git_commits_url":"https://api.github.com/repos/twitter/cassovary/git/commits{/sha}","comments_url":"https://api.github.com/repos/twitter/cassovary/comments{/number}","issue_comment_url":"https://api.github.com/repos/twitter/cassovary/issues/comments/{number}","contents_url":"https://api.github.com/repos/twitter/cassovary/contents/{+path}","compare_url":"https://api.github.com/repos/twitter/cassovary/compare/{base}...{head}","merges_url":"https://api.github.com/repos/twitter/cassovary/merges","archive_url":"https://api.github.com/repos/twitter/cassovary/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/twitter/cassovary/downloads","issues_url":"https://api.github.com/repos/twitter/cassovary/issues{/number}","pulls_url":"https://api.github.com/repos/twitter/cassovary/pulls{/number}","milestones_url":"https://api.github.com/repos/twitter/cassovary/milestones{/number}","notifications_url":"https://api.github.com/repos/twitter/cassovary/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/twitter/cassovary/labels{/name}","releases_url":"https://api.github.com/repos/twitter/cassovary/releases{/id}","created_at":"2012-02-21T23:22:30Z","updated_at":"2015-01-27T00:58:15Z","pushed_at":"2015-01-26T18:57:08Z","git_url":"git://github.com/twitter/cassovary.git","ssh_url":"git@github.com:twitter/cassovary.git","clone_url":"https://github.com/twitter/cassovary.git","svn_url":"https://github.com/twitter/cassovary","homepage":"http://twitter.com/cassovary","size":4163,"stargazers_count":674,"watchers_count":674,"language":"Scala","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":85,"mirror_url":null,"open_issues_count":12,"forks":85,"open_issues":12,"watchers":674,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/twitter/cassovary/pulls/135"},"html":{"href":"https://github.com/twitter/cassovary/pull/135"},"issue":{"href":"https://api.github.com/repos/twitter/cassovary/issues/135"},"comments":{"href":"https://api.github.com/repos/twitter/cassovary/issues/135/comments"},"review_comments":{"href":"https://api.github.com/repos/twitter/cassovary/pulls/135/comments"},"review_comment":{"href":"https://api.github.com/repos/twitter/cassovary/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/twitter/cassovary/pulls/135/commits"},"statuses":{"href":"https://api.github.com/repos/twitter/cassovary/statuses/1ee4c8aecd446b839886e8d5f24bec2bac2dd315"}}}}