https://git.ruby-lang.org/ruby.git/commit/?id=9f9045123e

From 9f9045123efefbd11dd397b4d59596290765feec Mon Sep 17 00:00:00 2001
From: "tompng (tomoya ishida)" <tomoyapenguin@g...>
Date: Sun, 11 Apr 2021 19:04:31 +0900
Subject: st.c: skip all deleted entries [Bug #17779]

Update the start entry skipping all already deleted entries.
Fixes performance issue of `Hash#first` in a certain case.
---
 benchmark/hash_first.yml | 11 +++++++++++
 st.c                     |  9 +++++++--
 2 files changed, 18 insertions(+), 2 deletions(-)
 create mode 100644 benchmark/hash_first.yml

diff --git a/benchmark/hash_first.yml b/benchmark/hash_first.yml
new file mode 100644
index 0000000..c26df1a
--- /dev/null
+++ b/benchmark/hash_first.yml
@@ -0,0 +1,11 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/hash_first.yml#L1
+prelude: |
+  hash1 = 1_000_000.times.to_h { [rand, true]}
+  hash2 = hash1.dup
+  hash2.keys[1..100_000].each { hash2.delete _1 }
+  hash2.delete hash2.first[0]
+
+benchmark:
+  hash1: hash1.first
+  hash2: hash2.first
+
+loop_count: 100_000
diff --git a/st.c b/st.c
index 5b178f6..9919f0a 100644
--- a/st.c
+++ b/st.c
@@ -1244,8 +1244,13 @@ update_range_for_deleted(st_table *tab, st_index_t n) https://github.com/ruby/ruby/blob/trunk/st.c#L1244
 {
     /* Do not update entries_bound here.  Otherwise, we can fill all
        bins by deleted entry value before rebuilding the table.  */
-    if (tab->entries_start == n)
-        tab->entries_start = n + 1;
+    if (tab->entries_start == n) {
+        st_index_t start = n + 1;
+        st_index_t bound = tab->entries_bound;
+        st_table_entry *entries = tab->entries;
+        while (start < bound && DELETED_ENTRY_P(&entries[start])) start++;
+        tab->entries_start = start;
+    }
 }
 
 /* Delete entry with KEY from table TAB, set up *VALUE (unless
-- 
cgit v1.1


--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/