{"action":"created","issue":{"url":"https://api.github.com/repos/open-mpi/hwloc/issues/121","labels_url":"https://api.github.com/repos/open-mpi/hwloc/issues/121/labels{/name}","comments_url":"https://api.github.com/repos/open-mpi/hwloc/issues/121/comments","events_url":"https://api.github.com/repos/open-mpi/hwloc/issues/121/events","html_url":"https://github.com/open-mpi/hwloc/issues/121","id":56646040,"number":121,"title":"Fix lstopo graphical exponential complexity","user":{"login":"bgoglin","id":827599,"avatar_url":"https://avatars.githubusercontent.com/u/827599?v=3","gravatar_id":"","url":"https://api.github.com/users/bgoglin","html_url":"https://github.com/bgoglin","followers_url":"https://api.github.com/users/bgoglin/followers","following_url":"https://api.github.com/users/bgoglin/following{/other_user}","gists_url":"https://api.github.com/users/bgoglin/gists{/gist_id}","starred_url":"https://api.github.com/users/bgoglin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bgoglin/subscriptions","organizations_url":"https://api.github.com/users/bgoglin/orgs","repos_url":"https://api.github.com/users/bgoglin/repos","events_url":"https://api.github.com/users/bgoglin/events{/privacy}","received_events_url":"https://api.github.com/users/bgoglin/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/open-mpi/hwloc/labels/enhancement","name":"enhancement","color":"84b6eb"},{"url":"https://api.github.com/repos/open-mpi/hwloc/labels/minor","name":"minor","color":"f7c6c7"},{"url":"https://api.github.com/repos/open-mpi/hwloc/labels/Tools","name":"Tools","color":"bfe5bf"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-02-05T09:27:03Z","updated_at":"2015-02-05T09:53:59Z","closed_at":null,"body":"On my laptop (dual-core, hyperthreaded), pu_draw() gets called 7164 times, and core_draw 1790, but they just draw 6 boxes in the end. In general, each object at depth N get its foo_draw() function called (7x2^N)-1 times.\r\n\r\nThe reason is that every object does a first recurse into its entire subtree without drawing, then draws its own box, and then recurse again with drawing. That's an exponential multi-recursion.\r\n\r\nIdeally, we should recurse in the tree once without drawing, go back to the top, and then recurse again with drawing. Only recurse twice from the top, no need to recurse twice in every object.\r\n\r\nLikely only matters for people that display dynamic information in lstopo, but could be a good opportunity to make the code more readable and flexible. Got an intern?"},"comment":{"url":"https://api.github.com/repos/open-mpi/hwloc/issues/comments/73020558","html_url":"https://github.com/open-mpi/hwloc/issues/121#issuecomment-73020558","issue_url":"https://api.github.com/repos/open-mpi/hwloc/issues/121","id":73020558,"user":{"login":"sthibaul","id":5405051,"avatar_url":"https://avatars.githubusercontent.com/u/5405051?v=3","gravatar_id":"","url":"https://api.github.com/users/sthibaul","html_url":"https://github.com/sthibaul","followers_url":"https://api.github.com/users/sthibaul/followers","following_url":"https://api.github.com/users/sthibaul/following{/other_user}","gists_url":"https://api.github.com/users/sthibaul/gists{/gist_id}","starred_url":"https://api.github.com/users/sthibaul/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sthibaul/subscriptions","organizations_url":"https://api.github.com/users/sthibaul/orgs","repos_url":"https://api.github.com/users/sthibaul/repos","events_url":"https://api.github.com/users/sthibaul/events{/privacy}","received_events_url":"https://api.github.com/users/sthibaul/received_events","type":"User","site_admin":false},"created_at":"2015-02-05T09:53:59Z","updated_at":"2015-02-05T09:53:59Z","body":"Well, the problem is NP-complete, so unless using heuristics, you can't\r\navoid exponential things. But several thousands for a laptop is a\r\nproblem indeed :)\r\n\r\nThere is already dynamic programming support in there to avoid this,\r\nsee the DYNA_SAVE and DYNA_CHECK macros, which already avoid computing\r\nanything several times.  I guess this is what is broken.  Reading the\r\nsource again, I don't see why we free the userdata which is precisely\r\nsupposed to store the dynamic information, see the attached patch.\r\n"}}