Project

General

Profile

Actions

Feature #15331

closed

[PATCH] Faster hashing for short string literals

Added by alanwu (Alan Wu) over 5 years ago. Updated about 5 years ago.

Status:
Closed
Assignee:
-
Target version:
-
[ruby-core:89985]

Description

Background

It's common for applications to use string literals as hash keys, especially
for applications that work with YAML or JSON:

paylod['name']

At the moment (r65895), hash lookups using a string key is about 30% slower
than using a symbol key.

Proposal

We memoize the hash code for short fstrings. There is extra, currently unused
space at the end of the RString struct we can use to store the hash code.
The unique nature of fstrings makes it so that every user of each fstring benefit
from the memoized hash.

Evaluation

The included benchmark hash_aref_fstr.rb is about 20% faster with this optimization.
hash_aref_long_str.rb shows that for long strings which we cannot memoize, there is
no visible performance penalty.

vm2_freezestring.yml is also not visibly slower after this optimization.

I have also attached a bechmark (string_key_vs_symbol_key.rb) that compares hash
lookups with symbols against hash lookups with strings. With this optimization, the
gap in performance is smaller. (10% slower post patch vs 30% slower on trunk)


Files

string_key_vs_symbol_key.rb (594 Bytes) string_key_vs_symbol_key.rb alanwu (Alan Wu), 11/22/2018 10:03 PM
0001-Hash-code-memoization-for-short-fstrings.patch (3.62 KB) 0001-Hash-code-memoization-for-short-fstrings.patch alanwu (Alan Wu), 11/22/2018 10:03 PM
0001-Hash-code-memoization-for-short-fstrings-v2.patch (4.29 KB) 0001-Hash-code-memoization-for-short-fstrings-v2.patch alanwu (Alan Wu), 11/23/2018 06:42 PM
0001-Hash-code-memoization-for-short-fstrings-v3.patch (4.36 KB) 0001-Hash-code-memoization-for-short-fstrings-v3.patch got bit by https://bugs.llvm.org/show_bug.cgi?id=27493 alanwu (Alan Wu), 11/23/2018 07:23 PM
0001-Hash-code-memoization-for-short-fstrings-v4.patch (4.31 KB) 0001-Hash-code-memoization-for-short-fstrings-v4.patch switched to RSTRING for casting to make the code look less noisy alanwu (Alan Wu), 11/23/2018 10:58 PM
0001-Hash-code-memoization-for-short-fstrings-v5.patch (12.9 KB) 0001-Hash-code-memoization-for-short-fstrings-v5.patch alanwu (Alan Wu), 11/26/2018 04:34 AM
0001-Add-st_update_with_hash.patch (3.09 KB) 0001-Add-st_update_with_hash.patch v6 alanwu (Alan Wu), 11/26/2018 04:24 PM
0002-Hash-code-memoization-for-short-fstrings.patch (10 KB) 0002-Hash-code-memoization-for-short-fstrings.patch v6 alanwu (Alan Wu), 11/26/2018 04:24 PM
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0