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

> On Apr 27, 2015, at 4:23 PM, Tab Atkins Jr. <jackalm...@gmail.com> wrote: > > On Mon, Apr 27, 2015 at 4:06 PM, Tab Atkins Jr. <jackalm...@gmail.com> > wrote: > > On Mon, Apr 27, 2015 at 3:42 PM, Ryosuke Niwa <rn...@apple.com> wrote: > > On Apr 27, 2015, at 3:15 PM, Steve Orvell <sorv...@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 > >