| Age | Commit message (Collapse) | Author |
|---|
| [Bug #21438] Previously GC could trigger a table rebuild of the generic fields st_table in the middle of calling the st_update callback. This could cause entries to be reallocated or rearranged and the update to be for the wrong entry. This commit adds an assertion to make that case easier to detect, and replaces the st_update with a separate st_lookup and st_insert. Co-authored-by: Aaron Patterson <[email protected]> Co-authored-by: Jean Boussier <[email protected]> Notes: Merged: https://.com/ruby/ruby/pull/13589 |
| Fixes [Bug #21201] This change addresses a performance regression where defining methods inside `refine` blocks caused severe slowdowns. The issue was due to `rb_clear_all_refinement_method_cache()` triggering a full object space scan via `rb_objspace_each_objects` to find and invalidate affected callcaches, which is very inefficient. To fix this, I introduce `vm->cc_refinement_table` to track callcaches related to refinements. This allows us to invalidate only the necessary callcaches without scanning the entire heap, resulting in significant performance improvement. Notes: Merged: https://.com/ruby/ruby/pull/13077 |
| Ivars will longer be the only thing stored inline via shapes, so keeping the `iv_index` and `ivptr` names would be confusing. Instance variables won't be the only thing stored inline via shapes, so keeping the `ivptr` name would be confusing. `field` encompass anything that can be stored in a VALUE array. Similarly, `gen_ivtbl` becomes `gen_fields_tbl`. Notes: Merged: https://.com/ruby/ruby/pull/13159 |
| Notes: Merged: https://.com/ruby/ruby/pull/13208 |
| Now that we have a `set_table` implementation, we can use it to track const caches and save some memory. We could even save some more memory if `numtable` didn't store a copy of the `hash` and instead recomputed it every time, but this is a quick win. Notes: Merged: https://.com/ruby/ruby/pull/13184 |
| Set has been an autoloaded standard library since Ruby 3.2. The standard library Set is less efficient than it could be, as it uses Hash for storage, which stores unnecessary values for each key. Implementation details: * Core Set uses a modified version of `st_table`, named `set_table`. than `s/st_/set_/`, the main difference is that the stored records do not have values, making them 1/3 smaller. `st_table_entry` stores `hash`, `key`, and `record` (value), while `set_table_entry` only stores `hash` and `key`. This results in large sets using ~33% less memory compared to stdlib Set. For small sets, core Set uses 12% more memory (160 byte object slot and 64 malloc bytes, while stdlib set uses 40 for Set and 160 for Hash). More memory is used because the set_table is embedded and 72 bytes in the object slot are currently wasted. Hopefully we can make this more efficient and have it stored in an 80 byte object slot in the future. * All methods are implemented as cfuncs, except the pretty_print methods, which were moved to `lib/pp.rb` (which is where the pretty_print methods for other core classes are defined). As is typical for core classes, internal calls call C functions and not Ruby methods. For example, to check if something is a Set, `rb_obj_is_kind_of` is used, instead of calling `is_a?(Set)` on the related object. * Almost all methods use the same algorithm that the pure-Ruby implementation used. The exception is when calling `Set#divide` with a block with 2-arity. The pure-Ruby method used tsort to implement this. I developed an algorithm that only allocates a single intermediate hash and does not need tsort. * The `flatten_merge` protected method is no longer necessary, so it is not implemented (it could be). * Similar to Hash/Array, subclasses of Set are no longer reflected in `inspect` output. * RDoc from stdlib Set was moved to core Set, with minor updates. This includes a comprehensive benchmark suite for all public Set methods. As you would expect, the native version is faster in the vast majority of cases, and multiple times faster in many cases. There are a few cases where it is significantly slower: * Set.new with no arguments (~1.6x) * Set#compare_by_identity for small sets (~1.3x) * Set#clone for small sets (~1.5x) * Set#dup for small sets (~1.7x) These are slower as Set does not currently use the AR table optimization that Hash does, so a new set_table is initialized for each call. I'm not sure it's worth the complexity to have an AR table-like optimization for small sets (for hashes it makes sense, as small hashes are used everywhere in Ruby). The rbs and repl_type_completor bundled gems will need updates to support core Set. The pull request marks them as allowed failures. This passes all set tests with no changes. The following specs needed modification: * Modifying frozen set error message (changed for the better) * `Set#divide` when passed a 2-arity block no longer yields the same object as both the first and second argument (this seems like an issue with the previous implementation). * Set-like objects that override `is_a?` such that `is_a?(Set)` return `true` are no longer treated as Set instances. * `Set.allocate.hash` is no longer the same as `nil.hash` * `Set#join` no longer calls `Set#to_a` (it calls the underlying C function). * `Set#flatten_merge` protected method is not implemented. Previously, `set.rb` added a `SortedSet` autoload, which loads `set/sorted_set.rb`. This replaces the `Set` autoload in `prelude.rb` with a `SortedSet` autoload, but I recommend removing it and `set/sorted_set.rb`. This moves `test/set/test_set.rb` to `test/ruby/test_set.rb`, reflecting that switch to a core class. This does not move the spec files, as I'm not sure how they should be handled. Internally, this uses the st_* types and functions as much as possible, and only adds set_* types and functions as needed. The underlying set_table implementation is stored in st.c, but there is no public C-API for it, nor is there one planned, in order to keep the ability to change the internals going forward. For internal uses of st_table with Qtrue values, those can probably be replaced with set_table. To do that, include internal/set_table.h. To handle symbol visibility (rb_ prefix), internal/set_table.h uses the same macro approach that include/ruby/st.h uses. The Set class (rb_cSet) and all methods are defined in set.c. There isn't currently a C-API for the Set class, though C-API functions can be added as needed going forward. Implements [Feature #21216] Co-authored-by: Jean Boussier <[email protected]> Co-authored-by: Oliver Nutter <[email protected]> |
| [Bug #21170] st_table reserves -1 as a special hash value to indicate that an entry has been deleted. So that that's a valid value to be returned from the hash function, do_hash replaces -1 with 0 so that it is not mistaken for the sentinel. Previously, when upgrading an AR table to an ST table, rb_st_add_direct_with_hash was used which did not perform the same conversion, this could lead to a hash in a broken state where one if its entries which was supposed to exist being marked as a tombstone. The hash could then become further corrupted when the ST table required resizing as the falsely tombstoned entry would be skipped but it would be counted in num entries, leading to an uninitialized entry at index 15. In most cases this will be really rare, unless using a very poorly implemented custom hash function. This also adds two debug assertions, one that st_add_direct_with_hash does not receive the reserved hash value, and a second in rebuild_table_with, which ensures that after we rebuild/compact a table it contains the expected number of elements. Co-authored-by: Alan Wu <[email protected]> Notes: Merged: https://.com/ruby/ruby/pull/12852 |
| Notes: Merged: https://.com/ruby/ruby/pull/12742 |
| Suppress a false positive alert by CodeQL. |
| st_replace and st_init_existing_table_with_size are functions used internally in Ruby and should not be publicly visible. |
| * delete `ar_try_convert` but use `ar_force_convert_table` to make program simple. * `ar_force_convert_table` checks hash modification while calling `#hash` method with the following strategy: 1. copy keys (and vals) of ar_table 2. calc hashes from keys 3. check copied keys and hash's keys. if not matched, repeat from 1 fix [Bug #20050] |
| |
| |
| ignored [-Wattributes]` |
| According to the C99 specification section 7.20.3.2 paragraph 2: > If ptr is a null pointer, no action occurs. So we do not need to check that the pointer is a null pointer. Notes: Merged: https://.com/ruby/ruby/pull/8004 |
| st_copy allocates a st_table, which is not needed for hashes since it is allocated by VWA and embedded, so this causes a memory . The following script demonstrates the issue: ```ruby 20.times do 100_000.times do {a: 1, b: 2, c: 3, d: 4, e: 5, f: 6, g: 7, h: 8, i: 9} end puts `ps -o rss= -p #{$$}` end ``` Notes: Merged: https://.com/ruby/ruby/pull/8000 |
| Notes: Merged: https://.com/ruby/ruby/pull/7956 |
| Notes: Merged: https://.com/ruby/ruby/pull/7949 |
| Include the functions which are only used for `rb_hash_bulk_insert_into_st_table`. Notes: Merged: https://.com/ruby/ruby/pull/7949 |
| Notes: Merged: https://.com/ruby/ruby/pull/7742 |
| st tables will maintain insertion order so we can marshal dump / load objects with instance variables in the same order they were set on that particular instance [ruby-core:112926] [Bug #19535] Co-Authored-By: Jemma Issroff <[email protected]> Notes: Merged: https://.com/ruby/ruby/pull/7560 |
| Otherwise, a reader may wonder who `Peter B.' is and why a variable is named after them... |
| Notes: Merged-By: ioquatix <[email protected]> |
| When the generic_iv_tbl is resized up, rebuild_table performs allocations that can trigger GC. If autocompaction is enabled, then moved objects are removed from and inserted into the generic_iv_tbl. This may cause another call to rebuild_table to resize the generic_iv_tbl. When returning back to the original rebuild_table, some of the data may be stale, causing the generic_iv_tbl to be corrupted. This commit changes rebuild_table to only read data from the st_table after the allocations have completed. Co-Authored-By: Matt Valentine-House <[email protected]> Notes: Merged: https://.com/ruby/ruby/pull/6494 |
| [Misc #18891] Notes: Merged: https://.com/ruby/ruby/pull/6094 |
| |
| tab->entries_bound is used to check if the bins are full in rebuild_table_if_necessary. Hash#shift against an empty hash assigned 0 to tab->entries_bound, but didn't clear the bins. Thus, the table is not rebuilt even when the bins are full. Attempting to add a new element into full-bin hash gets stuck. This change stops clearing tab->entries_bound in Hash#shift. [Bug #18578] Notes: Merged: https://.com/ruby/ruby/pull/5539 |
| * --braces-after-func-def-line * --dont-cuddle-else * --procnames-start-lines * --space-after-for * --space-after-if * --space-after-while |
| Update the start entry skipping all already deleted entries. Fixes performance issue of `Hash#first` in a certain case. |
| 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: https://.com/ruby/ruby/pull/4035 |
| Clarified that the first and second arguments to the callback function are pointers to the KEY and the VALUE, but not those values themselves. |
| iv_index_tbl manages instance variable indexes (ID -> index). This data structure should be synchronized with other ractors so introduce some VM locks. This 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: https://.com/ruby/ruby/pull/3662 |
| * 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 <[email protected]> |
| `RESERVED_HASH_VAL` and `RESERVED_HASH_SUBSTITUTION_VAL` have not been used directly in hash.c since 72825c35b0d8. |
| |
| * Fix a typo * Fix typos in st.[ch] Notes: Merged-By: k0kubun <[email protected]> |
| to suppress a warning "variable 'check' set but not used" |
| 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: https://.com/ruby/ruby/pull/2926 |
| Function pointers are not void*. See also ce4ea956d24eab5089a143bba38126f2b11b55b6 8427fca49bd85205f5a8766292dd893f003c0e48 |
| 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: https://.com/ruby/ruby/pull/2711 |
| Fixed misspellings reported at [Bug #16437], only in ruby and rubyspec. |
| Notes: Merged: https://.com/ruby/ruby/pull/2304 |
| These are found by Coverity. Notes: Merged: https://.com/ruby/ruby/pull/2304 |
| 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 <[email protected]> |
| It was originally static inline, but seemed to be accidentally published at 8f675cdd00e2c5b5a0f143f5e508dbbafdb20ccd. |
| Merged: https://.com/ruby/ruby/pull/2292 |
| After 5e86b005c0f2ef30df2f9906c7e2f3abefe286a2, I now think ANYARGS is dangerous and should be extinct. This commit adds function s for struct st_hash_type. Honestly I don't understand why they were commented out at the first place. |
| 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. |
| 🙏 git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@67620 b2dd03c8-39d4-4d8f-98ff-823fe69b080e |
| For some reason symbols (or classes) are being overridden in trunk git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@67598 b2dd03c8-39d4-4d8f-98ff-823fe69b080e |
