Immutable源码解析与性能优化

摘要：修改的节点和该父级链路上都变成新的对象显然是最优方案。如果你对比的两个中，一个被过，另一个数据又是由其衍生出来的，那效率将是最高的算法的原理与优化检测本地中是否存在已过当前对象字符串。

1.不可变,一成不变的

2.对immutable数据的每次修改操作都会返回一个新的data

掏出一副老生常谈的图

1.历史回退（同时不浪费内存），时间旅行之类的easy！

2.函数式编程

3.降低代码的复杂度

List: 类Array

Map：类Object/Map

Set：类Set

OrderMap/Set：有序Map/Set

....还有些不常用的数据类型

对传入对象或数组进行deepImmutable,array转成List,Object转成Map

const a = Immutable.fromJS({a:1,b:2})

console.log(a)    //Map {size: 2, _root: ArrayMapNode, __ownerID: undefined, __hash: 1014196085, __altered: false}

//定制化fromJS，根据key索引和value决定你想将他浅immutable还是深immutable，或者转换成其他immutable类型
const b = Immutable.fromJS({a:["a","b"],b:2},(key,value)=>{

    const isIndexed = Immutable.Iterable.isIndexed(value);
    return isIndexed ? value.toList() : value.toOrderedMap();

})

a.toJS() // {a:1,b:2}

语法上同时兼容了ES6 Map，支持[key,value]形式传入

const MapA = Immutable.Map([["a",1],["b","2"]])

const MapB = Immutable,Map({a:1})

console.log(MapA.toJS(),MapB.toJS()) // {a:1,b:2} {a:1}
  

const ListA = Immutable.List([["a",1],["b","2"]])

ListA.toJS() // [["a",1],["b","2"]]

  

获取大小

const ListA = Immutable.List([["a",1],["b","2"]])

const MapA = Immutable.Map({a:{a:1}})

ListA.size // 2

MapA.size // 1

  

使用方式：get(key:any, notSetValue) / getIn(keyPath:array,notSeValue)

const obj = Immutable.fromJS({a:{a:8}})

console.log(obj.get("a"),obj.getIn(["a","a"])) //Map.... 8

console.log(obj.get("b","joker"),obj.getIn(["b","b","b"],"joker")) //joker joker

const array = Immutable.fromJS([{a:1},"2"])

array.get(0).toJS() // {a:1}

array.getIn([0,"a"]) // 1

从此优雅写代码

以前的我们
if(a && a.data && a.data.productList && a.data.productList.length > 0) 

现在的我们
$immutable.getIn(["data","productList"],List()).size > 0

immutable除了对嵌套形式的数据进行分离外，对于同一层级的数据也进行了分割，见下文_tail+__root区间存储

const ListA = Immutable.from({a:{a:1}})

const ListB = ListA.set("a",{o:77}) // {a:{o:77}}

ListB === ListA // false

ListA.setIn(["a","a"],"7777") // {a:{a:777}}

set/setIn是我们最常用的api,其内部实现和update/updateIn一样。也是immutable之所以immutable的核心所在

在文章刚开始提到的immutable原理图中，为什么immutable在改变一个节点后，该父节点的链路上都变成了新的节点，一方面和实际需要有关，一方面也与set方法的实现有关。

从实际需要的角度，数据如果想immutable化，即前后完全是两个对象，同时为了避免deepClone的性能问题，达到不变数据内存的尽可能复用。修改的节点和该父级链路上都变成新的对象显然是最优方案。

从实现角度来说，我们修改一个层级很深的节点，一般会调用immutable提供的setIn(["a","a"],xx)/update(["a","a"],xxx)这样的方法。

实际immutable的整个一套修改流程是这样的

假设我们操作的数据是{a:{a:1}} 执行 setIn(["a","a"],"XXX")操作

["a","a"]这是一个keyPath,immutable会按照顺序一层层往里找 找到指定节点那块的时候，开始修改值 得到一个修改完的{a:xxx}后，再原路向上set每一级，会先将每一级浅拷贝一遍，然后更新浅拷贝后的对象，将修改完的再吐给上一层，重复这样的操作，最后返回了一个新的immutable对象

// 因为obj在immutable里的存储格式也是数组类型（类Map）,所以也可以使用arrCopy
function arrCopy(arr, offset) {
  offset = offset || 0;
  var len = Math.max(0, arr.length - offset);
  var newArr = new Array(len);
  for (var ii = 0; ii < len; ii++) {
    newArr[ii] = arr[ii + offset];
  }
  return newArr;
}

