Cache map data in Kothic

[Miroff]

Now, when tile moved out of visible area, the tile being completely removed from memory. We need to cache preprocessed data to reduce tile loading next time. Bobcat renderer already has cache implementation, so it can be easily copied.

[Miroff]

Bobcat cache isn't suitable here, because we need to cache rendered tiles for short period to increase map dragging performance.

[Komzpa]

this was posted to my e-mail today by unxed:

В общем, как и собирался, попробовал я к котику приделать кэширование отрендеренных тайлов.
Отчитываюсь о результатах, чтобы в будущем другие не наступали на те же грабли.

Первое, что пришло в голову заюзать - LocalStorage.
Получилось довольно быстро, но работало всё равно катастрофически медленно.
Начал разбираться, вышло вот что.
Во-первых, LocalStorage ограничен объемом в 5 мб, и поменять это значение в Chrome, например, известными мне способами нельзя.
Ладно. В лисе можно хоть 500 поставить.
Во-вторых, в том же хроме он тормозит безмерно безо всяких видимых причин.
Т.е. до 500 кб - пожалуйста, а дальше скорость доступа падает по экспоненте.
Ладно. Пробуем в лисе и на небольших объемах кэша.
И что получается?
А получается всё равно медленно. Да, быстрее, чем с нуля рендерить,
но ощутимо медленнее загрузки готовых растровых тайлов (а я именно это хотел победить в первую очередь).

Начинаю понимать, что дело не только в доступе в LocalStorage.
Пробую сделать небольшой кэш (~50мб) тупо в памяти.
И наблюдаю следующую картину: всё равно тупит.
Недолгие изыскания привели к пониманию того, что drawImage в современных браузерах медленный сам по себе
(я кэшировал тайлы через toDataURL, а потом рисовал из кэша через drawImage).
Реально, 3-4 тайла читаются из памяти и рендерятся примерно по 0,7 сек на тайл!
Труба.
Конечно, быстрее становится. Но всё равно это далеко от комфортной работы.
В багзилле лисы нашелся даже тикет по скорости drawImage:
https://bugzilla.mozilla.org/show_bug.cgi?id=600410
В хроме такого тикета нет, а drawImage всё равно медленный.

Если со временем починят скорость drawImage, можно попробовать кэшировать через IndexedDB
(WebSQL отметаем, ибо не кроссбраузерно, и вряд ли будет - лиса и ie принципиально от него отказываются).
Попробовал в качестве пруф-оф-концепта сделать кэш на IndexedDB, и уперся в то,
что в тех браузерах, где он есть, его реализация крайне глючная и несовместимая между собой.
На второй день экспериментов искать баги реализации методом тыка надоело.

Так что, похоже, идею с кэшированием есть смысл пока отложить до лучших времён,
или пока кто-нибудь не придумает какое-то более изящное решение.

PS: в кэш сохранял в onRenderComplete, из кэша читал в drawTile.

[unxed]

Here is my expierence in implementing some kind of caching in kothic-js (it is draft translation of russian comment above with some additions and fixes).

As we cannot directly access browser's cache from javascript, we have to use some other mechanisms to store cached tiles on the client side.
Here is a list of technologies that can possibly be used for this (fill free to comment if I had missed some):

• WebSQL API
• HTML5 Local Storage
• HTML IndexedDB API
• FileSystem API
• Google Gears Database API

Each of them has it's advantages and disadvantages.

First of all, I think we should not use browser- or vendor-specific technologies so we should exclude Gears API from that list (not to mention the fact that Gears are no longer supported).

Now we should exclude technologies with outdated/deprecated specs. Goodbye, WebSQL API (I personally will miss you...).

So, now we have:

• HTML5 Local Storage
• HTML IndexedDB API
• FileSystem API

My first try was to use HTML5 LocalStorage. It was relatively easy to implement, but all in all it was not dramaticly faster.
After some expirements I found three major problems.

The first thing is that the size of LocalStorage is limited at 5 Mb in most browsers, and in Chrome, for example, you can't even change that limit. Okay, we can set 500 Mb in Firefox through about:config page.

