On Apr 5, 2011, at 2:19 PM, David Bruant wrote:
> What I'm worried about is the memory cost of such an implementation. The
> current [[HasInstance]] implementation has a constant memory cost. Keeping
> references has a linear memory cost in terms of instance number. My favorite
> real-world memory-intensive use case is the one-page Standard HTML
> (http://www.whatwg.org/specs/web-apps/current-work/). Right now, it contains
> 125684 DOM Elements. If trying to implement EventTarget [[HasInstance]]
> internal method, it would require as many entries in the WeakMap.
First, there's no free lunch. Either the DOM objects need internal fields
(vptrs in C++ sense, plus static shared vtbls) or brands or trademarks, which
is per-object overhead. Or we need an entry in a weakmap for each object, which
can be quite efficient (better if the map were a set, but still).
Second, although the details do matter, the asymptotic space complexity is the
same, ignoring static or singleton costs which amortize to epsilon: k*n for
constant k and n objects, or O(n).
The time complexity to test is-a would be O(1), but of course as David Bacon
likes to point out, small constant factors can matter: a field load and compare
beats a hashtable lookup. A C++ virtual call to QueryInterface or the like is
slower than a well-implemented hashtable lookup.
Again, big-O does not distinguish even if some benchmarks run on different
implementations could tell.
/be
_______________________________________________
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
