rewrite: Caches

[Ludwig]

Playing with the Samples app, I noticed two things related to the tile caches.

1. A fixed (small) number of tiles is, at least for the InMemoryTileCache, not right as it does not take account of the screen size. In the Samples app the InMemoryTileCache has a capacity of 32 which leads to thrashing on devices where the screen shows more than 32 tiles at a time (tablets). The effect is that tiles are copied from the FileSystemTileCache into the InMemoryTileCache, only to be ejected again by one of the later tiles before it is ever retrieved from the cache. So the InMemoryCache is never read, but written on every tile access.
   Some sort of technique is needed to determine the number of tiles a screen requires as a minimum. That cannot be too difficult.
2. Setting the capacity of the FileSystemCache (second level cache) to 0 results in nothing being drawn at all. That does not seem right. Plus, there is actually a surprising number of devices out there that do not have any available storage (I think mostly the /sdcard/ is full), so not having a secondary storage must be an option.

Ludwig

[Thilo Mühlberg]

Good evening Ludwig,

1) Yes, you are right. A too small capacity effectively renders the
InMemoryTileCache useless. The minimum capacity can be calculated:

(width / TileSize + 1) * (height / TileSize + 1)

where TileSize is 256 pixel. Width and height are the dimensions of the
frame buffer - which is usually larger than the actual MapView. The
current default width and height is 1.5 times the size of the MapView.

I propose to add some utility method which calculates this minimum
capacity so that developers can easily adhere to this lower bound.

2) If you - for whatever reason - don't want a file system based tile
cache then you should simply not use one. The TwoLevelTileCache doesn't
have to be used, just a simple InMemoryTileCache will work fine. Or do
you have an idea how we can solve this problem in the tile cache code?

Greetings,
Thilo

On 01/05/13 15:40, Ludwig wrote:
> Playing with the Samples app, I noticed two things related to the tile
> caches.
>

> 1. A fixed (small) number of tiles is, at least for the

> InMemoryTileCache, not right as it does not take account of the
> screen size. In the Samples app the InMemoryTileCache has a capacity
> of 32 which leads to thrashing on devices where the screen shows
> more than 32 tiles at a time (tablets). The effect is that tiles are
> copied from the FileSystemTileCache into the InMemoryTileCache, only
> to be ejected again by one of the later tiles before it is ever
> retrieved from the cache. So the InMemoryCache is never read, but
> written on every tile access.
> Some sort of technique is needed to determine the number of tiles a
> screen requires as a minimum. That cannot be too difficult.

> 2. Setting the capacity of the FileSystemCache (second level cache) to

> 0 results in nothing being drawn at all. That does not seem right.
> Plus, there is actually a surprising number of devices out there
> that do not have any available storage (I think mostly the /sdcard/
> is full), so not having a secondary storage must be an option.
>
> Ludwig
>

> --
> You received this message because you are subscribed to the Google
> Groups "mapsforge-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to mapsforge-de...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Ludwig]

I propose to add some utility method which calculates this minimum
capacity so that developers can easily adhere to this lower bound.

Yes, but since the size of the MapView is only known after the layout is finished, I would, for simplity's sake, add a method that would calculate the number of tiles required for the screen size. Most of us know what proportion of the screensize is taken up by a MapView. 

2) If you - for whatever reason - don't want a file system based tile
cache then you should simply not use one. The TwoLevelTileCache doesn't
have to be used, just a simple InMemoryTileCache will work fine. Or do
you have an idea how we can solve this problem in the tile cache code?

I think this will need a solution inside the FileSystemCache as the class will need to deal with disk-space running out at any time regardless of the setting of its capacity.
For the previous version I had posted here some solution that, whenever a disk-full error occurred, it simply and silently set the cache capacity to 0. (Infinitely better than crashing the app and while power-users might know what to do if their storage fills up, most users do not, so alerting them to something does not really work. Any of this could of course be some sort of policy, but the cache itself dealing with the situation by not caching is not the worst solution. If a user later had storage again, at the next start this would be detected and the file cache used again).

Ludwig

[Ludwig]

Why not have in the TwoLevelTileCache something like:

    @Override
    public void put(Job key, Bitmap bitmap) {
        if (this.secondLevelTileCache.getCapacity() > 0) {
            synchronized (this.secondLevelTileCache) {
                this.secondLevelTileCache.put(key, bitmap);
            }
        }
        synchronized (this.firstLevelTileCache) {
            this.firstLevelTileCache.put(key, bitmap);
        }
    }

