chakra-core / chakra-core/ChakraCore
Re-evaluate hash function for RecyclerWeakReference
- Dominant language
- JavaScript
- Stars
- 9.3k
- Forks
- 1.2k
- PR merge metrics
- No merged PRs in 30d
Description
`RecyclerWeakReference` data structure is a data structure used to store weak reference to strong reference mapping inside recycler. Internally it uses hash table with chaining to save the mapped entries.
[HashKeyToBucket](https://github.com/Microsoft/ChakraCore/blob/master/lib/Common/Memory/RecyclerWeakReference.h#L285-L289) calculates the hash key from `strongReference` address and adds an entry into appropriate bucket. The assumption here is that chain length can rarely be greater than 1 and hence the [resize policy](https://github.com/Microsoft/ChakraCore/blob/master/lib/Common/Memory/RecyclerWeakReference.h#L335-L344) is that every time we add as many entries as size of hash-table array, we resize the hash-table to newSize which is next prime no. greater than `oldSize*2`.
However, in a crawler experiment that I conducted for 2 days on 5 machines, I found out that whenever we resize, **35%** of the buckets are empty i.e. their chain length is 0. **38%** of the buckets has chain length 1 and **18%** of buckets has chain length 2. We should tweak the hashing function to get distributed hash key so that we have higher no. of buckets that has chain-length 1. With that we can avoid subsequent re-sizes.
Contributor guide
Assessment
This issue has not been assessed yet.