Harmony collections NOW

На хабре уже проскакивала статья про такие замечательные вещи, как Map, WeakMap и Set, но в действительности реальные возможности этих API не были раскрыты (если я все-таки хорошо воспользовался поиском).
Эти API толком не реализованы нигде, кроме firefox (можно включить в chrome canary), но даже там до недавних пор не поддерживалось использование HTMLElement-подобных объектов в качестве ключей. Polymer, например, убрал только три недели назад

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

Чем же они так хороши? По сути Map/WeakMap можно воспринимать как обычные хэш-объекты, только в качестве ключей можно использовать только сложные объекты (Object, Function, Array), так как привязка идет не по содержимому, а по адресу в памяти.
Таким образом появляется возможность привязаться на фронтэнде к

• dom-элементу
• XHR-запросу
• File-элементу

Это дает нам возможность работать без id-шников элементов, делать дата-биндинг в разы быстрее, создать безумную альтернативную реализацию promises и так далее.
Мы будем говорить о WeakMap. Даже не так, мы будем говорить о существующих полифиллах для WeakMap.



Что касается остальных элементов:
Map — это хэш, ключи которого могут быть как примитивы, так и объекты.
Set — это набор уникальных элементов. Его достаточно просто можно построить поверх Map. Самое главное его преимущество — это обработка массивов, за счет его можно свести сложность задачи uniq с O(n^2) до O(n).

Про то, какие возможности работы с СУБД появляются на бэкэнде с node.js — я, пожалуй, промолчу, потому что еще недостаточно хорошо знаком с нодой, чтобы авторитетно что-либо рекомендовать.

Синтаксис чуть сложнее, чем у классического объекта, но тоже вполне понятен и читаем:

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

В нескольких проектах, в том числе в одной из прошлых версий cornerJS, такое решение было оправданным в плане краткости и читаемости кода, однако из-за того что использовался один из полифиллов, я считал это решение ощутимо отъедающим память.

Реализация ecmascript.org предлагает в качестве варианта подобную реализацию (перевел из псевдо-js в несколько сокращенный выполнимый, полная реализация на 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)
        });
    };

У такой реализации много проблем.
Во-первых, ощутимо течет память: даже когда элемент удаляется, он остается в keyList, и если такая WeakMap работает на реальном проекте, может утечь огромное количество памяти на хранение по сути уже удаленных объектов. GarbageCollector не отрабатывает по элементу, для него он считается еще существующим.
На уровне движка это можно решить, но все равно GarbageCollector в некоторых случаях будет отрабатывать некорректно.
Во-вторых, когда в keyList оказывается очень много элементов, выборка последних начинает занимать действительно много времени в chrome на macbook air 2013 поиск 1e9 -го элемента занимал больше секунды. Сложность задачи составляет O(n), что иногда ощутимо сказывается на производительности.

Есть альтернативная реализация, которая решает проблему со скоростью выборки, понижая сложность задачи до 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;
      	}
    }
}
})();

Однако проблему с памятью это не решает, а даже делает все еще хуже. Появляется цикличная ссылка в памяти у каждого элемента: key[name][0] === key. Если верить открытой документации, сборщик мусора не способен отловить такие сценарии, так что со временем память существенно забивается – правда, на это уйдет очень много времени.
Именно поэтому стоит пользоваться с осторожностью Polymer/X-tags, очень много где опирающиeся на WeakMap (выше приведена несколько сокращенная их же реализация). Так, например, на него опирается полифилл для MutationObserver, который используется не только у них, но и в большом количестве сторонних проектов, многие из которых могут и не знать о проблемах с памятью в нем.
Добавляется и еще пара минусов в сравнении с честной реализацией. Один из них для большинства окажется несущественным: мы теряем возможность привязываться к замороженным объектам. Второй для некоторых будет весьма серьезен. Эта реализация становится IE9+. Первый же вариант настолько прост, что способен работать в IE6+, если подключить Array.prototype.indexOf-полифилл (например, от Mozilla). Array.prototype.indexOf тоже появился в IE9, но его по крайней мере можно реализовать. В отличии от Object.defineProperty (строго говоря, в IE8 есть поддержка defineProperty для DOM-элементов, но на это полагаться нельзя).

В итоге, имеем либо медленную работу на больших объемах записей, либо лишнее свойство в ключевом элементе (а значит, возможно, даже доступ к нему извне), проблемы с некоторыми из итераторов, и в любом случае заполняемую дополнительными атрибутами память.

Есть еще и реализация WeakMaps в jQuery. Когда вы запрашиваете jQuery.data(element, key), вы работаете с одной из реализаций WeakMap. Она работает немного проще.
Возможно, вы когда-либо видели в коде что-то подобное:

document.body.jQuery19104357186993584037
20

Теперь вы знаете, что это id элемента в собственной WeakMap от jQuery.

