chakra-core / chakra-core/ChakraCore

Re-evaluate hash function for RecyclerWeakReference

Open
#3,282 6 comments 0 reactions 0 assignees View on GitHub
Performance
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.