摘要:双向链表的具体实现便在中可以看到,都是些修改链表中指针的操作,都十分高效。如此一来,既做到了定时器的复用优化,又对链表结构进行了扬长避短。
在 Node.js 中,许许多多的异步操作,都需要来一个兜底的超时,这时,就轮到 timer 登场了。由于需要使用它的地方是那么的多,而且都是基础的功能模块,所以,对于它性能的要求,自然是十分高的。总结来说,要求有:
更快的添加操作。
更快的移除操作。
更快的超时触发。
接下来就让我们跟着 Node.js 项目中的 lib/timer.js 和 lib/internal/linklist.js 来探究它具体的实现。
更快的添加 / 移除操作说到添加和移除都十分高效的数据结构,第一个映入脑帘的,自然就是链表啦。是的,Node.js 就是使用了双向链表,来将 timer 的插入和移除操作的时间复杂度都降至 O(1) 。双向链表的具体实现便在 lib/internal/linklist.js 中:
// lib/internal/linklist.js "use strict"; function init(list) { list._idleNext = list; list._idlePrev = list; } exports.init = init; function peek(list) { if (list._idlePrev == list) return null; return list._idlePrev; } exports.peek = peek; function shift(list) { var first = list._idlePrev; remove(first); return first; } exports.shift = shift; function remove(item) { if (item._idleNext) { item._idleNext._idlePrev = item._idlePrev; } if (item._idlePrev) { item._idlePrev._idleNext = item._idleNext; } item._idleNext = null; item._idlePrev = null; } exports.remove = remove; function append(list, item) { remove(item); item._idleNext = list._idleNext; list._idleNext._idlePrev = item; item._idlePrev = list; list._idleNext = item; } exports.append = append; function isEmpty(list) { return list._idleNext === list; } exports.isEmpty = isEmpty;
可以看到,都是些修改链表中指针的操作,都十分高效。
更快的超时触发链表的缺点,自然是它的查找时间,对于一个无序的链表来说,查找时间需要 O(n) ,但是,只要基于一个大前提,那么我们的实现就并不需要使用到链表的查询,这也是更高效的超时触发的基础所在,那就是,对于同一延迟的 timers ,后添加的一定比先添加的晚触发。所以,源码的具体做法就是,对于同一延迟的所有 timers ,全部都维护在同一个双向链表中,后来的,就不断往链表末尾追加,并且这条链表实际上共享同一个定时器 。这个定时器会在当次超时触发时,动态计算下一次的触发时间点。所有的链表,都保存在一个对象 map 中。如此一来,既做到了定时器的复用优化,又对链表结构进行了扬长避短。
让我们先以 setTimeout 为例看看具体代码,首先是插入:
// lib/timer.js // ... const refedLists = {}; const unrefedLists = {}; exports.setTimeout = function(callback, after) { // ... var timer = new Timeout(after); var length = arguments.length; var ontimeout = callback; // ... timer._onTimeout = ontimeout; active(timer); return timer; }; const active = exports.active = function(item) { insert(item, false); }; function insert(item, unrefed) { const msecs = item._idleTimeout; if (msecs < 0 || msecs === undefined) return; item._idleStart = TimerWrap.now(); var list = lists[msecs]; if (!list) { // ... list = new TimersList(msecs, unrefed); L.init(list); list._timer._list = list; if (unrefed === true) list._timer.unref(); list._timer.start(msecs, 0); lists[msecs] = list; list._timer[kOnTimeout] = listOnTimeout; } L.append(list, item); assert(!L.isEmpty(list)); }
即检查当前在对象 map 中,是否存在该超时时间(msecs)的双向链表,若无,则新建一条。你应该已经看出,超时触发时具体的处理逻辑,就在 listOnTimeout 函数中:
// lib/timer.js // ... function listOnTimeout() { var list = this._list; var msecs = list.msecs; var now = TimerWrap.now(); var diff, timer; while (timer = L.peek(list)) { diff = now - timer._idleStart; if (diff < msecs) { this.start(msecs - diff, 0); return; } L.remove(timer); // ... tryOnTimeout(timer, list); // ... } this.close(); // ... }
即不断从链表头取出封装好的包含了注册时间点和处理函数的对象,然后挨个执行,直到计算出的超时时间点已经超过当前时间点。
举个图例,在时间点 10,100,400 时分别注册了三个超时时间为 1000 的 timer,在时间点 300 注册了一个超时时间为 3000 的 timer,即在时间点 500 时,对象 map 的结构即为:
随后在时间点 1200 触发了超时事件,并在时间点 1300 执行完毕,彼时对象 map 的结构即为:
setInterval 和 setImmediatesetInterval 的实现总体和 setTimeout 很相似,区别在于对注册的回调函数进行了封装,在链表的尾部重新插入:
// lib/timer.js // ... function wrapper() { timer._repeat(); // 执行传入的回调函数 if (!timer._repeat) return; // ... timer._idleTimeout = repeat; active(timer); }
而 setImmediate 和 setTimeout 实现上的主要区别则在于,它会一次性将链表中注册的,都执行完:
// lib/timer.js // ... function processImmediate() { var queue = immediateQueue; var domain, immediate; immediateQueue = {}; L.init(immediateQueue); while (L.isEmpty(queue) === false) { immediate = L.shift(queue); // ... tryOnImmediate(immediate, queue); // ... } if (L.isEmpty(immediateQueue)) { process._needImmediateCallback = false; } }
所以作为功能类似的 process.nextTick 和 setImmediate ,在功能层面上看,每次事件循环,它们都会将存储的回调都执行完,但 process.nextTick 中的存储的回调,会先于 setImmediate 中的执行:
"use strict" const print = (i) => () => console.log(i) process.nextTick(print(1)) process.nextTick(print(2)) setImmediate(() => { print(3)() setImmediate(print(6)) process.nextTick(print(5)) }) setImmediate(print(4)) console.log("发车") // 发车 // 1 // 2 // 3 // 4 // 5 // 6最后
参考:
https://github.com/nodejs/node/blob/master/lib/timers.js
https://github.com/nodejs/node/blob/master/lib/internal/linkedlist.js
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/87765.html
摘要:关于定时器的源码在文件中,进入就关于定时器的一些设计解释,因为是做服务端代码,在内部等大部分事件都会创建一个定时器,任何时间都可能存在大量的定时器任务,所以设计一个高效的定时器是很有必要的。 博客文章地址 setTimeout与setInterval setTimeout 和 setInterval 是我们在 javaScript 中经常用到的定时器,setTimeout 方法用于...
摘要:注很多以前的源码分析文章中,所写的第一个执行的文件代码为,但这个文件在中已被移除,并被拆解为了等其他下的文件,为正文作为第一段被执行的代码,它的历史使命免不了就是进行一些环境和全局变量的初始化工作。 大家可能会好奇,在 Node.js 启动后,第一个执行的 JavaScript 文件会是哪个?它具体又会干些什么事? 一步步来看,翻开 Node.js 的源码,不难看出,入口文件在 src...
摘要:事件触发线程主要负责将准备好的事件交给引擎线程执行。它将不同的任务分配给不同的线程,形成一个事件循环,以异步的方式将任务的执行结果返回给引擎。 Fundebug经作者浪里行舟授权首发,未经同意请勿转载。 前言 本文我们将会介绍 JS 实现异步的原理,并且了解了在浏览器和 Node 中 Event Loop 其实是不相同的。 一、线程与进程 1. 概念 我们经常说 JS 是单线程执行的,...
摘要:通过查看的文档可以发现整个分为个阶段定时器相关任务,中我们关注的是它会执行和中到期的回调执行某些系统操作的回调内部使用执行,一定条件下会在这个阶段阻塞住执行的回调如果或者关闭了,就会在这个阶段触发事件,执行事件的回调的代码在文件中。 showImg(https://segmentfault.com/img/bVbd7B7?w=1227&h=644); 这次我们就不要那么多前戏,直奔主题...
摘要:异步在中,是在单线程中执行的没错,但是内部完成工作的另有线程池,使用一个主进程和多个线程来模拟异步。在事件循环中,观察者会不断的找到线程池中已经完成的请求对象,从中取出回调函数和数据并执行。 1. 介绍 单线程编程会因阻塞I/O导致硬件资源得不到更优的使用。多线程编程也因为编程中的死锁、状态同步等问题让开发人员头痛。Node在两者之间给出了它的解决方案:利用单线程,远离多线程死锁、状态...
阅读 3681·2021-11-11 11:00
阅读 2112·2021-10-08 10:05
阅读 2613·2021-10-08 10:04
阅读 3177·2021-09-30 09:48
阅读 3724·2021-09-27 14:10
阅读 1652·2021-09-09 09:33
阅读 2069·2019-08-30 15:55
阅读 1585·2019-08-30 13:53