Skip to content

Reduce load factor for Hash from 5 to 2#9124

Merged
headius merged 1 commit into
jruby:10.1-devfrom
headius:flatter_hash
Dec 8, 2025
Merged

Reduce load factor for Hash from 5 to 2#9124
headius merged 1 commit into
jruby:10.1-devfrom
headius:flatter_hash

Conversation

@headius

@headius headius commented Dec 8, 2025

Copy link
Copy Markdown
Member

The default load factor here was inherited from CRuby, which also used a load factor of 5 for its "chained bucket" implementation of Hash. Since then, they have moved on to a more space and cache- efficient open-addressing implementation.

In #9113, a user reported that large Hash initialization regressed in performance relative to JRuby 1.7 and CRuby 3.4, and this high load factor was found to be a big part of that.

A load factor of five means a saturated Hash may do 5x as much work to find a given entry, because up to five chained entries must be searched in a given bucket. Reducing this to a load factor of one may be too aggressive, so we use a load factor of two here to cut the maximum number of extra hops down to one.

Given 32-bit compressed OOPS and non-Liliput, we can do some math for the size increase:

A 1000-element Hash at load factor = 5 consumes 800 bytes for the bucket array and about 40_000 bytes for the entry objects for a total of 40_000 bytes (not including the Hash object itself).

The same Hash at load factor = 2 consumes 2000 bytes for the bucket array, an extra 1200 bytes or 2.9% size increase.

The default load factor here was inherited from CRuby, which also
used a load factor of 5 for its "chained bucket" implementation of
Hash. Since then, they have moved on to a more space and cache-
efficient open-addressing implementation.

In jruby#9113, a user reported that large Hash initialization
regressed in performance relative to JRuby 1.7 and CRuby 3.4, and
this high load factor was found to be a big part of that.

A load factor of five means a saturated Hash may do 5x as much work
to find a given entry, because up to five chained entries must be
searched in a given bucket. Reducing this to a load factor of one
may be too aggressive, so we use a load factor of two here to cut
the maximum number of extra hops down to one.

Given 32-bit compressed OOPS and non-Liliput, we can do some math
for the size increase:

A 1000-element Hash at load factor = 5 consumes 800 bytes for the
bucket array and about 40_000 bytes for the entry objects for a
total of 40_000 bytes (not including the Hash object itself).

The same Hash at load factor = 2 consumes 2000 bytes for the
bucket array, an extra 1200 bytes or 2.9% size increase.
@headius headius added this to the JRuby 10.1.0.0 milestone Dec 8, 2025
@headius
headius marked this pull request as ready for review December 8, 2025 20:52
@headius
headius merged commit 8c2eca7 into jruby:10.1-dev Dec 8, 2025
76 of 77 checks passed
@headius
headius deleted the flatter_hash branch December 8, 2025 20:52
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant