Tile prioritization redesign.

[Vladimir Levin]

Hey,

As a part of an effort to improve the CPU time in the compositor, we came up with a new tile prioritization scheme which should reduce the amount of tiles that we have process each frame. 

I just wanted to share the design doc for this:

https://docs.google.com/a/chromium.org/document/d/1tkwOlSlXiR320dFufuA_M-RF9L5LxFWmZFg5oW35rZk/edit#

Thanks,

Vlad

[m.hirv...@partner.samsung.com]

Hi!

I was studying this document and noticed that some things have already been implemented in M37. I would be interested to know if you are planning to implement the grid for the eviction as well? I noticed that now it is using heap which is mentioned as the first phase implementation in the document.

Best regards,
Mika Hirvikorpi

[Vladimir Levin]

Hi

As you noticed, lot of the piece of this have landed. However, the code itself isn't yet being used. I'm working on a few patches that would enable it right now.

After that is done, I do plan to work on the eviction iterators to make it match up the design doc. There were a few issues initially that prevented me from doing it right away: It wasn't clear if we would keep all tiles in the grid or only tiles with resources; If it was the latter, it wasn't clear how the tiling would get that information; If it was the former we'd have to reconstruct the grid frequently.

Thanks,

Vlad

[m.hirv...@partner.samsung.com]

Hi!

Ok, thanks for the quick reply.

Another question I have is related to the UpdateTilePriorities which is run always to all tiles. We were thinking if the tile priority update could be moved to the tile raster iterator. This way it would be done only the tiles selected for raster. Is this something that you are going to do in near future or do you see some problems in moving the priority calculation to the iterator?

Best regards,
Mika Hirvikorpi

[Vladimir Levin]

Hey,

Yeah that's the plan. We could even create tiles in the raster iterator, instead of creating all of the tiles in the interest rect ahead of time.

One small problem with just doing it is eviction iterators. Eviction also needs to update the priority of the tile. However, we have two priorities on the tile: active priority and pending priority. Eviction iterator will tend to visit a tile with lowest priority first. This means that we could return a tile from, say, active eviction iterator with an updated active priority.

However, it could be the case that the pending priority for that tile is actually pretty high, and thus the tile shouldn't be evicted. The question is when to update the pending priority, so that the tile manager eviction iterator can have all of the information to make a decision. I was thinking of having a priority_calculator type of thing on the tiling, and when the eviction update the priority it also checks its twin tiling and if it exists, it updates the twin priority as well. For now, we could do that for raster as well, so that we don't accidentally end up using a priority that wasn't updated.

For now, this is kind of up in the air, since I haven't started on any concrete implementation yet. 

Thanks,

Vlad

[m.hirv...@partner.samsung.com]

Hi,

It is good to know that you are planning to do this. My initial though was to update the tile priorities just before the eviction, because it seems to be fastest to implement at first.

Have you considered is the EVENTUALLY priority is needed? If it is not then it would be simplify the code if there would only be two priorities NOW and SOON (or renaming the SOON to something else).

Br,
Mika

[Vladimir Levin]

I think we still need the eventually priority, since the distance to visible is important to determine the relative raster (and eviction) order of the tiles. In cases where the viewport is static, most tiles near the viewport end up being in the eventually bin and in those cases, I think we still would prefer to raster content that is closer to the viewport first and evict content that is further from the viewport first. Note that it's not so much of an issue with one layer, since the spiral iterator determines the order of tiles (for raster, at least). However, it becomes an issue when trying to decide which layer should contribute the next tile.

If you have a concrete plan that deals with this situation, I would love to hear it. I think we do need to reduce some of the complexity around tile priorities.

Thanks,

Vlad

[Eero Häkkinen]

Hi,

25.06.2014 20:24, Vladimir Levin wrote:

I think we still need the eventually priority, since the distance to visible is important to determine the relative raster (and eviction) order of the tiles. In cases where the viewport is static, most tiles near the viewport end up being in the eventually bin and in those cases, I think we still would prefer to raster content that is closer to the viewport first and evict content that is further from the viewport first. Note that it's not so much of an issue with one layer, since the spiral iterator determines the order of tiles (for raster, at least). However, it becomes an issue when trying to decide which layer should contribute the next tile.

The idea is more like to simplify the handling of different tile related rectangles -- not remove distante_to_visible values or such.

At the moment, the tiling raster tile iterator iterates first over visible tiles (these tiles have priority bin set to NOW and distance_to_visible set to 0), then over skewport tiles (these tiles have priority bin set to SEEN and distance_to_visible set to a value greater than zero), then over soon border rect tiles (these tiles have also priority bin set to SEEN and distance_to_visible set to a value greater than zero) and finally over rest of the eventually rect tiles (these tiles have priority bin set to EVENTUALLY and distance_to_visible set to a value greater than zero).

