{"action":"created","issue":{"url":"https://api.github.com/repos/mapbox/mapbox-gl-js/issues/2224","repository_url":"https://api.github.com/repos/mapbox/mapbox-gl-js","labels_url":"https://api.github.com/repos/mapbox/mapbox-gl-js/issues/2224/labels{/name}","comments_url":"https://api.github.com/repos/mapbox/mapbox-gl-js/issues/2224/comments","events_url":"https://api.github.com/repos/mapbox/mapbox-gl-js/issues/2224/events","html_url":"https://github.com/mapbox/mapbox-gl-js/pull/2224","id":138623929,"number":2224,"title":"queryRenderFeatures continued [not ready]","user":{"login":"ansis","id":1421652,"avatar_url":"https://avatars.githubusercontent.com/u/1421652?v=3","gravatar_id":"","url":"https://api.github.com/users/ansis","html_url":"https://github.com/ansis","followers_url":"https://api.github.com/users/ansis/followers","following_url":"https://api.github.com/users/ansis/following{/other_user}","gists_url":"https://api.github.com/users/ansis/gists{/gist_id}","starred_url":"https://api.github.com/users/ansis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ansis/subscriptions","organizations_url":"https://api.github.com/users/ansis/orgs","repos_url":"https://api.github.com/users/ansis/repos","events_url":"https://api.github.com/users/ansis/events{/privacy}","received_events_url":"https://api.github.com/users/ansis/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/mapbox/mapbox-gl-js/labels/in%20progress","name":"in progress","color":"ededed"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":23,"created_at":"2016-03-05T00:20:48Z","updated_at":"2016-03-21T20:22:05Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/mapbox/mapbox-gl-js/pulls/2224","html_url":"https://github.com/mapbox/mapbox-gl-js/pull/2224","diff_url":"https://github.com/mapbox/mapbox-gl-js/pull/2224.diff","patch_url":"https://github.com/mapbox/mapbox-gl-js/pull/2224.patch"},"body":"This builds on https://github.com/mapbox/mapbox-gl-js/pull/2052.\r\n\r\nThis is not ready, but it could use some high level :eyes:. I probably should have gotten some :eyes: a bit earlier. Let me know if any of the high level ideas here concern you. I'll comment again later when this is more polished.\r\n\r\nThe raw vector tile pbf, FeatureTree and CollisionTile are now transferred to the main thread when a tile finishes loading. This lets use have a synchronous `queryRenderedFeatures`, it lets us eliminate `includeGeometry` without a performance hit, and it starts moving us towards more state-less workers.\r\n\r\n### A synchronous queryRenderedFeatures\r\nThis adds a synchronous version of `queryRenderedFeatures`.\r\n\r\n- it's faster\r\n- it's more convenient to use, especially when you want to make multiple queries\r\n- it's more consistent. It never gets delayed for 100s of ms while a worker is busy parsing a tile\r\n- you don't have to worry about callbacks being called out of order\r\n- things like https://github.com/mapbox/mapbox-gl-js/issues/1002 could be done lazily\r\n\r\nThere is still an async version. It transfers data back to workers.\r\n\r\nDespite being parallelized, the async version is not faster than the sync version. It ends up parsing from the pbfs twice instead of once. It spends less time on the main thread though which could be useful for large, expensive queries. I think it could be worthwhile to keep both versions as `queryRenderedFeatures` and `queryRenderedFeaturesAsync`\r\n\r\n### Getting rid of `includeGeometry`\r\n\r\nThe `includeGeometry` param for `queryRenderedFeatures` only exists because sending geometries from the worker back to the main thread was slow. When the pbf is on the main thread individual geometries can be deserialized **lazily**. This lets us drop `includeGeometry` without a performance penalty.\r\n\r\n### indexing with Grid\r\n\r\nI replaced rbush with a [`Grid`](https://github.com/mapbox/mapbox-gl-js/blob/query-rendered-features-continued/js/util/grid.js), a different kind of spatial index. `Grid` can be serialized to an ArrayBuffer to make it transferrable. The serialized version can be queried directly without deserializing individual elements to javascript objects. It is [faster than rbush for collision detection](https://github.com/mapbox/mapbox-gl-js/commit/0ec60ff96749276f32710ec43f26ccff03f50096) and comparable for [rendered feature querying](https://github.com/mapbox/mapbox-gl-js/commit/6e3f8c7a2a2388718afa5c2dc4d64395a6c82f5d). It's faster because insertions are faster. \r\n\r\n Grid is a grid of cells. When a bbox is inserted it is added to all the cells it intersects. When a bbox is queried it looks in all cells that intersects with that bbox. That's it.\r\n\r\nIt isn't faster than rbush generally, but it is faster for what we use it for: a fixed extent, mostly evenly sized bboxes, and a high number of insertions. More importantly, it's transferable. \r\n\r\n### Storing arrays of \"structs\" in ArrayBuffers\r\nThere are a bunch of cases where we have giant arrays of fixed size objects. I added a new abstraction, [StructArray](https://github.com/mapbox/mapbox-gl-js/blob/query-rendered-features-continued/js/util/struct_array.js), that makes it easier to store these kinds of objects in ArrayBuffers. It's inspired by the new Buffer implementation. It:\r\n- saves a lot of space. Switching collision boxes saved 500KB per tile.\r\n- makes transferring or even copying these arrays a lot faster\r\n- avoids creating a ton of garbage\r\n\r\nsee https://github.com/mapbox/mapbox-gl-js/commit/9a2e5fd4645cde999005796538da975ab5b5d217 's commit message for an example\r\n\r\n### Reducing worker state\r\nBoth Grid and StructArrays are transferrable and don't need to be deserialized to individual objects before they can be used. This makes moving them between workers and the main thread really fast and reduces the amount of data that is \"stuck\" on workers. When `symbolInstances` is made completely transferable we could get rid of WorkerTiles that live after parsing has finished.\r\n\r\nThe work requests would transfer all the data that is needed and not rely on the worker having any unique data. I think this is also more similar to how we want work requests to work in -native. \r\n\r\nSince work won't be tied to a specific thread, it should be possible to distribute work more consistently and speed things up.\r\n\r\n### Benchmarks\r\n\r\nCompared to https://github.com/mapbox/mapbox-gl-js/pull/2052\r\n\r\n```\r\n\r\npoint query\r\nhttp://localhost:9966/debug/#15.37/38.9047/-77.0299\r\nmapbox-streets-v6 (before all features were merged)\r\nnew sync                        1 ms\r\nnew sync with geometry          1 ms\r\nnew async                       5-6 ms\r\nnew async with geometry         5-6 ms\r\nold async                       1-2 ms\r\nold async with geometry         2 ms\r\n\r\npoint query\r\nhttp://localhost:9966/debug/#15.37/38.9047/-77.0299\r\nmapbox-streets-v7 (after many layers are merged into a single huge multi-geometry feature)\r\nnew sync                        2 ms\r\nnew sync with geometry          2 ms\r\nnew async                       5 ms\r\nnew async with geometry         5-6 ms\r\nold async                       5 ms\r\nold async with geometry         15-30 ms\r\n\r\nfull screen box query\r\nhttp://localhost:9966/debug/#15.37/38.9047/-77.0299\r\nmapbox-streets-v7 (after many layers are merged into a single huge multi-geometry feature)\r\nnew sync                        23 ms\r\nnew sync with geometry          70 ms\r\nnew async                       19-25 ms\r\nnew async with geometry         75 ms\r\nold async                       45 ms\r\nold async with geometry         770 ms\r\n\r\n\r\nfull screen bbox query\r\nhttp://localhost:9966/debug/#11.52/38.9262/-77.0420\r\nmapbox-streets-v7 (after many layers are merged into a single huge multi-geometry feature)\r\nnew sync                        115 ms\r\nnew sync with geometry          175 ms\r\nnew aysnc                       125 ms\r\nnew async with geometry         180 ms\r\nold async                       265 ms\r\nold async with geometry         560 ms\r\n```\r\n\r\n- The old and new sync queryRenderedFeatures are both really fast for point queries.\r\n- The new queryRenderedFeatures is much faster for large box queries, especially if geometries are included.\r\n- The new sync and async queryRenderedFeatures take a similar amount of time, but the async version spends less time on the main thread.\r\n\r\n### next steps\r\nCleaning things up. Fixing tests. Fixing a couple remaining bugs.\r\n\r\nDo all the high level changes sound ok?\r\n\r\n@lucaswoj @jfirebaugh @mourner "},"comment":{"url":"https://api.github.com/repos/mapbox/mapbox-gl-js/issues/comments/199460259","html_url":"https://github.com/mapbox/mapbox-gl-js/pull/2224#issuecomment-199460259","issue_url":"https://api.github.com/repos/mapbox/mapbox-gl-js/issues/2224","id":199460259,"user":{"login":"ansis","id":1421652,"avatar_url":"https://avatars.githubusercontent.com/u/1421652?v=3","gravatar_id":"","url":"https://api.github.com/users/ansis","html_url":"https://github.com/ansis","followers_url":"https://api.github.com/users/ansis/followers","following_url":"https://api.github.com/users/ansis/following{/other_user}","gists_url":"https://api.github.com/users/ansis/gists{/gist_id}","starred_url":"https://api.github.com/users/ansis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ansis/subscriptions","organizations_url":"https://api.github.com/users/ansis/orgs","repos_url":"https://api.github.com/users/ansis/repos","events_url":"https://api.github.com/users/ansis/events{/privacy}","received_events_url":"https://api.github.com/users/ansis/received_events","type":"User","site_admin":false},"created_at":"2016-03-21T20:22:05Z","updated_at":"2016-03-21T20:22:05Z","body":"@lucaswoj I think I've addressed all your comments. Let me know if you see anything else!"}}