{"action":"created","issue":{"url":"https://api.github.com/repos/sdboyer/gps/issues/165","repository_url":"https://api.github.com/repos/sdboyer/gps","labels_url":"https://api.github.com/repos/sdboyer/gps/issues/165/labels{/name}","comments_url":"https://api.github.com/repos/sdboyer/gps/issues/165/comments","events_url":"https://api.github.com/repos/sdboyer/gps/issues/165/events","html_url":"https://github.com/sdboyer/gps/issues/165","id":204666164,"number":165,"title":"Test solver against random graphs","user":{"login":"sdboyer","id":21599,"avatar_url":"https://avatars.githubusercontent.com/u/21599?v=3","gravatar_id":"","url":"https://api.github.com/users/sdboyer","html_url":"https://github.com/sdboyer","followers_url":"https://api.github.com/users/sdboyer/followers","following_url":"https://api.github.com/users/sdboyer/following{/other_user}","gists_url":"https://api.github.com/users/sdboyer/gists{/gist_id}","starred_url":"https://api.github.com/users/sdboyer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sdboyer/subscriptions","organizations_url":"https://api.github.com/users/sdboyer/orgs","repos_url":"https://api.github.com/users/sdboyer/repos","events_url":"https://api.github.com/users/sdboyer/events{/privacy}","received_events_url":"https://api.github.com/users/sdboyer/received_events","type":"User","site_admin":false},"labels":[{"id":341714245,"url":"https://api.github.com/repos/sdboyer/gps/labels/help%20wanted","name":"help wanted","color":"159818","default":true},{"id":363847595,"url":"https://api.github.com/repos/sdboyer/gps/labels/performance","name":"performance","color":"5319e7","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2017-02-01T18:30:24Z","updated_at":"2017-02-02T16:22:55Z","closed_at":null,"body":"Almost all of the tests I've written for gps' solver thus far are geared towards checking some aspect of correctness of the solver. Testing its performance has not been a priority. But the solver is tasked with constraint solving - an NP-hard search problem. Its performance (against real graphs) is something we have to care very much about.\r\n\r\nOf course, there's a chicken-or-egg problem there - getting real graphs is difficult when the ecosystem doesn't exist yet for us to test against. Even when it does, though, it would be ideal if we had a way to get out ahead of solver performance issues, rather than having to wait for them to arise.\r\n\r\nIt seems to me that a potentially good approach to \"getting ahead\" in this way is to invest in a system for testing the solver against random dependency graphs. It's not trivial to do so - the generator would need to work across several dimensions of variables - but it shouldn't be crazy hard to do, either. The crucial bit will be exporting the generated graphs into valid Go code, probably in the same form used to declare the handcrafted correctness-checking fixtures that exist today.\r\n\r\nThe basic loop would be something like this:\r\n1. Generate random graph\r\n2. Dispatch a solve using the random graph\r\n3. If solve time exceeds <threshold>, dump the graph\r\n   * Support for timing out a solve run would need to be added to the solver. Not hard, and no need to expose that control yet\r\n4. Repeat 1-3 until we find a graph that causes solving to run for more than X (maybe start with 5) seconds, then dump the templated declaration of it to stdout\r\n\r\nThis would be a great tool in our arsenal, though I'm not sure when I'd have time to get to it myself. Help would be awesome. I'm happy to add more info here, and generally provide guidance as needed to anyone interested."},"comment":{"url":"https://api.github.com/repos/sdboyer/gps/issues/comments/277005184","html_url":"https://github.com/sdboyer/gps/issues/165#issuecomment-277005184","issue_url":"https://api.github.com/repos/sdboyer/gps/issues/165","id":277005184,"user":{"login":"timtadh","id":38620,"avatar_url":"https://avatars.githubusercontent.com/u/38620?v=3","gravatar_id":"","url":"https://api.github.com/users/timtadh","html_url":"https://github.com/timtadh","followers_url":"https://api.github.com/users/timtadh/followers","following_url":"https://api.github.com/users/timtadh/following{/other_user}","gists_url":"https://api.github.com/users/timtadh/gists{/gist_id}","starred_url":"https://api.github.com/users/timtadh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/timtadh/subscriptions","organizations_url":"https://api.github.com/users/timtadh/orgs","repos_url":"https://api.github.com/users/timtadh/repos","events_url":"https://api.github.com/users/timtadh/events{/privacy}","received_events_url":"https://api.github.com/users/timtadh/received_events","type":"User","site_admin":false},"created_at":"2017-02-02T16:22:55Z","updated_at":"2017-02-02T16:22:55Z","body":"One way to construct \"worst case DAGs\" for version control operations is to generate a graph in the form of a N-dimensional grid or lattice structure. This effectively makes every \"non-edge\" commit in the DAG a merge commit. Here is a simple example:\r\n\r\nThe numbers are the commits, edges indicate `parent-commit --> child-commit` or `previous-version --> next-version`\r\n```\r\n1 --> 2 --> 3 --> 4\r\n|     |     |     |\r\nv     v     v     v\r\n5 --> 8 --> 9 -->10\r\n|     |     |     |\r\nv     v     v     v\r\n6 -->11 -->12 -->13\r\n|     |     |     |\r\nv     v     v     v\r\n7 -->14 -->15 -->16\r\n```\r\n\r\nVCS systems often have problems involving selecting ranges of commits and constructing these \"worst-case\" lattices can be used to test the performance of the operations.\r\n\r\nFor the dependency resolution problem a similar structure could be used. However, there are some wrinkles.\r\n\r\n1. VCS DAGs are different than the dependency resolution problem. So a different random structure will be needed. This type of structure may be useful to think about when constructing the random graphs.\r\n\r\n1. For [3SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability) (and by extension all NP-Complete problems) there is currently no know way to reliably and randomly select a \"hard-instance\" of a problem. If we could randomly generate hard instances of NP-Complete problems we could construct [simple and secure cryptographic systems](http://hackthology.com/cryptography-and-complexity.html). However, at present we cannot do this.\r\n\r\nHowever, we do not need to necessarily generate only hard instances. It may be reasonable to simply generate large instances. \r\n\r\nFrom  reading the [code](https://github.com/sdboyer/gps/blob/master/solve_basic_test.go#L474) it looks like the current testing infrastructure could be used to generate random graphs with some caveats. First, we may not know what the correct solution is but we could ensure only solvable graphs are generated. It could be a secondary test to ensure only non-solvable graphs are generated."}}
{"actor":{"display_login":"timtadh"}}