// 实际的更新逻辑
function updateInDeeply(
  inImmutable,
  existing,
  keyPath,
  i,
  notSetValue,
  updater
) {
  const wasNotSet = existing === NOT_SET;
  if (i === keyPath.length) {        //根据传进的keyPath进行迭代
    const existingValue = wasNotSet ? notSetValue : existing;
    const newValue = updater(existingValue); 
    return newValue === existingValue ? existing : newValue;
  }
  if (!wasNotSet && !isDataStructure(existing)) {
    throw new TypeError(
      "Cannot update within non-data-structure value in path [" +
        keyPath.slice(0, i).map(quoteString) +
        "]: " +
        existing
    );
  }
  const key = keyPath[i];
  const nextExisting = wasNotSet ? NOT_SET : get(existing, key, NOT_SET);    //get到每一层的Data
  const nextUpdated = updateInDeeply(
    nextExisting === NOT_SET ? inImmutable : isImmutable(nextExisting),
    nextExisting,
    keyPath,
    i + 1,
    notSetValue,
    updater
  );
  return nextUpdated === nextExisting
    ? existing
    : nextUpdated === NOT_SET
      ? remove(existing, key)
      : set(        //最核心的地方 将change后的结果set到每一层
          wasNotSet ? (inImmutable ? emptyMap() : {}) : existing,
          key,
          nextUpdated
        );
}

对对象进行merge，支持传入immutable对象和普通对象

const objA = Immutable.fromJS({a:1,b:{a:2}})

const objB = Immutable.fromJS({a:3,b:{h:2}})

objA.merge({a:3,b:{h:2}}) // {a:3,b:{h:2}}

objA.merge(objB) // {a:3,b:{h:2}}

objA.mergeDeep({a:3,b:{h:2}}) // {a:3,b:{a:2,h:2}}


// 通常我们reducer中对于action，state处理都会这样

 return {
     ...state,
     ...action.payload
 }

// 现在我们可以这么写
 return state.merge(action.payload)

对两个immutable对象进行diff

const immutableA = Immutable.fromJS({a:{a:1}})

const immutableB = immutableA.fromJS({a:{a:1}})

immutableA === immutableB // false

is(immutableA, immutableB) //true

is不支持浅immutable Data的对比，不支持普通对象的对比

1.List:pop,push,shift,unshift,slice,forEach,Map,filter

与原生用法几乎一致，但是有两点需要注意：所有修改型操作必定返回一个新的Data。foreach是返回迭代数

Immutable.fromJS([1, 2, 3, 4, 5, {a: 123}]).forEach((value, index, array)=>{
    return value < 5;
}); // 5

2.Map:同时也支持forEach之类的遍历，因为其存储方式以Array存储。特有方法的话mapKeys/mapEntries

常用api其实不想多说，网上有大把的资源 百度 必应 谷歌

将immutable对象hash化，在其属性_hash上挂载，

const obj1 = immutable.fromJS({a:{a:1}})
const obj2 = immutable.Map({a:{a:1}})

Immutable.hash(obj1)

Immutable.hash(obj2)

obj1.__hash === obj2.__hash // false 具体原理见下文Hash原理剖析

const ListA = Immutable.List(["a","b"])

ListA.push("gg")
    .pop()
    .shift()

按照immutable每个操作必定返回新的对象的这种说法，上述代码产生了很多冗余的List,而针对这点immutable给出了两种解决方案

//withMutation
const ListA = Immutable.List(["a","b"])

const ListB = ListA.withMutations(($list)=>{
    $list.push("gg")
        .pop()
        .shift()
})

//asMutable/asImutable
const ListA = Immutable.List(["a","b"])
const ListB = ListA.asMutable()

console.log(ListA === ListB,Immutable.is(ListA,ListB)) // false true

const ListC = ListB.pop()

console.log(ListB,ListC === ListB,Immutable.is(ListC,ListB)) // ["a"] true true

const ListFinally = ListC.asImmutable()    //asMutable/asImutable必须同时成对出现

而immutable是怎么实现这个的呢？？

仔细观察immutable对象，嗯，你会发现有个__ownerID,嗯，然后呢，就没有然后了。。。然后你就要看源码了

//asMutable源码
function asMutable() {
  return this.__ownerID ? this : this.__ensureOwner(new OwnerID());
}

//当我们修改节点时都会类似触发一个editableVNode这样的函数
function editableVNode(node, ownerID) {
  if (ownerID && node && ownerID === node.ownerID) {
    return node;
  }
  return new VNode(node ? node.array.slice() : [], ownerID); //
}

通过实例函数的方式获得唯一ID，这点还是很细腻的

如果说immutable他要转换一个length 1000的array，他会怎么做呢，存储上他会将1000按length32为单位进行存储，放置在_root中，剩下的扔进_tail。同理，immutable在进行get/set操作时，扔进去一个索引100，首先做的事是，确认这个100在那个索引区，然后再去那个32的array中拿数据。

// List.set
let newTail = list._tail;
  let newRoot = list._root;
  const didAlter = MakeRef(DID_ALTER);
  if (index >= getTailOffset(list._capacity)) {
    newTail = updateVNode(newTail, list.__ownerID, 0, index, value, didAlter);
  } else {
    newRoot = updateVNode(
      newRoot,
      list.__ownerID,
      list._level,
      index,
      value,
      didAlter
    );
  }