The second thing is that LocalStorage access in Chrome starts to slow down seriously after about ~500Kb of space used. I know no serious reson for this and consider it to be Chrome's bug.
Okay, we decided to make it work in firefox for a start.
And what do we see? It is still slow. Yes, it is somethat faster compared to rendering every tile each time, but TOO slow for just getting the tile from cache and drawing it on a canvas.

At that point I came to the conclusion that the problem is not only in LocalStorage speed, so I tried to make a simple tile cache in memory to see how fast it would be. As it was not much faster than LocalStorage-based cache, I started profiling the caching functions and found that the third thing that slows down cache implementation is drawImage function of canvas object (I used toDataURL to get tile's content and drawImage to place it on canvas from cache). Really, tiles are read from memory and rendered at about 0.7 second per tile! Yes, base64-decoding of data urls also takes some time, but the major time waste is inside drawImage call.

Yes, it is somethat faster than to render all tiles as it is done currently. But it should be at least as fast as showing pre-rendered .png tiles (and maybe even faster as tiles are stored localy).

Firefox has a bug ticket describing slow drawImage implementation. I don't know if it is releated to my problem or not:
https://bugzilla.mozilla.org/show_bug.cgi?id=600410

So if we will see (much) faster drawImage implementation in browsers in near future, we can try following:

• Use LocalStorage-based caching within allowed 5 Mbs and hope Chrome will fix the speed problem
• Use IndexedDB as soon as it will get implemented in stable and compatible way in major browsers (I've tried to make proof-of-concept IndexedDB-based caching, but failed to make it work as IndexedDB is not so stable and not so compatible in at least Firefox and Chrome presently)
• Try to make FileSystem API-based caching (I've also tried to implement this but it seems Chrome leaks too much memory while FileSystem API is used and Firefox seems not to support it at all presently)

PS: Most expirements was done in kothic-leaflet.js; I cached rendered tiles in onRenderComplete and read them from cache in drawTile.

[unxed]

Here is sample implementation of caching using FileSystem API. Works (somehow) in Chrome. Not supported in Firefox. Not tested in other browsers/engines. tileprxy.php is simple json-tile-proxy script that caches json tiles on server side to prevent high load on osmosnimki.ru. It accepts x, y and z (zoom) as GET parametres and returns corresponding json tile.

Remember, you should use some kind of proxy serverside script (or store json tiles on your own server) to follow browser's security policy. You cannot just replace var url ... string to "url = 'http://osmosnimki.ru/vtile/' + key + '.js';" - it will break everything.

As you will see, Chrome (at least Chrome 14) leaks too much memory while caching is enabled so it will definitely crash sooner or later. Remember, this is proof-of-concept implementation, it should have bugs et cetera.

https://gist.github.com/1313999

[unxed]

Fixed stupid bug in FileSystem API cache implementation. Now _canvases array does not grow infinitely, so memory usage is seriously decreased. But strange Chrome crashes still happens from time to time - needs further investigation.

https://gist.github.com/1314300

[unxed]

Bug report related to Chrome's crashes after several FileReader calls: http://code.google.com/p/chromium/issues/detail?id=101668

[unxed]

Implemented caching tiles as binary PNG files, not as text files with base64-encoded PNG data as it had been done previously.
Got notable speed improvement (some time is wasted now while converting from base64 to binary png while writing to cache, but we save much more time while showing an image from cache without the need to base64-decode it each time it is shown). .

https://gist.github.com/1319325

Demo with cache enabled: http://2g0.ru/map/kothic
(remember, caching works only in Chrome currently)

[unxed]

There is another way to gain some more speed. The following example eliminates the need to call drawImage to show images from cache by adding additional layer that shows cached png tiles directly from local filesystem.

You should patch leafleat.js, replace
replace("{z}",b)
with
replace("{z}",b-this.options.zoomOffset)
for this to work.

https://gist.github.com/1320056
and usage example:
https://gist.github.com/1320060 (lines 173 - 186; replace 2g0.ru with your domain name)

Demo as usual at http://2g0.ru/map/kothic