Geekly Articles each Day
📜 ⬆️ ⬇️

Harmony collections NOW


On Habré, an article about such wonderful things as Map, WeakMap and Set was already skipping, but in reality the real capabilities of these APIs were not disclosed (if I did use the search well).
These APIs are not really implemented anywhere except firefox (it can be included in chrome canary), but even there, until recently, the use of HTMLElement-like objects as keys was not supported. Polymer, for example, removed only three weeks ago.

if (navigator.userAgent.indexOf('Firefox/') > -1)


Why are they so good? In essence, Map / WeakMap can be perceived as ordinary hash objects, only complex objects (Object, Function, Array) can be used as keys, since the binding is not in content, but in memory.
In this way, it becomes possible to bind on the frontend to

')
This gives us the opportunity to work without id-schnik elements, do date-binding many times faster, create a crazy alternative implementation of promises, and so on.
We will talk about WeakMap. Even not so, we will talk about the existing polyfills for WeakMap.



As for the rest of the elements:
Map is a hash, the keys of which can be both primitives and objects.
Set is a set of unique elements. It is quite simple to build on top of the Map. Its most important advantage is the processing of arrays, due to which it is possible to reduce the complexity of the uniq task from O (n ^ 2) to O (n).

About what possibilities of working with the DBMS appear on the backend with node.js - I, perhaps, will keep silent, because I am not familiar enough with the node to recommend something authoritatively.

The syntax is a bit more complicated than that of a classic object, but it is also quite clear and we read:

 var map = new WeakMap; map.set(someObject, 'someKey'); alert(map.get(someObject)); map.delete(someObject);


In several projects, including one of the past versions of cornerJS , such a decision was justified in terms of brevity and readability of the code, however, due to the fact that one of the polyfills was used, I considered this solution to be very memory-consuming.

