{"action":"created","comment":{"url":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/comments/47862061","id":47862061,"diff_hunk":"@@ -0,0 +1,15 @@\n+Subproblem 1: Multithreading\n+\n+Using a serial implementation gave me ~12-13 simulation fps on average, while 4 threads gave me ~17-19 simulation fps on average. The speedup, while significant in terms of percentage, was not amazing. This could be due to a number of things, including poor spacial locality.\n+\n+Subproblem 2: Spatial Decomposition\n+\n+Adding in this part increased the fps significantly. Using a serial implementation gave ~1100-1300 simulation fps on average, while 4 threads gave ~1800-2000 simulation fps. This increase can be attributed to the fact that our checking algorithm went from an O(N^2) to an O(N) algorithm, which increases the efficiency dramatically.\n+\n+Subproblem 3: Spatially Coherent Sorting\n+\n+Using a serial implementation gave ~1200-1500 simulation fps on average, while 4 threads gave ~2000-2300 simulation fps. This increased performance was because of the improved space locality. Here, I used Morton ordering (and borrowed code from the Wikipedia page), which results in strong spatial coherence -- when the objects are closer to each other in memory, they will be accessed faster.\n+\n+Subproblem 4: Locking\n+\n+Using locks and 4 threads, I had ~1000-1200 simulation fps, while not using locking provided an average of ~2000 simulation fps. This is mostly likely due to the fact that there exists overhead in creating, acquiring, and releasing locks, in addition to waiting for access to pointers.","path":"HW2/P5/P5.txt","position":15,"original_position":15,"commit_id":"28d7b9e501d31f7753f18af2eddf38c31b25d831","original_commit_id":"28d7b9e501d31f7753f18af2eddf38c31b25d831","user":{"login":"georgeqi94","id":6043012,"avatar_url":"https://avatars.githubusercontent.com/u/6043012?v=3","gravatar_id":"","url":"https://api.github.com/users/georgeqi94","html_url":"https://github.com/georgeqi94","followers_url":"https://api.github.com/users/georgeqi94/followers","following_url":"https://api.github.com/users/georgeqi94/following{/other_user}","gists_url":"https://api.github.com/users/georgeqi94/gists{/gist_id}","starred_url":"https://api.github.com/users/georgeqi94/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/georgeqi94/subscriptions","organizations_url":"https://api.github.com/users/georgeqi94/orgs","repos_url":"https://api.github.com/users/georgeqi94/repos","events_url":"https://api.github.com/users/georgeqi94/events{/privacy}","received_events_url":"https://api.github.com/users/georgeqi94/received_events","type":"User","site_admin":false},"body":"Yes -- using the average numbers in the ranges that I provided above, I quickly mocked up a few sample graphs of what this shows. I used a separate graph for subproblem 1 because of the significantly lower range that it uses. Hope this helps!\r\n\r\n![subprob1](https://cloud.githubusercontent.com/assets/6043012/11859514/acd79cb0-a439-11e5-9bd9-5a74ddf0bdfd.png)\r\n![subprob2-4](https://cloud.githubusercontent.com/assets/6043012/11859517/b1e2cdec-a439-11e5-9f9f-169db5c2cc15.png)","created_at":"2015-12-17T02:13:20Z","updated_at":"2015-12-17T02:13:20Z","html_url":"https://github.com/harvard-cs205/cs205-homework/pull/306#discussion_r47862061","pull_request_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/306","_links":{"self":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/comments/47862061"},"html":{"href":"https://github.com/harvard-cs205/cs205-homework/pull/306#discussion_r47862061"},"pull_request":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/306"}}},"pull_request":{"url":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/306","id":49519023,"html_url":"https://github.com/harvard-cs205/cs205-homework/pull/306","diff_url":"https://github.com/harvard-cs205/cs205-homework/pull/306.diff","patch_url":"https://github.com/harvard-cs205/cs205-homework/pull/306.patch","issue_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/issues/306","number":306,"state":"open","locked":false,"title":"HW2","user":{"login":"georgeqi94","id":6043012,"avatar_url":"https://avatars.githubusercontent.com/u/6043012?v=3","gravatar_id":"","url":"https://api.github.com/users/georgeqi94","html_url":"https://github.com/georgeqi94","followers_url":"https://api.github.com/users/georgeqi94/followers","following_url":"https://api.github.com/users/georgeqi94/following{/other_user}","gists_url":"https://api.github.com/users/georgeqi94/gists{/gist_id}","starred_url":"https://api.github.com/users/georgeqi94/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/georgeqi94/subscriptions","organizations_url":"https://api.github.com/users/georgeqi94/orgs","repos_url":"https://api.github.com/users/georgeqi94/repos","events_url":"https://api.github.com/users/georgeqi94/events{/privacy}","received_events_url":"https://api.github.com/users/georgeqi94/received_events","type":"User","site_admin":false},"body":"","created_at":"2015-11-03T04:40:45Z","updated_at":"2015-12-17T02:13:20Z","closed_at":null,"merged_at":null,"merge_commit_sha":"d2c4f294ecf550a15f52dae74b9476f8886fabd7","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/306/commits","review_comments_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/306/comments","review_comment_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/comments{/number}","comments_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/issues/306/comments","statuses_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/statuses/28d7b9e501d31f7753f18af2eddf38c31b25d831","head":{"label":"georgeqi94:HW2","ref":"HW2","sha":"28d7b9e501d31f7753f18af2eddf38c31b25d831","user":{"login":"georgeqi94","id":6043012,"avatar_url":"https://avatars.githubusercontent.com/u/6043012?v=3","gravatar_id":"","url":"https://api.github.com/users/georgeqi94","html_url":"https://github.com/georgeqi94","followers_url":"https://api.github.com/users/georgeqi94/followers","following_url":"https://api.github.com/users/georgeqi94/following{/other_user}","gists_url":"https://api.github.com/users/georgeqi94/gists{/gist_id}","starred_url":"https://api.github.com/users/georgeqi94/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/georgeqi94/subscriptions","organizations_url":"https://api.github.com/users/georgeqi94/orgs","repos_url":"https://api.github.com/users/georgeqi94/repos","events_url":"https://api.github.com/users/georgeqi94/events{/privacy}","received_events_url":"https://api.github.com/users/georgeqi94/received_events","type":"User","site_admin":false},"repo":{"id":42093251,"name":"cs205-homework","full_name":"georgeqi94/cs205-homework","owner":{"login":"georgeqi94","id":6043012,"avatar_url":"https://avatars.githubusercontent.com/u/6043012?v=3","gravatar_id":"","url":"https://api.github.com/users/georgeqi94","html_url":"https://github.com/georgeqi94","followers_url":"https://api.github.com/users/georgeqi94/followers","following_url":"https://api.github.com/users/georgeqi94/following{/other_user}","gists_url":"https://api.github.com/users/georgeqi94/gists{/gist_id}","starred_url":"https://api.github.com/users/georgeqi94/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/georgeqi94/subscriptions","organizations_url":"https://api.github.com/users/georgeqi94/orgs","repos_url":"https://api.github.com/users/georgeqi94/repos","events_url":"https://api.github.com/users/georgeqi94/events{/privacy}","received_events_url":"https://api.github.com/users/georgeqi94/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/georgeqi94/cs205-homework","description":"","fork":true,"url":"https://api.github.com/repos/georgeqi94/cs205-homework","forks_url":"https://api.github.com/repos/georgeqi94/cs205-homework/forks","keys_url":"https://api.github.com/repos/georgeqi94/cs205-homework/keys{/key_id}","collaborators_url":"https://api.github.com/repos/georgeqi94/cs205-homework/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/georgeqi94/cs205-homework/teams","hooks_url":"https://api.github.com/repos/georgeqi94/cs205-homework/hooks","issue_events_url":"https://api.github.com/repos/georgeqi94/cs205-homework/issues/events{/number}","events_url":"https://api.github.com/repos/georgeqi94/cs205-homework/events","assignees_url":"https://api.github.com/repos/georgeqi94/cs205-homework/assignees{/user}","branches_url":"https://api.github.com/repos/georgeqi94/cs205-homework/branches{/branch}","tags_url":"https://api.github.com/repos/georgeqi94/cs205-homework/tags","blobs_url":"https://api.github.com/repos/georgeqi94/cs205-homework/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/georgeqi94/cs205-homework/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/georgeqi94/cs205-homework/git/refs{/sha}","trees_url":"https://api.github.com/repos/georgeqi94/cs205-homework/git/trees{/sha}","statuses_url":"https://api.github.com/repos/georgeqi94/cs205-homework/statuses/{sha}","languages_url":"https://api.github.com/repos/georgeqi94/cs205-homework/languages","stargazers_url":"https://api.github.com/repos/georgeqi94/cs205-homework/stargazers","contributors_url":"https://api.github.com/repos/georgeqi94/cs205-homework/contributors","subscribers_url":"https://api.github.com/repos/georgeqi94/cs205-homework/subscribers","subscription_url":"https://api.github.com/repos/georgeqi94/cs205-homework/subscription","commits_url":"https://api.github.com/repos/georgeqi94/cs205-homework/commits{/sha}","git_commits_url":"https://api.github.com/repos/georgeqi94/cs205-homework/git/commits{/sha}","comments_url":"https://api.github.com/repos/georgeqi94/cs205-homework/comments{/number}","issue_comment_url":"https://api.github.com/repos/georgeqi94/cs205-homework/issues/comments{/number}","contents_url":"https://api.github.com/repos/georgeqi94/cs205-homework/contents/{+path}","compare_url":"https://api.github.com/repos/georgeqi94/cs205-homework/compare/{base}...{head}","merges_url":"https://api.github.com/repos/georgeqi94/cs205-homework/merges","archive_url":"https://api.github.com/repos/georgeqi94/cs205-homework/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/georgeqi94/cs205-homework/downloads","issues_url":"https://api.github.com/repos/georgeqi94/cs205-homework/issues{/number}","pulls_url":"https://api.github.com/repos/georgeqi94/cs205-homework/pulls{/number}","milestones_url":"https://api.github.com/repos/georgeqi94/cs205-homework/milestones{/number}","notifications_url":"https://api.github.com/repos/georgeqi94/cs205-homework/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/georgeqi94/cs205-homework/labels{/name}","releases_url":"https://api.github.com/repos/georgeqi94/cs205-homework/releases{/id}","created_at":"2015-09-08T06:08:00Z","updated_at":"2015-09-08T06:08:00Z","pushed_at":"2015-11-20T14:29:40Z","git_url":"git://github.com/georgeqi94/cs205-homework.git","ssh_url":"git@github.com:georgeqi94/cs205-homework.git","clone_url":"https://github.com/georgeqi94/cs205-homework.git","svn_url":"https://github.com/georgeqi94/cs205-homework","homepage":null,"size":67890,"stargazers_count":0,"watchers_count":0,"language":"Python","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":"harvard-cs205:master","ref":"master","sha":"ed6f0167fd1f6097ce9e454c2950c5db00a0c513","user":{"login":"harvard-cs205","id":13456002,"avatar_url":"https://avatars.githubusercontent.com/u/13456002?v=3","gravatar_id":"","url":"https://api.github.com/users/harvard-cs205","html_url":"https://github.com/harvard-cs205","followers_url":"https://api.github.com/users/harvard-cs205/followers","following_url":"https://api.github.com/users/harvard-cs205/following{/other_user}","gists_url":"https://api.github.com/users/harvard-cs205/gists{/gist_id}","starred_url":"https://api.github.com/users/harvard-cs205/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/harvard-cs205/subscriptions","organizations_url":"https://api.github.com/users/harvard-cs205/orgs","repos_url":"https://api.github.com/users/harvard-cs205/repos","events_url":"https://api.github.com/users/harvard-cs205/events{/privacy}","received_events_url":"https://api.github.com/users/harvard-cs205/received_events","type":"Organization","site_admin":false},"repo":{"id":40614104,"name":"cs205-homework","full_name":"harvard-cs205/cs205-homework","owner":{"login":"harvard-cs205","id":13456002,"avatar_url":"https://avatars.githubusercontent.com/u/13456002?v=3","gravatar_id":"","url":"https://api.github.com/users/harvard-cs205","html_url":"https://github.com/harvard-cs205","followers_url":"https://api.github.com/users/harvard-cs205/followers","following_url":"https://api.github.com/users/harvard-cs205/following{/other_user}","gists_url":"https://api.github.com/users/harvard-cs205/gists{/gist_id}","starred_url":"https://api.github.com/users/harvard-cs205/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/harvard-cs205/subscriptions","organizations_url":"https://api.github.com/users/harvard-cs205/orgs","repos_url":"https://api.github.com/users/harvard-cs205/repos","events_url":"https://api.github.com/users/harvard-cs205/events{/privacy}","received_events_url":"https://api.github.com/users/harvard-cs205/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/harvard-cs205/cs205-homework","description":"","fork":false,"url":"https://api.github.com/repos/harvard-cs205/cs205-homework","forks_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/forks","keys_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/keys{/key_id}","collaborators_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/teams","hooks_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/hooks","issue_events_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/issues/events{/number}","events_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/events","assignees_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/assignees{/user}","branches_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/branches{/branch}","tags_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/tags","blobs_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/git/refs{/sha}","trees_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/git/trees{/sha}","statuses_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/statuses/{sha}","languages_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/languages","stargazers_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/stargazers","contributors_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/contributors","subscribers_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/subscribers","subscription_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/subscription","commits_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/commits{/sha}","git_commits_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/git/commits{/sha}","comments_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/comments{/number}","issue_comment_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/issues/comments{/number}","contents_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/contents/{+path}","compare_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/compare/{base}...{head}","merges_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/merges","archive_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/downloads","issues_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/issues{/number}","pulls_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls{/number}","milestones_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/milestones{/number}","notifications_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/labels{/name}","releases_url":"https://api.github.com/repos/harvard-cs205/cs205-homework/releases{/id}","created_at":"2015-08-12T17:18:15Z","updated_at":"2015-10-21T19:21:28Z","pushed_at":"2015-11-21T12:21:39Z","git_url":"git://github.com/harvard-cs205/cs205-homework.git","ssh_url":"git@github.com:harvard-cs205/cs205-homework.git","clone_url":"https://github.com/harvard-cs205/cs205-homework.git","svn_url":"https://github.com/harvard-cs205/cs205-homework","homepage":null,"size":162893,"stargazers_count":5,"watchers_count":5,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":100,"mirror_url":null,"open_issues_count":421,"forks":100,"open_issues":421,"watchers":5,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/306"},"html":{"href":"https://github.com/harvard-cs205/cs205-homework/pull/306"},"issue":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/issues/306"},"comments":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/issues/306/comments"},"review_comments":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/306/comments"},"review_comment":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/pulls/306/commits"},"statuses":{"href":"https://api.github.com/repos/harvard-cs205/cs205-homework/statuses/28d7b9e501d31f7753f18af2eddf38c31b25d831"}}}}