{"action":"opened","number":61,"pull_request":{"url":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls/61","id":70857046,"html_url":"https://github.com/RubenVerborgh/N3.js/pull/61","diff_url":"https://github.com/RubenVerborgh/N3.js/pull/61.diff","patch_url":"https://github.com/RubenVerborgh/N3.js/pull/61.patch","issue_url":"https://api.github.com/repos/RubenVerborgh/N3.js/issues/61","number":61,"state":"open","locked":false,"title":"Improve N3Store lookup efficiency by maintaining an inverse index","user":{"login":"rubensworks","id":440384,"avatar_url":"https://avatars.githubusercontent.com/u/440384?v=3","gravatar_id":"","url":"https://api.github.com/users/rubensworks","html_url":"https://github.com/rubensworks","followers_url":"https://api.github.com/users/rubensworks/followers","following_url":"https://api.github.com/users/rubensworks/following{/other_user}","gists_url":"https://api.github.com/users/rubensworks/gists{/gist_id}","starred_url":"https://api.github.com/users/rubensworks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rubensworks/subscriptions","organizations_url":"https://api.github.com/users/rubensworks/orgs","repos_url":"https://api.github.com/users/rubensworks/repos","events_url":"https://api.github.com/users/rubensworks/events{/privacy}","received_events_url":"https://api.github.com/users/rubensworks/received_events","type":"User","site_admin":false},"body":"This is an improvement for the lookup-speed of the `N3Store`, as discussed in https://github.com/rubensworks/N3.js/commit/87cae2914751c93fdeb8c005b6c445d002b6f446.\r\nApparently, `Object.keys` became more expensive since one of the newer Node versions,\r\nso this PR avoids calling this function every time on `this._entities` when doing lookups.\r\nInstead, a inverse-index is maintained to avoid this operation.\r\n\r\nI ran the performance tests to compare this new approach with the old one,\r\nand it resulted in some interesting results:\r\n\r\n```\r\n2 variables for lookups (a.k.a original perf tests):\r\nNEW:\r\n    N3Store performance test\r\n    - Adding 16777216 triples in the default graph: 18177.111ms\r\n    * Memory usage for triples: 831MB\r\n    - Finding all 16777216 triples to the default graph 196608 times: 6421.472ms\r\n\r\n    - Adding 16777216 quads: 24892.776ms\r\n    * Memory usage for quads: 676MB\r\n    - Finding all 16777216 quads 1048576 times: 13141.350ms\r\n\r\nOLD:\r\n    N3Store performance test\r\n    - Adding 16777216 triples in the default graph: 19465.032ms\r\n    * Memory usage for triples: 808MB\r\n    - Finding all 16777216 triples to the default graph 196608 times: 3206.058ms\r\n\r\n    - Adding 16777216 quads: 24860.754ms\r\n    * Memory usage for quads: 717MB\r\n    - Finding all 16777216 quads 1048576 times: 19608.113ms\r\n------------------------------------------------------------------------------------\r\n1 variable for lookup:\r\nNEW:\r\n    - Finding all 16777216 triples to the default graph 65536 times: 1207.522ms\r\nOLD:\r\n    - Finding all 16777216 triples to the default graph 65536 times: 2133.597ms\r\n------------------------------------------------------------------------------------\r\n0 variables for lookup:\r\nNEW:\r\n    - Finding all 16777216 triples to the default graph 65536 times: 92602.621ms\r\nOLD:\r\n    - Finding all 16777216 triples to the default graph 65536 times: 283470.831ms\r\n```\r\n\r\nIt appears that this new approach (precalculation of inverse index) is two times *slower* than the original approach for lookups with two variables (? ? o, ? p ?, s ? ?).\r\nWhen increasing the selectivity of the lookups, this new approach becomes *faster* than the old one.\r\nThe new version is twice as fast as the old version for lookups with only one variables.\r\nAnd it is three times faster than the old version for lookups without variables.\r\n\r\nLike you have said before, the efficiency strongly depends on the access patterns.\r\nSo I'm not sure if you should accept this PR, since it makes lookups slower with two variables, but faster for the rest.\r\nMaybe we should make two versions of the `N3Store` that are optimized for different cases.\r\nOr maybe some more elaborate solution is possible.\r\n","created_at":"2016-05-20T13:45:32Z","updated_at":"2016-05-20T13:45:32Z","closed_at":null,"merged_at":null,"merge_commit_sha":null,"assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls/61/commits","review_comments_url":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls/61/comments","review_comment_url":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls/comments{/number}","comments_url":"https://api.github.com/repos/RubenVerborgh/N3.js/issues/61/comments","statuses_url":"https://api.github.com/repos/RubenVerborgh/N3.js/statuses/1d2d975c10ad3252d38393c3ea97b36fd3ab986a","head":{"label":"rubensworks:fix-lookup-efficiency2","ref":"fix-lookup-efficiency2","sha":"1d2d975c10ad3252d38393c3ea97b36fd3ab986a","user":{"login":"rubensworks","id":440384,"avatar_url":"https://avatars.githubusercontent.com/u/440384?v=3","gravatar_id":"","url":"https://api.github.com/users/rubensworks","html_url":"https://github.com/rubensworks","followers_url":"https://api.github.com/users/rubensworks/followers","following_url":"https://api.github.com/users/rubensworks/following{/other_user}","gists_url":"https://api.github.com/users/rubensworks/gists{/gist_id}","starred_url":"https://api.github.com/users/rubensworks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rubensworks/subscriptions","organizations_url":"https://api.github.com/users/rubensworks/orgs","repos_url":"https://api.github.com/users/rubensworks/repos","events_url":"https://api.github.com/users/rubensworks/events{/privacy}","received_events_url":"https://api.github.com/users/rubensworks/received_events","type":"User","site_admin":false},"repo":{"id":26714306,"name":"N3.js","full_name":"rubensworks/N3.js","owner":{"login":"rubensworks","id":440384,"avatar_url":"https://avatars.githubusercontent.com/u/440384?v=3","gravatar_id":"","url":"https://api.github.com/users/rubensworks","html_url":"https://github.com/rubensworks","followers_url":"https://api.github.com/users/rubensworks/followers","following_url":"https://api.github.com/users/rubensworks/following{/other_user}","gists_url":"https://api.github.com/users/rubensworks/gists{/gist_id}","starred_url":"https://api.github.com/users/rubensworks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rubensworks/subscriptions","organizations_url":"https://api.github.com/users/rubensworks/orgs","repos_url":"https://api.github.com/users/rubensworks/repos","events_url":"https://api.github.com/users/rubensworks/events{/privacy}","received_events_url":"https://api.github.com/users/rubensworks/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/rubensworks/N3.js","description":"Lightning fast, asynchronous, streaming Turtle for JavaScript","fork":true,"url":"https://api.github.com/repos/rubensworks/N3.js","forks_url":"https://api.github.com/repos/rubensworks/N3.js/forks","keys_url":"https://api.github.com/repos/rubensworks/N3.js/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rubensworks/N3.js/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rubensworks/N3.js/teams","hooks_url":"https://api.github.com/repos/rubensworks/N3.js/hooks","issue_events_url":"https://api.github.com/repos/rubensworks/N3.js/issues/events{/number}","events_url":"https://api.github.com/repos/rubensworks/N3.js/events","assignees_url":"https://api.github.com/repos/rubensworks/N3.js/assignees{/user}","branches_url":"https://api.github.com/repos/rubensworks/N3.js/branches{/branch}","tags_url":"https://api.github.com/repos/rubensworks/N3.js/tags","blobs_url":"https://api.github.com/repos/rubensworks/N3.js/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rubensworks/N3.js/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rubensworks/N3.js/git/refs{/sha}","trees_url":"https://api.github.com/repos/rubensworks/N3.js/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rubensworks/N3.js/statuses/{sha}","languages_url":"https://api.github.com/repos/rubensworks/N3.js/languages","stargazers_url":"https://api.github.com/repos/rubensworks/N3.js/stargazers","contributors_url":"https://api.github.com/repos/rubensworks/N3.js/contributors","subscribers_url":"https://api.github.com/repos/rubensworks/N3.js/subscribers","subscription_url":"https://api.github.com/repos/rubensworks/N3.js/subscription","commits_url":"https://api.github.com/repos/rubensworks/N3.js/commits{/sha}","git_commits_url":"https://api.github.com/repos/rubensworks/N3.js/git/commits{/sha}","comments_url":"https://api.github.com/repos/rubensworks/N3.js/comments{/number}","issue_comment_url":"https://api.github.com/repos/rubensworks/N3.js/issues/comments{/number}","contents_url":"https://api.github.com/repos/rubensworks/N3.js/contents/{+path}","compare_url":"https://api.github.com/repos/rubensworks/N3.js/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rubensworks/N3.js/merges","archive_url":"https://api.github.com/repos/rubensworks/N3.js/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rubensworks/N3.js/downloads","issues_url":"https://api.github.com/repos/rubensworks/N3.js/issues{/number}","pulls_url":"https://api.github.com/repos/rubensworks/N3.js/pulls{/number}","milestones_url":"https://api.github.com/repos/rubensworks/N3.js/milestones{/number}","notifications_url":"https://api.github.com/repos/rubensworks/N3.js/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rubensworks/N3.js/labels{/name}","releases_url":"https://api.github.com/repos/rubensworks/N3.js/releases{/id}","deployments_url":"https://api.github.com/repos/rubensworks/N3.js/deployments","created_at":"2014-11-16T13:06:24Z","updated_at":"2014-11-19T14:28:15Z","pushed_at":"2016-05-20T13:43:24Z","git_url":"git://github.com/rubensworks/N3.js.git","ssh_url":"git@github.com:rubensworks/N3.js.git","clone_url":"https://github.com/rubensworks/N3.js.git","svn_url":"https://github.com/rubensworks/N3.js","homepage":"","size":720,"stargazers_count":0,"watchers_count":0,"language":"JavaScript","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":"RubenVerborgh:master","ref":"master","sha":"04f4e21f4ccb351587dc00a3f26340b28d4bb10f","user":{"login":"RubenVerborgh","id":675313,"avatar_url":"https://avatars.githubusercontent.com/u/675313?v=3","gravatar_id":"","url":"https://api.github.com/users/RubenVerborgh","html_url":"https://github.com/RubenVerborgh","followers_url":"https://api.github.com/users/RubenVerborgh/followers","following_url":"https://api.github.com/users/RubenVerborgh/following{/other_user}","gists_url":"https://api.github.com/users/RubenVerborgh/gists{/gist_id}","starred_url":"https://api.github.com/users/RubenVerborgh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RubenVerborgh/subscriptions","organizations_url":"https://api.github.com/users/RubenVerborgh/orgs","repos_url":"https://api.github.com/users/RubenVerborgh/repos","events_url":"https://api.github.com/users/RubenVerborgh/events{/privacy}","received_events_url":"https://api.github.com/users/RubenVerborgh/received_events","type":"User","site_admin":false},"repo":{"id":3058202,"name":"N3.js","full_name":"RubenVerborgh/N3.js","owner":{"login":"RubenVerborgh","id":675313,"avatar_url":"https://avatars.githubusercontent.com/u/675313?v=3","gravatar_id":"","url":"https://api.github.com/users/RubenVerborgh","html_url":"https://github.com/RubenVerborgh","followers_url":"https://api.github.com/users/RubenVerborgh/followers","following_url":"https://api.github.com/users/RubenVerborgh/following{/other_user}","gists_url":"https://api.github.com/users/RubenVerborgh/gists{/gist_id}","starred_url":"https://api.github.com/users/RubenVerborgh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RubenVerborgh/subscriptions","organizations_url":"https://api.github.com/users/RubenVerborgh/orgs","repos_url":"https://api.github.com/users/RubenVerborgh/repos","events_url":"https://api.github.com/users/RubenVerborgh/events{/privacy}","received_events_url":"https://api.github.com/users/RubenVerborgh/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/RubenVerborgh/N3.js","description":"Lightning fast, asynchronous, streaming RDF for JavaScript","fork":false,"url":"https://api.github.com/repos/RubenVerborgh/N3.js","forks_url":"https://api.github.com/repos/RubenVerborgh/N3.js/forks","keys_url":"https://api.github.com/repos/RubenVerborgh/N3.js/keys{/key_id}","collaborators_url":"https://api.github.com/repos/RubenVerborgh/N3.js/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/RubenVerborgh/N3.js/teams","hooks_url":"https://api.github.com/repos/RubenVerborgh/N3.js/hooks","issue_events_url":"https://api.github.com/repos/RubenVerborgh/N3.js/issues/events{/number}","events_url":"https://api.github.com/repos/RubenVerborgh/N3.js/events","assignees_url":"https://api.github.com/repos/RubenVerborgh/N3.js/assignees{/user}","branches_url":"https://api.github.com/repos/RubenVerborgh/N3.js/branches{/branch}","tags_url":"https://api.github.com/repos/RubenVerborgh/N3.js/tags","blobs_url":"https://api.github.com/repos/RubenVerborgh/N3.js/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/RubenVerborgh/N3.js/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/RubenVerborgh/N3.js/git/refs{/sha}","trees_url":"https://api.github.com/repos/RubenVerborgh/N3.js/git/trees{/sha}","statuses_url":"https://api.github.com/repos/RubenVerborgh/N3.js/statuses/{sha}","languages_url":"https://api.github.com/repos/RubenVerborgh/N3.js/languages","stargazers_url":"https://api.github.com/repos/RubenVerborgh/N3.js/stargazers","contributors_url":"https://api.github.com/repos/RubenVerborgh/N3.js/contributors","subscribers_url":"https://api.github.com/repos/RubenVerborgh/N3.js/subscribers","subscription_url":"https://api.github.com/repos/RubenVerborgh/N3.js/subscription","commits_url":"https://api.github.com/repos/RubenVerborgh/N3.js/commits{/sha}","git_commits_url":"https://api.github.com/repos/RubenVerborgh/N3.js/git/commits{/sha}","comments_url":"https://api.github.com/repos/RubenVerborgh/N3.js/comments{/number}","issue_comment_url":"https://api.github.com/repos/RubenVerborgh/N3.js/issues/comments{/number}","contents_url":"https://api.github.com/repos/RubenVerborgh/N3.js/contents/{+path}","compare_url":"https://api.github.com/repos/RubenVerborgh/N3.js/compare/{base}...{head}","merges_url":"https://api.github.com/repos/RubenVerborgh/N3.js/merges","archive_url":"https://api.github.com/repos/RubenVerborgh/N3.js/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/RubenVerborgh/N3.js/downloads","issues_url":"https://api.github.com/repos/RubenVerborgh/N3.js/issues{/number}","pulls_url":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls{/number}","milestones_url":"https://api.github.com/repos/RubenVerborgh/N3.js/milestones{/number}","notifications_url":"https://api.github.com/repos/RubenVerborgh/N3.js/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/RubenVerborgh/N3.js/labels{/name}","releases_url":"https://api.github.com/repos/RubenVerborgh/N3.js/releases{/id}","deployments_url":"https://api.github.com/repos/RubenVerborgh/N3.js/deployments","created_at":"2011-12-27T18:34:09Z","updated_at":"2016-05-09T09:39:32Z","pushed_at":"2015-10-30T14:16:04Z","git_url":"git://github.com/RubenVerborgh/N3.js.git","ssh_url":"git@github.com:RubenVerborgh/N3.js.git","clone_url":"https://github.com/RubenVerborgh/N3.js.git","svn_url":"https://github.com/RubenVerborgh/N3.js","homepage":"","size":1708,"stargazers_count":204,"watchers_count":204,"language":"JavaScript","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":41,"mirror_url":null,"open_issues_count":4,"forks":41,"open_issues":4,"watchers":204,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls/61"},"html":{"href":"https://github.com/RubenVerborgh/N3.js/pull/61"},"issue":{"href":"https://api.github.com/repos/RubenVerborgh/N3.js/issues/61"},"comments":{"href":"https://api.github.com/repos/RubenVerborgh/N3.js/issues/61/comments"},"review_comments":{"href":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls/61/comments"},"review_comment":{"href":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/RubenVerborgh/N3.js/pulls/61/commits"},"statuses":{"href":"https://api.github.com/repos/RubenVerborgh/N3.js/statuses/1d2d975c10ad3252d38393c3ea97b36fd3ab986a"}},"merged":false,"mergeable":null,"mergeable_state":"unknown","merged_by":null,"comments":0,"review_comments":0,"commits":1,"additions":7,"deletions":5,"changed_files":1}}
{"actor":{"display_login":"rubensworks"}}