Bug 207184

Summary: [WTF] Introduce FrozenHashMap
Product: WebKit Reporter: Yusuke Suzuki <ysuzuki>
Component: JavaScriptCoreAssignee: Yusuke Suzuki <ysuzuki>
Status: NEW ---    
Severity: Normal CC: annulen, benjamin, cdumez, cmarcelo, dbates, ews-watchlist, gyuyoung.kim, keith_miller, mark.lam, msaboff, ryuan.choi, saam, sergio, tzagallo
Priority: P2    
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
none
Patch
none
Patch
none
Patch none

Description Yusuke Suzuki 2020-02-03 22:25:31 PST 
Introduce FrozenHashMap. This is space-efficient, non-modifiable HashMap.
The relationship is something like,

1. RefCountedArray <-> Vector
2. FrozenHashMap <-> HashMap

Idea,

1. For small sized hash-map, we transparently convert it to associative-vector and perform binary searching.
2. For medium / large sized hash-map, we recalculate best-fit-size and make HashTable allocated.
Comment 1 Yusuke Suzuki 2020-02-03 22:26:58 PST 
(In reply to Yusuke Suzuki from comment #0)
> Introduce FrozenHashMap. This is space-efficient, non-modifiable HashMap.
> The relationship is something like,
> 
> 1. RefCountedArray <-> Vector
> 2. FrozenHashMap <-> HashMap
> 
> Idea,
> 
> 1. For small sized hash-map, we transparently convert it to
> associative-vector and perform binary searching.

I'm planning to add lower-tier for HashMap, which is, like, up to 8 elements, we use linear search. But I don't want to make them sorted since this involves many moves.
So, for normal HashMap, we just append it in an insertion order, and doing linear search.
But once it is converted to FrozenHashMap, we should construct sorted vector and perform binary-search.

> 2. For medium / large sized hash-map, we recalculate best-fit-size and make
> HashTable allocated.
Comment 2 Yusuke Suzuki 2020-02-04 22:53:09 PST 
Created attachment 389771 [details]
Patch
Comment 3 Yusuke Suzuki 2020-02-04 23:00:25 PST 
Created attachment 389772 [details]
Patch
Comment 4 Yusuke Suzuki 2020-02-06 15:41:16 PST 
Created attachment 390016 [details]
Patch
Comment 5 Yusuke Suzuki 2020-02-06 16:06:28 PST 
Created attachment 390017 [details]
Patch