日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間:8:30-17:00
你可能遇到了下面的問題
關閉右側工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
從Chrome源碼看JS Object的實現(xiàn)

看到這個題目,可能有些人會覺得奇怪——Object不是JS的基本數(shù)據(jù)類型么,有什么實現(xiàn)不實現(xiàn)的呢?如果你這么想的話,說明你沒有接觸過其它語言,一直都是在和JS打交道,編程世界那么大,你沒有出去看一看。C/C++/Java等語言是沒有這種json的數(shù)據(jù)類型的,其它一些有的:如在Pthyon里面叫做字典,在Ruby/Perl里面叫散列表,當然這只是個名稱而已,本質上可以當作json類型。而C是“萬物之母”,C里面沒有的,就得通過某種方式實現(xiàn)。

成都創(chuàng)新互聯(lián)公司2013年開創(chuàng)至今,先為丹江口等服務建站,丹江口等地企業(yè),進行企業(yè)商務咨詢服務。為丹江口企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務解決您的所有建站問題。

并且JS里面的Object是如何查找屬性的,這個問題有人說是通過遍歷key的字符串查找的,也有人說是通過哈希查找的。究竟它是怎么存儲和查找的,能不能把Object當作一個map來使用?如果無法從源碼的角度實際地看一下瀏覽器的實現(xiàn),你的觀點可能就站不住腳,只能人云亦云。

Chrome自行開發(fā)了V8引擎,并被Node拿去當解析器。本文將通過V8的源碼嘗試分析Object的實現(xiàn)。

1. V8的代碼結構

v8的源碼位于 src/v8/src/ ,代碼層級相對比較簡單,但是實現(xiàn)比較復雜,為了能看懂,需要找到一個切入點,通過打斷點、加log等方式確定這個切入點是對的,如果這個點并不是關鍵的點,進行到某一步的時候就斷了,那么由這個點出發(fā)嘗試去找其它的點。不斷驗證,***找到一個最關鍵的地方,由這個地方由淺入深地擴展到其它地方,***形成一個體系。

以下,先說明JS Object的類圖。

2. JS Object類圖

V8里面所有的數(shù)據(jù)類型的根父類都是Object,Object派生HeapObject,提供存儲基本功能,往下的JSReceiver用于原型查找,再往下的JSObject就是JS里面的Object,Array/Function/Date等繼承于JSObject。左邊的FixedArray是實際存儲數(shù)據(jù)的地方。

3. 創(chuàng)建JSObject

在創(chuàng)建一個JSObject之前,會先把讀到的Object的文本屬性序列化成 constant_properties ,如下的data:

 
 
 
 
  1. var data = {  
  2. name: "yin",  
  3. age: 18,  
  4. "-school-": "high school"  
  5. }; 

會被序列成:

 
 
 
 
  1. ../../v8/src/runtime/runtime-literals.cc 72 constant_properties:  
  2. 0xdf9ed2aed19: [FixedArray]  
  3. – length: 6  
  4. [0]: 0x1b5ec69833d1  
  5. [1]: 0xdf9ed2aec51  
  6. [2]: 0xdf9ed2aec71  
  7. [3]: 18  
  8. [4]: 0xdf9ed2aec91  
  9. [5]: 0xdf9ed2aecb1  

它是一個FixedArray,一共有6個元素,由于data總共是有3個屬性,每個屬性有一個key和一個value,所以Array就有6個。***個元素是***個key,第二個元素是***個value,第三個元素是第二個key,第四個元素是第二個key,依次類推。Object提供了一個Print()的函數(shù),把它用來打印對象的信息非常有幫助。上面的輸出有兩種類型的數(shù)據(jù),一種是String類型,第二種是整型類型的。

FixedArray是V8實現(xiàn)的一個類似于數(shù)組的類,它表示一段連續(xù)的內存,上面的FixedArray的length = 6,那么它占的內存大小將是:

 
 
 
 
  1. length * kPointerSize 

