W3C home > Mailing lists > Public > public-webapi@w3.org > February 2006

Re: Asymptotic computational complexity bounds for DOM methods

From: Maciej Stachowiak <mjs@apple.com>
Date: Mon, 27 Feb 2006 01:06:27 -0800
Message-Id: <8D56951D-39BA-499E-A86D-7B95B1FF972A@apple.com>
Cc: "Web APIs WG (public)" <public-webapi@w3.org>
To: Bjoern Hoehrmann <derhoermi@gmx.net>


I don't think this is the most important thing in the world, so I am  
not going to debate it much. Tthere are lots of more important things  
that need specifying.But a couple of comments:

On Feb 27, 2006, at 12:15 AM, Bjoern Hoehrmann wrote:

>
> * Maciej Stachowiak wrote:
>> We should consider placing computational complexity bounds on DOM
>> methods in the future. For example, it would be perfectly legal to
>> make getElementById be O(N) in the number of elements in the
>> document, or even O(N^2). But in practice unless it is O(1) your
>> implementation will not be interoperable with web content, as there
>> will be web apps that will lock the user's machine for hours or even
>> days.
>
> It does not matter whether your gEBI implementation is O(1) or O 
> (N^2) if
> your script engine is too slow in general, or if you are running on  
> too
> slow hardware,

An O(N^2) implementation of getElementById would be much much worse  
than a 1000 times slower scripting engine or 1000 times slower hardware.

> or if your implementations is limited to an environment where gEBI  
> is rarely, if ever, used, and so on.

This might be a plausible argument if there are such implementations  
(but nontheless they need to be DOM compliant). However, taken to the  
extreme this argument could equally apply to making getElementById  
itself OPTIONAL.

> I see no reason to put this information into the specifications  
> (let alone as requirements).

The C++ standard has requirements on asymptotic complexity for  
certain standard library functions, so it would not be completely  
unprecedented to do so. The reason they do this is so that you can  
write code that you know won't completely melt on larger than  
expected datasets, and will continue to have this characteristic  
across all standards-conforming implementations. In other words, this  
aids interoperability.

Another value of this excercise is that it makes you think about  
whether the things you are specifying even *can* be implemented  
efficiently in principle.

Regards,
Maciej
Received on Monday, 27 February 2006 09:06:35 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:18:53 GMT