[Pixman] [PATCH 2/3] Optimize BILINEAR filter to NEAREST for identity transforms

[Siarhei Siamashka]

On Thu, May 26, 2011 at 5:12 PM, Soeren Sandmann <sandmann at cs.au.dk> wrote:
> Siarhei Siamashka <siarhei.siamashka at gmail.com> writes:
>
>>> The problem for the analyze_extents() code is that if it chooses to
>>> provide the COVER flag, then some code might read common.filter and try
>>> to read outside the image to do bilinear filtering. But without COVER,
>>> the standard fast paths won't run.
>>>
>>> It seems to me that the cause of the problem is that the meaning of
>>> COVER depends on what the filter is: it means "there is enough space
>>> around the sample area for the chosen filter", which then becomes wrong
>>> when doing filter reductions.
>>
>> The meaning of COVER flag does not become wrong after doing filter
>> reduction, it's the "common.filter" variable which gets kind of wrong.
>> This "common.filter" value means "a filter value set by the user
>> application via pixman_image_set_filter() call". When no filter
>> reductions are done, it is also happens to be valid in any part of
>> code.
>
> Yes, we do in all cases need to preserve the state that the user
> set. This is in fact one of the key properties of the flags: they
> contain a 'summary' of the user set state, but they are not in
> themselves a full description of the image. The full description is
> stored elsewhere in the image struct.

Actually, the state is saved only as much as it is needed to provide
correct behaviour as observed from the outside. Maybe it's not the
best example, but we already don't particularly care whether the user
provided NULL pointer or identity matrix to
'pixman_image_set_transform' function:
    http://cgit.freedesktop.org/pixman/tree/pixman/pixman-image.c?id=pixman-0.22.0#n504
The same could have been done to the filter value, replacing
PIXMAN_FILTER_GOOD and PIXMAN_FILTER_BEST with PIXMAN_FILTER_BILINEAR
early in 'pixman_image_set_filter' function (that's just another
example). This all is possible because the user is not supposed to
read back the filter value and the transformation matrix, so he can't
be confused by setting one particular value and then reading back a
different one, even though they are exact equivalents. The case of
optimizing BILINEAR->NEAREST is almost the same, except that the
correct behaviour of "set transform" -> "set filter" -> "set
transform" must be preserved. So saving the original filter value is
needed, but that's just an implementation detail.

>> A subjective advantage is that it also gets rid of a somewhat
>> illogical NO_CONVOLUTION_FILTER flag. This flag does not cause any
>> problems itself, but just distracts attention when looking at the
>> printout of fast path flags.
>
> The flags with "NO" in their names are a bit confusing in that they lead
> to double negatives, but they are needed, because fast paths need to say
> "I _can't_ deal with property X, so I'll set the FAST_PATH_NO_X
> flag".

They are needed only when they are used for something. If no code
depends on some flag anymore, then it can be safely discarded. Getting
rid of NO_CONVOLUTION_FILTER was never my goal, it just happened to be
a side effect.

