Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Missing optimization: small literal hashes #2989

Open
headius opened this issue May 26, 2015 · 0 comments
Open

Missing optimization: small literal hashes #2989

headius opened this issue May 26, 2015 · 0 comments
Labels
ir jit JRuby 9000 performance

Comments

@headius
Copy link
Member

headius commented May 26, 2015

JRuby 1.7 attempted to reduce the cost of small literal hashes by using the "small" form that puts all entries in the same bucket. In addition, literal hashes below a certain size could be allocated without an intermediate array of key/value pairs. 9k lacks both of these optimizations in the JIT and interpreter. They should be restored.
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 13, 2018
@ChrisBr
Refactor RubyHash to be more performant
09965f3 
This commit basically implements two approaches
to improve the performance of RubyHash:

Switching from closed addressing hashing (double linked list)
to open addressing hashing because of better cache locality.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation (which helps for better cache
locality as well).

Further more small hashes (less than 8 entires) are now
implemented via a linear search which reduces memory
allocation for a buckets. For fast bucket skips we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 14, 2018
@ChrisBr
Refactor RubyHash to be more performant
5ae7260 
This commit basically implements two approaches
to improve the performance of RubyHash:

Switching from closed addressing hashing (double linked list)
to open addressing hashing because of better cache locality.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation (which helps for better cache
locality as well).

Further more small hashes (less than 8 entires) are now
implemented via a linear search which reduces memory
allocation for a buckets. For fast bucket skips we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 16, 2018
@ChrisBr
Refactor RubyHash to be more performant
356a56b 
This commit basically implements two approaches
to improve the performance of RubyHash:

Switching from closed addressing hashing (double linked list)
to open addressing hashing because of better cache locality.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation (which helps for better cache
locality as well).

Further more small hashes (less than 8 entires) are now
implemented via a linear search which reduces memory
allocation for a buckets. For fast bucket skips we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 16, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
58e0a06 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 16, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
349b5cd 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 16, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
956af21 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 17, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
d25da9e 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 23, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
651d78f 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 27, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
45e1b3c 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Jul 29, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
82ca102 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Aug 2, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
bc3fbeb 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Aug 3, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
2deaf66 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
ChrisBr added a commit to ChrisBr/jruby that referenced this issue Aug 4, 2018
@ChrisBr
Implement open addressing algorithm for RubyHash
69d19c4 
to improve the performance by leverage better
cache locality.

Switching from closed addressing hash algorithm (linked list)
to open addressing hashing because of a better cache locality
on modern CPU architectures.
Furthermore we removed almost all RubyHashEntry objects
for smaller memory allocation.
This is already implemented in MRI since 2.4, see
https://bugs.ruby-lang.org/issues/12142

Small hashes (less than 8 entries) are now
implemented via a linear search which reduces memory
allocation in this case and has almost no performance
implication. For a fast bucket skip we maintain
in this case a hashes array to cache the hash values.

Implements jruby#4708 & jruby#2989
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
ir jit JRuby 9000 performance
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@headius