{"action":"closed","number":195,"pull_request":{"url":"https://api.github.com/repos/klee/klee/pulls/195","id":29032063,"html_url":"https://github.com/klee/klee/pull/195","diff_url":"https://github.com/klee/klee/pull/195.diff","patch_url":"https://github.com/klee/klee/pull/195.patch","issue_url":"https://api.github.com/repos/klee/klee/issues/195","number":195,"state":"closed","locked":false,"title":"Commit of improved IndependentSolver::getInitalValues().","user":{"login":"holycrap872","id":682536,"avatar_url":"https://avatars.githubusercontent.com/u/682536?v=3","gravatar_id":"","url":"https://api.github.com/users/holycrap872","html_url":"https://github.com/holycrap872","followers_url":"https://api.github.com/users/holycrap872/followers","following_url":"https://api.github.com/users/holycrap872/following{/other_user}","gists_url":"https://api.github.com/users/holycrap872/gists{/gist_id}","starred_url":"https://api.github.com/users/holycrap872/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/holycrap872/subscriptions","organizations_url":"https://api.github.com/users/holycrap872/orgs","repos_url":"https://api.github.com/users/holycrap872/repos","events_url":"https://api.github.com/users/holycrap872/events{/privacy}","received_events_url":"https://api.github.com/users/holycrap872/received_events","type":"User","site_admin":false},"body":"The previous implementation simply passes the entire constraint forward\r\nwithout any factoring of the constraint at all.  This is a problem\r\nsince it is highly likely that there are cached solutions to pieces\r\nof the constraint.  The new implementation breaks the entire\r\nconstraint down into its requisite factors and passes each piece\r\nforward, one by one, down the solver chain.  After an answer is\r\nreturned, it is integrated into a larger solution.  Since, by\r\ndefinition, no factor can affect another, we can safely create a\r\nsolution to the larger constraint from the answers of its smaller\r\npieces.\r\n\r\nIn addition, the command line option -max-forks-terminate, was added to\r\nprovide a fair test of the optimization.  The command line option works\r\nby terminating the exploration, and dumping the explored states upon\r\nforking a certain number of times.  This allows for a fair, head to head\r\ncomparison of the improved getInitialValues relative to the old \r\nimplementation.\r\n\r\nAfter completion, the changes:\r\n1) Pass all provided tests (other than ones that were expected to fail)\r\n2) Have been verified via -debug-validate-solver by a complete run through of 9 members of the bin-utils for\r\n     --search=dfs with a halt being placed, and states dumped, after 500 forks\r\n     --search=default with a halt being placed, and the states dumped, after 1000 forks\r\n3) Achieved significant speedup on test programs\r\n     --search=dfs\r\n            a. On average 10% improvement (for example strings saw a decrease from 252 seconds to 162 seconds)\r\n            b. Worst case (objcopy) saw decrease in performance of 27% (950 seconds to 1287 seconds)\r\n     --search=default\r\n            a. On average 48% improvement (for example regElf saw a decrease from 1078 seconds to 884 seconds)\r\n            b. Worse case (objcopy) saw decrease in performance of 15% (862 seconds to 1022 seconds)","created_at":"2015-02-10T18:32:14Z","updated_at":"2015-02-11T20:20:40Z","closed_at":"2015-02-11T20:20:40Z","merged_at":null,"merge_commit_sha":"7180090950642559a7c0ea2c3fe30bbb3fa864ae","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/klee/klee/pulls/195/commits","review_comments_url":"https://api.github.com/repos/klee/klee/pulls/195/comments","review_comment_url":"https://api.github.com/repos/klee/klee/pulls/comments/{number}","comments_url":"https://api.github.com/repos/klee/klee/issues/195/comments","statuses_url":"https://api.github.com/repos/klee/klee/statuses/c29f691b93b4cc570d7f0409c7b46318b9bd43e8","head":{"label":"holycrap872:IndependentSolverGetInitFactorizer","ref":"IndependentSolverGetInitFactorizer","sha":"c29f691b93b4cc570d7f0409c7b46318b9bd43e8","user":{"login":"holycrap872","id":682536,"avatar_url":"https://avatars.githubusercontent.com/u/682536?v=3","gravatar_id":"","url":"https://api.github.com/users/holycrap872","html_url":"https://github.com/holycrap872","followers_url":"https://api.github.com/users/holycrap872/followers","following_url":"https://api.github.com/users/holycrap872/following{/other_user}","gists_url":"https://api.github.com/users/holycrap872/gists{/gist_id}","starred_url":"https://api.github.com/users/holycrap872/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/holycrap872/subscriptions","organizations_url":"https://api.github.com/users/holycrap872/orgs","repos_url":"https://api.github.com/users/holycrap872/repos","events_url":"https://api.github.com/users/holycrap872/events{/privacy}","received_events_url":"https://api.github.com/users/holycrap872/received_events","type":"User","site_admin":false},"repo":{"id":30367821,"name":"klee","full_name":"holycrap872/klee","owner":{"login":"holycrap872","id":682536,"avatar_url":"https://avatars.githubusercontent.com/u/682536?v=3","gravatar_id":"","url":"https://api.github.com/users/holycrap872","html_url":"https://github.com/holycrap872","followers_url":"https://api.github.com/users/holycrap872/followers","following_url":"https://api.github.com/users/holycrap872/following{/other_user}","gists_url":"https://api.github.com/users/holycrap872/gists{/gist_id}","starred_url":"https://api.github.com/users/holycrap872/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/holycrap872/subscriptions","organizations_url":"https://api.github.com/users/holycrap872/orgs","repos_url":"https://api.github.com/users/holycrap872/repos","events_url":"https://api.github.com/users/holycrap872/events{/privacy}","received_events_url":"https://api.github.com/users/holycrap872/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/holycrap872/klee","description":"KLEE Symbolic Virtual Machine","fork":true,"url":"https://api.github.com/repos/holycrap872/klee","forks_url":"https://api.github.com/repos/holycrap872/klee/forks","keys_url":"https://api.github.com/repos/holycrap872/klee/keys{/key_id}","collaborators_url":"https://api.github.com/repos/holycrap872/klee/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/holycrap872/klee/teams","hooks_url":"https://api.github.com/repos/holycrap872/klee/hooks","issue_events_url":"https://api.github.com/repos/holycrap872/klee/issues/events{/number}","events_url":"https://api.github.com/repos/holycrap872/klee/events","assignees_url":"https://api.github.com/repos/holycrap872/klee/assignees{/user}","branches_url":"https://api.github.com/repos/holycrap872/klee/branches{/branch}","tags_url":"https://api.github.com/repos/holycrap872/klee/tags","blobs_url":"https://api.github.com/repos/holycrap872/klee/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/holycrap872/klee/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/holycrap872/klee/git/refs{/sha}","trees_url":"https://api.github.com/repos/holycrap872/klee/git/trees{/sha}","statuses_url":"https://api.github.com/repos/holycrap872/klee/statuses/{sha}","languages_url":"https://api.github.com/repos/holycrap872/klee/languages","stargazers_url":"https://api.github.com/repos/holycrap872/klee/stargazers","contributors_url":"https://api.github.com/repos/holycrap872/klee/contributors","subscribers_url":"https://api.github.com/repos/holycrap872/klee/subscribers","subscription_url":"https://api.github.com/repos/holycrap872/klee/subscription","commits_url":"https://api.github.com/repos/holycrap872/klee/commits{/sha}","git_commits_url":"https://api.github.com/repos/holycrap872/klee/git/commits{/sha}","comments_url":"https://api.github.com/repos/holycrap872/klee/comments{/number}","issue_comment_url":"https://api.github.com/repos/holycrap872/klee/issues/comments/{number}","contents_url":"https://api.github.com/repos/holycrap872/klee/contents/{+path}","compare_url":"https://api.github.com/repos/holycrap872/klee/compare/{base}...{head}","merges_url":"https://api.github.com/repos/holycrap872/klee/merges","archive_url":"https://api.github.com/repos/holycrap872/klee/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/holycrap872/klee/downloads","issues_url":"https://api.github.com/repos/holycrap872/klee/issues{/number}","pulls_url":"https://api.github.com/repos/holycrap872/klee/pulls{/number}","milestones_url":"https://api.github.com/repos/holycrap872/klee/milestones{/number}","notifications_url":"https://api.github.com/repos/holycrap872/klee/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/holycrap872/klee/labels{/name}","releases_url":"https://api.github.com/repos/holycrap872/klee/releases{/id}","created_at":"2015-02-05T17:16:19Z","updated_at":"2015-02-09T20:06:58Z","pushed_at":"2015-02-11T01:34:49Z","git_url":"git://github.com/holycrap872/klee.git","ssh_url":"git@github.com:holycrap872/klee.git","clone_url":"https://github.com/holycrap872/klee.git","svn_url":"https://github.com/holycrap872/klee","homepage":"http://klee.llvm.org","size":4205,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_downloads":true,"has_wiki":true,"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":"klee:master","ref":"master","sha":"a743d7072d9ccf11f96e3df45f25ad07da6ad9d6","user":{"login":"klee","id":6224192,"avatar_url":"https://avatars.githubusercontent.com/u/6224192?v=3","gravatar_id":"","url":"https://api.github.com/users/klee","html_url":"https://github.com/klee","followers_url":"https://api.github.com/users/klee/followers","following_url":"https://api.github.com/users/klee/following{/other_user}","gists_url":"https://api.github.com/users/klee/gists{/gist_id}","starred_url":"https://api.github.com/users/klee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/klee/subscriptions","organizations_url":"https://api.github.com/users/klee/orgs","repos_url":"https://api.github.com/users/klee/repos","events_url":"https://api.github.com/users/klee/events{/privacy}","received_events_url":"https://api.github.com/users/klee/received_events","type":"Organization","site_admin":false},"repo":{"id":11568417,"name":"klee","full_name":"klee/klee","owner":{"login":"klee","id":6224192,"avatar_url":"https://avatars.githubusercontent.com/u/6224192?v=3","gravatar_id":"","url":"https://api.github.com/users/klee","html_url":"https://github.com/klee","followers_url":"https://api.github.com/users/klee/followers","following_url":"https://api.github.com/users/klee/following{/other_user}","gists_url":"https://api.github.com/users/klee/gists{/gist_id}","starred_url":"https://api.github.com/users/klee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/klee/subscriptions","organizations_url":"https://api.github.com/users/klee/orgs","repos_url":"https://api.github.com/users/klee/repos","events_url":"https://api.github.com/users/klee/events{/privacy}","received_events_url":"https://api.github.com/users/klee/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/klee/klee","description":"KLEE Symbolic Virtual Machine","fork":false,"url":"https://api.github.com/repos/klee/klee","forks_url":"https://api.github.com/repos/klee/klee/forks","keys_url":"https://api.github.com/repos/klee/klee/keys{/key_id}","collaborators_url":"https://api.github.com/repos/klee/klee/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/klee/klee/teams","hooks_url":"https://api.github.com/repos/klee/klee/hooks","issue_events_url":"https://api.github.com/repos/klee/klee/issues/events{/number}","events_url":"https://api.github.com/repos/klee/klee/events","assignees_url":"https://api.github.com/repos/klee/klee/assignees{/user}","branches_url":"https://api.github.com/repos/klee/klee/branches{/branch}","tags_url":"https://api.github.com/repos/klee/klee/tags","blobs_url":"https://api.github.com/repos/klee/klee/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/klee/klee/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/klee/klee/git/refs{/sha}","trees_url":"https://api.github.com/repos/klee/klee/git/trees{/sha}","statuses_url":"https://api.github.com/repos/klee/klee/statuses/{sha}","languages_url":"https://api.github.com/repos/klee/klee/languages","stargazers_url":"https://api.github.com/repos/klee/klee/stargazers","contributors_url":"https://api.github.com/repos/klee/klee/contributors","subscribers_url":"https://api.github.com/repos/klee/klee/subscribers","subscription_url":"https://api.github.com/repos/klee/klee/subscription","commits_url":"https://api.github.com/repos/klee/klee/commits{/sha}","git_commits_url":"https://api.github.com/repos/klee/klee/git/commits{/sha}","comments_url":"https://api.github.com/repos/klee/klee/comments{/number}","issue_comment_url":"https://api.github.com/repos/klee/klee/issues/comments/{number}","contents_url":"https://api.github.com/repos/klee/klee/contents/{+path}","compare_url":"https://api.github.com/repos/klee/klee/compare/{base}...{head}","merges_url":"https://api.github.com/repos/klee/klee/merges","archive_url":"https://api.github.com/repos/klee/klee/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/klee/klee/downloads","issues_url":"https://api.github.com/repos/klee/klee/issues{/number}","pulls_url":"https://api.github.com/repos/klee/klee/pulls{/number}","milestones_url":"https://api.github.com/repos/klee/klee/milestones{/number}","notifications_url":"https://api.github.com/repos/klee/klee/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/klee/klee/labels{/name}","releases_url":"https://api.github.com/repos/klee/klee/releases{/id}","created_at":"2013-07-21T22:03:03Z","updated_at":"2015-02-10T13:31:39Z","pushed_at":"2015-02-10T13:31:38Z","git_url":"git://github.com/klee/klee.git","ssh_url":"git@github.com:klee/klee.git","clone_url":"https://github.com/klee/klee.git","svn_url":"https://github.com/klee/klee","homepage":"http://klee.llvm.org","size":5346,"stargazers_count":154,"watchers_count":154,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":62,"mirror_url":null,"open_issues_count":37,"forks":62,"open_issues":37,"watchers":154,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/klee/klee/pulls/195"},"html":{"href":"https://github.com/klee/klee/pull/195"},"issue":{"href":"https://api.github.com/repos/klee/klee/issues/195"},"comments":{"href":"https://api.github.com/repos/klee/klee/issues/195/comments"},"review_comments":{"href":"https://api.github.com/repos/klee/klee/pulls/195/comments"},"review_comment":{"href":"https://api.github.com/repos/klee/klee/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/klee/klee/pulls/195/commits"},"statuses":{"href":"https://api.github.com/repos/klee/klee/statuses/c29f691b93b4cc570d7f0409c7b46318b9bd43e8"}},"merged":false,"mergeable":true,"mergeable_state":"unstable","merged_by":null,"comments":0,"review_comments":0,"commits":3,"additions":920,"deletions":321,"changed_files":14}}