Когда элемент удаляется — он удаляется, но мы по-прежнему:

• не защищены от изменений данных со стороны;
• не защищены от утечек памяти для значений — удаляются ключи, но связанные с ними значения сохраняются в памяти.

Вот тут мы и подходим к основной части.

WeakMap назвали именно так, потому что хотели реализовать weak reference — слабую связь, которая не учитывается в GC, соответственно, и ключ, и значение удаляются, когда не существует больше других записей этого ключа.
В правильной реализации должны удаляться как ключ, так и значение.
Но я даже не представлял, что это возможно, пока не наткнулся в одном из репозиториев на гитхабе в заголовке на фразу, которая не могла не удивить:

Shim for WeakMap with non-leaky O(1) lookup time

Он опирается на Object.defineProperty — что значит IE9+ и невозможность ссылаться на frozen объекты, однако новых атрибутов у элемента не было видно, что не могло не удивить.
Сам репозиторий находится тут: https://github.com/Benvie/WeakMap/
Я не удержался от того, чтобы проверить, насколько это вообще может быть правдой.

Для этого был сделан простой и быстрый тест с снапшотами памяти.

• первый снимался на пустой странице (синяя стрелка)
• второй снимался на имплементировании полифилла (желтая стрелка)
• третий снимался после создания элементов и внесения их в память (красная стрелка)
• четвертый снимался после того, как оставшиеся в памяти ссылки на элементы были удалены (зеленая стрелка)

полностью код теста

//снимается "синий" снэпшот 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

Результаты следующие:

Chrome 30 (Mac 10.9)


Firefox 24 (Mac 10.9)


IE 11 (Win 8.1)


Признаюсь честно — был в шоке, когда увидел, что вся память, которую забрало приложение, была отдана — как память для ключей, так и для значений.

После чего я решил на всякий случай убедиться в том, что время поиска реально O(1). Оказалось правдой.

Chrome 30(Mac 10.9)


Firefox 24(Mac 10.9)


В итоге, это все правда. WeakMap можно реально использовать в большом количестве проектов, он дает огромный потенциал для data-binding-а, работы со скопами, создания большого количества плагинов, и это можно делать уже сегодня, во всяком случае у нас только каждый пятый проект IE8+ и остальные IE9+. При этом WeakMap не только упрощает работу с некоторыми типами данных, но и позволяет повысить быстродействие и оптимизировать, причем в некоторых случаях значительно, работу с памятью.
Главное – выбрать правильный полифилл.

Кстати, можно сделать и двойной полифилл, что-то вроде:

if (Object.defineProperty) {
	window.weakMap = //O(1) решение без текущей памяти и с задаваемыми атрибутами
} else {
	window.weakMap = //O(n) правильное решение, но с текущей памятью
}

Конечно, самое интересное в этом решении то, как оно работает. Решение настолько запутанное, что для того, чтобы понять его, пришлось связаться с автором (Brandon Benvie) и задать ему несколько вопросов, чтобы понять наиболее запутанные детали.

Я не люблю досконально лезть в чужой код, но этот был безумно интересен в реализации, и оказалось, что изучить его стоит, все-таки Брэндон (автор) написал компилятор ES6 на ES3, создал app.js (платформа для десктопных приложений на ноде) и реализовал еще много разных действительно сложных решений на JS.

Дисклеймер: в большинстве примеров код немного сокращен для лучшей читаемости: убраны некоторые проверки, часть вещей заинлайнена. Код, который я цитирую тут, не рекомендую использовать на практике, так как это все либо своего рода шаманство для того, чтобы garbage collector увидел, что память можно освобождать, либо практики, которые позволяют коду работать быстрее, но могут легко запутать и напугать обычного среднестатистического фронтэнд-разработчика.

Вначале может смутить то, что все методы возвращают

function toString() { [native code] }

При этом нигде не делается bind, который может превращать обычную функцию в такую.
Однако все оказалось куда проще: метод prep, который задается так:

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

делает объект __proto__, который выступает прототипом конкретного элемента.
stringifier — это другая функция:

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

Она задается самой себе в качестве метода toString (как я понял — это делается для краткости кода). В итоге, мы получаем на самом деле что-то вроде:

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

Кстати, конкретно этот код будет работать не особо хорошо в силу того, что атрибут name функции доступен не во всех имплементациях JS, считается плохой практикой использовать ее. Функция не должна опираться на окружение (и в том числе ее название) и должна отрабатывать в любых условиях одинаково.
Именно потому что Function.prototype.name есть не во всех реализациях, в коде Брэндона имя функции определяется так:

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

Достаточно было убрать define(stringifier, stringifier);, чтобы код перестал нас смущать.

Итак, нам нужно понять, где же хранятся ключи. Для этого мы задаем значение, и оно попадает в функцию set:

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

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

