summaryrefslogtreecommitdiffhomepage
path: root/mrblib/hash.rb
AgeCommit message (Collapse)Author
2021-05-13Simplify module inclusion for `Array`, `Hash` and `Range`.Yukihiro "Matz" Matsumoto
2021-04-16feat(CI): add the GitHub Super LinterJohn Bampton
The GitHub Super Linter is a more robust and better supported tool than the current GitHub Actions we are using. Running these checks: ERROR_ON_MISSING_EXEC_BIT: true VALIDATE_BASH: true VALIDATE_BASH_EXEC: true VALIDATE_EDITORCONFIG: true VALIDATE_MARKDOWN: true VALIDATE_SHELL_SHFMT: true VALIDATE_YAML: true https://github.com/marketplace/actions/super-linter https://github.com/github/super-linter Added the GitHub Super Linter badge to the README. Also updated the pre-commit framework and added more documentation on pre-commit. Added one more pre-commit check: check-executables-have-shebangs Added one extra check for merge conflicts to our GitHub Actions. EditorConfig and Markdown linting. Minor grammar and spelling fixes. Update linter.yml
2020-11-10Reduce memory usage of Hash objectKOBAYASHI Shuji
## Implementation Summary * Change entry list from segmented list to flat array. * Change value of hash bucket from pointer to entry to index of entry list, and represent it by variable length bits according to capacity of hash buckets. * Store management information about entry list and hash table to `struct RHash` as much as possible. ## Benchmark Summary Only the results of typical situations on 64-bit Word-boxing are present here. For more detailed information, including consideration, see below (although most of the body is written in Japanese). * https://shuujii.github.io/mruby-hash-benchmark ### Memory Usage Lower value is better. | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 344B | 256B | 0.74419x | | 40 | 1,464B | 840B | 0.57377x | | 200 | 8,056B | 3,784B | 0.46971x | | 500 | 17,169B | 9,944B | 0.57949x | ### Performance Higher value is better. #### `mrb_hash_set` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 1.41847M i/s | 1.36004M i/s | 0.95881x | | 40 | 0.39224M i/s | 0.31888M i/s | 0.81296x | | 200 | 0.03780M i/s | 0.04290M i/s | 1.13494x | | 500 | 0.01225M i/s | 0.01314M i/s | 1.07275x | #### `mrb_hash_get` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 26.05920M i/s | 30.19543M i/s | 1.15872x | | 40 | 44.26420M i/s | 32.75781M i/s | 0.74005x | | 200 | 44.55171M i/s | 31.56926M i/s | 0.70860x | | 500 | 39.19250M i/s | 29.73806M i/s | 0.75877x | #### `mrb_hash_each` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 25.11964M i/s | 30.34167M i/s | 1.20789x | | 40 | 11.74253M i/s | 13.25539M i/s | 1.12884x | | 200 | 2.01133M i/s | 2.97214M i/s | 1.47770x | | 500 | 0.87411M i/s | 1.21178M i/s | 1.38631x | #### `Hash#[]=` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.50095M i/s | 0.56490M i/s | 1.12764x | | 40 | 0.19132M i/s | 0.18392M i/s | 0.96129x | | 200 | 0.03624M i/s | 0.03256M i/s | 0.89860x | | 500 | 0.01527M i/s | 0.01236M i/s | 0.80935x | #### `Hash#[]` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 11.53211M i/s | 12.78806M i/s | 1.10891x | | 40 | 15.26920M i/s | 13.37529M i/s | 0.87596x | | 200 | 15.28550M i/s | 13.36410M i/s | 0.87430x | | 500 | 14.57695M i/s | 12.75388M i/s | 0.87494x | #### `Hash#each` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.30462M i/s | 0.27080M i/s | 0.88898x | | 40 | 0.12912M i/s | 0.11704M i/s | 0.90642x | | 200 | 0.02638M i/s | 0.02402M i/s | 0.91071x | | 500 | 0.01066M i/s | 0.00959M i/s | 0.89953x | #### `Hash#delete` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 7.84167M i/s | 6.96419M i/s | 0.88810x | | 40 | 6.91292M i/s | 7.41427M i/s | 1.07252x | | 200 | 3.75952M i/s | 7.32080M i/s | 1.94727x | | 500 | 2.10754M i/s | 7.05963M i/s | 3.34970x | #### `Hash#shift` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 14.66444M i/s | 13.18876M i/s | 0.89937x | | 40 | 11.95124M i/s | 11.10420M i/s | 0.92913x | | 200 | 5.53681M i/s | 7.88155M i/s | 1.42348x | | 500 | 2.96728M i/s | 5.40405M i/s | 1.82121x | #### `Hash#dup` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.15063M i/s | 5.37889M i/s | 35.71024x | | 40 | 0.06515M i/s | 3.38196M i/s | 51.91279x | | 200 | 0.01359M i/s | 1.46538M i/s | 107.84056x | | 500 | 0.00559M i/s | 0.75411M i/s | 134.88057x | ### Binary Size Lower value is better. | File | Baseline | New | Factor | |:-----------|--------------:|--------------:|----------:| | mruby | 730,408B | 734,176B | 1.00519x | | libmruby.a | 1,068,134B | 1,072,846B | 1.00441x | ## Other Fixes The following issues have also been fixed in the parts where there was some change this time. * [Heap use-after-free in `Hash#value?`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-hash-value-md) * [Heap use-after-free in `ht_hash_equal`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_equal-md) * [Heap use-after-free in `ht_hash_func`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_func-md) * [Heap use-after-free in `mrb_hash_merge`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-mrb_hash_merge-md) * [Self-replacement does not work for `Hash#replace`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-self-replacement-does-not-work-for-hash-replace-md) * [Repeated deletes and inserts increase memory usage of `Hash`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-repeated-deletes-and-inserts-increase-memory-usage-of-hash-md) * [`Hash#rehash` does not reindex completely](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-hash-rehash-does-not-reindex-completely-md) * `mrb_hash_delete_key` does not cause an error for frozen object * `mrb_hash_new_capa` does not allocate required space first * [`mrb_os_memsize_of_hash_table` result is incorrect](https://github.com/mruby/mruby/pull/5032#discussion_r457994075)
2020-05-09Fix some `Hash` methods are inconsistent with `values`KOBAYASHI Shuji
Inconsistent when hash has duplicate key. ### Example ```ruby # example.rb keys = (1..3).map{[_1]} h = keys.to_h{[_1, _1[0]]} keys[0][0] = 2 p h.values p h.each_value.to_a p h ``` #### Before this patch: ```console $ bin/mruby example.rb [1, 2, 3] [1, 1, 3] {[2]=>1, [2]=>1, [3]=>3} ``` #### After this patch (same as Ruby) ```console $ bin/mruby example.rb [1, 2, 3] [1, 2, 3] {[2]=>1, [2]=>2, [3]=>3} ```
2019-07-17Fixed a bug in #4034Yukihiro "Matz" Matsumoto
2019-07-17Merge branch 'master' into i110/inspect-recursionYukihiro "Matz" Matsumoto
2018-11-19Removed `to_hash` conversion method.Yukihiro "Matz" Matsumoto
2018-10-29Re-implement `Array#_inspect` and `Hash#_inspect` without blocks.Yukihiro "Matz" Matsumoto
To reduce the env object allocation; ref #4143
2018-09-26Implement `Hash#rehash` in C using `sg_compact()`.Yukihiro "Matz" Matsumoto
2018-09-26Add index to larger segment lists for performanceYukihiro "Matz" Matsumoto
2018-09-26Use `mrb_undef_value` for delete mark instead of shifting Hash entry table.Yukihiro "Matz" Matsumoto
That means entry table should be compacted periodically by `sg_compact()`.
2018-08-25Remove unused `Hash#__update` method.Yukihiro "Matz" Matsumoto
2018-06-04Let inspect recursion do the right thingIchito Nagata
2018-06-01let Hash#merge keep ifnone valueIchito Nagata
2017-07-30Improved speed of enumeration methodsChristopher Aue
2016-09-28Removed trailing spacesNobuyoshi Nakada
2016-01-27protect NoMethodError from calling to_hash in replaceSayed Abdelhaleem
2015-10-20Remove obvious warnings from docsSeba Gamboa
2015-09-10add Hash#rehash to handle key modification; ref #2945Yukihiro "Matz" Matsumoto
2015-05-29update mrblib/*.rb files to conform (some of) Rubocop checksYukihiro "Matz" Matsumoto
2014-07-12rescue SystemStackError that comes from inspecting self-referencing Hashes ↵Yukihiro "Matz" Matsumoto
and Arrays; fix #2461
2014-05-10Add comments to Hash methodsJun Hiroe
2014-05-10Change to raise TypeError (Hash#merge, #merge!)yui-knk
2014-04-30remove trailing spacesNobuyoshi Nakada
2014-04-12retrieve values in Hash#each to handle modified keysYukihiro "Matz" Matsumoto
2014-04-07Hash#replace should copy default from original even when the default value ↵Yukihiro "Matz" Matsumoto
of the original is not set
2014-04-04Hash#replace should copy default as well; close #2004Yukihiro "Matz" Matsumoto
2014-04-04implement Hash#initialize in CYukihiro "Matz" Matsumoto
2014-04-04call to_hash before replacing hashYukihiro "Matz" Matsumoto
2014-04-04protect NoMethodError from calling to_hash in ==/eql?; close #2002Yukihiro "Matz" Matsumoto
2014-04-04Hash#replace to preserve order; close #2001Yukihiro "Matz" Matsumoto
2014-04-01implement Hash#== and eql? in RubyYukihiro "Matz" Matsumoto
2014-04-01move Array#inspect implementation to mrblib/array.rbYukihiro "Matz" Matsumoto
2014-04-01move Hash#inspect implementation to mrblib/hash.rbYukihiro "Matz" Matsumoto
2014-03-24Hash#__update fix typoksss
It's called by create Hash of over 126 keys
2014-03-23Hash#{reject,reject!} fix yield valueksss
2014-03-23Hash#{reject,reject!} support return Enumeratorksss
2014-03-23Hash#{select,select!} fix yield valueksss
2014-03-23Hash#{select,select!} support return Enumeratorksss
if non block given
2014-03-23Hash#each_{key,value} support return Enumeratorksss
if non block given
2014-03-21reduce object allocation in __updateYukihiro "Matz" Matsumoto
2014-03-21reduce hash creation by using update methodYukihiro "Matz" Matsumoto
2014-03-14mruby-enumerator: move definitions in core_mod.rb to mrblib coreYukihiro "Matz" Matsumoto
2014-02-08made mrb_define_class to return existing class, with heavy refactoringYukihiro "Matz" Matsumoto
2013-05-08Move comments from hash.c to hash.rb.Masaki Muranaka
2013-03-03Remove trailing whitespaces. This is just a cosmetic change.Masaki Muranaka
2012-06-03stupid naming errorYukihiro Matsumoto
2012-06-02add Hash#{select/reject} to return Hash as 1.9Yukihiro Matsumoto
2012-05-06Some fixes for the Documentation of Hash and KernelDaniel Bovensiepen
2012-05-06Add documentation to HashDaniel Bovensiepen
generated by cgit v1.2.3 (git 2.39.1) at 2026-04-15 05:47:17 +0000