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

[Amos Jeffries <[e-mail]>]

On 25/01/2017 12:20 p.m., Patrick McManus wrote:
> media frames are another really good use case for linear orders. These, and
> Tom's cases, were all cited as use cases during standardization.
> 

Gateways translating for HTTP/1 clients also need their responses to be
as linear as possible to match the 1.1 sequence. Otherwise they will be
forced to either spend RAM caching response data with a blocked
pipeline, or forgoe the h2 multiplexing and PUSH benefits.


> 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)
>>
>