以32位划分存储分区
const SHIFT = 5;
const SIZE = 1 << SHIFT;
function getTailOffset(size) {
  return size < SIZE ? 0 : ((size - 1) >>> 5) << 5;
}

is其实就是immutable中Map/List对象的deepDiff，而实际真正的diff过程就是hash与漫长的迭代diff。如果你对比的两个immutable中，一个data被hash过，另一个数据又是由其衍生出来的，那diff效率将是最高的

1.检测本地weakMap/stringHashCache中是否存在已hash过当前对象/字符串。

一方面通过WeakMap的弱引用，让这些作为key的obj可以被gc，另一方面对于数据的hash过程只会是越来越快

2.对于immutable Data的特殊对象如何Hash？如DOMElement，非immutable Obj
对于DOMElement

首先检测是否为IE 低版本 IE对于每一个DOM都赋予了唯一的node.uniqueID

function getIENodeHash(node) {
  if (node && node.nodeType > 0) {
    switch (node.nodeType) {
      case 1: // Element
        return node.uniqueID;
      case 9: // Document
        return node.documentElement && node.documentElement.uniqueID;
    }
  }
}

若为非IE

手动维护一个递增的hashWeakMap，Symbol私有化后放在prototype中

let UID_HASH_KEY = "__immutablehash__";
if (typeof Symbol === "function") {
  UID_HASH_KEY = Symbol(UID_HASH_KEY);
}
hashed = ++objHashUID;
if (objHashUID & 0x40000000) {
    objHashUID = 0;
}
Object.defineProperty(obj, UID_HASH_KEY, {
  enumerable: false,
  configurable: false,
  writable: false,
  value: hashed,
});

对于非immutable Data（Map浅immutable后里的深层嵌套数据）

代码同上，维护一个WeakMap，key是obj，Value是递增的objHashUID

3.Hash冲突？merge KeyHash+ValueHash

对于纯数组，immutable的hash方案是hash所有索引下的value然后进行叠加

对于object，immutable对每一个object单元以Hash(key)+Hash(value)最后进行叠加

function hashCollection(collection) {
  if (collection.size === Infinity) {
    return 0;
  }
  const ordered = isOrdered(collection);
  const keyed = isKeyed(collection);
  let h = ordered ? 1 : 0;
  const size = collection.__iterate(
    keyed
      ? ordered
        ? (v, k) => {
            h = (31 * h + hashMerge(hash(v), hash(k))) | 0;
          }
        : (v, k) => {
            h = (h + hashMerge(hash(v), hash(k))) | 0;
          }
      : ordered
        ? v => {
            h = (31 * h + hash(v)) | 0;
          }
        : v => {
            h = (h + hash(v)) | 0;
          }
  );
  return murmurHashOfSize(size, h);
}

使用技巧

1.尽早提前hash的时间点，在一些ajax请求，launch加载的时候，这样在进行长列表render的时候可以很大程度上优化性能，同时安利一波biz-decorator，集成autobind，debounce，throttle，pureRender装饰器

2.如果想用hash去做diff，要仔细考虑immutable是否Deep

Deep&Hash immutable时间长 初始hash时间长 diff速度快(与层次有关)

!Deep&Hash immutable时间短 初始hash时间短 diff速度快

!Deep&!Hash immutable时间短 无hash时间 diff速度快

结论：

Deep&Hash 耗时长，但是可以给hashMap提供更多的hash样本，前提是这个数据样本会频繁被用到

diff时无需对元数据衍生出来的数据hash化，并不会优化diff时间

//我们对一个5MB的商品数据进行immutable

const Map = Immutable.Map(MockData) // 3.489013671875ms
Immutable.hash(Map)    // 1.677001953125ms

const fromJS = Immutable.fromJS(MockData) // 962.42724609375ms
Immutable.hash(fromJS)    // 306.51318359375ms

const Map2 = Map.setIn(["data","data",10,"state"],"5");

Immutable.is(Map2,Map) //3.2197265625ms

const fromJS2 = fromJS.setIn(["data","data",10,"state"],"5");

Immutable.is(fromJS2,fromJS) //10.624267578125ms

//相比之前fromJS的Immutable hash 时间成本节省了一个数量级
Immutable.hash(fromJS2); //16.772216796875ms

//diff时间上并没有显著的提升
Immutable.is(fromJS2,fromJS) //7.08203125ms

1.请求或存入LS时都需要转成通用对象，但是仍然可以使用JSON.stringify，也可以toJS()

2.语法上基本兼容以前api（类ES6 Map/Set），但是写法上有很大转变（建议新项目或外部依赖较少的项目切immutable）

3.提供api较为基础，或达不到使用目的，可以在原有基础上扩展

4.基本常用类型多为Map，List，可对immutable针对性的阉割，或者自行实行一套