Closed ftanuma closed 1 month ago
This pull request was exported from Phabricator. Differential Revision: D53062194
This pull request was exported from Phabricator. Differential Revision: D53062194
This pull request was exported from Phabricator. Differential Revision: D53062194
This pull request was exported from Phabricator. Differential Revision: D53062194
This pull request was exported from Phabricator. Differential Revision: D53062194
This pull request was exported from Phabricator. Differential Revision: D53062194
Summary: Currently OrderedHashMap is using ArrayStorageSmall for the backing storage. ArrayStorageSmall has max element limit at around 500,000. When we try to insert more then 500K elements, all the insertion will become hash collision and will start linked list in each bucket. This is the measure reason why Set construction from large Array is slow.
By using SegmentedArray instead, the backing storage can grow more than 500K, thus it will not have as much collision as with ArrayStorageSmall, which result to much faster Set construction.
Reviewed By: neildhar
Differential Revision: D53062194