{"action":"created","issue":{"url":"https://api.github.com/repos/libgit2/libgit2/issues/3508","labels_url":"https://api.github.com/repos/libgit2/libgit2/issues/3508/labels{/name}","comments_url":"https://api.github.com/repos/libgit2/libgit2/issues/3508/comments","events_url":"https://api.github.com/repos/libgit2/libgit2/issues/3508/events","html_url":"https://github.com/libgit2/libgit2/pull/3508","id":116960403,"number":3508,"title":"Improvements to tree parsing speed","user":{"login":"carlosmn","id":335443,"avatar_url":"https://avatars.githubusercontent.com/u/335443?v=3","gravatar_id":"","url":"https://api.github.com/users/carlosmn","html_url":"https://github.com/carlosmn","followers_url":"https://api.github.com/users/carlosmn/followers","following_url":"https://api.github.com/users/carlosmn/following{/other_user}","gists_url":"https://api.github.com/users/carlosmn/gists{/gist_id}","starred_url":"https://api.github.com/users/carlosmn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/carlosmn/subscriptions","organizations_url":"https://api.github.com/users/carlosmn/orgs","repos_url":"https://api.github.com/users/carlosmn/repos","events_url":"https://api.github.com/users/carlosmn/events{/privacy}","received_events_url":"https://api.github.com/users/carlosmn/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2015-11-14T23:46:26Z","updated_at":"2015-11-28T18:52:43Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/libgit2/libgit2/pulls/3508","html_url":"https://github.com/libgit2/libgit2/pull/3508","diff_url":"https://github.com/libgit2/libgit2/pull/3508.diff","patch_url":"https://github.com/libgit2/libgit2/pull/3508.patch"},"body":"Here's a couple of simple changes to the way we parse trees which gives us significant improvements.\r\n\r\nThe first one is just silly, really. We've already calculated how long the filename is, so we can just skip over it instead of looking for the terminator again. This gives us about half the gains.\r\n\r\nThen, we can also very easily avoid constantly asking the system for memory by allocating the entries in a pool owned by the tree. The lifetime of the entries is tied to the tree already, so this is a great place to use a pool. Those entries for which we give ownership to the user don't need to change, as we already perform an extra allocation to give them their own lifetime.\r\n\r\nI checked the speedup by parsing the top-level tree for `git.git` for ~41k commits. The timing is a bit rough, but the speedup ends up being a bit under 1/3, which is not bad, considering. The most expensive thing right now is parsing the filemode number; and using libc's (presumably) optimised one doesn't really help.\r\n\r\n|             |  master | this |\r\n-----------|-----------|--------\r\n| Debug | 4.7s | 3.8s |\r\n| Release | 2.7s | 2.0 s |\r\n\r\nI've also tested by grabbing the parent's tree for each commit we walk and diffing it with a pathspec of \"README\" (I initially tried with a full diff but that takes over two minutes, which is also pretty bad but a different story). The speedup isn't quite as drastic since we're still doing the diff, which I haven't touched here, but still noticeable, especially in release mode.\r\n\r\n|             |  master | this |\r\n-----------|-----------|--------\r\n| Debug | 11.5s | 9.5s |\r\n| Release | 6.0s | 4.3 s |\r\n"},"comment":{"url":"https://api.github.com/repos/libgit2/libgit2/issues/comments/160329109","html_url":"https://github.com/libgit2/libgit2/pull/3508#issuecomment-160329109","issue_url":"https://api.github.com/repos/libgit2/libgit2/issues/3508","id":160329109,"user":{"login":"carlosmn","id":335443,"avatar_url":"https://avatars.githubusercontent.com/u/335443?v=3","gravatar_id":"","url":"https://api.github.com/users/carlosmn","html_url":"https://github.com/carlosmn","followers_url":"https://api.github.com/users/carlosmn/followers","following_url":"https://api.github.com/users/carlosmn/following{/other_user}","gists_url":"https://api.github.com/users/carlosmn/gists{/gist_id}","starred_url":"https://api.github.com/users/carlosmn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/carlosmn/subscriptions","organizations_url":"https://api.github.com/users/carlosmn/orgs","repos_url":"https://api.github.com/users/carlosmn/repos","events_url":"https://api.github.com/users/carlosmn/events{/privacy}","received_events_url":"https://api.github.com/users/carlosmn/received_events","type":"User","site_admin":false},"created_at":"2015-11-28T18:52:42Z","updated_at":"2015-11-28T18:52:42Z","body":"Both the tree-read microbench and the larger diff test are sped up, so I'm happy to merge this as-is."}}