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, 1. HashSet / HashMap The fastest and the most memory efficient. No guarantee about iteration ordering. Data structure gets corrupted if you are adding / removing entries while iterating. 2. OrderedHashSet / OrderedHashMap Still offering good performance and not taking significant memory cost, but offering “insertion ordering” iteration. As the same to HashSet / HashMap, data structure gets corrupted if you are adding / removing entries while iterating. 3. ListHashSet Performance is not so great and taking larger memory footprint. But offering “insertion ordering” iteration as well. The critical difference from (2) is it is allowing users to add and remove entries while iterating (since it is LinkedList). Best regards, -Yusuke Suzuki _______________________________________________ webkit-dev mailing list -- [email protected] To unsubscribe send an email to [email protected]
