Good question! With a bit of careful size selection (to make sure each one gets the right capacity / load), and fixing load factor difference, I’ve got a fun table. The data is obtained on M5 Max MBP, lower number is better (ns/op).
Key takeaways, 1. This is performance measurement, not measuring memory. HashSet is the best in terms of memory usage. OrderedHashSet is second, and ListHashSet is the worst. 2. Insert is showing very interesting result. The fastest container for insertion is actually OrderedHashSet! There is legit reason: OrderedHashSet is maintaining index-hash-table and entries are separate contiguous buffer. So when rehashing, we need to reconstruct the integer hashtable part, but entries buffers are literally just you can copy (& compact by removing tombstones). Still, integer key cases, UncheckedHashSet is the fastest because both are rehashing integer hashtable. But if the key is string for example, OrderedHashTable gets better since hashtable rehashing is only happening for index buffer. Furthermore, this is related to (4), iteration of entries are dramatically faster in OrderedHashSet. So rehashing becomes in general faster than normal HashSet since we need to iterate entries and reinsert them. But OrderedHashSet only needs to scan the entries in very packed manner, significantly better cache miss rate. 3. ContainsHit is showing the something we just expected. HashSet / UncheckedHashSet is faster than the others and ListHashSet is the slowest. OrderedHashSet / ListHashSet requires load-dependent double-dereference so this is strictly slower than HashSet / UnchecheckedHashSet. 4. Iterate shows interesting results too. Because of packed entries in OrderedHashSet, iteration in this is really faster than even normal HashSet. HashSet is having many empty slots, while OrderedHashSet entries are packed. Overall, given that most of HashTable are look-up heavy typically, the good guidance is use HashSet if possible, consider using OrderedHashSet if insertion ordering is necessary. You can use ListHashSet only when you have very particular algorithm that you need to add / remove entries during iteration :) === Insert (ns/op) === container key 7 63 511 3K 31K 255K ---------------- -------- -------- -------- -------- -------- -------- -------- HashSet uint32_t 4.12 3.99 4.00 4.09 8.61 13.24 UncheckedHashSet uint32_t 3.80 3.36 3.77 3.78 7.77 12.80 OrderedHashSet uint32_t 4.02 3.63 3.31 2.62 4.65 8.16 ListHashSet uint32_t 11.19 11.49 12.52 15.08 24.41 31.28 HashSet void* 4.20 3.74 4.35 4.53 10.05 14.04 UncheckedHashSet void* 3.77 3.43 4.13 4.42 8.72 13.63 OrderedHashSet void* 4.59 3.51 3.13 2.65 4.33 8.23 ListHashSet void* 11.48 11.61 12.44 14.60 24.17 31.09 HashSet String 7.11 7.37 8.95 9.03 17.58 23.67 UncheckedHashSet String 6.84 7.10 8.53 9.14 17.65 23.56 OrderedHashSet String 7.73 7.45 8.54 7.51 11.43 14.55 ListHashSet String 11.89 11.44 13.35 16.59 27.06 38.42 === ContainsHit (ns/op) === container key 7 63 511 3K 31K 255K ---------------- -------- -------- -------- -------- -------- -------- -------- HashSet uint32_t 0.64 0.76 0.80 0.99 1.40 3.67 UncheckedHashSet uint32_t 0.43 0.57 0.56 0.79 1.14 3.41 OrderedHashSet uint32_t 0.56 0.74 0.79 0.97 1.95 4.87 ListHashSet uint32_t 0.66 0.73 0.76 0.98 1.67 5.43 HashSet void* 0.75 0.69 0.77 0.98 1.53 3.96 UncheckedHashSet void* 0.45 0.49 0.54 0.78 0.85 3.21 OrderedHashSet void* 0.63 0.65 0.75 0.92 2.21 5.01 ListHashSet void* 0.68 0.64 0.73 0.96 1.80 5.31 HashSet String 2.43 3.17 3.96 4.96 6.80 10.57 UncheckedHashSet String 2.68 3.05 3.99 4.77 6.89 9.86 OrderedHashSet String 2.48 3.08 4.04 5.04 7.84 11.35 ListHashSet String 2.55 3.22 4.40 5.96 9.01 14.13 === Iterate (ns/op) === container key 7 63 511 3K 31K 255K ---------------- -------- -------- -------- -------- -------- -------- -------- HashSet uint32_t 0.72 0.62 0.93 1.20 2.68 4.66 UncheckedHashSet uint32_t 0.74 0.61 0.91 1.19 3.15 4.69 OrderedHashSet uint32_t 0.41 0.37 0.37 0.36 0.36 0.36 ListHashSet uint32_t 0.25 0.41 0.73 0.85 0.85 0.85 HashSet void* 0.66 0.57 0.94 1.22 3.40 4.61 UncheckedHashSet void* 0.70 0.56 1.00 1.21 3.13 4.71 OrderedHashSet void* 0.40 0.33 0.32 0.25 0.29 0.29 ListHashSet void* 0.26 0.30 0.72 0.85 0.81 0.83 HashSet String 0.94 0.81 1.17 1.45 3.56 5.30 UncheckedHashSet String 1.00 0.82 1.17 1.44 3.27 5.01 OrderedHashSet String 0.67 0.53 0.51 0.54 0.48 0.51 ListHashSet String 0.46 0.63 0.71 0.95 0.85 0.91 === Churn (ns/op) === container key 7 63 511 3K 31K 255K ---------------- -------- -------- -------- -------- -------- -------- -------- HashSet uint32_t 1.48 2.47 2.77 3.24 6.73 10.65 UncheckedHashSet uint32_t 1.43 1.98 1.98 2.92 5.30 10.60 OrderedHashSet uint32_t 2.29 2.57 2.64 2.68 3.91 9.35 ListHashSet uint32_t 4.26 5.56 5.44 7.80 12.59 20.49 HashSet void* 1.52 1.77 2.49 3.86 6.62 11.73 UncheckedHashSet void* 1.49 1.74 2.33 3.32 5.15 11.42 OrderedHashSet void* 2.27 2.27 2.40 2.44 3.41 9.28 ListHashSet void* 4.48 4.55 5.21 7.88 13.85 20.76 HashSet String 4.16 4.28 6.35 7.29 12.77 20.31 UncheckedHashSet String 4.01 4.08 6.23 6.95 12.79 19.57 OrderedHashSet String 3.97 4.05 5.20 5.71 9.53 15.05 ListHashSet String 6.35 6.26 8.43 11.43 17.53 29.89 Total benchmark wall time: 28.957827 s Best regards, -Yusuke Suzuki > On May 19, 2026, at 12:55 AM, Jean-Yves Avenard <[email protected]> > wrote: > > > >> On 14 May 2026, at 9:36 am, Yusuke Suzuki via webkit-dev >> <[email protected]> wrote: >> >> Hello WebKittens! >> >> Many DOM (& some JS, like, ES6 modules code) data structures require HashSet >> / HashMap while also requiring “insertion ordering* iteration. >> Previously ListHashSet was the canonical solution for that, but this was >> really costly in both memory and performance because it is internally a >> doubly-linked list with HashTable. >> >> I’ve introduced WTF OrderedHashSet / OrderedHashMap, which preserves >> insertion ordering while maintain better memory footprint and performance >> efficiency. >> HashSet / HashMap are the fastest and the most memory efficient, but >> OrderedHashSet / OrderedHashMap is offering insertion ordering iteration >> (and you can also rbegin / rend) while it does not add significant cost. >> >> Internally, the algorithm is pretty similar to JSC’s PropertyTable (as >> JSObject also needs to preserve insertion ordering and Hash table). >> Let’s summarize, > > Have we done benchmarks to compare our HashMaps to std::map ? > > Jean-Yves
_______________________________________________ webkit-dev mailing list -- [email protected] To unsubscribe send an email to [email protected]
