admin/mruby-mruby
1
0
Fork 0
mirror of https://github.com/mruby/mruby synced 2026-06-08 16:11:16 +00:00
Code Issues Packages Projects Releases Wiki Activity
12,451 Commits 6 Branches 38 Tags
3.0.0
Commit Graph

49 Commits

Author SHA1 Message Date
KOBAYASHI Shuji f2d8db39be Reduce memory usage of Hash object 
## 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-11-10 15:21:49 +09:00
KOBAYASHI Shuji 181f7b97d6 Fix some Hash methods are inconsistent with values 
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}
  ```
 2020-05-09 15:27:42 +09:00
Yukihiro "Matz" Matsumoto d5939879cc Fixed a bug in #4034 2019-07-17 10:39:17 +09:00
Yukihiro "Matz" Matsumoto d605b72c1d Merge branch 'master' into i110/inspect-recursion 2019-07-17 10:35:41 +09:00
Yukihiro "Matz" Matsumoto 610bcc88c2 Removed to_hash conversion method. 2018-11-19 12:08:28 +09:00
Yukihiro "Matz" Matsumoto 34872e90d4 Re-implement Array#_inspect and Hash#_inspect without blocks. 
To reduce the env object allocation; ref #4143
 2018-10-29 11:55:49 +09:00
Yukihiro "Matz" Matsumoto 54ec08c7f1 Implement Hash#rehash in C using sg_compact(). 2018-09-26 23:09:48 +09:00
Yukihiro "Matz" Matsumoto d78acc7afe Add index to larger segment lists for performance 2018-09-26 23:09:48 +09:00
Yukihiro "Matz" Matsumoto 8ffd4e47fb Use mrb_undef_value for delete mark instead of shifting Hash entry table. 
That means entry table should be compacted periodically by `sg_compact()`.
 2018-09-26 23:09:48 +09:00
Yukihiro "Matz" Matsumoto a3fb80904d Remove unused Hash#__update method. 2018-08-25 09:41:21 +09:00
Ichito Nagata 2af92d0ebc Let inspect recursion do the right thing 2018-06-04 11:25:10 +09:00
Ichito Nagata 4a2b055cdd let Hash#merge keep ifnone value 2018-06-01 12:48:17 +09:00
Christopher Aue 3359b86ec7 Improved speed of enumeration methods 2017-07-30 13:19:31 +02:00
Nobuyoshi Nakada 6511bfd79a Removed trailing spaces 2016-09-28 12:29:41 +09:00
Sayed Abdelhaleem f5f48d9400 protect NoMethodError from calling to_hash in replace 2016-01-27 21:17:33 +02:00
Seba Gamboa 13b552538a Remove obvious warnings from docs 2015-10-20 12:48:31 -03:00
Yukihiro "Matz" Matsumoto 698b3c925d add Hash#rehash to handle key modification; ref #2945 2015-09-10 23:03:53 +09:00
Yukihiro "Matz" Matsumoto b05d736b49 update mrblib/*.rb files to conform (some of) Rubocop checks 2015-05-29 17:01:52 +09:00
Yukihiro "Matz" Matsumoto 79fb18445d rescue SystemStackError that comes from inspecting self-referencing Hashes and Arrays; fix #2461 2014-07-12 23:22:20 +09:00
Jun Hiroe 012c32ad0a Add comments to Hash methods 2014-05-10 18:11:07 +09:00
yui-knk 658a00ba49 Change to raise TypeError (Hash#merge, #merge!) 2014-05-10 10:18:15 +09:00
Nobuyoshi Nakada ab67c57f65 remove trailing spaces 2014-04-30 09:50:14 +09:00
Yukihiro "Matz" Matsumoto 3308177c4d retrieve values in Hash#each to handle modified keys 2014-04-12 10:42:02 +09:00
Yukihiro "Matz" Matsumoto 4e2ae3e376 Hash#replace should copy default from original even when the default value of the original is not set 2014-04-07 02:02:53 +09:00
Yukihiro "Matz" Matsumoto 59cd24d41f Hash#replace should copy default as well; close #2004 2014-04-04 12:14:23 +09:00
Yukihiro "Matz" Matsumoto b9a4d64064 implement Hash#initialize in C 2014-04-04 11:03:26 +09:00
Yukihiro "Matz" Matsumoto 786ed10d59 call to_hash before replacing hash 2014-04-04 10:55:48 +09:00
Yukihiro "Matz" Matsumoto b8ab6af39d protect NoMethodError from calling to_hash in ==/eql?; close #2002 2014-04-04 10:54:46 +09:00
Yukihiro "Matz" Matsumoto 28ab106292 Hash#replace to preserve order; close #2001 2014-04-04 10:50:42 +09:00
Yukihiro "Matz" Matsumoto 1690fc4c99 implement Hash#== and eql? in Ruby 2014-04-01 14:56:23 +09:00
Yukihiro "Matz" Matsumoto d9feed6703 move Array#inspect implementation to mrblib/array.rb 2014-04-01 14:31:39 +09:00
Yukihiro "Matz" Matsumoto cf58d0d3e9 move Hash#inspect implementation to mrblib/hash.rb 2014-04-01 14:21:40 +09:00
ksss 2981b4e3d9 Hash#__update fix typo 
It's called by create Hash of over 126 keys
 2014-03-24 08:43:44 +09:00
ksss d9068f0583 Hash#{reject,reject!} fix yield value 2014-03-23 20:13:49 +09:00
ksss d8fc05fcb9 Hash#{reject,reject!} support return Enumerator 2014-03-23 20:11:20 +09:00
ksss d09e4475bf Hash#{select,select!} fix yield value 2014-03-23 13:31:26 +09:00
ksss 5e4626c9ba Hash#{select,select!} support return Enumerator 
if non block given
 2014-03-23 13:31:26 +09:00
ksss 5386cd9b9b Hash#each_{key,value} support return Enumerator 
if non block given
 2014-03-23 00:22:22 +09:00
Yukihiro "Matz" Matsumoto 041b5a9f67 reduce object allocation in __update 2014-03-21 21:53:50 +09:00
Yukihiro "Matz" Matsumoto 2c44f96e78 reduce hash creation by using update method 2014-03-21 09:31:44 +09:00
Yukihiro "Matz" Matsumoto 113ab60784 mruby-enumerator: move definitions in core_mod.rb to mrblib core 2014-03-14 02:41:22 +09:00
Yukihiro "Matz" Matsumoto 4a2c37df93 made mrb_define_class to return existing class, with heavy refactoring 2014-02-08 13:44:31 +09:00
Masaki Muranaka 82c891acee Move comments from hash.c to hash.rb. 2013-05-08 13:22:35 +09:00
Masaki Muranaka 6cd7017ec1 Remove trailing whitespaces. This is just a cosmetic change. 2013-03-03 10:54:00 +09:00
Yukihiro Matsumoto 15b9d74fc7 stupid naming error 2012-06-03 02:14:30 +09:00
Yukihiro Matsumoto d060c8a713 add Hash#{select/reject} to return Hash as 1.9 2012-06-02 23:21:12 +09:00
Daniel Bovensiepen 580b0267a8 Some fixes for the Documentation of Hash and Kernel 2012-05-06 18:24:39 +08:00
Daniel Bovensiepen 8f4c1af9e4 Add documentation to Hash 2012-05-06 18:15:23 +08:00
mimaki e0d6430f63 add mruby sources 2012-04-20 09:39:03 +09:00