当前位置: 首页 > 科技观察

从Chrome源码看JSObject的实现

时间:2023-03-13 06:24:50 科技观察

看到这个题目,可能有人会觉得奇怪——Object不是JS的基本数据类型吗?有没有实现不了的?如果你这么认为,那说明你还没有接触过其他语言,一直和JS打交道。编程世界那么大,你没有出去看看。C/C++/Java等语言没有这个json数据类型。其他人这样做:例如,它在Pthyon中称为字典,在Ruby/Perl中称为哈希表。当然这只是一个名字,可以作为json类型使用。而C是“万物之母”,C中没有的东西必须通过一定的方式实现。而JS中的Object是如何找到属性的呢?有人说是遍历key的字符串查找,也有人说是hash查找。它是如何存储和搜索的?Object可以用作地图吗?如果你不能真正从源码的角度去看待浏览器的实现,你的观点可能站不住脚,只能听从别人的意见。Chrome开发了自己的V8引擎,Node将其用作解析器。本文将尝试通过V8的源码来分析Object的实现。一、V8的代码结构V8的源代码位于src/v8/src/,代码层次比较简单,但是实现比较复杂。为了理解它,需要找到一个入口点,并通过断点和添加日志的方式来确定这个。入口点是正确的。如果这个点不是关键点,会在某一步断掉,那就从这个点开始,再尝试寻找其他点。不断验证,最后找到最关键的地方,从这个地方由浅入深扩展到其他地方,最终形成一个体系。下面先介绍JSObject的类图。2、JSObject类图V8中所有数据类型的根父类都是Object。Object派生HeapObject提供基本的存储功能。下面的JSReceiver是用来做原型查找的,下面的JSObject就是JS中的Object和Array。/Function/Date等继承自JSObject。左边的FixedArray是实际存储数据的地方。3、创建JSObject在创建JSObject之前,首先会将读取到的Object的文本属性序列化为constant_properties,如下数据:vardata={name:"yin",age:18,"-school-":"highschool"};将被排序为:../../v8/src/runtime/runtime-literals.cc72constant_properties:0xdf9ed2aed19:[FixedArray]–length:6[0]:0x1b5ec69833d1[1]:0xdf9ed2aec51[2]:0xdf9ed2aec71[3]:18[4]:0xdf9ed2aec91[5]:0xdf9ed2aecb1是一个FixedArray,共有6个元素。由于data一共有3个属性,每个属性都有key和value,所以有6个Array。第一个元素是第一个键,第二个元素是第一个值,第三个元素是第二个键,第四个元素是第二个键,依此类推。Object提供了一个Print()函数,对于打印对象信息很有帮助。上面输出的数据有两种,一种是String类型,一种是整型。FixedArray是V8实现的类数组类。它代表了一个连续的记忆。上面FixedArray的长度=6,那么它占用的内存大小会是:length*kPointerSize因为它存放的是对象指针(或者直接是整型数据类型,比如上面的18。在64位操作系统上,一个指针是8个字节,它的大小将是48个字节,它记录了一个初始内存起始地址,用元素索引乘以指针大小作为偏移量,加上起始地址,就可以得到对应索引的元素,和数组一样,只是V8自己封装了一个,方便添加一些自定义的功能,FixedArray主要用来表示数据的存储位置,上面还有一个Map,就是用来表示数据的结构,这里的Map并不是hash的意思,而是更接近map的意思,用来操作FixedArray所代表的内存。V8根据constant_properties的长度,开辟一个对应大小的Map:Handlemap=ComputeObjectLiteralMap(context,constant_properties,&is_result_from_cache);打印出应用的Map:../../v8/src/heap/heap.cc3472mapis0x21528af9cb39:[Map]–type:JS_OBJECT_TYPE–instancesize:48–inobjectproperties:3–backpointer:0x3e2ca8902311–instancedescriptors(own)#0:0x3e2ca8902231从第4行的粗体可以看出,它的大小确实和我们计算的一样。而且它还有一个叫做描述符的数据结构来表示它。描述符记录了每个键值对及其在FixedArray中的索引。后续对属性的操作基本都是通过描述符进行的。有了这个地图对象之后,用它来创建一个JSObect:Handleboilerplate=isolate->factory()->NewJSObjectFromMap(map,pretenure_flag);重新开一段内存,复制地图的内容。由于map只是一块相应大小的内存空间,内容为空,所以接下来要设置它的属性:for(intindex=0;indexkey(constant_properties->get(index+0));Handlevalue(constant_properties->get(index+1));Handlename=Handle::cast(key);JSObject::SetOwnPropertyIgnoreAttributes(boilerplate,name,value,NONE);}通过上面的代码,将属性设置到地图的FixedArray中,通过索引和描述符快速获取key-value。由于此过程的复杂性,将不讨论细节。在设置属性时,会初始化一个searchCache,它支持哈希查找属性。4.Stringhashlookup设置缓存时,会先检查同属性名是否已经存在,如果已经存在则覆盖其值,否则加入缓存:intDescriptorArray::SearchWithCache(Isolate*isolate,Name*name,Map*map){DescriptorLookupCache*cache=isolate->descriptor_lookup_cache();//找到它的indexintnumber=cache->Lookup(map,name);//如果没有if(number==DescriptorLookupCache::kAbsent){//通过遍历找到它的indexnumber=Search(name,number_of_own_descriptors);//更新cachecache->Update(map,name,number);}returnnumber;}作为上面代码的注释,我们先来看看这个Search函数是如何工作的:templateintSearch(T*array,Name*name,intvalid_entries,int*out_insertion_index){//Fastcase:dolinearsearchforsmallarrays.constintkMaxElementsForLinearSearch=8;if(valid_entries<=kMaxElementsForLinearSearch){returnLinearSearch<搜索模式>(数组,名称,valid_entries,out_insertion_index);}//Slowcase:performbinarysearch...在线性搜索中,它用于内部存储地址比较:for(intnumber=0;numberGetKey(number)==name)returnnumber;}因为name上面第三点设置Map时传入的是name,所以在初始化时同名指向同一个对象,所以可以直接和内存地址比较得到FixedArray的索引号。然后使用key和number更新缓存:cache->Update(map,name,number);重点是这个更新缓存。这个缓存的数据结构是这样的:staticconstintkLength=64;structKey{Map*source;Name*name;};Keykeys_[kLength];intresults_[kLength];它有一个数组keys_的成员变量来存放key,数组的大小为64。数组的索引是通过hash计算的。不同的密钥具有不同的哈希值。这个散列是它在数组中的索引。它还有一个results_,里面存放的是上面线性搜索得到的数。这个数字就是内存中的偏移量。有了这个偏移量,就可以很快定位到它的内容,所以放在结果中。关键就在于这个hash这个是怎么计算出来的。看一下更新函数:voidDescriptorLookupCache::Update(Map*source,Name*name,intresult){intindex=Hash(source,name);Key&key=keys_[index];key.source=source;key.name=name;results_[index]=result;}先计算哈希索引index,然后将数据存储在results_和keys_数组的索引位置。这个Hash函数是这样的:intDescriptorLookupCache::Hash(Object*source,Name*name){//Usesonlylower32bitsifpointersarelarger.uint32_tsource_hash=static_cast(reinterpret_cast(source))>>kPointerSizeLog2;uint32_tname_hash=name->hash_field();return(source_hash^name_hash)%kLength;}首先计算map和key的hash。map的hash为source_hash,使用map地址的低32位。为了统一不同指针大小的差异,key的hash计算为name_hash,核心代码应该是如下几行:uint32_tStringHasher::AddCharacterCore(uint32_trunning_hash,uint16_tc){running_hash+=c;running_hash+=(running_hash<<10);running_hash^=(running_hash>>6);returnrunning_hash;}循环依次对每串name做一些位运算,结果累加到running_hash中。source_hash是map的内存地址,因为这个地址是唯一的,而name_hash是使用的字符串的内容,只要字符串相同,那么它的hash值就必须相同,这就保证了同一个对象的相同key值的索引值必须相同。XORsource_hash和name_hash***,模kLength=64得到它在数组中的索引。自然,这里就会出现问题。这样的计算不能保证不同名字计算出来的哈希值一定不一样。一个好的哈希算法只能让结果尽可能的随机,但是不能保证不重复,所以这里也遇到了同样的问题。我们先来看一下,它是如何查找的:intDescriptorLookupCache::Lookup(Map*source,Name*name){intindex=Hash(source,name);Key&key=keys_[index];if((key.source==source)&&(key.name==name))returnresults_[index];returnAbsent;}先用相同的hash算法计算出相同的index,取出key中的map和name,与存储的map和name进行比较,如果相同则说明已经找到,否则返回-1不存在的flag。一旦不存在,就会再次执行上面的updatecache。首先调用Search查找其偏移索引作为结果。如果索引存在,则再次更新缓存。所以上面的问题是可以回答的。重复的hash索引覆盖了第一个,导致查找第一个找不到,于是又去update,把索引值的数组元素改成第一个。因此,如果依次访问两个重复的元素,就会导致索引不断被搜索,搜索缓存不断被更新。但这仍然比较少见。如何保证传入的相同字符串的名称与原名称是同一个对象,使它们的内存地址相同?一种方式是维护一个Name的数据池,相同字符串的name只能存在一个。以上数据的三个名字的索引是笔者在电脑上实验计算得到的:#namehashindex=62#agehashindex=32#-school-hashindex=51奇怪的是重复实验,他们的hash值都是一样的。并且具有相同属性和相同顺序的对象具有相同的映射地址。如果一个元素有超过64个属性值怎么办?也就是同样的处理,后面的设置会覆盖前面的设置。学过散列的都知道,当元素个数大于容器容量的一半时,重复的概率会大大增加。因此,一个对象属性的最佳最大尺寸是32,一旦超过32,在一个:for(varkeyinobj){obj[key]//dosth.}for循环中,这次查找的开销会非常大。那为什么要把长度设置为64呢?如果改成更大的值,是不是可以降低重复率?但是这样会造成更多的内存消耗。即使一个Object只有一个属性,也会初始化这么大的一个数组。对于这种属性比较少的对象来说是一种浪费。所以取64应该是一个比较适中的值。同时,另一方面,频繁使用的属性仍然可以通过哈希计算快速定位到其内容。而且这种场景还是很常见的,比如获取数组元素的长度。根据上面的讨论,用Object作为映射并不是很合适。在下面的代码中:vardata=[10001,10002/*manyElement*/];varkeys={"1000a":''"1000b":''/*manyattributes*/}varexists=[];for(vari=0;i