That would not only allow the second level cache capacity to be 0 (if disk space runs out, the second level tile cache could simply set its own capacity to 0, maybe sync is needed here), but would also be closer to an LRU model: at the moment a tile is cached first only on the file system and only after another read operation is put into the first level cache. The first level write operation is very cheap (only a map entry) and it would make sure that a tile can be retrieved directly again if needed.

(Technically you could even have a separate thread that would shuffle new entries into the second level cache after they have been added to the first level cache).

Ludwig

[Thilo Mühlberg]

The reason why new tiles are put in the second level cache is the job
queue. When you move the map around, the job queue gets filled with more
than hundred jobs which are all rendered (or downloaded) one by one
according to their priority. After they have been rendered (or
downloaded) the resulting tile images are stored in the tile cache.

Due to the very limited capacity of the first level tile cache, less
important tiles might evict more important tiles. Therefore the general
idea is to only move tiles to the first level cache if they are actually
requested from the TileLayer.

Your proposed code snippet is a possible solution for the problem. Of
course it requires a smarter implementation of the getCapacity() method
in the FileSystemTileCache. But maybe the performance will suffer if we
ask for the amount of free disk space at each put operation. Or is this
a very fast operation without any significant delay?

Greetings,
Thilo

On 03/05/13 14:51, Ludwig wrote:
> Why not have in the TwoLevelTileCache something like:
>
> @Override
> public void put(Job key, Bitmap bitmap) {
> if (this.secondLevelTileCache.getCapacity() > 0) {
> synchronized (this.secondLevelTileCache) {
> this.secondLevelTileCache.put(key, bitmap);
> }
> }
> synchronized (this.firstLevelTileCache) {
> this.firstLevelTileCache.put(key, bitmap);
> }
> }
>
> That would not only allow the second level cache capacity to be 0 (if
> disk space runs out, the second level tile cache could simply set its
> own capacity to 0, maybe sync is needed here), but would also be closer
> to an LRU model: at the moment a tile is cached first only on the file
> system and only after another read operation is put into the first level
> cache. The first level write operation is very cheap (only a map entry)
> and it would make sure that a tile can be retrieved directly again if
> needed.
>
> (Technically you could even have a separate thread that would shuffle
> new entries into the second level cache after they have been added to
> the first level cache).
>
> Ludwig
>
>
>
> On 3 May 2013 13:04, Ludwig <ludwigbr...@gmail.com

[Ludwig]

I have just been playing a bit with this and I have a little food for thought (I have really not made up my mind about this).

I have been comparing two strategies for filling the TwoLevelCache:

1. the current one where data is written first into the 2LC, then upon request into the 1LC,
   
2. where data is written first into the 1LC and also into the 2LC, with the following algorithm:

    @Override
    public void put(Job key, Bitmap bitmap) {

        synchronized (this.firstLevelTileCache) {
            this.firstLevelTileCache.put(key, bitmap);
        }
        synchronized (this.secondLevelTileCache) {
            if (this.secondLevelTileCache.getCapacity() > 0) {
                this.secondLevelTileCache.put(key, bitmap);
            }
        }
    }

(This differs from the first proposal in my previous email in writing first to the 1LC, then to the 2LC. Not only avoids it any possible deadlock through resource-ordering it also is always better as the data becomes available from drawing quicker).

Now I have added some counting to the cache, recording the number of cache requests according to their result: from first, from second and cache miss.

The 1LC size I have chosen here is relatively large, double the number of tiles that is considered a minimum for the screen size (following Thilo's suggested computation and taking the Overdrawfactor into account and then multiplying by 2).

The first results here are comparing the cache operation running the BasicMapViewerXmlTest from my Samples_Test (so the operations are identical, the results randomly vary I guess with rendering performance on the emulator):

old algo with BasicMapViewerTest

first second miss

10358 464 7004
9569 475 7260
10331 466 7394

new algo with BasicMapViewerTest
11709 0 3862
12005 2 7389
11211 0 7331

So, the main difference seems that the number of read requests to 2LC go very significantly down with the new strategy.

Tests on a real device scrolling around by hand (so the operations are not exactly reproducible, but maybe more realistic in timing) show very similar results:

Galaxy Note old algo

from_first from_second cache_miss

7953 161 4090
7970 341 3513

new algo
7881 4 4015
10609 4 5343

My interpretation of this data: as long as the 1LC is large enough (as it is in the case with these experiments), writing into it immediately is ok and drastically reduces the number of more costly reads from 2LC. If the number of tiles rendered in advance would be larger than the 1LC then this strategy would be wrong.

Again, I am not entirely sure about the results, the key problem being what is actually the best performance measurement here.

Ludwig