{"action":"created","issue":{"url":"https://api.github.com/repos/roystgnr/MetaPhysicL/issues/1","labels_url":"https://api.github.com/repos/roystgnr/MetaPhysicL/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/roystgnr/MetaPhysicL/issues/1/comments","events_url":"https://api.github.com/repos/roystgnr/MetaPhysicL/issues/1/events","html_url":"https://github.com/roystgnr/MetaPhysicL/issues/1","id":104888847,"number":1,"title":"Improve DynamicSparseNumberFoo performance","user":{"login":"roystgnr","id":2367346,"avatar_url":"https://avatars.githubusercontent.com/u/2367346?v=3","gravatar_id":"","url":"https://api.github.com/users/roystgnr","html_url":"https://github.com/roystgnr","followers_url":"https://api.github.com/users/roystgnr/followers","following_url":"https://api.github.com/users/roystgnr/following{/other_user}","gists_url":"https://api.github.com/users/roystgnr/gists{/gist_id}","starred_url":"https://api.github.com/users/roystgnr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/roystgnr/subscriptions","organizations_url":"https://api.github.com/users/roystgnr/orgs","repos_url":"https://api.github.com/users/roystgnr/repos","events_url":"https://api.github.com/users/roystgnr/events{/privacy}","received_events_url":"https://api.github.com/users/roystgnr/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":18,"created_at":"2015-09-04T13:15:40Z","updated_at":"2015-09-10T20:09:12Z","closed_at":null,"body":"The good news: we now have a working class that gives O(N_nonzero) instead of O(N) performance.  This could be a big deal for https://github.com/libantioch/antioch sensitivity applications where our eventual N/N_nonzero will be ~1000.\r\n\r\nThe bad news: @friedmud reports that the current implementation has a constant performance overhead of ~1000.  (based on profiling https://github.com/idaholab/moose/pull/5661, and according to the profiler the cost is mostly from new/delete).  He fixed the obvious flaws (pass-by-value to the sparsity operations) to little effect.\r\n\r\nSo let's brainstorm ideas.  I'll sort what I've got so far by increasing level of difficulty IMHO:\r\n\r\nPBR:  Pass-by-reference in the sparsity operations (even if it's not a big win it's still better than nothing)\r\n\r\nRI:  Use reverse iteration to do in-place sparsity operations rather than creating temporary merged_foo vectors.\r\n\r\nRV:  Add C++11 rvalue operations so we can steal doomed input arguments' allocations where available.\r\n\r\nCA:  Give a custom allocator to the underlying std::vector.\r\n\r\nCC:  Replace std::vector with a custom container that keeps the first O(N_nonzero) elements on the stack and only hits the heap for larger cases.\r\n\r\nET:  Use expression templates to postpone evaluations until we can do more of them at once without creating so many intermediate temporaries."},"comment":{"url":"https://api.github.com/repos/roystgnr/MetaPhysicL/issues/comments/139365955","html_url":"https://github.com/roystgnr/MetaPhysicL/issues/1#issuecomment-139365955","issue_url":"https://api.github.com/repos/roystgnr/MetaPhysicL/issues/1","id":139365955,"user":{"login":"roystgnr","id":2367346,"avatar_url":"https://avatars.githubusercontent.com/u/2367346?v=3","gravatar_id":"","url":"https://api.github.com/users/roystgnr","html_url":"https://github.com/roystgnr","followers_url":"https://api.github.com/users/roystgnr/followers","following_url":"https://api.github.com/users/roystgnr/following{/other_user}","gists_url":"https://api.github.com/users/roystgnr/gists{/gist_id}","starred_url":"https://api.github.com/users/roystgnr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/roystgnr/subscriptions","organizations_url":"https://api.github.com/users/roystgnr/orgs","repos_url":"https://api.github.com/users/roystgnr/repos","events_url":"https://api.github.com/users/roystgnr/events{/privacy}","received_events_url":"https://api.github.com/users/roystgnr/received_events","type":"User","site_admin":false},"created_at":"2015-09-10T20:09:12Z","updated_at":"2015-09-10T20:09:12Z","body":"The only remaining allocation in empty-DSNA is on the stack as part of the DualNumber, and so is nearly free (there's a chance that the extra bytes will increase cache misses).\r\n\r\nThere are currently two tests for indices.begin()==indices.end() in each empty-DSNA operation, though, which might be twice as much overhead as a single if(compute_derivatives) test..."}}