{"action":"opened","issue":{"url":"https://api.github.com/repos/mapbox/protozero/issues/46","repository_url":"https://api.github.com/repos/mapbox/protozero","labels_url":"https://api.github.com/repos/mapbox/protozero/issues/46/labels{/name}","comments_url":"https://api.github.com/repos/mapbox/protozero/issues/46/comments","events_url":"https://api.github.com/repos/mapbox/protozero/issues/46/events","html_url":"https://github.com/mapbox/protozero/issues/46","id":132923099,"number":46,"title":"Optimizing varint","user":{"login":"joto","id":113756,"avatar_url":"https://avatars.githubusercontent.com/u/113756?v=3","gravatar_id":"","url":"https://api.github.com/users/joto","html_url":"https://github.com/joto","followers_url":"https://api.github.com/users/joto/followers","following_url":"https://api.github.com/users/joto/following{/other_user}","gists_url":"https://api.github.com/users/joto/gists{/gist_id}","starred_url":"https://api.github.com/users/joto/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/joto/subscriptions","organizations_url":"https://api.github.com/users/joto/orgs","repos_url":"https://api.github.com/users/joto/repos","events_url":"https://api.github.com/users/joto/events{/privacy}","received_events_url":"https://api.github.com/users/joto/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2016-02-11T09:15:13Z","updated_at":"2016-02-11T09:15:13Z","closed_at":null,"body":"Decoding varints is a major bottleneck. When doing profiling, the `decode_varint` function always shows up high in the list. I have done some experiments which show that over half the varints in OSM PBF files are 1-byte varints. Optimizing this specific case speeds up reading of those files by about 10%! I optimized this by using a wrapper function around `decode_varint` that checks for this specific case and handles it locally and otherwise hands work over to the original `decode_varint` function. I believe the compiler inlines the outer function which reduces the overhead for this common case. Forcing the compiler to inline the whole function didn't do much, the function is too big to be inlines anyway.\r\n\r\nThere are some more things we need to figure out here:\r\n* Is the OSM PBF unusual in some way that it has so many 1-byte varints? Part of this is that Protobuf uses varints for the field tags (which say which type of field something is). If the tag is <15, this will be encoded in 1 byte varint. I suspect that most Protobuf formats will do this, because this optimization is specifically mention in the Protobuf documentation. And OSM PBF uses delta encoding of IDs etc. to get small integers in several places, so this also helps. But do other formats have similar rations? We have to check how vector tiles fare here.\r\n* Does it make sense to optimize this, or could we make some other optimization that would help in all cases. The varint decoder we use is from folly, I suspect they have done their homework on this, but we don't know their exact circumstances.\r\n* Can we do some general optimization that just works in most cases, or do we want the programmer to give hints to the library, such as what size integer to expect or so.\r\n\r\nI looked at the SIMD speedup things mentioned in #20 and #27, but that code is huge. Folly has some code to speed up multiple varints stored together which could help with repeated packed varints, but this will not help with the very common case of the varint-encoded tag.\r\n"}}