JS 数组操作之源码分析

2018/4/17 晴天

想单独拿一篇博客来记录是因为，在我想要了解一些方法操作的效率或性能怎么样时，网上资料很少，所以专门去查看了一下源码，特写此文。希望能帮助到和我一样有疑惑的前端小盆友。

下面进入正题：

1 JS Array的特点

  • 既可以当作一个普通的数组来使用，即通过下标找到数组的元素，比如：
var array = [19,50,99];
console.log(array[0]);

  • 也可以当作一个栈来使用，并且继承栈的特点，先进后出，push和pop。

  • 还可以当作一个哈希表来使用
    例如：

var map = [];
map["id"] = 1234;
map["name"] = yin;
console.log(map["name"]);

2 JS Array的实现

源码里说：JSArray有两种模式，一种是快速的，一种是慢速的，快速的用的是索引直接定位，慢速的使用哈希查找。快速和慢速的讲解见传送门。

3 Push和扩容

  • 初始化：举个例子，数组初始化大小为4
//number of element slots to pre-allocate for an empty array
static const int kPreallocatedArrayElements = 4;
  • push操作：执行push的时候会在数组的末尾添加新的元素，而一旦空间不足时，将进行扩容。
    push过程
    源码里面push是用汇编实现的，在c++里面嵌入的汇编，这个应该是考虑到push是一个最常用的操作，所以用汇编实现提高执行速度，在汇编的上面封装了一层用C++封装的函数，在编译组装的时候，将把这些C++代码转成汇编代码。

扩容后，计算新容量的函数：

Node *code StubAssemBler::CalculateNewElementsCapacity(Node *old_capacity,ParameterMode mode){
Node *half_old_capacity = WordOrSmiShr(old_capacity,old_capacity,mode);
Node *new_capacity = IntPtrOrSmiAdd(half_old_capacity,old_capacity,mode);
Node *padding = IntPtrOrSmiConstant(16,mode);
return IntPtrOrSmiAdd(new _capacity,padding,mode);
}

如上代码新容量等于：

new _capacity = old_capacity/2 + old_capacity + 16;

即旧容量的1.5倍加上16。初始化是4个，当push第五个时，容量会变成 4/2+4+16=22

push过程

  • 申请内存：申请一块刚刚计算出来的大小的内存，把旧的数据拷过去
Node* CodeStubAssembler::GrowElementsCapacity(
Node *object,Node *element,Node *capacity,Node *new_capacity){
Node *new_elements = AllocateFixedArray(new_capacity,mode);
CopyFixedArrayElements(elements,new_elements,capacity,new_capacity);
return new_elements;
}
  • 复制内容
    由于复制是用的memcopy，把整一段内存空间拷贝过去，所以这个操作还是比较快的。
    再把新元素放到当前length的位置，再把length++

4 Pop和减容

pop的逻辑使用c++写的，在执行pop的时候，第一步，获取到当前的length，用这个length-1得到要删除的元素，然后调用setLength调整容量，最后返回删除的元素。

int new_length = length - 1;
int remove_index = remove_position == AT_START?0:new_length;
Handle<Object> result = Subclass::GetImpl(isolate,*backing_store,remove_index);
Subclass::SetLengthImpl(isolate,receiver,new_length,backing_store);
return result;

减容过程

if(2*length <= capacity){
isolate->heap()->RightTrimFixedArray(*backing_store,capacity-length);
}else{
BackingStore::cast(*backing_store)->FillWithHoles(length,old_length);
}

如果容量大于等于length的2倍，则进行容量调整，否则用holes对象填充，第三行的rightTrim函数，会算出需要释放的空间大小，并做标记，并等待GC回收。

int bytes_to_trim = elements_to_trim*element_size;
Address old_end = object->address() + object ->Size();
Address new_end = old_end-bytes_to_trim;
CreateFillterObjectAt(new_end,bytes_to_trim,ClearRecorderedSlots::kYes);

5 shift和splice数组中间的操作

push和pop都是在数组末尾操作，相对比较简单，而shift、unshift和splice是在数组的开始或者中间进行操纵。

(1)shift 出队

即删除并返回数组的第一个元素，shift和pop调用的都是同样的删除函数，只不过shift传的删除的Position是AT_START，源码里面会判断如果是AT_START的话，会把元素进行移动。

