[ruby-core:90076] [Ruby trunk Feature#15331] [PATCH] Faster hashing for short string literals

[nobu@ruby-lang.org]

Issue #15331 has been updated by nobu (Nobuyoshi Nakada).


alanwu (Alan Wu) wrote:
> I've taken multi-byte terminators into account and updated my implementation. I've also included a test that should warn us about hash clobbering.

Seems nice.

About the macro `BUILTIN_SINGLE_BYTE_ENC_IDX_P`, its name is misleading as it is true for UTF-8.
In common, single-byte encoding means that it uses just one byte per character, 0..255 range, e.g., ASCII-8BIT, US-ASCII, and ISO-8859 family.
UTF-8 is one of mutli-byte encodings.
Also it doesn't cover all non-wchar encodings, so it doesn't seem generic enough to be shared in encindex.h.

> I had to change the hash table interaction for fstring creation a bit to make up the performance difference.
> Apologies for the bigger patch size.

It may be nice to separate `st_update_with_hash` patch.


----------------------------------------
Feature #15331: [PATCH] Faster hashing for short string literals
https://bugs.ruby-lang.org/issues/15331#change-75200

* Author: alanwu (Alan Wu)
* Status: Open
* Priority: Normal
* Assignee: 
* Target version: 
----------------------------------------
## 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)
0001-Hash-code-memoization-for-short-fstrings.patch (3.62 KB)
0001-Hash-code-memoization-for-short-fstrings-v2.patch (4.29 KB)
0001-Hash-code-memoization-for-short-fstrings-v3.patch (4.36 KB)
0001-Hash-code-memoization-for-short-fstrings-v4.patch (4.31 KB)
0001-Hash-code-memoization-for-short-fstrings-v5.patch (12.9 KB)


-- 
https://bugs.ruby-lang.org/