[webkit-dev] LayoutTests results fallback graph

[Dirk Pranke]

On Mon, Jul 11, 2011 at 10:46 AM, Adam Barth <abarth at webkit.org> wrote:
> On Mon, Jul 11, 2011 at 12:30 AM, Maciej Stachowiak <mjs at apple.com> wrote:
>> On Jul 10, 2011, at 12:11 PM, Adam Barth wrote:
>>> On Sun, Jul 10, 2011 at 12:01 PM, James Robinson <jamesr at google.com> wrote:
>>>> On Jul 10, 2011 10:53 AM, "Adam Barth" <abarth at webkit.org> wrote:
>>>>> Hi webkit-dev,
>>>>>
>>>>> In trying to understand how our LayoutTest results system works, I've
>>>>> created a digram of the fallback graph among the various
>>>>> platform-specific directories:
>>>>> https://docs.google.com/drawings/d/1z65SKkWrD4Slm6jobIphHwwRADyUtjOAxwGBVKBY8Kc/edit?hl=en_US
>>>>>
>>>>> Unfortunately, the fallback graph is not a tree, as one might imagine
>>>>> initially.  I'd like to propose two small changes, which will
>>>>> hopefully make the system more sensible globally.  I'm happy to do all
>>>>> the work required to make these changes:
>>>>>
>>>>> 1) The "win" port should fall back either to "all" (the platform
>>>>> independent results) or to "mac," but not to "mac-snowleopard", as it
>>>>> does currently.  (I slightly prefer "all", but "mac" would also be
>>>>> fine with me.)
>>>>>
>>>>> 2) The "chromium" port should fall back directly to "all" rather than
>>>>> taking a detour through various Apple-maintained ports, as it does
>>>>> currently.
>>>>>
>>>>> These changes have the following virtues:
>>>>>
>>>>> A) The resulting fallback graph will be a tree, making the fallback
>>>>> graph easier to understand for both humans and automated tools.
>>>>> B) The Chromium port will behave more like the other ports (e.g., GTK
>>>>> and Qt), rather than being a parasite on Apple-maintained ports.
>>>>>
>>>>> These changes might increase the number of image baselines we store in
>>>>> the tree for "chromium-mac"-derived ports (because there will be fewer
>>>>> redundant fallback paths), but I expect that cost to be relatively
>>>>> small because essentially every port has different image baselines
>>>>> anyway
>>>>
>>>> Could you measure this? I suspect that not falling back on the mac pixel
>>>> results will mean checking in a few thousand more pngs, but that's just a
>>>> guess.
>>>
>>> That seems possible:
>>>
>>> abarth at quadzen:~/git/webkit/LayoutTests/platform/chromium-mac$ find .
>>> -name "*.png" | wc -l
>>>     900
>>> abarth at quadzen:~/git/webkit/LayoutTests/platform/mac$ find . -name
>>> "*.png" | wc -l
>>>    6688
>>> abarth at quadzen:~/git/webkit/LayoutTests/platform/chromium-win$ find .
>>> -name "*.png" | wc -l
>>>    5988
>>> abarth at quadzen:~/git/webkit/LayoutTests/platform/chromium-linux$ find
>>> . -name "*.png" | wc -l
>>>    5731
>>
>> Adding thousands more PNGs would be unfortunate, especially if a significant number of them are going to be rolled over frequently.
>
> I wouldn't expect a significant number of them to change frequently.
>
>> What are the concrete benefits of the fallback graph being a tree?
>
> There are two main benefits:
>
> 1) A tree is much easier to understand than a rats nest of interwoven
> fallback paths.  Today, the graph is close to a tree so it's possible
> for experts to understand how things work, but if we continue to add
> non-transitive paths, the situation will quickly spiral out of
> control.  For folks who aren't experts about how the system works
> today, I doubt they could correctly predict the consequence of certain
> actions.  One of my short-term goals is to make managing the expecte
> results easier, which is why I'm interested in having the system be
> understandable to non-experts.
>
> 2) Without a tree structure, it's difficult to compute the optimum
> assignments of expected results to directories.  With a tree
> structure, it's very easy.  If all the children of a node have the
> same result, you can delete the result at the children and promote it
> to the parent.  That reasoning is false for our current fallback
> graph.  The correct rule for when you can promote a result instead
> requires reasoning over all paths (of which, of course, there are
> exponentially many).
>

I'm not sure I understand in what sense you're using the word
"optimum" here. Normally I would define it as "fewest overall
baselines in the tree". Using my definition, it seems possible that
having multiple "parents" could result in fewer baselines. Example: if
chromium-mac is allowed to fallback on chromium, then mac, then "all"
(rather than just chromium then "all" or mac then "all") you may need
fewer total baselines

Of course, I'm not sure that "fewest overall baselines" is in fact the
goal we should be shooting for. I definitely agree that a tree is
easier to understand. This of course is the same debate as single
inheritance vs. multiple ... multiple may reduce the total lines of
code, but be harder to understand

NRWT has nearly all of the code needed to make it easy to evaluate
what the total impact of changing the paths would be. I think I had
some scripts to do this long ago but I've lost them. I should be able
to reconstruct them this afternoon.

-- Dirk