if(remove_position==AT_START){
Subclass::MoveElements(isolate,receiver,backing_store,0,1,new_length,0,0);
(2)unshift在数组的开始位置插入元素
  • 首先判断容量是否足够存放，如果不够，将容量扩展为老容量的1.5倍加16
  • 再把老元素移到新的内存空间偏移为unshift元素个数的位置，也就是说要腾出起始的空间放unshift传进来的元素
  • 如果空间够了，则直接执行memmove移动内存空间
  • 最后再把unshift传进来的参数copy到开始的位置。
  • 更新array的length。
(3)splice

splice的操作已经几乎不用去看源码了，通过shift和unshift的操作，就可以想象到它的执行过程是怎样的，只是shift和unshift的操作的Index是0，而splice可以制定index。

6 Join和Sort

说join和sort小清新，是因为它们是用JS实现的，然后再用wasm打包成native code

  • Join
    不过join的实现逻辑并不简单，因为array的元素本身具有多样化，可能为慢元素或者快元素，还可能带有循环引用。对于慢元素，需要先排下序：
    var keys=GetSortedArrayKeys(array,%GetArrayKeys(array,length));
    预处理完之后，最后创建一个字符串数组，用连接符连起来。
var elements = new InternalArray(length);
for(var i = 0; i < length; i++){
elements[i] = ConverToString(use_local,array[i]);
}
if(separator==' '){
return %SrtingBuilderConcat(elements,length,' ');
}else{
return %SrtingBuilderJoin(elements,length,separator);
}

join()方法在使用的时候，如果参数为空，则默认用“，”连接数组之间的元素；如果参数不为空，则用参数来连接数组之间的元素。

  • Sort
    sort函数是用的快速排序:
function ArraySort(comparefn){
CHECK_OBJECT_COERCIBLE(this,"Array.prototype.sort");
%Log("js/array.js execute ArraySort");
var array=TO_BOJECT(this);
var length = TO_LENGTH(array.length);
return InnerArraySort(array,length,comparefn);
}

不过当数组元素的个数不超过10个时，排序用的是插入排序。

function InnerArraySort(array,length,comparefn){
function QuickSort(a,from,to){
var third_index = 0;
while(true){
if(to-from<=10){
InsertionSort(a,from,to);
return;
}
//other code...
}
}
}

快速排序算法有一个关键点就是选择枢纽元素，最简单的是每次都是选取第一个元素，或者中间的元素，sort的源码里是这样选择的：

if(to-from>1000){
third_index = GetThirdIndex(a,from,to);
}else{
third_index = from+((to-from)>>1);
}

如果元素个数在1000以内，则使用它们的中间元素，否则要算一下，这个算法比较有趣；

function GetThirdIndex(a,from,to){
var t_array = new InternalArray;
var increment = 200+((to-from)&15);
var j = 0;
from+=1;
to-=1;
for(var i=from;i<to;i+=increment){
t_array[j]=[i,a[i]];
j++;
}
t_array.sort(function(a,b){
return comparefn(a[1],b[1]);
});
var third_index = t_array[t_array.length>>1][0];
return third_index;
}

先取一个递增区间200~215之间，再循环取出原元素里面落到这个间距的元素，放到一个新的数组里面（这个数组时C++中的数组），然后排下序，取中间的元素，因为枢纽元素刚好是所有元素的中位数时，排序效果最好，而这里取出少数元素的中位数，类似于抽样模拟，缺点是它得再借助另外的排序算法。

7 Array和线性链接（List）的速度

线性链接是一种非连续存储的数据结构，每个元素都有一个指针指向它的下一个元素，所以它删除元素的时候不需要移动其它元素，也不需要考虑扩容的事情，但它的查找比较慢。

我们实现一个简单的List和Array进行比较。
List的每个节点用一个Node表示：

class Node{
constructor(value,next){
this.value = value;
this.next=next;
}
}

每个List都有一个头指针指向第一个元素，和一个Length记录它的长度。

class List{
constructor(){
this.head= null;
this.tail=null;
this.length=0;
}
}

然后实现它的push和unshift函数：

class List{
unshift(value){
return this.insert(0,value);
}
push(value){
if(this.head===null){
this.head=new Node(value,this,tail);
this.length++;
}else{
this.insert(this.length,value);
}
return this.length;
}
}

push和unshift都会调用一个通用的Insert函数：

insert(index,value){
var insertPos = this.head;
//找到需要插入的位置的节点
for(var i = 0; i < index-1; i++){
insertPos = insertPos.next;
}
var node = null;
if(index===0){
node = new Node(value,this.head);
}else{
node = new Node(value,insertPos.next);
insertPos.next = node;
}
this,length++;
return value;
}

有了这个List之后，就可以初始化一个List和array：

var list = new List();
var arr = [];
for(var i = 0;i<100;i++){
list.push(i);
arr.push(i);
}

用下面代码可以比较List和Array在数组起始位置插入元素的操作时间:

var count = 10000;
console.time("list unshift");
for(var i = 0; i<count; i++){
list.unshift(i);
}
console.timeEnd("list unshift");
console.time("array unshift");
for(var i = 0;i<count;i++){
arr.unshift(i);
}
console.timeEnd("array unshift");

在比较从正中间位置插入元素的时间：

console.time("list insert middle with index");
for(var i = 0; i < count; i++){
insert.unshift(i);
}
console.timeEnd("list unshift");

console.time("array unshift");
for(var i = 0; i < count; i++){
arr.unshift(i);
}
console.timeEnd("array unshift");

运行之后可以得到如下表格：


运行时间

可以由图得到结论：
在队首插入元素，使用线性链接List的时间将会数量级的优先于Array；如果是在中间位置插入的话，由于List的查找花费了很多时间，导致总时间明显高于Array，但是如果在插入的时候，记住上一次的位置i，那么List又会明显快于Array。

8 reverse

reverse是将数组逆转的方法，该方法不返回新数组，所以会在原数组上进行改动。
实现代码如下：

function myreverse(arr){
  for(var i=0;i<arr.length/2;i++){
    vat tmp = arr[i];
    arr[i] = arr[arr.length - i - 1];
    arr[arr.length - i - 1] = tmp;
  }
  return arr;
}

综上：
Array的实现用了三种语言：汇编，C++和JS，最常用的如push用了汇编实现，比较常用的如Pop/splice等用了C++，较为少用的如join/sort用了JS。

Array为快元素即普通的数组时，增删元素操作需要不断的扩容、减容和调整元素的位置，特别是当不断地在起始位置插入元素时，和链表相比，这种时间效率还是比较低下的。如果使用的场景是要根据Index删除元素，使用Array还是有优势，但是若能很快定位到删除元素的位置，链表毫无疑问还是更合适的。

末尾挂一下资料原文
我们要做文明的知识搬运工~

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,132评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,802评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,566评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,858评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,867评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,695评论 1赞 282
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,064评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,705评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,915评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,677评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,796评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,432评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,041评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,992评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,223评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,185评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,535评论 2赞 343