因為它存的都是對象的指針(或者直接是整型數(shù)據(jù)類型,如上面的18),在64位的操作系統(tǒng)上,一個指針為8個字節(jié),它的大小將是48個字節(jié)。它記錄了一個初始的內存開始地址,使用元素index乘以指針大小作為偏移,加上開始地址,就可以取到相應index的元素,這和數(shù)組是一樣的道理。只是V8自己封裝了一個,方便添加一些自定義的函數(shù)。

FixedArray主要用于表示數(shù)據(jù)的存儲位置,在它上面還有一個Map,這個Map用于表示數(shù)據(jù)的結構。這里的Map并不是哈希的意思,更接近于地圖的意義,用來操作FixedArray表示的這段內存。V8根據(jù) constant_properties的 length,去開辟相應大小空間的Map:

 
 
 
 
  1. Handle map = ComputeObjectLiteralMap(context, constant_properties,  
  2. &is_result_from_cache); 

把這個申請后的Map打印出來:

 
 
 
 
  1. ../../v8/src/heap/heap.cc 3472 map is  
  2. 0x21528af9cb39: [Map]  
  3. – type: JS_OBJECT_TYPE  
  4. – instance size: 48  
  5. – inobject properties: 3  
  6. – back pointer: 0x3e2ca8902311  
  7. – instance descriptors (own) #0: 0x3e2ca8902231  

從第4行加粗字體可以看到,它的大小確實和我們算的一樣。并且它還有一個叫做descriptors表示它的數(shù)據(jù)結構。descriptor記錄了每個key-value對,以及它們在FixedArray里面的index. 后續(xù)對properties的操作基本上通過descriptor進行。

有了這個map的對象之后,用它來創(chuàng)建一個JSObect:

 
 
 
 
  1. Handle boilerplate =  
  2. isolate->factory()->NewJSObjectFromMap(map, pretenure_flag); 

重新開辟一段內存,把map的內容拷過去。

