You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I know this engine is not focused on speed, however the spec contains this paragraph (and similar for WeakMap, Set and WeakSet):
Maps must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structure used in this specification is only intended to describe the required observable semantics of Maps. It is not intended to be a viable implementation model.
The current implementation here strictly follows the spec algorithms, meaning access times are not sublinear, and are not even proportional to the number of elements in the collection. They are linear with respect to the total number of successful insertions over the collection's lifetime.
The text was updated successfully, but these errors were encountered:
indeed, the point is to validate the spec's required observable semantics, not to be fast here.
you might be interested in https://github.com/engine262/boost/, something I've been planning to continue work on at some point but haven't gotten around to it.
That boost thing doesn't sound right. I'd have to somehow replace bootstrapMap((Iterator)?Prototype)? and basically copy the whole Map class just to change a few lines in each method.
I'm not asking for fast. I've been thinking how it could be made reasonably slow while still following the spec (almost) step by step. For WeakMap/WeakSet it's trivial — since these can only store non-primitive keys, they could simply store their elements directly in a (node) Map/Set, instead of records in an array.
For Map/Set it's not so straightforward, but doable. The List that stores [[MapData/SetData]] doesn't have to be backed by an array. It is only required to be an ordered sequence. Could be backed by a (node) Map with integer indices, or a linked list, either of which would achieve linear-time operations with respect to the number of elements in the collection. Especially with a backing Map, there would be very few diversions from the current implementation — mostly in steps mentioning empty values, which would not be present.
I know this engine is not focused on speed, however the spec contains this paragraph (and similar for WeakMap, Set and WeakSet):
The current implementation here strictly follows the spec algorithms, meaning access times are not sublinear, and are not even proportional to the number of elements in the collection. They are linear with respect to the total number of successful insertions over the collection's lifetime.
The text was updated successfully, but these errors were encountered: