Feature #8998

string keys for hash literals should use fstrings

Added by Eric Wong almost 2 years ago. Updated over 1 year ago.

[ruby-core:57727]
Status:Closed
Priority:Normal
Assignee:-

Description

While we're introducing optimizations from frozen strings,
string keys inside hashes should be frozen at the compiler level
to prevent duplication.

a = { "ABC" => :t }
b = { "ABC" => :t }

# the following ought to print true
p(a.keys[0].object_id == b.keys[0].object_id)

This should introduce no incompatibilities and be transparent to users of
older rubies.

hash_aset_fstring.diff Magnifier - proposed patch (411 Bytes) Eric Wong, 10/09/2013 06:17 AM

hash_aset_fstring_check_fail.txt Magnifier - "make check" output (166 KB) Eric Wong, 10/09/2013 06:29 AM

hash_aset_fstring_check_bt.txt Magnifier - backtrace from gdb (8.07 KB) Eric Wong, 10/09/2013 06:29 AM


Related issues

Related to Ruby trunk - Misc #9188: r43870 make benchmark/bm_so_k_nucleotide.rb slow Closed 12/01/2013
Related to Ruby trunk - Bug #9382: [patch] add opt_aref_str and opt_aset_str Closed 01/08/2014

Associated revisions

Revision 43870
Added by Aman Gupta over 1 year ago

  • hash.c (hash_aset_str): Use rb_fstring() to de-duplicate hash string keys. Patch by Eric Wong. [Bug #8998]
  • test/ruby/test_hash.rb (class TestHash): test for above.

Revision 43870
Added by Aman Gupta over 1 year ago

  • hash.c (hash_aset_str): Use rb_fstring() to de-duplicate hash string keys. Patch by Eric Wong. [Bug #8998]
  • test/ruby/test_hash.rb (class TestHash): test for above.

History

#1 Updated by Eric Wong almost 2 years ago

Proposed patch to partially implement this, but I get segfaults (backtrace/dump coming) with "make check".
There probably needs to be some RGenGC-related calls/fixes for this.

Note: this patch does not avoid the short-lived, unfrozen string literal.
I don't currently know the parser/compiler code well enough to make
that optimization.

#2 Updated by Eric Wong almost 2 years ago

attaching output of "make check" and gdb backtrace

#3 Updated by Eric Wong almost 2 years ago

I think my failed patch exposes a bug with lazy sweep + rb_fstring.
Lazy sweep GC means the element remains in the frozen_string hash,

fstr1 = rb_fstring(str)
fstr1 goes out of scope
GC mark runs ...
fstr1 is eligible for lazy sweep
fstr2 = rb_fstring(str)
fstr2 is identical to fstr1
fstr1 is swept
fstr2 use attempted -> crash

#4 Updated by Eric Wong almost 2 years ago

The issue I had with my original patch is fixed by nobu with r43210
Thanks!

So my proposed patch should be safe to apply, but it's only a partial
implementation of the idea for this feature.

I don't think I'll have time+energy to implement this for the
parser/compiler.

#5 Updated by Eric Wong almost 2 years ago

Eric Wong normalperson@yhbt.net wrote:

So my proposed patch should be safe to apply, but it's only a partial
implementation of the idea for this feature.

While that's true, I haven't been able to measure performance
improvements from this (no real apps which are very hash-dependent).

Can anybody else?

#6 Updated by Aman Gupta over 1 year ago

I didn't realize MRI already froze string keys in hashes.

Your patch reduces long-lived strings in our rails app by ~11%:

$ ruby -rconfig/environment -e' GC.start; p ObjectSpace.count_objects[:T_STRING] '
173956

$ ruby -rconfig/environment -e' GC.start; p ObjectSpace.count_objects[:T_STRING] '
154750

I am inclined to merge it.

#7 Updated by Aman Gupta over 1 year ago

  • if (!OBJ_FROZEN(str))
  • *key = rb_fstring(str);

Do you know why the OBJ_FROZEN check is required here?

I tried to investigate and it appears this function is sometimes invoked with symbols.

#8 Updated by Aman Gupta over 1 year ago

  • Status changed from Open to Closed
  • % Done changed from 0 to 100

This issue was solved with changeset r43870.
Eric, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.


  • hash.c (hash_aset_str): Use rb_fstring() to de-duplicate hash string keys. Patch by Eric Wong. [Bug #8998]
  • test/ruby/test_hash.rb (class TestHash): test for above.

#9 Updated by Eric Wong over 1 year ago

"tmm1 (Aman Gupta)" ruby@tmm1.net wrote:

Issue #8998 has been updated by tmm1 (Aman Gupta).

Cool, I didn't check object lifetimes.
Any measurable impact on speed?

  • if (!OBJ_FROZEN(str))
  • *key = rb_fstring(str);

Do you know why the OBJ_FROZEN check is required here?

Some apps use frozen constant strings to speed up hash assignment for
common string keys. No point in having the extra hash lookup if it was
already a pre-frozen string (and it could break existing behavior).

Ideally it would be nice to transparently freeze strings used for hash
assignment in the parser so apps wouldn't have to add the ugly frozen
constants. Mongrel, and most probably every server descended from
Mongrel uses pre-frozen constants to speed up hash assignment.

I tried to investigate and it appears this function is sometimes
invoked with symbols.

Really? Yikes! That's strange. I didn't expect that, and I'm
not sure how it could be from reading rb_hash_aset()...

#10 Updated by Aman Gupta over 1 year ago

Seeing some occasional segfaults in CI after this change. Not quite sure what's up yet.

http://c5632.rubyci.org/~chkbuild/ruby-trunk/log/20131127T070302Z.log.html.gz

#3 0x0063fb97 in rb_bug (fmt=0x67363d "Segmentation fault") at error.c:341
#4 0x00557a16 in sigsegv (sig=11, info=0x95f9c7c, ctx=0x95f9cfc)
at signal.c:699
#5
#6 search_nonascii (p=0x1c ,
len=, enc=0x95df180) at string.c:202
#7 coderange_scan (p=0x1c ,
len=, enc=0x95df180) at string.c:232
#8 0x0057ab6e in rb_enc_str_coderange (str1=184779220, str2=173130540)
at string.c:376
#9 rb_str_comparable (str1=184779220, str2=173130540) at string.c:2403
#10 0x0057bb32 in rb_str_hash_cmp (a=184779220, b=173130540) at string.c:2367
#11 fstring_cmp (a=184779220, b=173130540) at string.c:161
#12 0x00561257 in find_entry (table=0x9603aa0, key=184779220,
value=0xbf9a818c) at st.c:387
#13 st_lookup (table=0x9603aa0, key=184779220, value=0xbf9a818c) at st.c:425
#14 0x00568062 in rb_fstring (str=184779220) at string.c:144
#15 0x004b00da in hash_aset_str (key=0xbf9a8234, val=0xbf9a8218,
arg=3214574164, existing=0) at hash.c:1267
#16 hash_aset_str_insert (key=0xbf9a8234, val=0xbf9a8218, arg=3214574164,
existing=0) at hash.c:1273
#17 0x00561dba in st_update (table=0xa069f50, key=184779220,
func=0x4b0040 , arg=3214574164) at st.c:908
#18 0x004b4c0f in tbl_update (hash=184779600, key=184779220, val=171144140)
at hash.c:380
#19 rb_hash_aset (hash=184779600, key=184779220, val=171144140) at hash.c:1316

#11 Updated by Eric Wong over 1 year ago

"tmm1 (Aman Gupta)" ruby@tmm1.net wrote:

Seeing some occasional segfaults in CI after this change. Not quite
sure what's up yet.

http://c5632.rubyci.org/~chkbuild/ruby-trunk/log/20131127T070302Z.log.html.gz

#3 0x0063fb97 in rb_bug (fmt=0x67363d "Segmentation fault") at error.c:341
#4 0x00557a16 in sigsegv (sig=11, info=0x95f9c7c, ctx=0x95f9cfc)
at signal.c:699
#5
#6 search_nonascii (p=0x1c ,
len=, enc=0x95df180) at string.c:202
#7 coderange_scan (p=0x1c ,
len=, enc=0x95df180) at string.c:232

So it seems GC is not preserving the hash used by rb_fstring, still. I
wonder if something else changed since r43210 which caused this, perhaps
r43718? I've never been a GC expert, especially not with the current GC.

#8 0x0057ab6e in rb_enc_str_coderange (str1=184779220, str2=173130540)
at string.c:376

#12 Updated by Aman Gupta over 1 year ago

The regression was indeed caused by r43718, and has been resolved with r43887.

#13 Updated by Koichi Sasada over 1 year ago

The regression was indeed caused by r43718, and has been resolved with r43887.

