summaryrefslogtreecommitdiffhomepage
path: root/test/t/hash.rb
AgeCommit message (Collapse)Author
2021-09-13parse.y: allow value omission in Hash literals introduced in Ruby3.1.Yukihiro "Matz" Matsumoto
`{x:, y:}` now is a syntax sugar of `{x: x, y: y}`. This fix also includes the update of #4815 fix.
2021-03-17hash.c: `Hash#shift` to return `nil` when a hash is empty.Yukihiro "Matz" Matsumoto
It used to be return the default value if available, but it should ignore the default value for behavior consistency. CRuby will adopt this behavior too in the future. [ruby-bugs:16908]
2021-02-10Fix heap-buffer-overflow for small `Hash` (HT) in `Hash#rehash`KOBAYASHI Shuji
### Example ##### example.rb ```ruby h = {} (1..17).each{h[_1] = _1} (1..16).each{h.delete(_1)} h.rehash ``` ##### ASAN report ```console $ bin/mruby example.rb ==52587==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000006998 at pc 0x55a29cddf96b bp 0x7fff7b1b1720 sp 0x7fff7b1b1710 READ of size 4 at 0x602000006998 thread T0 #0 0x55a29cddf96a in ib_it_next /mruby/src/hash.c:639 #1 0x55a29cde2ca2 in ht_rehash /mruby/src/hash.c:900 #2 0x55a29cde379f in h_rehash /mruby/src/hash.c:996 #3 0x55a29cde7f3d in mrb_hash_rehash /mruby/src/hash.c:1735 #4 0x55a29ce77b62 in mrb_vm_exec /mruby/src/vm.c:1451 #5 0x55a29ce5fa88 in mrb_vm_run /mruby/src/vm.c:981 #6 0x55a29ceb87e1 in mrb_top_run /mruby/src/vm.c:2874 #7 0x55a29cf36bdf in mrb_load_exec mrbgems/mruby-compiler/core/parse.y:6805 #8 0x55a29cf36f25 in mrb_load_detect_file_cxt mrbgems/mruby-compiler/core/parse.y:6848 #9 0x55a29cdba0a2 in main /mruby/mrbgems/mruby-bin-mruby/tools/mruby/mruby.c:347 #10 0x7f24ef43b0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #11 0x55a29cdb4a6d in _start (/mruby/bin/mruby+0x2a3a6d) 0x602000006998 is located 0 bytes to the right of 8-byte region [0x602000006990,0x602000006998) allocated by thread T0 here: #0 0x7f24f01cfffe in __interceptor_realloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dffe) #1 0x55a29ceb9440 in mrb_default_allocf /mruby/src/state.c:68 #2 0x55a29cdba747 in mrb_realloc_simple /mruby/src/gc.c:228 #3 0x55a29cdba928 in mrb_realloc /mruby/src/gc.c:242 #4 0x55a29cde12e5 in ht_init /mruby/src/hash.c:749 #5 0x55a29cde2b8e in ht_rehash /mruby/src/hash.c:897 #6 0x55a29cde379f in h_rehash /mruby/src/hash.c:996 #7 0x55a29cde7f3d in mrb_hash_rehash /mruby/src/hash.c:1735 #8 0x55a29ce77b62 in mrb_vm_exec /mruby/src/vm.c:1451 #9 0x55a29ce5fa88 in mrb_vm_run /mruby/src/vm.c:981 #10 0x55a29ceb87e1 in mrb_top_run /mruby/src/vm.c:2874 #11 0x55a29cf36bdf in mrb_load_exec mrbgems/mruby-compiler/core/parse.y:6805 #12 0x55a29cf36f25 in mrb_load_detect_file_cxt mrbgems/mruby-compiler/core/parse.y:6848 #13 0x55a29cdba0a2 in main /mruby/mrbgems/mruby-bin-mruby/tools/mruby/mruby.c:347 #14 0x7f24ef43b0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) ```
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)
2019-07-17Merge branch 'master' into i110/inspect-recursionYukihiro "Matz" Matsumoto
2019-03-19Use `FrozenError` instead of `RuntimeError` in frozen object modification testKOBAYASHI Shuji
2019-01-03Remove `Kernel#class_defined?` which is not available in CRuby; #3829Yukihiro "Matz" Matsumoto
2018-10-12`Hash#delete` should return the deleted value; fix #4133Yukihiro "Matz" Matsumoto
2018-06-04Let inspect recursion do the right thingIchito Nagata
2017-10-11Test for MRB_WITHOUT_FLOATYAMAMOTO Masaya
2016-12-11Implement Object#freezeTakashi Kokubun
2016-12-07Copy default_proc by Hash#dup.Shugo Maeda
2016-12-01Add test for recently fixed bugsYutaka HARA
2016-01-27protect NoMethodError from calling to_hash in replaceSayed Abdelhaleem
2015-09-10add Hash#rehash to handle key modification; ref #2945Yukihiro "Matz" Matsumoto
2014-06-15Move direct superclass checking to `test/t/superclass.rb`.take_cheeze
2014-05-12Fix Hash testJun Hiroe
2014-05-10Change to raise TypeError (Hash#merge, #merge!)yui-knk
2014-04-30remove trailing spacesNobuyoshi Nakada
2014-04-04Hash#replace should copy default as well; close #2004Yukihiro "Matz" Matsumoto
2014-04-04merge test code from #2003Yukihiro "Matz" Matsumoto
2014-03-15Hash#shift may return any entriesYukihiro "Matz" Matsumoto
2014-03-08fix #1823ksss
2014-03-07Fix behavior Hash#eql?ksss
2014-02-14add test for Hash#dupLi Yazhou
2013-08-02I fix order of actual and expect test value in hash.rb.Jun Hiroe
2013-06-15Improve Hash TestsDaniel Bovensiepen
2013-05-08Add more test cases for test coverage.Masaki Muranaka
2013-04-02Add test cases.Masaki Muranaka
2012-06-03Add more superclass testsDaniel Bovensiepen
2012-06-02Add test cases for HashDaniel Bovensiepen
2012-05-30remove debug printYukihiro Matsumoto
2012-05-30specify allocating array size for Hash#valuesYukihiro Matsumoto
2012-05-29Add Test cases for Literals, Enumeration, Exceptions and clean line endingsDaniel Bovensiepen
2012-05-23test t/*.rb spacing fixYukihiro Matsumoto
2012-05-20Fix Hash#shift return value from Hash to ArrayDaniel Bovensiepen
2012-05-19Complete ISO test cases for Hash, Range, String and SymbolDaniel Bovensiepen
generated by cgit v1.2.3 (git 2.39.1) at 2026-04-15 11:52:29 +0000