js 内存

博客分类: 江河计划
JavaScript (120)

js 内存

JavaScript (120)

算法

背包问题 - 找出背包中装了哪些东西

    const knapsack = (weights:number[], values:number[], total:number) => {
    var n = weights.length;
    var f = [[]];
    f[-1] = new Array(total+1).fill(0);
    for(var i=0; i<n; i++){
        f[i] = new Array(total).fill(0);
        for(var j=0; j<=total; j++){
            if(j < weights[i]){
                f[i][j] = f[i-1][j];
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]);
            }
        }
    }
    console.log(f)
    var totalWeight = 0,
        j = total;
    for(var i=n;i--;){
        if(f[i][j] > f[i-1][j]){
            console.log(`选择物品：${i}；重量为：${weights[i]}；价值为：${values[i]}`);
            totalWeight += weights[i];
            j -= weights[i];
        }
    }
    console.log(`背包最大承重：${total}；实际重量：${totalWeight}；最大价值：${f[n-1][total-1]}`)
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],14)

内存

以下讨论的内存模型为 node V8 的内存模型

内存管理模型

  1. 代码区：存放即将执行的代码片段
  2. 栈：存放局部变量
  3. 堆：存放对象、闭包上下文
  4. 堆外内存：不通过 V8 分配，也不受 V8 管理的内存，Buffer 对象的数据就存放于此。

image

代码区内存回收

这部分内存几乎不回收，存储的大部分是 AST，代码通过解释器引擎解析出来的结果。

栈区内存回收

栈（Stack）的分配与回收非常直接，当程序离开某作用域后，其栈指针下移（回退），整个作用域的局部变量都会出栈，内存收回。

堆外内存回收

堆外内存由系统管理，内存回收也只收到系统级别的调度。

堆内存回收

堆区内存结构

首先 V8 引擎内存由两部分组成：新生代、老年代。

新生代：年轻的新对象，未经历垃圾回收或仅经历过一次

老年代：存活时间长的老对象，经历过一次或更多次垃圾回收的对象

两个不同的内存结构回收机制也不同，大小也不同，老年代大约是新生代的 40 倍左右。

image

新生代垃圾回收

新生代由于大部分的对象是段时间存在的，所以在 GC 时大部分的对象都会是被删除，少部分是存活的，所以在新生代采用的是复制算法，这样的话性能会更好，但是对空间的利用率更低，因为需要拿出一部分来作为复制。

Scavenge 算法将新生代的总空间一分为二，只使用其中一个，另一个处于闲置，等待垃圾回收时使用。使用中的那块空间称为 From，闲置的空间称为 To。

image

垃圾回收开始时 From 空间所有应该存活的对象都复制完成后，原本的 From 空间将被释放，成为闲置空间，原本 To 空间则成为使用中空间，两个空间进行角色翻转。

image

新生代内存晋升老年代

对象一开始进来的时候都会先进入新生代，但是由于内存有限，所有的对象不可能一直存活在新生代，所以会有对象从新生代晋升到老年代的过程。

  1. 对象此前已经经历过一次新生代垃圾回收，这次依旧应该存活，则晋升至老年代。

  2. To空间已经使用了25%，则将此对象直接晋升至老年代。

标记清除

顾名思义，标记-清除算法分为两个阶段，标记(mark)和清除(sweep)

老年代的内存回收为标记清除，想要了解老年代的回收内存，首先就会先想到如何标记哪些是会需要回收的，哪些是不需要的。

标记的方案是从根节点开始向下遍历，js 是基于原型链的，根对象就那么几个（BOM，DOM，CSSOM）是一个深度遍历的过程，所有被引用的对象存在引用关系的就是活着的对象，这个时候会记录为可达对象，就是能访问到的对象。

这个时候会对堆内存从头到尾进行线性的遍历，如果发现对象没有被标识为可达对象，就会将其回收。下图就是一个堆内存区被标记并且清除过后的内存现状，呈碎片化。

image

标记整理

上述的标记清除之后会留下一堆不连续的内存段，这些内存段不完整意味着如果有大的对象过来，发现每个小格子都放不下，但是他们把空格子合并起来是可以放下的，这就会造成空间浪费。

那就又想到一种方法，标记整理，将实体的对象都合并起来，然后放到一起，重新整理内存，合并地址，然后将大的内存块腾出来，使空间变得紧凑重新让空间利用起来。

但是标记整理会非常耗费时间，并且在整理的过程中必须是所有的运行都会停下来，等整理完成之后才会恢复，所以标记整理发生的时机就变成了，当有大对象进来已经放不下的时候。下图是整理之后的结果

image

增量标记

上述的方案能完成整个垃圾回收了，但是标记清楚是需要全停顿的，所以一旦进行 GC 的时候，浏览器就卡住了，在我们的视觉上，60 fps 左右的帧频是最接受的，所以我们采取了增量标记的方案，如果触发 GC，那我们会把每个整个 GC 分成多个步骤，每执行一个步骤，停歇一下，把内存还给浏览器，执行完浏览器的操作，GC 再进行下一个步骤。这样交替执行就提高了程序流畅性，一定程度上避免了长时间的卡顿。

内存泄露

前端的内存泄露的情况会一般发生引用计数。这也是垃圾回收的机制。但是引用计数只是标记的阶段。

引用计数是指一个值的引用次数是 0，就表示这个值将不再用到，因此可以将这块内存释放。

内存泄露发生于这个值不再需要了，但是引用计数却不为 0，垃圾回收机制并不能回收这块内存，从而导致内存泄露。

比如说 DOM：如果一个 js 对象对一个 DOM 持有引用，删除了 DOM，但是这个时候 js 对 DOM 有引用，所以 DOM 的引用计数是 1，所以内存并不会将 DOM 进行回收。

var element = document.getElementById('button');
function onClick(event) {
    element.innerHtml = 'text';
}
element.addEventListener('click', onClick);
element.removeEventListener('click', onClick);
element.parentNode.removeChild(element);

下面是几个常见的内存泄露实例：

function foo(arg) {
    bar = "this is a hidden global variable";
}

理论上讲弹栈之后，内存就会被回收的，但是由于 bar 变成了全局对象，此时内存并不会回收 bar，如果不手动清除，bar 就永远不会清楚了

var someResource = getData();
    setInterval(function() {
        var node = document.getElementById('Node');
        if(node) {
            node.innerHTML = JSON.stringify(someResource));
        }
}, 1000);

当 node DOM 节点被删掉了，但是 setInterval 会不断的执行，但是处理程序一直处于活跃，所以并不能回收 someResource 也会导致内存泄露。

var theThing = null;
var replaceThing = function () {
    var originalThing = theThing;
    var unused = function () {
        if (originalThing)
            console.log("hi");
    };
    theThing = {
        longStr: new Array(1000000).join('*'),
        someMethod: function () {
            console.log(someMessage);
        }
    };
};
setInterval(replaceThing, 1000);

闭包对于环境变量的持有，由于 unused 和 someMethod 共享了闭包上下文环境，所以两者没有都被标记为不用时，一直不会回收