No. Before r43718, it works accidentally.

#14 Updated by Aman Gupta over 1 year ago

Oops, @ko1 is right.

The issue at hand is that fstrings were allowed to be shared strings. With rb_gc_mark(), the shared string was more likely to get marked (due to the mark_stack addition). But there were still cases where the shared string had already been lazy swept by the time the fstring was marked or resurrected.

With r43718, we resolved the issue once and for all by disallowing shared fstrings altogether.

#15 Updated by Charles Nutter over 1 year ago

I've implemented something like this for JRuby 9k. Both the interpreter and the compiler pre-freeze and dedup the keys, allowing them to go straight into literal hashes.

Performance is significantly improved by doing this:

Before:

$ jruby -rbenchmark -e "10.times { puts Benchmark.measure { hash = nil; 10_000_000.times { hash = { 'a' => 1, 'b' => 1, 'c' => 1, 'd' => 1, 'e' => 1 } } } }"
5.810000 0.100000 5.910000 ( 5.282000)
5.230000 0.030000 5.260000 ( 5.101000)
4.710000 0.020000 4.730000 ( 4.509000)
4.500000 0.030000 4.530000 ( 4.375000)
4.630000 0.030000 4.660000 ( 4.516000)
4.510000 0.020000 4.530000 ( 4.390000)
4.560000 0.030000 4.590000 ( 4.433000)
4.580000 0.030000 4.610000 ( 4.455000)
4.540000 0.020000 4.560000 ( 4.416000)
4.560000 0.030000 4.590000 ( 4.435000)

After:

$ jruby -rbenchmark -e "10.times { puts Benchmark.measure { hash = nil; 10_000_000.times { hash = { 'a' => 1, 'b' => 1, 'c' => 1, 'd' => 1, 'e' => 1 } } } }"
3.270000 0.100000 3.370000 ( 2.295000)
2.140000 0.020000 2.160000 ( 2.069000)
1.870000 0.010000 1.880000 ( 1.779000)
1.930000 0.020000 1.950000 ( 1.744000)
1.790000 0.010000 1.800000 ( 1.734000)
1.810000 0.010000 1.820000 ( 1.750000)
1.790000 0.010000 1.800000 ( 1.743000)
1.820000 0.020000 1.840000 ( 1.769000)
1.820000 0.010000 1.830000 ( 1.766000)
1.770000 0.010000 1.780000 ( 1.712000)

For reference, 2.1p0 on my system:

$ rvm ruby-2.1 do ruby -rbenchmark -e "10.times { puts Benchmark.measure { hash = nil; 10_000_000.times { hash = { 'a' => 1, 'b' => 1, 'c' => 1, 'd' => 1, 'e' => 1 } } } }"
9.060000 0.040000 9.100000 ( 9.098937)
9.030000 0.030000 9.060000 ( 9.064616)
8.980000 0.020000 9.000000 ( 9.007513)
9.050000 0.030000 9.080000 ( 9.078869)
9.250000 0.040000 9.290000 ( 9.292398)
9.020000 0.030000 9.050000 ( 9.053593)
9.080000 0.030000 9.110000 ( 9.113024)
8.970000 0.020000 8.990000 ( 8.986615)
8.870000 0.010000 8.880000 ( 8.884534)
8.940000 0.010000 8.950000 ( 8.954753)

When I have the commit done (needs a little cleanup...only a couple hours work at the moment) I will link here in case it is useful.

#16 Updated by Charles Nutter over 1 year ago

I ran into a small snag so I think it will be useful to have my JRuby commits here.

First, a background commit... adding a weak dedup cache: https://github.com/jruby/jruby/commit/926ca89075a4a4c84592add729531189263c143f

It's not particularly complicated; a double-weak hash synchronized for concurrency purposes.

Here's the commit that adds dedup to literal hashes with literal string keys: https://github.com/jruby/jruby/commit/aedcbc7b4024cf651a1df3bb65a8490a74a66562

This commit does all of the following:

  • Interpreter and compiler logic for literal hash with literal keys will only freeze-dup them once, using the dedup cache.
  • Hash will use dedup cache for all incoming strings.

The first problem I ran into was that there are tests in CSV that appear to depend on already-frozen strings not being deduplicated during hash insertion. This brought about the following failures:

