Re: Asymptotic computational complexity bounds for DOM methods

On Feb 27, 2006, at 2:02 AM, L. David Baron wrote:

> On Monday 2006-02-27 01:51 -0800, Maciej Stachowiak wrote:
>> On Feb 27, 2006, at 1:15 AM, L. David Baron wrote:
>>> Mozilla's implementation of Node.nextSibling is O(N) in the  
>>> number of
>>> (prior) siblings of the element.
>>
>> Are you sure? I tried this test, with varying numbers of spans in the
>> div. With an O(N) implementation of nextSibling, it should be  
>> taking O
>> (N^2) time in the number of spans, but the scaling seems to be linear
>> in Firefox 1.5 as expected. With ~2000 spans I get a time of 134,
>
> So my knowledge turns out to be a little out of date.  There are some
> caching optimizations to make it faster in some cases:
>   https://bugzilla.mozilla.org/show_bug.cgi?id=240884
> I'm haven't looked at those in detail, though, so I'm not quite sure
> what's needed to defeat them, but it's still O(N) for at least some  
> use
> cases.
>
> Also, the coefficient for the O(N) term could be really small, since
> searching an array is a very simple operation; I suggest trying bigger
> numbers.

These numbers are big enough to show a significant difference in the  
times, and the difference shows linear scaling, not quadractic, so  
the underlying nextSibling operation is definitely O(1), at least in  
this case.

I also tried the "nextToLast" case with 160,000 child nodes and I  
still got constant time.

I tried reading the code for nsIContent and I think the cache could  
be defeated by doing an insert but I couldn't get this to happen  
either. I will admit to being somewhat baffled by the code.

Anyway, it's obvious there is a lot of variation here in design  
approaches, so maybe there is no good guarantee to give content authors.

Regards,
Maciej

Received on Monday, 27 February 2006 11:26:33 UTC