И тут начинается самое интересное:

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

data — это экземпляр внутреннего класса Data, который сам по себе очень похож на WeakMap, но у него есть всего два метода, get и set, при этом все weakMap сами по себе хранятся в одном большом Data-объекте, который хранит для каждой weakMap еще один Data-объект.
Мы имеем мета-WeakMap(если называть вещи своими именами), хранящий в себе все WeakMap-ы, каждая из которых уже содержит пары ключ-значение для объектов.

И, наконец, все самое интересное в объекте Data.

Первый трюк: прячем значение из общего множества ключей, чтобы оно не попадало ни в один из итераторов. Для этого мы переназначаем 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;
	}
});

В итоге о существовании свойства не подозревает даже дебаггер хрома:



Второй трюк:

function storage(obj){
	if (hasOwn.call(obj, globalID))
		return obj[globalID];
//опущена проверка на Object.isExtensible
	var store = create(null);
	defProp(obj, globalID, { value: store });
		return store;
};

На выходе мы получаем уникальный объект с ключом value.

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;
  }
}

Первая очень интересная строчка, это:

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

Мы создаем объект, наследуясь от null, что дает нам объект-пустышку без каких-либо расширений, и тут же вторым аргументом передаем propertiesObject, который позволяет задать через defineProperty нужные нам значения. Мы явно создаем value, но передаем ему undefined, исключительно для того, чтобы оно уже существовало и в дальнейшем проходило проверку («value» in data).

Вторая безумно интересная строка:

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

По сути, мы получаем функцию, которая принимает на вход уникальный серкретный объект-пустышку, уникальный для каждого WeakMap, и возвращает хранящееся значение, если оно соответствует секретному ключу.

На самом деле, в изначальном коде она выполнена еще более запутанно:

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

Брэндон прокомментировал это так:

Simply performance. By defining a literal function, you also entrain all the local variables in scope. By using `Function` the only thing in scope is the global object. The goal was to prevent inadvertently leaking memory. Your version would probably work fine as well, but there's the potential to leak references that wouldn't otherwise be retained, and much of the goal of using a WeakMap is to prevent this kind of leakage.

В вольном и расширенном переводе на русский:

Это сделано для производительности. Создавая функцию через function(){}, ты привязываешься в ней к локальному скопу — несмотря на то, что она его никак не задействует. Если использовать дебаггер — можно увидеть, что изнутри этой функции доступен весь тот скоп, в котором она создавалась.
new Function создает функцию, которая работает в глобальном скопе, что убирает привязку к локальному. Задачей реализации было отсутствие утечек в памяти, и все что там понакодено — сделано в первую очередь для отсутствия утечек.

В итоге, в реальности это выглядит в памяти как-то так:

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

где a['2ql3g5ae6pcwstt9'] — хранилище ключей, представляющее из себя объект-пустышку, с именем из случайно сгенерированного globalID, общего для всех элементов, попавших в какой-либо weakMap, а a['2ql3g5ae6pcwstt9']['o6tnzx1xskf39pb9'] — объект, который хранит в себе замыкание с

{
	value: 'содержимое'
}

в качестве второго аргумента. В случае смены значения — мы заменяем value, при этом объект остается по-прежнему внутри замыкания.

Все ключи являются скрытыми во всех возможных смыслах, вплоть до удаления их из Object.getOwnPropertyNames, за счет этого мы получаем почти-не-существующие ключи, о существовании которых внутри кода невозможно заподозрить — они не перечисляются в итераторах и не выдаются ни в одном из запросов.
В результате мы получаем IE9+ реализацию WeakMaps с абсолютно защищенными (получить доступ без внесения модификаций внутри кода невозможно) ключами для открытия контейнера с содержимым, которое может быть легко изменено, и которое всегда удаляется вместе с ключом, что дает нам действительно не протекающую реализацию WeakMap с сложностью O(1) и неперезаписываемыми и неудаляемыми за счет Object.defineProperty с атрибутами configurable: false, enumerable: false, writable: false(выставляются по умолчанию) ключами доступа.

Мне, конечно, не нравится то что все-таки создается атрибут для ключа, но не знаю, какое решение могло бы быть более идеальным, чем это. Остается только признать, что Брэндон провел огромную работу по работе с памятью и сделал решение, которое стоит использовать в продакшне.

Рад буду услышать в комментариях идеи о том, для чего еще можно использовать Harmony collections и WeakMap в частности, и отношение к подобным API в целом.

UPD. Брэндон объяснил, зачем сделано (0, eval)('this') в конце. (0,eval)(«this») примерно эквивалентно var e = eval; e(«this»). Дело в том, что eval всегда работает в локальном скопе, однако если присвоить eval другой переменной и запустить ее — он будет выполняться в глобальном окружении.