The implementation of ecmascript.org offers as an option a similar implementation (translated from pseudo-js to a slightly reduced executable, full implementation on github ):

 window.WeakMap = function () { var keyList = []; var valueList = []; return Object.freeze({ 'get': function (key, defaultValue) { var index = keyList.indexOf(key); var value = valueList[index]; return index === -1 ? defaultValue : value; }, 'set': function (key, value) { var index = keyList.indexOf(key); if (index === -1) { keyList.push(key); valueList.push(value); } else { valueList[index] = value; } } //...( has, delete  clear) }); };


Such an implementation has many problems.
First, memory flows perceptibly: even when an element is deleted, it remains in keyList, and if such a WeakMap is working on a real project, a huge amount of memory can leak to the storage of essentially deleted objects. GarbageCollector does not work on the element, for it it is considered still existing.
At the engine level, this can be solved, but in any case, the GarbageCollector will still work incorrectly.
Secondly, when there are a lot of elements in keyList, the selection of the latter starts to take really a lot of time in chrome on macbook air 2013, the search for the 1e9th element took more than a second. The complexity of the problem is O (n), which sometimes significantly affects performance.

There is an alternative implementation that solves the problem with the sample rate, reducing the complexity of the task to O (1):

 window.WeakMap = (function(){ var counter = Date.now() % 1e9; return function(){ var name = '__st' + (Math.random() * 1e9 >>> 0) + (counter++ + '__'); return { set: function(key, value) { var entry = key[this.name]; if (entry && entry[0] === key) entry[1] = value; else defineProperty(key, this.name, {value: [key, value], writable: true}); }, get: function(key) { var entry; return (entry = key[this.name]) && entry[0] === key ? entry[1] : undefined; } } } })();


However, this does not solve the memory problem, and even makes it worse. A cyclic reference appears in the memory of each element: key [name] [0] === key. If you believe open documentation, the garbage collector is not able to catch such scenarios, so that over time, the memory becomes significantly clogged - however, it will take a lot of time.
That is why it is worth using Polymer / X-tags with caution, a lot of which rely on WeakMap (the above is a somewhat abbreviated implementation of them). For example, the polyfill for MutationObserver relies on it, which is used not only by them, but also by a large number of third-party projects, many of which may not be aware of memory problems in it.
Added a couple more minuses in comparison with fair implementation. One of them will turn out to be insignificant for the majority: we lose the ability to bind to frozen objects. The second for some will be quite serious. This implementation becomes IE9 +. The first option is so simple that it can work in IE6 + if you connect Array.prototype.indexOf-polyfill (for example, from Mozilla ). Array.prototype.indexOf also appeared in IE9, but at least it can be implemented. Unlike Object.defineProperty (strictly speaking, IE8 has defineProperty support for DOM elements, but you can't rely on this).

As a result, we have either slow work on large volumes of records, or an extra property in a key element (which means, perhaps, even access to it from the outside), problems with some of the iterators, and in any case, memory filled with additional attributes.

There is also a WeakMaps implementation in jQuery. When you request jQuery.data (element, key), you work with one of the WeakMap implementations. It works a little easier.
Perhaps you've ever seen something like this in your code:

 document.body.jQuery19104357186993584037 20


Now you know that this is the id of the element in your own WeakMap from jQuery.

When an item is deleted, it is deleted, but we still:


Here we come to the main part.

WeakMap was called this way because they wanted to implement weak reference - a weak link that is not taken into account in the GC, respectively, both the key and the value are deleted when there are no more other records of this key.
In the correct implementation, both the key and the value must be deleted.
But I couldn’t even imagine that it was possible until I came across a phrase in one of the repositories on the githaba that could not but surprise:
Shim for WeakMap with non-leaky O (1) lookup time

It relies on Object.defineProperty - which means IE9 + and the impossibility of referencing frozen objects, but the element was not visible on the element, which was a surprise.
The repository itself is here: https://github.com/Benvie/WeakMap/
I could not resist checking to the extent that this may be true at all.

For this, a simple and quick memory snapshot test was made.



fully test code
 // ""  1 //  // ""  2 var someStorage = []; var map = new WeakMap; var length = 1e5; // ie    1e4,     1e5      10   . for (var i = 0; i < length; i++) { someStorage[i] = {randomValue: Math.random() * 1e9 >>> 0}; //     ,        -  garbage collector       map.set(someStorage[i], {otherRandomValue: Math.random() * 1e9 >>> 0}) } // ""  3 for (var i = 0; i < length; i++) { someStorage[i] = void 0; } // ""  4


The results are as follows:

Chrome 30 (Mac 10.9)


Firefox 24 (Mac 10.9)


IE 11 (Win 8.1)


I admit honestly - I was shocked when I saw that all the memory that the application took was given away - both as a memory for keys and for values.

After that, I decided just in case to make sure that the search time is real O (1). It turned out to be true.

Chrome 30 (Mac 10.9)


Firefox 24 (Mac 10.9)


In the end, it's all true. WeakMap can really be used in a large number of projects, it provides tremendous potential for data-binding, working with Osprey, creating a large number of plug-ins, and this can be done today, at least we have only every fifth IE8 + project and the rest of IE9 +. At the same time, WeakMap not only simplifies work with some types of data, but also allows you to increase speed and optimize, and in some cases significantly, work with memory.
The main thing is to choose the right polyfill.

By the way, you can make a double polyfill, something like:

 if (Object.defineProperty) { window.weakMap = //O(1)         } else { window.weakMap = //O(n)  ,     }


Of course, the most interesting thing about this solution is how it works. The solution is so confusing that in order to understand it, I had to contact the author ( Brandon Benvie ) and ask him a few questions in order to understand the most confusing details.

I do not like to thoroughly climb into someone else's code, but this one was incredibly interesting to implement, and it turned out that it’s worth exploring, after all, Brandon (author) wrote the ES6 compiler on ES3, created app.js (platform for desktop applications on the node) and implemented a lot of different really complex solutions on JS.
Disclaimer: in most examples, the code is slightly shortened for better readability: some checks are removed, some things are inlined. I do not recommend using the code I quote here in practice, since this is all or a kind of shamanism so that the garbage collector can see that the memory can be freed, or practices that allow the code to work faster, but can easily confuse and frighten the usual average frontend developer.

Initially, it can be confusing that all methods return

 function toString() { [native code] }


No bind is done anywhere, which can transform a normal function into one.
However, everything turned out to be much simpler: the prep method, which is defined as:

 var prep = { __proto__: [] } instanceof Array ? function(f){ f.__proto__ = stringifier } : function(f){ define(f, stringifier) };


makes the object __proto__, which acts as a prototype of a specific element.
stringifier is another function:

 var stringifier = function toString(){ return src[0] + nameOf(this) + src[1]; };


It is set to itself as a toString method (as I understand it - this is done for short code). As a result, we actually get something like:

 a.__proto__ = { toString: function(){ return "function "+this.name+"() { [native code] }" } }


By the way, this particular code will not work very well due to the fact that the function name attribute is not available in all JS implementations, it is considered bad practice to use it. The function should not rely on the environment (including its name) and should work the same way in all conditions.
Just because Function.prototype.name is not in all implementations, in Brandon code the function name is defined as:

 function nameOf(func){ return 'name' in func ? func.name : toSource.call(func).match(/^\n?function\s?(\w*)?_?\(/)[1]; }


It was enough to remove define (stringifier, stringifier); so that the code would stop confusing us.

So, we need to understand where the keys are stored. To do this, we set the value, and it falls into the set function:

 function set(key, value){ unwrap(this).set(key, value); } function get(key){ return unwrap(this).get(key); }


And here the most interesting begins:

 var unwrap = function(weakMap){ return data.unlock(weakMap).value; }


data is an instance of the internal Data class, which in itself is very similar to WeakMap, but it has only two methods, get and set, while all the weakMap itself are stored in one large Data object that stores for each weakMap one data object.
We have meta-WeakMap (if you call things by their proper names), which contains all WeakMaps, each of which already contains key-value pairs for objects.

And finally, all the fun in the Data object.

First trick: we hide the value from the common set of keys so that it does not fall into any of the iterators. To do this, we reassign getOwnPropertyNames

 Object.defineProperty(Object, 'getOwnPropertyNames', { value: function getOwnPropertyNames(obj){ var props = getProps(obj); if (Object.prototype.hasOwnProperty.call(obj, globalID)) //   hasOwnProperty,       - . props.splice(props.indexOf(globalID), 1); return props; } });


As a result, even the debugger of chromium is not aware of the existence of the property:



Second trick:

 function storage(obj){ if (hasOwn.call(obj, globalID)) return obj[globalID]; //   Object.isExtensible var store = create(null); defProp(obj, globalID, { value: store }); return store; };


At the output we get a unique object with the value key.

 function Data(){ var puid = createUID(), //   16-  secret = {}; // -      WeakMap   ,             .      ,      ,     .     –   private    Data this.unlock = function(obj){ var store = storage(obj); if (hasOwn.call(store, puid)) return store[puid](secret); var data = Object.create(null, { value: { writable: true, value: undefined } }); Object.defineProperty(store, puid, { value: (function(secret,data){ return function(key){ if(key===secret) return data } })(secret, data) }); return data; } }


The first very interesting line is:

 Object.create(null, { value: { writable: true, value: undefined } });


We create an object, inheriting from null, which gives us a dummy object without any extensions, and then the second argument is passed to the propertiesObject, which allows us to define the values ​​we need via defineProperty. We explicitly create value, but pass it undefined, solely to ensure that it already exists and is subsequently tested (“value” in data).

The second insanely interesting line:

 Object.defineProperty(store, puid, { value: (function(secret,data){ return function(key){ if(key===secret) return data } })(secret, data) });


In essence, we get a function that takes as input a unique, specific dummy object, unique for each WeakMap, and returns the stored value if it corresponds to a private key.

In fact, in the original code, it is even more complicated:

 defProp(store, puid, { value: new Function('s', 'l', 'return function(k){if(k===s)return l}')(secret, data) });


Brandon commented on it like this:
Simply performance. By defining a literal function, you also have all the local variables in scope. By using `Function` the global object. The goal was to prevent inadvertently leaking memory. It would not have been possible to retain this concept.

In a free and extended translation into Russian:
This is done for performance. Creating a function through function () {}, you bind it to the local osprey - despite the fact that it does not use it in any way. If you use a debugger, you can see that the entire osp in which it was created is available from inside this function.
The new Function creates a function that works in the global osprey, which removes the binding to the local one. The task of the implementation was the absence of leaks in the memory, and all that was done there was done primarily for the absence of leaks.

As a result, in reality it looks like this in the memory:

 var map = new WeakMap; var a = {}; map.set(a, ['test']) console.log(a['2ql3g5ae6pcwstt9']['o6tnzx1xskf39pb9']) >function (k){if(k===s)return l}


where a ['2ql3g5ae6pcwstt9'] is the keystore, which is a dummy object named by a randomly generated globalID that is common to all elements that fall into some kind of weakMap, an object that stores a closure with

 { value: '' }


as a second argument. In the case of a change in the value, we replace the value, while the object remains inside the closure.

All keys are hidden in all possible ways, right up to deleting them from Object.getOwnPropertyNames, due to this we get almost non-existing keys, the existence of which within the code cannot be suspected - they are not listed in iterators and are not issued in any of requests.
As a result, we get IE9 + implementation of WeakMaps with absolutely protected (it is impossible to get access without making modifications inside the code) to open a container with contents that can be easily changed and which is always deleted along with the key, which gives us a really non-flowing WeakMap implementation O (1) complexity and non-rewritable and undeletable with Object.defineProperty with configurable attributes: false, enumerable: false, writable: false (set by default) access keys.

Of course, I don’t like the fact that an attribute for a key is still created, but I don’t know which solution could be more perfect than this. One can only admit that Brandon did a great job working with memory and made a decision that should be used in production.

I will be glad to hear in the comments ideas for what else you can use Harmony collections and WeakMap in particular, and the attitude to similar APIs in general.

UPD. Brandon explained why (0, eval) ('this') was done at the end. (0, eval) (“this”) is roughly equivalent to var e = eval; e ("this"). The fact is that eval always works in the local skop, but if you assign eval to another variable and run it, it will be executed in the global environment.

Source: https://habr.com/ru/post/200644/

More articles:


All Articles