W3C home > Mailing lists > Public > public-webapps@w3.org > April to June 2015

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

From: Tab Atkins Jr. <jackalmage@gmail.com>
Date: Mon, 27 Apr 2015 16:23:34 -0700
Message-ID: <CAAWBYDBEspWmarFGPM1jX1ODd-iZxVPpw-0XGLjRYwU4nzYQOA@mail.gmail.com>
To: Ryosuke Niwa <rniwa@apple.com>
Cc: Steve Orvell <sorvell@google.com>, Olli Pettay <olli@pettay.fi>, Anne van Kesteren <annevk@annevk.nl>, WebApps WG <public-webapps@w3.org>, Erik Bryn <erik@erikbryn.com>, Dimitri Glazkov <dglazkov@google.com>
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.

~TJ
Received on Monday, 27 April 2015 23:24:22 UTC

This archive was generated by hypermail 2.3.1 : Friday, 27 October 2017 07:27:31 UTC