Re: Imperative API for Node Distribution in Shadow DOM (Revisited)

On Apr 27, 2015, at 4:23 PM, Tab Atkins Jr. <jackalmage@gmail.com> wrote:
> On Mon, Apr 27, 2015 at 4:06 PM, Tab Atkins Jr. <jackalmage@gmail.com> wrote:
>> On Mon, Apr 27, 2015 at 3:42 PM, Ryosuke Niwa <rniwa@apple.com> wrote:
>>>> On Apr 27, 2015, at 3:15 PM, Steve Orvell <sorvell@google.com> wrote:
>>>> IMO, the appeal of this proposal is that it's a small change to the current spec and avoids changing user expectations about the state of the dom and can explain the two declarative proposals for distribution.
>>>> 
>>>>> It seems like with this API, we’d have to make O(n^k) calls where n is the number of distribution candidates and k is the number of insertion points, and that’s bad.  Or am I misunderstanding your design?
>>>> 
>>>> I think you've understood the proposed design. As you noted, the cost is actually O(n*k). In our use cases, k is generally very small.
>>> 
>>> I don't think we want to introduce O(nk) algorithm. Pretty much every browser optimization we implement these days are removing O(n^2) algorithms in the favor of O(n) algorithms. Hard-baking O(nk) behavior is bad because we can't even theoretically optimize it away.
>> 
>> You're aware, obviously, that O(n^2) is a far different beast than
>> O(nk).  If k is generally small, which it is, O(nk) is basically just
>> O(n) with a constant factor applied.
> 
> To make it clear: I'm not trying to troll Ryosuke here.
> 
> He argued that we don't want to add new O(n^2) algorithms if we can
> help it, and that we prefer O(n).  (Uncontroversial.)
> 
> He then further said that an O(nk) algorithm is sufficiently close to
> O(n^2) that he'd similarly like to avoid it.  I'm trying to
> reiterate/expand on Steve's message here, that the k value in question
> is usually very small, relative to the value of n, so in practice this
> O(nk) is more similar to O(n) than O(n^2), and Ryosuke's aversion to
> new O(n^2) algorithms may be mistargeted here.

Thanks for clarification. Just as Justin pointed out [1], one of the most important use case of imperative API is to dynamically insert as many insertion points as needed to wrap each distributed node.  In such a use case, this algorithm DOES result in O(n^2).

In fact, it could even result in O(n^3) behavior depending on how we spec it.  If the user code had dynamically inserted insertion points one by one and UA invoked this callback function for each insertion point and each node.  If we didn't, then author needs a mechanism to let UA know that the condition by which insertion points select a node has changed and it needs to re-distribute all the nodes again.

- R. Niwa

[1] https://lists.w3.org/Archives/Public/public-webapps/2015AprJun/0325.html <https://lists.w3.org/Archives/Public/public-webapps/2015AprJun/0325.html>