> This is a key part of how the flags work. As you wrote yourself:
>
>    The flags in pixman are implemented in such a way that they all
>    have some kind of "positive" meaning, indicating that the
>    operation is going to be more simple than the general case in one
>    way or another. Having more flags set on the initial analysis
>    stage is always good. Forgetting to set some of the flags is safe
>    in the sense that it will not make pixman misbehave, pixman will
>    just run slower because of not taking some fast paths.
>
>    Each fast path function has a mask with flags (provided separately
>    for source, mask and destination), with each bit set there telling
>    something like "I can't handle case X" (or with alternative
>    interpretation "I can't handle cases other than Y"). Fast path
>    functions with many flags set in their description are allowed to
>    cut more corners and run a lot faster because of this.
>
>    When asked to do something via pixman_image_composite() function
>    call, pixman first calculates the flags for the current operation
>    (again, separately for the source, mask and destination
>    images). Setting each bit is kind of like telling to the the rest
>    of the code: "You are allowed not to care about case X".
>
>  [ http://www.mail-archive.com/pixman@lists.freedesktop.org/msg00569.html ]
>
> But this breaks down if the compositing code starts *relying* on the
> flags being set, for example to know what the filter is; it will no
> longer be the case that "Forgetting to set some of the flags is safe in
> the sense that it will not make pixman misbehave, pixman will just run
> slower because of not taking some fast paths".
>
> This is an important rule to preserve, because it allows people to work
> on the flag computing code without knowing the details of the
> compositing code, and it allows people to write a new compositing
> routine or implementation without knowing that the flags even exist.

I see it more like as an extra convenience feature. It's just because
some flags may be difficult to set precisely, so that it is always set
when we do have some feature and not set when we don't. One example is
SAMPLE_OPAQUE flag (we would need to check all the pixels of a8r8g8b8
images when setting flags to be sure that we never miss any opaque
image, and this naturally does not make sense). But some of the flags
may be easily set precisely.

> When such general rules break down is when the code base becomes
> incomprehensible and only understandable to people who are intimately
> familiar with it.

The rules just need to be properly documented. Fast path flags can
have a longer comment section, explaining what they actually mean and
whether they are precise.

>> Regarding the potential risk of using "common.filter" accidentally in
>>a wrong way, I think that this variable can be just renamed and get an
>>unattractive discouraging name, maybe something like
>>"common.filter_before_optimization". Also for additional safety and
>>debugging purposes, maybe even valgrind client requests could be used
>>to mark this variable as unaccessible at the wrong time in a special
>>debug configuration, but that could be an overkill.
>
> Having to rename a basic property of images to prevent other code from
> reading it, it is a symptom of a misdesign taking place. It adds a
> strong coupling between the compositing code and the flag computing code
> that wasn't there before.

The names of the variables just should clearly reflect their purpose.
If some variable is intended to be used only in some stages of the
rendering pipeline, then it makes sense to name it appropriately.

>>> So maybe a solution would be to provide two separate flags:
>>>
>>>        COVER_NEAREST:  "there is enough space for a nearest filter"
>>>        COVER_BILINEAR: "there is enough space for a bilinear filter"
>>>
>>> These are unambiguous and because either there is enough space for a
>>> bilinear filter, or there isn't, they can be set independently of what
>>> the filter actually is.
>>
>> Sure, it's one of the multiple possible options. But I think that
>> evaluating and potentially setting both of these flags may introduce a
>> bit more overhead on the common code path.
>
> Could be, but not much difference in either case. It could also go the
> other way because the "switch (image->common.filter)" might no longer be
> necessary.
>
>> Also it still may be a good idea to divide responsibilities between
>> different parts of the library, optimize the filter early enough and
>> let the rest of code not to deal with extra flags and just forget that
>> this filter reduction optimization even happened. After all, cairo
>> already does filter reduction optimization itself, and nobody
>> complained about the original filter information not reaching pixman
>> fast path functions ;)
>
> Division of responsibilities is precisely why the COVER_* flags are
> better. The early code can simply set these flags if they are valid, and
> it can also set *both* FILTER_NEAREST and FILTER_BILINEAR flags in the
> case where a bilinear filter reduces to nearest. This is conceptually
> much cleaner because it says to the compositing code:
>
> - this image may be treated as if it is *either* bilinear filtered *or*
>  nearest filtered,
>
> which is exactly what is going on. Similarly, the COVER_* flags mean:
>
> - the source area is such that you can ignore the repeat mode, even if
>  you need to sample for a bilinear/nearest filter
>
> The compositing code can then do whatever it wants with this
> information, including ignore it.

Even though both FILTER_NEAREST and FILTER_BILINEAR flags may be valid
for certain operations, setting both of them may be no very practical,
or even harmful. Just one example. Currently for ARM target we
implement bilinear scaling using NEON instructions (fast path
registered in 'pixman-arm-neon.c'), but nearest scaling does not need
it, so we do it with just ARMv6 (with fast path registered in
'pixman-arm-simd.c'). Now let's suppose that we have both
FILTER_NEAREST and FILTER_BILINEAR flags set for some scaling
operation. And in this case NEON bilinear fast path will be selected
instead of a better nearest fast path which is available further in
the list after fallback.

I still think that optimizing the filter as early as possible in the
pipeline is the best choice. So that the rest of the pipeline just
does not need to care. And while it's probably just more like a band
aid (the performance is still not going to be great), optimized filter
is also somewhat helping here:
    http://cgit.freedesktop.org/pixman/tree/pixman/pixman-bits-image.c?id=pixman-0.22.0#n565


I have an updated patch v2 here:
    http://cgit.freedesktop.org/~siamashka/pixman/log/?h=permalink/20110526-unscaled-bilinear-fix-v2
Actually it's more like v0, because this is the initial variant of
code that I tried before attempting to optimize it for smaller memory
footprint and a bit better performance.

-- 
Best regards,
Siarhei Siamashka