[ruby-core:121670] [Ruby Feature#21268] Implement a lock-free hash set for fstring table
Issue #21268 has been reported by jhawthorn (John Hawthorn). ---------------------------------------- Feature #21268: Implement a lock-free hash set for fstring table https://bugs.ruby-lang.org/issues/21268 * Author: jhawthorn (John Hawthorn) * Status: Open * Assignee: jhawthorn (John Hawthorn) * Target version: 3.5 ---------------------------------------- I would like to propose replacing the st_table used for fstrings (de-duplicated frozen strings) with a lock-free hash set to have improved performance in a Ractor environment. Fstrings are shared between Ractors, and can be looked up concurrently by multiple Ractors, it's desirable to be able to do this work in parallel. There should be no change visible to users (other than improved performance :) ) Previously this table used the VM lock (`RB_VM_LOCK_ENTER`, not the GVL) to serialize access. I first experimented with using a reader-writer lock, but that was a little awkward to use as it was easy to cause a deadlock between the new lock, `RB_VM_LOCK_ENTER`, and `rb_vm_barrier()`. An RW lock also can cause cache ping ponging (though striping can help). Lastly, this table is somewhat write-heavy, so it's desirable for even writes to be possible in parallel. A lock free table is not necessarily faster than a table with locking, but due to these constraints and usage I believe a lock-free table is desirable here. The design is a fairly standard open-addressing hash table with quadratic probing. Similar to our existing st_table or id_table. Deletes (which happen on GC) replace existing keys with a tombstone, which is the only type of update which can occur. Tombstones are only cleared out on rebuilds (necessary for the lock-free design I used). The set is wait-free for lookup (the thread performing lookup always makes progress) and lock-free for insert (we may sometimes retry if another thread made a concurrent insertion, we never spin on a lock) unless resizing/rebuilding. The implementation itself is at https://github.com/ruby/ruby/pull/12921 and details are within. I will include benchmarks in a comment below. -- https://bugs.ruby-lang.org/
Issue #21268 has been updated by jhawthorn (John Hawthorn). I've added two new benchmarks to measure this. This is on my M2 macbook air. When run in Ractors inserting is ~3x faster and lookups are ~8x faster. In a single Ractor performance is about the same. ``` compare-ruby: ruby 3.5.0dev (2025-04-15T23:29:23Z master 2cf95e2e04) +PRISM [arm64-darwin24] built-ruby: ruby 3.5.0dev (2025-04-16T03:10:21Z ractor_fstring_has.. 20acd942ae) +PRISM [arm64-darwin24] # Iteration per second (i/s) | |compare-ruby|built-ruby| |:----------------------|-----------:|---------:| |ractor_fstring_random | 0.567| 1.671| | | -| 2.95x| |ractor_fstring_same | 1.132| 9.917| | | -| 8.76x| # Iteration per second (i/s) | |compare-ruby|built-ruby| |:---------------|-----------:|---------:| |fstring_random | 1.499| 1.383| | | 1.08x| -| |fstring_same | 2.141| 2.254| | | -| 1.05x| ``` ---------------------------------------- Feature #21268: Implement a lock-free hash set for fstring table https://bugs.ruby-lang.org/issues/21268#change-112730 * Author: jhawthorn (John Hawthorn) * Status: Open * Assignee: jhawthorn (John Hawthorn) * Target version: 3.5 ---------------------------------------- I would like to propose replacing the st_table used for fstrings (de-duplicated frozen strings) with a lock-free hash set to have improved performance in a Ractor environment. Fstrings are shared between Ractors, and can be looked up concurrently by multiple Ractors, it's desirable to be able to do this work in parallel. There should be no change visible to users (other than improved performance :) ) Previously this table used the VM lock (`RB_VM_LOCK_ENTER`, not the GVL) to serialize access. I first experimented with using a reader-writer lock, but that was a little awkward to use as it was easy to cause a deadlock between the new lock, `RB_VM_LOCK_ENTER`, and `rb_vm_barrier()`. An RW lock also can cause cache ping ponging (though striping can help). Lastly, this table is somewhat write-heavy, so it's desirable for even writes to be possible in parallel. A lock free table is not necessarily faster than a table with locking, but due to these constraints and usage I believe a lock-free table is desirable here. The design is a fairly standard open-addressing hash table with quadratic probing. Similar to our existing st_table or id_table. Deletes (which happen on GC) replace existing keys with a tombstone, which is the only type of update which can occur. Tombstones are only cleared out on rebuilds (necessary for the lock-free design I used). The set is wait-free for lookup (the thread performing lookup always makes progress) and lock-free for insert (we may sometimes retry if another thread made a concurrent insertion, we never spin on a lock) unless resizing/rebuilding. The implementation itself is at https://github.com/ruby/ruby/pull/12921 and details are within. I will include benchmarks in a comment below. -- https://bugs.ruby-lang.org/
participants (1)
-
jhawthorn (John Hawthorn)