由于map只是一段相應大小的內存空間,它的內容是空的,所以接下來要設置它的properties:

 
 
 
 
  1. for (int index = 0; index < length; index += 2) { 
  2.   Handle key(constant_properties->get(index + 0)); 
  3.   Handle value(constant_properties->get(index + 1)); 
  4.   Handle name = Handle::cast(key); 
  5.   JSObject::SetOwnPropertyIgnoreAttributes(boilerplate, name, 
  6.                                           value, NONE); 
  7. 通過上面的代碼,把properties設置到map的FixedArray里面,并且可以通過index用descriptors迅速地取出key-value。由于這個過程比較復雜,細節(jié)不展開討論。

    在設置properties的同時,會初始化一個searchCache,這個cache支持哈希查找某個屬性。

    4. 字符串哈希查找

    在設置cache的時候,會先進行查找是否已存在相同的屬性名,如果已經(jīng)有了就把它的value值覆蓋掉,否則把它添加到cache里面:

     
     
     
     
    1. int DescriptorArray::SearchWithCache(Isolate* isolate, Name* name, Map* map) { 
    2.   DescriptorLookupCache* cache = isolate->descriptor_lookup_cache(); 
    3.   //找到它的index 
    4.   int number = cache->Lookup(map, name); 
    5.   //如果沒有的話 
    6.   if (number == DescriptorLookupCache::kAbsent) { 
    7.     //通過遍歷找到它的index 
    8.     number = Search(name, number_of_own_descriptors); 
    9.     //更新cache 
    10.     cache->Update(map, name, number); 
    11.   } 
    12.   return number; 

    如上代碼的注釋,我們先來看一下這個Search函數(shù)是怎么進行的:

     
     
     
     
    1. template  
    2. int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) { 
    3.   // Fast case: do linear search for small arrays. 
    4.   const int kMaxElementsForLinearSearch = 8; 
    5.   if (valid_entries <= kMaxElementsForLinearSearch) { 
    6.     return LinearSearch(array, name, valid_entries, 
    7.                                     out_insertion_index); 
    8.   }   
    9.   // Slow case: perform binary search. 
    10.   return BinarySearch(array, name, valid_entries, 
    11.                                   out_insertion_index); 

    如果屬性少于等于8個時,則直接線性查找即依次遍歷,否則進行二分查找,在線性查找里面判斷是否相等,是用的內存地址比較:

     
     
     
     
    1. for (int number = 0; number < valid_entries; number++) { 
    2.   if (array->GetKey(number) == name) return number; 

    因為name都是用的上面第三點設置Map的時候傳進來的name,因此初始化的時候相同的name都指向同一個對象。所以可以直接用內存地址進行比較,得到FixedArray的索引number。然后用key和number去update cache:

     
     
     
     
    1. cache->Update(map, name, number); 

    重點在于這個update cache。這個cache的數(shù)據(jù)結構是這樣的:

     
     
     
     
    1. static const int kLength = 64;  
    2. struct Key {  
    3. Map* source;  
    4. Name* name;  
    5. };  
    6. Keykeys_[kLength];  
    7. int results_[kLength]; 

    它有一個數(shù)組keys_的成員變量存放key,這個數(shù)組的大小是64,數(shù)組的索引用哈希算出來,不同的key有不同的哈希,這個哈希就是它在數(shù)組里面的索引。它還有一個results_,存放上面線性查找出來的number,這個number就是內存里面的偏移,有了這個偏移就可以很快地定位到它的內容,所以放到results里面.

    關鍵在于這個哈希是怎么算的。來看一下update的函數(shù):

     
     
     
     
    1. void DescriptorLookupCache::Update(Map* source, Name* name, int result) { 
    2.   int index = Hash(source, name); 
    3.   Key& key = keys_[index]; 
    4.   key.source = source; 
    5.   key.name = name; 
    6.   results_[index] = result; 

    先計算哈希索引index,然后把數(shù)據(jù)存到results_和keys_這兩個數(shù)組的index位置。這個Hash函數(shù)是這樣的:

     
     
     
     
    1. int DescriptorLookupCache::Hash(Object* source, Name* name) { 
    2.   // Uses only lower 32 bits if pointers are larger. 
    3.   uint32_tsource_hash = 
    4.       static_cast(reinterpret_cast(source)) >> 
    5.       kPointerSizeLog2; 
    6.   uint32_tname_hash = name->hash_field(); 
    7.   return (source_hash ^ name_hash) % kLength; 
     

    先計算map和key的hash,map的hash即source_hash是用map的地址的低32位,為了統(tǒng)一不同指針大小的區(qū)別,而計算key的hash即name_hash,最核心的代碼應該是以下幾行:

     
     
     
     
    1. uint32_tStringHasher::AddCharacterCore(uint32_trunning_hash, uint16_t c) {  
    2. running_hash += c;  
    3. running_hash += (running_hash << 10);  
    4. running_hash ^= (running_hash >> 6);  
    5. return running_hash;  

    依次循環(huán)name的每個字符串做一些位運算,結果累計給running_hash.

    source_hash是用map的內存地址,因為這個地址是唯一的,而name_hash是用的字符串的內容,只要字符串一樣,那么它的hash值就一定一樣,這樣保證了同一個object,它的同個key值的索引值就一定一樣。source_hash和name_hash***異或一下,模以kLength = 64得到它在數(shù)組里面的索引。

    這里自然而然會有一個問題,通過這樣的計算不能夠保證不同的name計算出來的哈希值一定不一樣,好的哈希算法只能讓結果盡可能隨機,但是無法做到一定不重復,所以這里也有同樣的問題。

    先來看一下,它是怎么查找的:

     
     
     
     
    1. int DescriptorLookupCache::Lookup(Map* source, Name* name) {  
    2. int index = Hash(source, name);  
    3. Key& key = keys_[index];  
    4. if ((key.source == source) && (key.name == name)) return results_[index];  
    5. return kAbsent;  

    先用同樣的哈希算法,算出同樣的index,取出key里面的map和name,和存儲的map和name進行比較,如果相同則說明找到了,否則的話返回不存在-1的標志。一旦不存在了又會執(zhí)行上面的update cache,先調Search找到它的偏移index作為result,如果index存在重新update cache。所以上面的問題就可以得到解答了,重復的哈希索引覆蓋了***個,導致查找***個的時候沒找找到,所以又去重新update,把那個索引值的數(shù)組元素又改成了***個的。因此,如果兩個重復的元素如果循環(huán)輪流訪問的話,就會造成不斷地查找index,不斷地更新搜索cache。但是這種情況還是比較少的。

    如何保證傳進來的具有相同字符串的name和原始的name是同一個對象,從而才能使它們的內存地址一樣?一個辦法是維護一個Name的數(shù)據(jù)池,據(jù)有相同字符串的name只能存在一個。

    上面的那個data它的三個name的index在筆者電腦上實驗計算結果為:

    • #name hash index = 62
    • #age hash index = 32
    • #-school- hash index = 51

    有一個比較奇怪的地方是重復實驗,它們的哈希值都是一樣的。并且具有相同屬性且順序也相同的object,它們的map地址就是一樣的。

    如果一個元素的屬性值超過64個呢?那也是同樣的處理,后面設置的會覆蓋前面設置的。學過哈希的都知道,當元素的個數(shù)大于容器容量的一半時,重復的概率將會大大增加。所以一個object的屬性的比較優(yōu)的***大小為32。一旦超過32,在一個:

     
     
     
     
    1. for(var keyin obj){  
    2. obj[key] //do sth.  

    for循環(huán)里面,這種查找的開銷將會很大。

    那為什么它要把長度設置成64呢,如果改大了,不就可以減少重復率?但是這樣會造成更多的內存消耗,即使一個Object只有一個屬性,它也會初始化一個這么大的數(shù)組,對于這種屬性比較少的object來說就很浪費。所以取64,應該是一個比較適中的值。

    同時另一方面,經(jīng)常使用的那幾個屬性還是能夠很快通過哈希計算定位到它的內容。并且這種場景還是很常見的,如獲取數(shù)組元素的lengh.

    根據(jù)上面的討論,將Object當作map來使用,并不是很合適,在如下的代碼里面:

     
     
     
     
    1. var data = [10001, 10002/* 很多個元素 */]; 
    2. var keys = { 
    3.     "1000a": '' 
    4.     "1000b": '' 
    5.     /* 很多個屬性 */ 
    6. var exists = []; 
    7. for(var i = 0; i < data.length; i++){ 
    8.     if(typeof keys[data[i]] !== "undefined"){ 
    9.         exists.push(data[i]); 
    10.     } 

    由于在keys查找時,可能會存在大量沒有的元素,這樣就導致它哈希查找沒有找到,然后需要進行線性查找/二分查找,結果也沒找到。所以它和哈希map還是有很多的差別的。這樣的效率雖然比不上直接使用一個哈希map,但至少它的效率要比寫一個數(shù)組,然后一個個去比較來得高效,怎么說它還是用的內存地址進行二分查找。

    這里就體現(xiàn)了ES6新增了Map/Set類型的價值,它是一個真正的哈希Map。如果不能使用ES6的map,那么自行實現(xiàn)一個或者使用第三方的庫也是可取的。

    在說Map之前,Object還有數(shù)字類型的屬性沒有討論。

    5. 數(shù)字索引哈希查找

    假設data變成:

     
     
     
     
    1. var data = { 
    2.        name: "yin", 
    3.        age: 18, 
    4.        "-school-": "high school", 
    5.        1: "Monday", 
    6.        2: "Thuesday", 
    7.        "3": "Wednesday" 
    8.    }; 

    把生成的data Object打印出來是這樣的:

     
     
     
     
    1. ../../v8/src/runtime/runtime-literals.cc 105 boilerplate obj:  
    2. 0x3930221af3a9: [JS_OBJECT_TYPE]  
    3. – map = 0x6712e19cc41 [FastProperties]  
    4. – prototype = 0x27d71d20f19  
    5. – elements = 0x2e1e1a56b579 [FAST_HOLEY_ELEMENTS]  
    6. – properties = 0x2c2a4d782241 {  
    7. #name: 0x3930221aec51 (data field at offset 0)  
    8. #age: 18 (data field at offset 1)  
    9. #-school-: 0x3930221aecb1 (data field at offset 2)  
    10. }  
    11. – elements = {  
    12. 0: 0x2c2a4d782351  
    13. 1: 0x3930221aecf9  
    14. 2: 0x3930221aed39  
    15. 3: 0x3930221aed79 
    16. 4-18: 0x2c2a4d782351  

    那些key為數(shù)字的存放在elements的數(shù)據(jù)結構里面,elements和properties的區(qū)別在于——elements有獨立的一個哈希表,并且它不是覆蓋存放的,它會根據(jù)哈希值算元素的數(shù)組索引,判斷如果當前索引已經(jīng)存在元素,則一直找到下一個空的位置來存放它:

     
     
     
     
    1. uint32_tcapacity = Capacity(); 
    2.  uint32_tentry = FirstProbe(hash, capacity); 
    3.  uint32_tcount = 1; 
    4.  // EnsureCapacity will guarantee the hash table is never full. 
    5.  while (true) { 
    6.    Object* element = KeyAt(entry); 
    7.    if (!IsKey(isolate, element)) break; 
    8.    entry = NextProbe(entry, count++, capacity); 
    9.  } 
    10.  return entry; 

    為什么數(shù)字的key要單獨這么搞呢?如果把它當成一個字符串的key按上面字符串處理的邏輯也是行得通的。原因可能是一方面如果key是數(shù)字,那在在算哈希值可以做一個優(yōu)化,另一方面數(shù)字的key可能會有很多個就像上面提的例子,使用者可能把object當作一個map來用,所以為它作一個優(yōu)化。

    可以說elements幾乎是一個真正意義的哈希表。

    然后再來簡單看一下ES6的Map的實現(xiàn)

    6. ES6 Map的實現(xiàn)

    這里有一個比較有趣的事情,就是V8的Map的核心邏輯是用JS實現(xiàn)的,具體文件是在 v8/src/js/collection.js ,用JS來實現(xiàn)JS,比寫C++要高效多了,但是執(zhí)行效率可能就沒有直接寫C++的高,可以來看一下set函數(shù)的實現(xiàn):

     
     
     
     
    1. function MapSet(key, value) { 
    2.   //添加一個log 
    3.   %LOG("MapSet", key); 
    4.   var table = %_JSCollectionGetTable(this); 
    5.   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 
    6.   var hash = GetHash(key); 
    7.   var entry = MapFindEntry(table, numBuckets, key, hash); 
    8.   if (entry !== NOT_FOUND) return ...//return代碼省略 
    9.   //如果個數(shù)大于capacity的二分之一,則執(zhí)行%MapGrow(this)代碼略 
    10.   FIXED_ARRAY_SET(table, index, key); 
    11.   FIXED_ARRAY_SET(table, index + 1, value); 

    第三行添加一個log函數(shù),確認確實是執(zhí)行這里的代碼。%開頭的LOG,表示它是一個C++的函數(shù),這個代碼寫在runtime.h和runtime.cc里面。這些JS代碼***會被組裝成native code。在V8里,除了Map/Set之外,很多ES6新加的功能,都是用的JS實現(xiàn)的,如數(shù)組新加的很多函數(shù)。

    上文介紹了Object是如何實現(xiàn)的,重點分析了V8是如何存儲一個Object的屬性,并用了一個真正的Map作為參照。***的結論是Object屬性主要是通過哈希查找的,但是它不太適合拿來當作哈希Map使用,特別是當key很多并且都是字符串的時候。

    其它的瀏覽器引擎可能會有不同的實現(xiàn),但是至少不會笨到直接用key的字符串進行遍歷。筆者將嘗試在下一篇介紹Array的實現(xiàn),特別是分析一下它的操作函數(shù)是如何實現(xiàn)的。


    本文名稱:從Chrome源碼看JS Object的實現(xiàn)
    當前鏈接:http://www.dlmjj.cn/article/djsehpe.html