path: root/st.c
AgeCommit message (Collapse)Author
2021-06-17Adjust styles [ci skip]Nobuyoshi Nakada
* --braces-after-func-def-line * --dont-cuddle-else * --procnames-start-lines * --space-after-for * --space-after-if * --space-after-while
2021-04-11st.c: skip all deleted entries [Bug #17779]tompng (tomoya ishida)
Update the start entry skipping all already deleted entries. Fixes performance issue of `Hash#first` in a certain case.
2021-01-19Replace "iff" with "if and only if"Gannon McGibbon
iff means if and only if, but readers without that knowledge might assume this to be a spelling mistake. To me, this seems like exclusionary language that is unnecessary. Simply using "if and only if" instead should suffice. Notes: Merged:
2020-11-30[DOC] Fixed st_udpate comment [ci skip]Nobuyoshi Nakada
Clarified that the first and second arguments to the callback function are pointers to the KEY and the VALUE, but not those values themselves.
2020-10-17sync RClass::ext::iv_index_tblKoichi Sasada
iv_index_tbl manages instance variable indexes (ID -> index). This data structure should be synchronized with other ractors so introduce some VM locks. This patch also introduced atomic ivar cache used by set/getinlinecache instructions. To make updating ivar cache (IVC), we changed iv_index_tbl data structure to manage (ID -> entry) and an entry points serial and index. IVC points to this entry so that cache update becomes atomically. Notes: Merged:
2020-08-14Enable arm64 optimizations that exist for power/x86 (#3393)AGSaidi
* Enable unaligned accesses on arm64 64-bit Arm platforms support unaligned accesses. Running the string benchmarks this change improves performance by an average of 1.04x, min .96x, max 1.21x, median 1.01x * arm64 enable gc optimizations Similar to x86 and powerpc optimizations. | |compare-ruby|built-ruby| |:------|-----------:|---------:| |hash1 | 0.225| 0.237| | | -| 1.05x| |hash2 | 0.110| 0.110| | | 1.00x| -| * vm_exec.c: improve performance for arm64 | |compare-ruby|built-ruby| |:------------------------------|-----------:|---------:| |vm_array | 26.501M| 27.959M| | | -| 1.06x| |vm_attr_ivar | 21.606M| 31.429M| | | -| 1.45x| |vm_attr_ivar_set | 21.178M| 26.113M| | | -| 1.23x| |vm_backtrace | 6.621| 6.668| | | -| 1.01x| |vm_bigarray | 26.205M| 29.958M| | | -| 1.14x| |vm_bighash | 504.155k| 479.306k| | | 1.05x| -| |vm_block | 16.692M| 21.315M| | | -| 1.28x| |block_handler_type_iseq | 5.083| 7.004| | | -| 1.38x| Notes: Merged-By: nurse <>
2020-06-04Removed no longer used constants [Bug #16934]Nobuyoshi Nakada
`RESERVED_HASH_VAL` and `RESERVED_HASH_SUBSTITUTION_VAL` have not been used directly in hash.c since 72825c35b0d8.
2020-03-16Adjusted indents [ci skip]Nobuyoshi Nakada
2020-03-11Fix typos (#2958)K.Takata
* Fix a typo * Fix typos in st.[ch] Notes: Merged-By: k0kubun <>
2020-02-27st.c: remove variables that are no longer usedYusuke Endoh
to suppress a warning "variable 'check' set but not used"
2020-02-26kill ST_DEBUG [Bug #16521]卜部昌平
This compile-time option has been broken for years (at least since commit 4663c224fa6c925ce54af32fd1c1cbac9508f5ec, according to git bisect). Let's delete codes that no longer work. Notes: Merged:
2020-02-07more on NULL versus functions.卜部昌平
Function pointers are not void*. See also ce4ea956d24eab5089a143bba38126f2b11b55b6 8427fca49bd85205f5a8766292dd893f003c0e48
2019-12-26decouple internal.h headers卜部昌平
Saves comitters' daily life by avoid #include-ing everything from internal.h to make each file do so instead. This would significantly speed up incremental builds. We take the following inclusion order in this changeset: 1. "ruby/config.h", where _GNU_SOURCE is defined (must be the very first thing among everything). 2. RUBY_EXTCONF_H if any. 3. Standard C headers, sorted alphabetically. 4. Other system headers, maybe guarded by #ifdef 5. Everything else, sorted alphabetically. Exceptions are those win32-related headers, which tend not be self- containing (headers have inclusion order dependencies). Notes: Merged:
2019-12-20Fixed misspellingsNobuyoshi Nakada
Fixed misspellings reported at [Bug #16437], only in ruby and rubyspec.
2019-10-21st: Do error check only on non-RubyK.Takata
Notes: Merged:
2019-10-21st: Add NULL checkingK.Takata
These are found by Coverity. Notes: Merged:
2019-09-22st.c: Use rb_st_* prefix instead of st_* (#2479)Yusuke Endoh
The original st.c was public domain hash table implementation, but Ruby's st.c is highly modified, and its data structure is not compatiblie with the original one. Therefore, when creating an extension library to wrap C code that uses the original st.c, the symbols conflict, which leads to segfault. This changes the prefix `st_*` of st.c functions to `rb_st_*` for reflecting that they are specific to Ruby's, and avoid symbol conflicts. Notes: Merged-By: mame <>
2019-09-22st.c (st_add_direct_with_hash): make it "static inline"Yusuke Endoh
It was originally static inline, but seemed to be accidentally published at 8f675cdd00e2c5b5a0f143f5e508dbbafdb20ccd.
2019-08-28optimize get_power2 [Feature #15631]pavel
2019-08-27struct st_hash_type now free from ANYARGS卜部昌平
After 5e86b005c0f2ef30df2f9906c7e2f3abefe286a2, I now think ANYARGS is dangerous and should be extinct. This commit adds function prototypes for struct st_hash_type. Honestly I don't understand why they were commented out at the first place.
2019-08-27st_foreach now free from ANYARGS卜部昌平
After 5e86b005c0f2ef30df2f9906c7e2f3abefe286a2, I now think ANYARGS is dangerous and should be extinct. This commit deletes ANYARGS from st_foreach. I strongly believe that this commit should have had come with b0af0592fdd9e9d4e4b863fde006d67ccefeac21, which added extra parameter to st_foreach callbacks.
2019-04-20Add `GC.compact` again.tenderlove
🙏 git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2019-04-17Reverting compaction for nowtenderlove
For some reason symbols (or classes) are being overridden in trunk git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2019-04-17Adding `GC.compact` and compacting GC support.tenderlove
This commit adds the new method `GC.compact` and compacting GC support. Please see this issue for caveats: [Feature #15626] git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2019-04-10Reverting all commits from r67479 to r67496 because of CI failureskazu
Because hard to specify commits related to r67479 only. So please commit again. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2019-04-09Adding `GC.compact` and compacting GC support.tenderlove
This commit adds the new method `GC.compact` and compacting GC support. Please see this issue for caveats: [Feature #15626] git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2019-01-15st.c (rb_hash_bulk_insert_into_st_table): avoid out-of-bounds writemame
"hash_bulk_insert" first expands the table, but the target size was wrong: it was calculated by "num_entries + (size to buld insert)", but it was wrong when "num_entries < entries_bound", i.e., it has a deleted entry. "hash_bulk_insert" adds the given entries from entries_bound, which led to out-of-bounds write access. [Bug #15536] As a simple fix, this commit changes the calculation to "entries_bound + size". I'm afraid if this might be inefficient, but I think it is safe anyway. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-12-07Adjust reserved hash valuesnobu
The reserved hash values in hash.c must be consistend with st.c. [ruby-core:90356] [Bug #15389] git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-11-08st.c: bin might be zeroshyouhei
When EMPTY_OR_DELETED_BIN_P(bin) is true, it is a wrong idea to subtract ENTRY_BASE from it. Delay doing so until we are sure to be safe. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-11-08avoid (size_t)-- (2nd try)shyouhei
The decrements overflow and these variables remain ~0 when leaving the while loops. They are not fatal by accident, but better replace with ordinal for loops. See also: git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-11-08svn merge -r 65625:65623 .shyouhei
Was breaking make test-all git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-11-08st.c: fix comparison between signed and unsignedshyouhei
git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-11-08avoid (size_t)--shyouhei
The decrements overflow and these variables remain ~0 when leaving the while loops. They are not fatal by accident, but better replace with ordinal for loops. See also: git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-11-08st.c: straight-forward comparison of charactersshyouhei
These functions are used in strcasehash, which is used to store encoding names. Encoding names often include hyphens (e.g. "UTF-8"), and ` '-' - 'A' ` is negative (cannot express in unsigned int). Don't be tricky, just do what to do. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-11-08st.c: suppress integer overlow warningsshyouhei
This `i += h;` overflows. Don't know the intention of the operation, so just suppress UBSAN. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-11-07blacklist UBSAN's unsigned integer overflowshyouhei
Integer overflow for unsigned types are fully defined in C. They are not always problematic (but not always OK). These functions in this changeset intentionally utilizes that behaviour. Blacklist from UBSAN checks for better output. See also: git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-10-30support theap for T_HASH. [Feature #14989]ko1
* hash.c, internal.h: support theap for small Hash. Introduce RHASH_ARRAY (li_table) besides st_table and small Hash (<=8 entries) are managed by an array data structure. This array data can be managed by theap. If st_table is needed, then converting array data to st_table data. For st_table using code, we prepare "stlike" APIs which accepts hash value and are very similar to st_ APIs. This work is based on the GSoC achievement by tacinight <> and refined by ko1. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-05-27st.c: remove redundant export declarationk0kubun
rb_hash_bulk_insert is added to official C API in r63488. It's no longer exported only for MJIT. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-02-13st.c: retry operations if rebuiltnormal
Calling the .eql? and .hash methods during a Hash operation can result in a thread switch or a signal handler to run: allowing one execution context to rebuild the hash table while another is still reading or writing the table. This results in a use-after-free bug affecting the thread_safe-0.3.6 test suite and likely other bugs. This bug did not affect users of commonly keys (String, Symbol, Fixnum) as those are optimized to avoid method dispatch for .eql? and .hash methods. A separate version of this change needs to be ported to Ruby 2.3.x which had a different implementation of st.c but was affected by the same bug. * st.c: Add comment about table rebuilding during comparison. (DO_PTR_EQUAL_CHECK): New macro. (REBUILT_TABLE_ENTRY_IND, REBUILT_TABLE_BIN_IND): New macros. (find_entry, find_table_entry_ind, find_table_bin_ind): Use new macros. Return the rebuild flag. (find_table_bin_ptr_and_reserve): Ditto. (st_lookup, st_get_key, st_insert, st_insert2): Retry the operation if the table was rebuilt. (st_general_delete, st_shift, st_update, st_general_foreach): Ditto. (st_rehash_linear, st_rehash_indexed): Use DO_PTR_EQUAL_CHECK. Return the rebuild flag. (st_rehash): Retry the operation if the table was rebuilt. [ruby-core:85510] [Ruby trunk Bug#14357] Thanks to Vit Ondruch for reporting the bug. From: Vladimir Makarov <> git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-02-04mjit_compile.c: merge initial JIT compilerk0kubun
which has been developed by Takashi Kokubun <takashikkbn@gmail> as YARV-MJIT. Many of its bugs are fixed by wanabe <>. This JIT compiler is designed to be a safe migration path to introduce JIT compiler to MRI. So this commit does not include any bytecode changes or dynamic instruction modifications, which are done in original MJIT. This commit even strips off some aggressive optimizations from YARV-MJIT, and thus it's slower than YARV-MJIT too. But it's still fairly faster than Ruby 2.5 in some benchmarks (attached below). Note that this JIT compiler passes `make test`, `make test-all`, `make test-spec` without JIT, and even with JIT. Not only it's perfectly safe with JIT disabled because it does not replace VM instructions unlike MJIT, but also with JIT enabled it stably runs Ruby applications including Rails applications. I'm expecting this version as just "initial" JIT compiler. I have many optimization ideas which are skipped for initial merging, and you may easily replace this JIT compiler with a faster one by just replacing mjit_compile.c. `mjit_compile` interface is designed for the purpose. update dependencies for mjit_compile.c. internal.h: declare `rb_vm_insn_addr2insn` for MJIT. vm.c: exclude some definitions if `-DMJIT_HEADER` is provided to compiler. This avoids to include some functions which take a long time to compile, e.g. vm_exec_core. Some of the purpose is achieved in transform_mjit_header.rb (see `IGNORED_FUNCTIONS`) but others are manually resolved for now. Load mjit_helper.h for MJIT header. mjit_helper.h: New. This is a file used only by JIT-ed code. I'll refactor `mjit_call_cfunc` later. vm_eval.c: add some #ifdef switches to skip compiling some functions like Init_vm_eval. win32/mkexports.rb: export thread/ec functions, which are used by MJIT. include/ruby/defines.h: add MJIT_FUNC_EXPORTED macro alis to clarify that a function is exported only for MJIT. array.c: export a function used by MJIT. bignum.c: ditto. class.c: ditto. compile.c: ditto. error.c: ditto. gc.c: ditto. hash.c: ditto. iseq.c: ditto. numeric.c: ditto. object.c: ditto. proc.c: ditto. re.c: ditto. st.c: ditto. string.c: ditto. thread.c: ditto. variable.c: ditto. vm_backtrace.c: ditto. vm_insnhelper.c: ditto. vm_method.c: ditto. I would like to improve maintainability of function exports, but I believe this way is acceptable as initial merging if we clarify the new exports are for MJIT (so that we can use them as TODO list to fix) and add unit tests to detect unresolved symbols. I'll add unit tests of JIT compilations in succeeding commits. Author: Takashi Kokubun <> Contributor: wanabe <> Part of [Feature #14235] --- * Known issues * Code generated by gcc is faster than clang. The benchmark may be worse in macOS. Following benchmark result is provided by gcc w/ Linux. * Performance is decreased when Google Chrome is running * JIT can work on MinGW, but it doesn't improve performance at least in short running benchmark. * Currently it doesn't perform well with Rails. We'll try to fix this before release. --- * Benchmark reslts Benchmarked with: Intel 4.0GHz i7-4790K with 16GB memory under x86-64 Ubuntu 8 Cores - 2.0.0-p0: Ruby 2.0.0-p0 - r62186: Ruby trunk (early 2.6.0), before MJIT changes - JIT off: On this commit, but without `--jit` option - JIT on: On this commit, and with `--jit` option ** Optcarrot fps Benchmark: | |2.0.0-p0 |r62186 |JIT off |JIT on | |:--------|:--------|:--------|:--------|:--------| |fps |37.32 |51.46 |51.31 |58.88 | |vs 2.0.0 |1.00x |1.38x |1.37x |1.58x | ** MJIT benchmarks Benchmark: (Original: | |2.0.0-p0 |r62186 |JIT off |JIT on | |:----------|:--------|:--------|:--------|:--------| |aread |1.00 |1.09 |1.07 |2.19 | |aref |1.00 |1.13 |1.11 |2.22 | |aset |1.00 |1.50 |1.45 |2.64 | |awrite |1.00 |1.17 |1.13 |2.20 | |call |1.00 |1.29 |1.26 |2.02 | |const2 |1.00 |1.10 |1.10 |2.19 | |const |1.00 |1.11 |1.10 |2.19 | |fannk |1.00 |1.04 |1.02 |1.00 | |fib |1.00 |1.32 |1.31 |1.84 | |ivread |1.00 |1.13 |1.12 |2.43 | |ivwrite |1.00 |1.23 |1.21 |2.40 | |mandelbrot |1.00 |1.13 |1.16 |1.28 | |meteor |1.00 |2.97 |2.92 |3.17 | |nbody |1.00 |1.17 |1.15 |1.49 | |nest-ntimes|1.00 |1.22 |1.20 |1.39 | |nest-while |1.00 |1.10 |1.10 |1.37 | |norm |1.00 |1.18 |1.16 |1.24 | |nsvb |1.00 |1.16 |1.16 |1.17 | |red-black |1.00 |1.02 |0.99 |1.12 | |sieve |1.00 |1.30 |1.28 |1.62 | |trees |1.00 |1.14 |1.13 |1.19 | |while |1.00 |1.12 |1.11 |2.41 | ** Discourse's script/bench.rb Benchmark: NOTE: Rails performance was somehow a little degraded with JIT for now. We should fix this. (At least I know opt_aref is performing badly in JIT and I have an idea to fix it. Please wait for the fix.) *** JIT off Your Results: (note for timings- percentile is first, duration is second in millisecs) categories_admin: 50: 17 75: 18 90: 22 99: 29 home_admin: 50: 21 75: 21 90: 27 99: 40 topic_admin: 50: 17 75: 18 90: 22 99: 32 categories: 50: 35 75: 41 90: 43 99: 77 home: 50: 39 75: 46 90: 49 99: 95 topic: 50: 46 75: 52 90: 56 99: 101 *** JIT on Your Results: (note for timings- percentile is first, duration is second in millisecs) categories_admin: 50: 19 75: 21 90: 25 99: 33 home_admin: 50: 24 75: 26 90: 30 99: 35 topic_admin: 50: 19 75: 20 90: 25 99: 30 categories: 50: 40 75: 44 90: 48 99: 76 home: 50: 42 75: 48 90: 51 99: 89 topic: 50: 49 75: 55 90: 58 99: 99 git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-01-19st_hashtype_num marked as staticshyouhei
git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2018-01-15__builtin_assume_aligned for *(foo *) castsshyouhei
These casts are guarded. Must be safe to assume alignments. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-12-30hash literal deduplicates like Hash#[]=normal
From: Eric Wong <> * hash.c (rb_hash_key_str): new function (hash_aset_str): use rb_hash_key_str * internal.h: add rb_hash_key_str * st.c (st_stringify): use rb_hash_key_str * test/ruby/test_hash.rb (test_NEWHASH_fstring_key): dynamic key [ruby-core:84554] [Feature #14258] git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-12-19Revert "Improve performance of creating Hash object"watson1978
This reverts commit r61309 Because it was unstable on mswin CI. [ruby-dev:50370][Bug #14203] git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-12-19st.c: fix upnobu
* st.c (_st_table_list, _st_table_pool): symbols beginning with an underscore and a lower letter are preserved by the standard. * st.c (get_st_table): protoized. * st.c (st_insert_generic): adjust local variable type to an argument argc. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-12-18st.c: no C99 commentnobu
git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-12-18Improve performance of creating Hash objectwatson1978
When generate Hash object, the heap area of st_table will be always allocated in internally and seems it take a time. To improve performance of creating Hash object, this patch will reduce count of allocating heap areas for st_table by reuse them. Performance of creating Hash literal -> 1.53 times faster. [Fix GH-1766] [ruby-core:84008] [Feature #14146] ### Environment * OS : macOS 10.13.1 * CPU : 1.4 GHz Intel Core i7 * Compiler : Apple LLVM version 9.0.0 (clang-900.0.39) ### Before $ ./miniruby -v -I. -I../benchmark-ips/lib ~/tmp/bench/literal.rb ruby 2.5.0dev (2017-11-28 hash 60926) [x86_64-darwin17] Warming up -------------------------------------- Hash literal 51.544k i/100ms Calculating ------------------------------------- Hash literal 869.132k (± 1.1%) i/s - 4.381M in 5.041574s ### After $ ./miniruby -v -I. -I../benchmark-ips/lib ~/tmp/bench/literal.rb ruby 2.5.0dev (2017-11-28 hash 60926) [x86_64-darwin17] Warming up -------------------------------------- Hash literal 63.068k i/100ms Calculating ------------------------------------- Hash literal 1.328M (± 2.3%) i/s - 6.685M in 5.037861s ### Test code require 'benchmark/ips' Benchmark.ips do |x| "Hash literal" do |loop| count = 0 while count < loop hash = {foo: 12, bar: 34, baz: 56} count += 1 end end end git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-09-05st.c: fix num_entriesnobu
* st.c (st_insert2): should manage num_entries when the key is undefined, as well as st_insert(). git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-09-05st.c: fix false assertionsnobu
* st.c: split assertion conditions. * st.c (rb_hash_bulk_insert): the number of arguments should be even. git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-09-05optimize rb_hash_bulk_insert to generally outperform 2.4.shyouhei
Specialized routine for small linear-probling hash instances to boost creation of such things [Bug #13861] Signed-off-by: Urabe, Shyouhei <> git-svn-id: svn+ssh:// b2dd03c8-39d4-4d8f-98ff-823fe69b080e