1) Failure:
TestCSV::Interface#test_write_hash_with_string_keys [/Users/headius/projects/jruby/test/mri/csv/test_interface.rb:214]:
Expected "a" (oid=9726) to be the same as "a" (oid=9728).

2) Failure:
TestCSV::Interface::DifferentOFS#test_write_hash_with_string_keys [/Users/headius/projects/jruby/test/mri/csv/test_interface.rb:214]:
Expected "a" (oid=9726) to be the same as "a" (oid=9746).

3) Failure:
TestCSV::Row#test_to_hash [/Users/headius/projects/jruby/test/mri/csv/test_row.rb:304]:
Expected "A" (oid=9748) to be the same as "A" (oid=9750).

4) Failure:
TestCSV::Row::DifferentOFS#test_to_hash [/Users/headius/projects/jruby/test/mri/csv/test_row.rb:304]:
Expected "A" (oid=9752) to be the same as "A" (oid=9750).

I fixed these by adding a check to only dedup incoming strings if they weren't already frozen. I'm not sure if that's the right course of action or if the tests should be changed.

Then I ran into a more unusual snag. In RubySpec, there are tests for Hash#compare_by_identity/= that fail if I dedup incoming strings, since they test that the same string content in two different objects can hold two different values in the Hash. Specifically:

1)
Hash#compare_by_identity perists over #dups FAILED
Expected {"foo"=>:glark}
to equal {"foo"=>:bar, "foo"=>:glark}

/Users/headius/projects/jruby/spec/ruby/core/hash/compare_by_identity_spec.rb:77:in (root)'
org/jruby/RubyBasicObject.java:1573:in
instance_eval'
org/jruby/RubyEnumerable.java:1437:in all?'
org/jruby/RubyFixnum.java:269:in
times'
org/jruby/RubyArray.java:1556:in each'
/Users/headius/projects/jruby/spec/ruby/core/hash/compare_by_identity_spec.rb:2:in
(root)'
/Users/headius/projects/jruby/spec/ruby/core/hash/compare_by_identity_spec.rb:1:in (root)'
org/jruby/RubyKernel.java:881:in
load'
org/jruby/RubyBasicObject.java:1573:in instance_eval'
org/jruby/RubyArray.java:1556:in
each'

2)
Hash#compare_by_identity persists over #clones FAILED
Expected {"foo"=>:glark}
to equal {"foo"=>:bar, "foo"=>:glark}

/Users/headius/projects/jruby/spec/ruby/core/hash/compare_by_identity_spec.rb:84:in (root)'
org/jruby/RubyBasicObject.java:1573:in
instance_eval'
org/jruby/RubyEnumerable.java:1437:in all?'
org/jruby/RubyFixnum.java:269:in
times'
org/jruby/RubyArray.java:1556:in each'
/Users/headius/projects/jruby/spec/ruby/core/hash/compare_by_identity_spec.rb:2:in
(root)'
/Users/headius/projects/jruby/spec/ruby/core/hash/compare_by_identity_spec.rb:1:in (root)'
org/jruby/RubyKernel.java:881:in
load'
org/jruby/RubyBasicObject.java:1573:in instance_eval'
org/jruby/RubyArray.java:1556:in
each'

I fixed this issue by only deduping when compare_by_identity is false, but I'm not sure if it's correct.

So the basic question that came out of my experiment:

  • Should string freeze-duping in Hash#[]= always dedup, regardless of whether the string has already been frozen or the Hash has compare_by_identity == true? Or else what combination of those conditions should lead to deduping?

#17 Updated by Eric Wong over 1 year ago

  • Should string freeze-duping in Hash#[]= always dedup, regardless of whether the string has already been frozen or the Hash has compare_by_identity == true? Or else what combination of those conditions should lead to deduping?

MRI doesn't replace/alter the key at all if compare_by_identity is true.
Thus keys remain mutable strings in the case of compare_by_identity.

Also, in my original proposed patch, it only deduped when a new frozen
string was required, so there's almost zero chance of incompatibility.
Pre-frozen strings are used as-is when used as keys in all cases.

Btw, in addition to the current optimization and in lieu of my original
patch, I also have a proposed patch in
https://bugs.ruby-lang.org/issues/9188 which also optimizes aref along
with aset only when literal strings are used. This means we won't bust
the fstring cache with dynamically-generated strings, but string
literals in the source are not duplicated.

I'm not sure what the real-world performance impact is, but I suspect
Rails apps will benefit from that.

Also available in: Atom PDF