NEW207184
[WTF] Introduce FrozenHashMap 
https://bugs.webkit.org/show_bug.cgi?id=207184
Summary [WTF] Introduce FrozenHashMap
Yusuke Suzuki
Reported 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.
Attachments
Patch (43.28 KB, patch)
2020-02-04 22:53 PST, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (45.90 KB, patch)
2020-02-04 23:00 PST, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (46.40 KB, patch)
2020-02-06 15:41 PST, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (46.48 KB, patch)
2020-02-06 16:06 PST, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Show Obsolete (3) View All Add attachment proposed patch, testcase, etc.
Yusuke Suzuki
Comment 1 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.
Yusuke Suzuki
Comment 2 2020-02-04 22:53:09 PST
Created attachment 389771 [details] Patch
Yusuke Suzuki
Comment 3 2020-02-04 23:00:25 PST
Created attachment 389772 [details] Patch
Yusuke Suzuki
Comment 4 2020-02-06 15:41:16 PST
Created attachment 390016 [details] Patch
Yusuke Suzuki
Comment 5 2020-02-06 16:06:28 PST
Created attachment 390017 [details] Patch
Note You need to log in before you can comment on or make changes to this bug.