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

On Tue, Apr 28, 2015 at 4:32 PM, Ryosuke Niwa <rniwa@apple.com> wrote:

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

I think I said it was a possibility opened by an imperative API, but I
thought it would be very rare (as will be any modification of the shadow
root in the distribution callback). I think that accomplishing decoration
by inserting an insertion point per distributed node is probably a
degenerate case and it would be better if we supported decoration, but that
seems like a v2+ type feature.

-Justin


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