There is one problem here: if the skewport is very high, some skewport tiles have priorities which are smaller than those of soon border rect tiles even though tiling raster tile iterators yield skewport tiles (correctly) before soon border rect tiles. This may result layer raster tile iterators to prioritize tiling raster tile iterators incorrectly. That is, it might happen that if only some layers have high skewports, some of those skewport tiles are rasterized only after soon border rect tiles of other layers are rasterized even though skewport tiles are more important than soon border tiles.

The other thing is that (from the raster tile iterator point of view) soon border rect tiles (having priority bin SOON) and eventually rect tiles (having priority bin EVENTUALLY) are not that different. The only difference is that soon border rect tiles are closer to the visible rect than eventually rect tiles. But that is already handled by smaller distance_to_visible values. Therefore there is not need to iterate over soon border rect tiles and eventually rect tiles separately or for them to have different priority bins.

It would be enough to have one priority bin for visible tiles and skewport tiles (the former ones should have distance_to_visible set to 0 and the latter ones should have distance_to_visible set to a value greater than 0) and one priority bin for soon border rect tiles and eventually rect tiles (the former ones have smaller distance_to_visible values than the latter ones).

Br,
Eero

[Vladimir Levin]

On Thu, Jun 26, 2014 at 3:05 AM, Eero Häkkinen <e.hak...@partner.samsung.com> wrote:

Hi,

25.06.2014 20:24, Vladimir Levin wrote:

I think we still need the eventually priority, since the distance to visible is important to determine the relative raster (and eviction) order of the tiles. In cases where the viewport is static, most tiles near the viewport end up being in the eventually bin and in those cases, I think we still would prefer to raster content that is closer to the viewport first and evict content that is further from the viewport first. Note that it's not so much of an issue with one layer, since the spiral iterator determines the order of tiles (for raster, at least). However, it becomes an issue when trying to decide which layer should contribute the next tile.

The idea is more like to simplify the handling of different tile related rectangles -- not remove distante_to_visible values or such.

At the moment, the tiling raster tile iterator iterates first over visible tiles (these tiles have priority bin set to NOW and distance_to_visible set to 0), then over skewport tiles (these tiles have priority bin set to SEEN and distance_to_visible set to a value greater than zero), then over soon border rect tiles (these tiles have also priority bin set to SEEN and distance_to_visible set to a value greater than zero) and finally over rest of the eventually rect tiles (these tiles have priority bin set to EVENTUALLY and distance_to_visible set to a value greater than zero).

There is one problem here: if the skewport is very high, some skewport tiles have priorities which are smaller than those of soon border rect tiles even though tiling raster tile iterators yield skewport tiles (correctly) before soon border rect tiles. This may result layer raster tile iterators to prioritize tiling raster tile iterators incorrectly. That is, it might happen that if only some layers have high skewports, some of those skewport tiles are rasterized only after soon border rect tiles of other layers are rasterized even though skewport tiles are more important than soon border tiles.

SOON and EVENTUALLY bin tiles fall under prepainting, which means that the layer will only consider the high resolution tiling for these tiles. However, I see your point that at tile manager level, in order to break ties between different layers, it might consider a soon border tile before a skewport tile. 

 

The other thing is that (from the raster tile iterator point of view) soon border rect tiles (having priority bin SOON) and eventually rect tiles (having priority bin EVENTUALLY) are not that different. The only difference is that soon border rect tiles are closer to the visible rect than eventually rect tiles. But that is already handled by smaller distance_to_visible values. Therefore there is not need to iterate over soon border rect tiles and eventually rect tiles separately or for them to have different priority bins.

It would be enough to have one priority bin for visible tiles and skewport tiles (the former ones should have distance_to_visible set to 0 and the latter ones should have distance_to_visible set to a value greater than 0) and one priority bin for soon border rect tiles and eventually rect tiles (the former ones have smaller distance_to_visible values than the latter ones).

That is true and is worth considering. One thing of note is that in the tile manager, we have another... limit, called memory policy which limits which tiles we raster. Currently there are four limits (naming might be off): allow anything, allow prepaint, allow bare minimum, allow nothing. These roughly correspond to everything, SOON only, NOW only, and nothing. So the distinction between SOON and EVENTUALLY (or between NOW and SOON) is still being used. That being said, removing bins is a good thing IMHO, so this is probably a good thing to consider.

 

Br,
Eero