{"action":"created","issue":{"url":"https://api.github.com/repos/probmods/webppl/issues/150","labels_url":"https://api.github.com/repos/probmods/webppl/issues/150/labels{/name}","comments_url":"https://api.github.com/repos/probmods/webppl/issues/150/comments","events_url":"https://api.github.com/repos/probmods/webppl/issues/150/events","html_url":"https://github.com/probmods/webppl/issues/150","id":95264572,"number":150,"title":"Naming strategy causes poor scaling of MH+recursive models","user":{"login":"null-a","id":9109012,"avatar_url":"https://avatars.githubusercontent.com/u/9109012?v=3","gravatar_id":"","url":"https://api.github.com/users/null-a","html_url":"https://github.com/null-a","followers_url":"https://api.github.com/users/null-a/followers","following_url":"https://api.github.com/users/null-a/following{/other_user}","gists_url":"https://api.github.com/users/null-a/gists{/gist_id}","starred_url":"https://api.github.com/users/null-a/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/null-a/subscriptions","organizations_url":"https://api.github.com/users/null-a/orgs","repos_url":"https://api.github.com/users/null-a/repos","events_url":"https://api.github.com/users/null-a/events{/privacy}","received_events_url":"https://api.github.com/users/null-a/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"null-a","id":9109012,"avatar_url":"https://avatars.githubusercontent.com/u/9109012?v=3","gravatar_id":"","url":"https://api.github.com/users/null-a","html_url":"https://github.com/null-a","followers_url":"https://api.github.com/users/null-a/followers","following_url":"https://api.github.com/users/null-a/following{/other_user}","gists_url":"https://api.github.com/users/null-a/gists{/gist_id}","starred_url":"https://api.github.com/users/null-a/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/null-a/subscriptions","organizations_url":"https://api.github.com/users/null-a/orgs","repos_url":"https://api.github.com/users/null-a/repos","events_url":"https://api.github.com/users/null-a/events{/privacy}","received_events_url":"https://api.github.com/users/null-a/received_events","type":"User","site_admin":false},"milestone":null,"comments":6,"created_at":"2015-07-15T18:52:32Z","updated_at":"2015-08-05T18:05:38Z","closed_at":null,"body":"With models which build structure recursively, (Hash)MH run time doesn't appear to scale linearly with the number of ERP (n) as I expected:\r\n\r\n![current](https://cloud.githubusercontent.com/assets/9109012/8706727/447bbc52-2b29-11e5-928d-e5fdc1654d36.png)\r\n\r\nI think there are a couple of reasons for this:\r\n\r\n1. In recursive models stack addresses grow with model size. I think this makes `concat`ing the result of `gensym` onto the current address O(n), leading to O(n^2) per iteration.\r\n2. I speculate that V8 uses a fancy data structure for strings which delays computing the result of a `concat` as long as possible. In our case I think this means every time we look at `address` in MH's `sample` we trigger the concatenation of lots of tiny fragments of address, many of which we've already concatenated elsewhere.\r\n\r\nTo test this idea I tweaked the naming scheme to hash each address with MD5 after the `gensym` is concatenated to the current address. This probably isn't suitable for all of our needs, but I think it side steps both problems I mentioned. Here's what happened:\r\n\r\n![hash](https://cloud.githubusercontent.com/assets/9109012/8706739/4e70f86c-2b29-11e5-8455-83f7736cc968.png)\r\n\r\nHere's the same plot with a different y limit:\r\n\r\n![hash2](https://cloud.githubusercontent.com/assets/9109012/8706742/5344be3c-2b29-11e5-94a1-9e27f7a96fb0.png)\r\n\r\nI also tried forcing the `concat` to happen immediately (but without the hashing) by replacing `address.concat(gensym())` with something like `[address, gensym()].join('')`. This helps, presumable because it addresses problem 2 (?) but the hashing addresses approach does better:\r\n\r\n![hash_vs_force_join](https://cloud.githubusercontent.com/assets/9109012/8706750/5ae8359c-2b29-11e5-8643-c3c3a216ca90.png)\r\n\r\nThe forced join approach seg faulted at ~15K random variables.\r\n\r\nI'm not sure whether this plot supports the O(n^2) idea I mention in problem 1 or not.\r\n\r\nSmall print:\r\n\r\n* [Benchmark code](https://github.com/null-a/webppl/commit/8d1fa04176741c9e1dd3ed13a26f050018785376)\r\n* [Address hashing code](https://github.com/null-a/webppl/commit/f7218ea33de0aa28126567f51ad6e8c1c639dea3)\r\n* All the inference tests still pass.\r\n* In all MH benchmarks I deterministically picked the middle ERP to regen from in order to reduce the noise in the timings. I included a version of HashMH which doesn't exit early when the same value is re-sampled (at the regen point) for the same reason."},"comment":{"url":"https://api.github.com/repos/probmods/webppl/issues/comments/128093976","html_url":"https://github.com/probmods/webppl/issues/150#issuecomment-128093976","issue_url":"https://api.github.com/repos/probmods/webppl/issues/150","id":128093976,"user":{"login":"null-a","id":9109012,"avatar_url":"https://avatars.githubusercontent.com/u/9109012?v=3","gravatar_id":"","url":"https://api.github.com/users/null-a","html_url":"https://github.com/null-a","followers_url":"https://api.github.com/users/null-a/followers","following_url":"https://api.github.com/users/null-a/following{/other_user}","gists_url":"https://api.github.com/users/null-a/gists{/gist_id}","starred_url":"https://api.github.com/users/null-a/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/null-a/subscriptions","organizations_url":"https://api.github.com/users/null-a/orgs","repos_url":"https://api.github.com/users/null-a/repos","events_url":"https://api.github.com/users/null-a/events{/privacy}","received_events_url":"https://api.github.com/users/null-a/received_events","type":"User","site_admin":false},"created_at":"2015-08-05T18:05:38Z","updated_at":"2015-08-05T18:05:38Z","body":"> Here's some relevant info:\r\n\r\nThanks!\r\n\r\n> the d[address]; line in your program has no effect, so it's possible that the JIT can get rid of it\r\n\r\nGood idea, but if you remove it all 3 run in 0-1ms for all n so I don't think they are optimizing it away. \r\n\r\n"}}