Re: Is a faithful HTTP/2 response scheduler necessarily O(n) in the worst case?

[Patrick McManus <[e-mail]>]

media frames are another really good use case for linear orders. These, and
Tom's cases, were all cited as use cases during standardization.

I think the discussion about how to process that organization is germane
and interesting (chair hat!), and we should do that cognizant that this is
an expected use of the priority feature.

On Wed, Jan 25, 2017 at 8:09 AM, Tom Bergan <[e-mail]> wrote:

> On Tue, Jan 24, 2017 at 2:55 PM, Kazu Yamamoto <[e-mail]> wrote:
>
>> Hi Tom,
>>
>> >> http://www.mew.org/~kazu/material/2015-http2-priority2.pdf
>> >> http://www.mew.org/~kazu/doc/paper/http2-haskell-2016.pdf
>> >
>> > Thanks. IIUC, the algorithms described in both links are still at least
>> > O(depth), which can be O(n) for dependency trees generated by certain
>> > clients such as Chrome.
>>
>> Yes. Your understanding is correct.
>>
>> If a browser creates a list-like tree, I think it is misuse of priority.
>> And servers should limit the depth of trees.
>
>
> Why is that a misuse of priority? It seems entirely reasonable for a
> client to specify a mostly-linear order. There is a very good reason for
> this: inside HTML pages, CSS links and synchronous scripts must be
> evaluated in the order they appear in the HTML file. This implies that the
> server should send those resources in a linear order. This is exactly the
> rationale behind Chrome using mostly-linear orders. (This is not to say
> that mostly-linear orders are not occasionally problematic -- they are
> <https://bugs.chromium.org/p/chromium/issues/detail?id=651538#c1> -- but
> there are good reasons to linear orders at least some of the time.)
>
> (sorry for the duplicate message, replied from the wrong address)
>