sl1673495 commented 4 years ago

Fiber

出现背景

JavaScript 是单线程运行的，而且在浏览器环境屁事非常多，它要负责页面的JS解析和执行、绘制、事件处理、静态资源加载和处理, 这些任务可以类比上面’进程‘。

对于 Vue 来说，

模板的静态可优化特性
响应式底层机制带来的组件的精确更新使得他可以把每个任务尽可能的压缩小，这也是尤大觉得Vue3不需要时间分片的原因。

这是React V15 下面的一个列表渲染资源消耗情况。整个渲染花费了130ms, 🔴在这里面 React 会递归比对VirtualDOM树，找出需要变动的节点，然后同步更新它们, 一气呵成。这个过程 React 称为 Reconcilation(中文可以译为协调)。在 Reconcilation 期间，React 会霸占着浏览器资源，一则会导致用户触发的事件得不到响应, 二则会导致掉帧，用户可以感知到这些卡顿。

所以 React 通过Fiber 架构，让自己的Reconcilation 过程变成可被中断。 '适时'地让出CPU执行权，除了可以让浏览器及时地响应用户的交互。

Fiber 的做法

Fiber 和浏览器之间配合调度，属于 合作式调度(Cooperative Scheduling)，并没有人有权利抢占，而是 Fiber 主动向浏览器申请空闲时间的时间片 requestIdleCallback，然后 Fiber 自己查询剩余时间是否充足，不足的话再把执行权交回给浏览器。

window.requestIdleCallback(
  callback: (dealine: IdleDeadline) => void,
  option?: {timeout: number}
)

interface IdleDealine {
  didTimeout: boolean // 表示任务执行是否超过约定时间
  timeRemaining(): DOMHighResTimeStamp // 任务可供执行的剩余时间
}

浏览器每一帧会做什么事情：

处理用户输入事件
Javascript执行
requestAnimation 调用
布局 Layout
绘制 Paint

如果浏览器处理完上述的任务(布局和绘制之后)，还有盈余时间，浏览器就会调用 requestIdleCallback 的回调。

但是在浏览器繁忙的时候，可能不会有盈余时间，这时候requestIdleCallback回调可能就不会被执行。为了避免饿死，可以通过requestIdleCallback的第二个参数指定一个超时时间。

sl1673495 commented 4 years ago

fps算法：

function fps() {
  return new Promise(resolve => {
    requestAnimationFrame(rAFTime => {
      requestAnimationFrame(nextRAFTime => {
        resolve(1000 / (nextRAFTime - rAFTime));
      });
    });
  });
}

sl1673495 commented 4 years ago

观察performence面板可以发现，postMessage确实是在下一个task的开始执行。

requestAnimationFrame 是在这一帧结束之前调用回调函数，此后会经历 Recalculate Style、Update Layer Tree、Paint重绘、Composite Layers合成层

虽然 HTML 规范文档中说 task 之间会经历浏览器的渲染，但是一帧之间是允许存在多个 task 的。

嵌套的setTimeout 并不一定能保证两个 task 分别经历自己的渲染轮次（chrome）中，可能会对其进行合并优化。

嵌套 postMessage 也一样不能保证，而且经过测验发现还会随机的把一个帧卡成上百毫秒。

所以如果要写动画还是要requestAnimationFrame比较靠谱。它一定会保证每一个rAF的回调都能经历一次渲染。

no:

setTimeout(() => {
  document.body.style.background = 'red'
  setTimeout(() => {
    document.body.style.background = 'yellow'
  });
});

good:

requestAnimationFrame(() => {
  document.body.style.background = 'red'
  requestAnimationFrame(() => {
    document.body.style.background = 'yellow'
  });
});

sl1673495 commented 4 years ago

岛屿问题

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    let count = 0
    for (let i = 0; i < grid.length; i++) {
        let row = grid[i]
        for (let j = 0; j < row.length; j++) {
            if (row[j] === '1') {
                dfs(grid, i, j)
                count++
            }
        }
    }
    return count
};

function dfs(grid, i, j) {
    let point = grid[i] && grid[i][j]
    if (point === '0' || point === undefined) {
        return
    }
    grid[i][j] = '0'

    dfs(grid, i - 1, j) // 上
    dfs(grid, i + 1, j) // 下
    dfs(grid, i, j - 1) // 左
    dfs(grid, i, j + 1) // 右
}

分析

很经典的 dfs 问题，很棒很棒的思路，当找到一个点为1的时候，先记录数量加一。

然后对于每个点递归的去遍历自己和上下左右的节点，如果值为1就置为0再继续遍历上下左右，这样直到遇到某一边本身就为0的时候停止。

这样，一片 “值为1的岛屿” 就全部归零了。

sl1673495 / daily-plan

2020-04-15日计划：Fiber、requestIdleCallback、岛屿问题 #9

Fiber

出现背景

Fiber 的做法

分析