On 2011-04-07, at 13:27, Brendan Eich wrote: > 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.
An oldie, but a goodie, perhaps relevant to this discussion: http://www.cs.purdue.edu/homes/jv/pubs/oopsla97.pdf _______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
